Рекурсии

@skifcha · Регистрация: 09.12.2015

Author24 — интернет-сервис помощи студентам

Ребят,программа по задаче 22 из ЕГЭ.
При вводе программа зависает.

C++

#include <stdio.h>
 
int f(int n,int c)
{
    if(n<1)
        return 0;
    else 
        return f((n+3)*2,c)+f((n-2)/3,c);
 
}
 
int main()
{
    int a,b;
    scanf("%d%d",&a ,&b);
    printf("%d",f(a,b));
}

@deepz · 12.12.2016, 01:48

дело в том, что в функции f, переменная n постоянно растет, а критерий остановки рекурсии, n < 1; поэтому программа зависает
return f((n + 3) * 2, c) + f((n - 2) / 3, c);

@Catstail · 12.12.2016, 15:16

Приведи условие задачи

@skifcha · 12.12.2016, 17:27 **[ТС]**

Сообщение от Catstail

Приведи условие задачи

1) Исполнителю присвоены команды:

Увеличить на 3,затем умножить на 2;
Вычесть 2,затем поделить на 3;
Сколько всего существует программ,преобразующих число 3 в число 65?

@Catstail · 12.12.2016, 18:23

Ты уверен, что 65? Что-то не получается ни разу...

@skifcha · 12.12.2016, 18:28 **[ТС]**

Сообщение от Catstail

Ты уверен, что 65? Что-то не получается ни разу...

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

@Catstail · 12.12.2016, 18:34

Как вариант:

C

#include <stdio.h>
#include <stdlib.h>
 
int c;
int F[66];
 
void Next(int n)
{
    int k; 
    if (n==66)  {c++; return;}
    if ((n > 66) || (n < 0)) return;
    k=(n+3)*2;
    if (F[k]==0) {F[k]=1; Next(k);}
    k=(n-2)/3;
    if (F[k]==0) {F[k]=1; Next(k);}
}
 
int main(int argc, char *argv[])
{
 
  int i;
  c=0;
  for (i=1; i<66; i++) F[i]=0;
  
  Next(3);
 
  printf("c=%d\n",c); 
  system("PAUSE");  
  return 0;
}

@deepz 62 / 62 / 53 Регистрация: 04.10.2013 Сообщений: 264
	12.12.2016, 01:48	2
	дело в том, что в функции f, переменная n постоянно растет, а критерий остановки рекурсии, n < 1; поэтому программа зависает return f((n + 3) * 2, c) + f((n - 2) / 3, c); 0

@Catstail Модератор 37352 / 20782 / 4277 Регистрация: 12.02.2012 Сообщений: 34,192 Записей в блоге: 14
	12.12.2016, 15:16	3
	Приведи условие задачи 0

@skifcha 0 / 0 / 0 Регистрация: 09.12.2015 Сообщений: 24
	12.12.2016, 17:27 [ТС]	4
	Сообщение от Catstail Приведи условие задачи 1) Исполнителю присвоены команды: Увеличить на 3,затем умножить на 2; Вычесть 2,затем поделить на 3; Сколько всего существует программ,преобразующих число 3 в число 65? 0

@Catstail Модератор 37352 / 20782 / 4277 Регистрация: 12.02.2012 Сообщений: 34,192 Записей в блоге: 14
	12.12.2016, 18:23	5
	Ты уверен, что 65? Что-то не получается ни разу... 0

@skifcha 0 / 0 / 0 Регистрация: 09.12.2015 Сообщений: 24
	12.12.2016, 18:28 [ТС]	6
	Сообщение от Catstail Ты уверен, что 65? Что-то не получается ни разу... Мне главное,чтобы просто составить шаблон на Си,чтобы работал,и чтобы самому задавать начальное и конечное значения. 0

	12.12.2016, 18:34