Ускорить работу программы

[akademochka]

#include <cstdlib>
#include <iostream>

double p(int s, int r)
{ if(s%2!=0) return 0;
if(r==0) return 0;
if(s==0) return 1;
if((p==0)&&(s==0)) return 0;
else return ((2*s*r*p(s,r-1)) + (s*(s-1)*p(s-2,r)))/ (((s+r)*(s+r-1))-(r*(r-1)));     }
using namespace std;

int main(int argc, char *argv[])
{int s,r;
    scanf("%d%d",&s,&r);
    printf("%.11lf\n",p(s,r));
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Помогите, пожалуйста.

[Rififi]

akademochka

Ускорить работу программы

это тебе поможет

[PathTheir]

#include <cstdlib>
#include <iostream>

double p(int s, int r)
{ 
if ((s%2!=0) || (r == 0) || (p==0) && (s==0)) return 0;
if(s==0) return 1;
else {
  double l = p(s-2, r);
  return ((2*r*p(s,r-1) + s*l - l)/(2*r + s - 1));  
}   
}
using namespace std;

int main(int argc, char *argv[])
{int s,r;
    scanf("%d%d",&s,&r);
    printf("%.11lf\n",p(s,r));
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

Так должно быть чуть побыстрее. (Самую малость)

[akademochka]

Спасибо большое! своим остроумием вы мне очень помогли

[Abstraction]

Было бы здорово, если бы Вы предоставили алгебраическое описание функции p.

if((p==0)&&(s==0)) return 0;

p==0 ???

Rififi, добрый Вы. Хотя функция неприятная, факт.
Если я не напутал в расчётах, то для чётного s она равна... TeX-разметки нет, поэтому вот так:
(C(s/2,0)*П1 <= k <= r(2k-1) + C(s/2 + 1, 1) * 2r * П1 <= k <= r-1(2k-1) + ... + C(s/2 + r-1, r-1) * 2r*(2r-2)*(2r-4)*...*4) / Пs/2 < k <= r + s/2(2k-1)
(C(n,k) - биноминальный коэффициент) Растёт быстро, считается фигово.

[akademochka]

Спасибо, конечно, но этого не достаточно : Максимальное время выполнения: 1.014 секунды из 1 секунда

[Abstraction]

Нужна мемоизация. Обратите внимание, что при вызове p(5,4) значение p(2,1) сейчас будет независимо считаться 20 раз. Если вместо этого завести динамический массив, изначально заполненный, скажем, -1 и сначала пытаться искать значение в нём, всё станет чуть менее мрачно.

[akademochka]

Что-то типа этого? Только я понимаю, что написала бред(не работает), но все же....помогите исправить

#include <cstdlib>
#include <iostream>

using namespace std;
int A[2010][2010];

double p(int s, int r) {
       if(s%2!=0) return 0;
if(r==0) return 0;
if(s==0) return 1;
if((p==0)&&(s==0)) return 0;
 
    if (A[s][r] == -1) {
       

        for (int i = 1; i <= s ; i++) {
        for(int j=1 ;j<=r;j++) {
           A[s][r] =((2*s*r*A[s][r-1]) + (s*(s-1)*A[s-2][r]))/ (((s+r)*(s+r-1))-(r*(r-1)));}}
        
    return A[s][r];
}}

int main() {
  int s,r;
    scanf("%d%d",&s,&r);
    memset(A, -1, sizeof A);
    A[1][1]=1;
printf("%.11lf\n",p(s,r));
    system("PAUSE");
    return EXIT_SUCCESS;
}

[Abstraction]

Прочитайте описание функции memset(). Нужен массив double (причём вариант с фиксированным размером не вполне удачен), и инициализировать его проще в цикле (заодно загнав туда условия выхода из рекурсии):

for(int i=1; i<=MAX_S; ++i){
  for(int j=1; j<=MAX_R; ++j){
    if(i%2 != 0) A[i][j] = 0; //if-else конструкцию можно заменить на A[i][j] = i%2 - 1;
    else A[i][j] = -1;  //Но не факт, что это будет быстрее
  }
}

for(int i=0; i<=MAX_S; ++i) A[i][0] = 0;
for(int j=0; j<=MAX_R; ++j) A[0][j] = 1;

Условие с p==0 бессмысленно. Если Вы этого не понимаете - поймите (разберите, что такое идентификатор p и чему может быть равно его численное значение).

Соответственно:

double p(int s, int r){
  if(A[s][r] >= 0) return A[s][r];

  A[s][r] = (2*r*p(s,r-1) + (s-1)*p(s-2,r)) / (s + 2*r - 1); //Выражение упрощено
  return A[s][r];
}

[_Bers]

а при каких значениях вы замеряете время исполнения?
У меня показатель: 0.001354 секунды на таком коде:

double p(int s, int r)
{ 
    if ((s%2!=0) || (r == 0) || (p==0) && (s==0)) return 0;
    if(s==0) return 1;
    else
    {
        double l = p(s-2, r);
        return ((2*r*p(s,r-1) + s*l - l)/(2*r + s - 1));  
    }   
}
int main()
{
    Timer timer;  timer.Quant();
    cout<<"result = "<<p(5,4)<<endl;
    cout<<"elapsed = "<<timer.Quant()<<endl;
}