Отправлено: 20.05.21 06:06. Заголовок: задание 3696

Делаю такие задания, где надо найти определено значение или нет, через try и except, и получаю даже правильный ответ, но считаю это решение плохим . Как теоретически можно понять, определено ли значение или нет?

 Отправлено: 20.05.21 06:54. Заголовок: Теоретический анализ..

Теоретический анализ индивидуален для каждой задачи. В этой можно сразу понять, что бесконечная рекурсия происходит для 6 и 7, а также для всех остальных чисел, больших 5, для которых рекурсия в конце концов приводит к 6 и 7. Это числа вида 6k и 6k+1 (12, 13, 18, 19, ...).

 Отправлено: 20.05.21 10:32. Заголовок: Спасибо большое за р..

Спасибо большое за разъяснение.

 Отправлено: 03.11.21 17:21. Заголовок: Паскаль

Здравствуйте. А если знаком только с паскалем. Как исправить ошибку выхода

var n, min: integer; 
 function F(n :integer): integer;                    
 begin 
      if (n <=5) then Result := 1; 
      if n>5 then  
      if (n mod 5 = 0)  then Result := F((n div 5)+1) +n 
      Else 
           if (n mod 5 <> 0) and (n >5) then Result := F(n +6) + n; 
 end; 
    begin 
      min:=10000; 
      for n := 1  to 10000 do  
     begin 
       F(n);  
       if (F(n)=1000) and (n<min)  then  
         min:=n;  
   end; 
   writeln(min); 
 end.

 Отправлено: 03.11.21 17:30. Заголовок: Татьяна733 пишет: Ка..

Татьяна733 пишет:

цитата:

Как исправить ошибку выхода

Посмотрите обсуждение здесь. Или ставить счётчик вложенных вызовов, или ловить исключение по переполнению стека.

 Отправлено: 21.12.21 17:54. Заголовок: возможно ли другое решение и ответ задачи №3696?

Мне кажется, что условие этой задачи №3696 допускает и такое решение (без рекурсии, простой итерацией).
Сначала заполняем в массиве все номера, которые делятся на 5.
Затем те номера, которые не делятся на 5 и которые могут быть получены с номеров на 6 больших.
Ответ в таком случае будет 464 (на этом номере появляется число 1054).
По-моему такое решение не противоречит условию.

 
 #include <iostream> 
  
 using namespace std; 
  
 int main() { 
 	int n=10000; 
 	int a[n],i,num; 
 	for (i=0;i<n;i++) 
 		a[i]=-1; 
 	for (i=0;i<=5;i++) 
 		a[i]=i; 
 	for (i=10;i<n;i=i+5){ 
 		num=i/5+1; 
 		if (a[num]!=-1) 
 			a[i]=a[num]+i; 
 	} 
 	for (i=6;i<n-6;i++){ 
 		if (a[i+6]!=-1 && i%5!=0) 
 			a[i]=a[i+6]+i; 
 	} 
 	i=1; 
 	while (a[i]<1000 && i<n){ 
 		i++; 
 	} 
 	cout<<i; 
  
 } 
  
 

 Отправлено: 21.12.21 20:15. Заголовок: Serov Sergej пишет: ..

Serov Sergej пишет:

цитата:

Затем те номера, которые не делятся на 5 и которые могут быть получены с номеров на 6 больших.

А там еще неправильные значения...

 Отправлено: 22.12.21 10:59. Заголовок: Хотя если номера, ко..

Хотя если номера, которые не делятся на 5, заполнять начиная от больших номеров ("обратным ходом"), то ответ будет 196.

 
 #include <iostream> 
  
 using namespace std; 
  
 int main() { 
 	int n=10000; 
 	int a[n],i,num; 
 	for (i=0;i<n;i++) 
 		a[i]=-1; 
 	for (i=0;i<=5;i++) 
 		a[i]=i; 
 	for (i=10;i<n;i=i+5){ 
 		num=i/5+1; 
 		if (a[num]!=-1) 
 			a[i]=a[num]+i; 
 	} 
 	for (i=n-7;i>=6;i--){ 
 		if (a[i+6]!=-1 && i%5!=0) 
 			a[i]=a[i+6]+i; 
 	} 
 	i=1; 
 	while (a[i]<1000 && i<n){ 
 		i++; 
 	} 
 	cout<<i; 
 } 
  
  
  
  
 

 Отправлено: 22.12.21 11:09. Заголовок: Serov Sergej пишет: ..

Serov Sergej пишет:

цитата:

Хотя если номера, которые не делятся на 5, заполнять начиная от больших номеров ("обратным ходом"), то ответ будет 196.

А если вы возьмете другое n, то получите другой результат.

 Отправлено: 02.02.22 20:06. Заголовок: До меня никак не дох..

До меня никак не доходит. Почему при n=6k, 6k+1. Как Вы догадались? И как обработали это исключение?
Как можно решить на С++, используя именно рекурсию? Подскажите, плиз.

 Отправлено: 02.02.22 21:13. Заголовок: Qwerty пишет: До мен..

Qwerty пишет:

цитата:

До меня никак не доходит. Почему при n=6k, 6k+1. Как Вы догадались?

При 6 и 7 можно проверить вручную. Предположим, что работет только последняя ветвь рекурсии. Начнем с n = 6. Тогда вызовы происходят при n = 12, 18, ..., это все семейство, которое описывается формулой 6k. Если начать с 7, то получаем семейство с формулой 6k+1 (также увеличение на 6). Интереснее другой момент: в какой-то момент 6k разделится на 5 и сработает другая ветка рекурсии, пройдет вызов при 6k/5 + 1 => 6m + 1 для некоторого m (переход на вторую "бесконечную" цепочку). Несложно показать, что если 6k+1 разделилось на 5, то есть 6k+1=5m, то m+1 делится на 6, то есть мы свалились на первую "бесконечную" ветку".

цитата:

И как обработали это исключение? Как можно решить на С++, используя именно рекурсию?

Вот вариант решения:

 #include <iostream> 
 using namespace std; 
 int F( int n, int nest = 0 ) { 
   if( nest > 100 ) return -9999; 
   if( n <= 5 ) return n; 
   if( n % 5 == 0 ) 
     return n + F(n/5 + 1, nest+1); 
   else 
     return n + F(n+6, nest+1); 
 } 
  
 int main() 
 { 
   int n = 1; 
   while( 1 ) { 
     int r = F(n); 
     if( r < 0 ) 
       cout << "***" << n << endl; 
     else { 
       cout << n << " " << r << endl; 
       if( r > 1000 ) break; 
       } 
     n += 1; 
     } 
 }

 Отправлено: 22.12.21 11:35. Заголовок: наконец дошло!

Понял! Действительно сначала нужно сделать анализ при каких значениях n эти рекуррентные формулы будут "ходить по кругу" (бесконечный цикл). И это действительно при n=6k, 6k+1. И тогда, исключив эти номера, рекурсия может заполнить все остальные. Ответ действительно 131! Будем надеяться, что на реальном ЕГЭ таких задач хотя бы этой весной не будет (за 1 балл неоправданно большая работа)..

 Отправлено: 21.01.22 22:26. Заголовок: Добрый вечер, не идё..

Добрый вечер, не идёт программа, выдаёт бесконечную ошибку, что не так???? номер 81

def f(n):
if n<=5:return n
if n>5 and (n%5==0):return n+f(n/5+1)
if n>5 and (n%5!=0): return n+f(n+6)
for n in range (1,1000):
if f(n)>=1000:
print(n)
break

 Отправлено: 22.01.22 23:18. Заголовок: Ксения1102 Посмотри..

Ксения1102
Посмотрите разбор подобной задачи здесь
Причем к этой задаче подойдет именно решение Константина Юрьевича. Последнюю ветку игнорить в этой задаче нельзя.