Форум » Рекурсивные процедуры и функции » задание 3696 » Ответить
задание 3696
real1ty: Делаю такие задания, где надо найти определено значение или нет, через try и except, и получаю даже правильный ответ, но считаю это решение плохим . Как теоретически можно понять, определено ли значение или нет?
Ответов - 13
Поляков: Теоретический анализ индивидуален для каждой задачи. В этой можно сразу понять, что бесконечная рекурсия происходит для 6 и 7, а также для всех остальных чисел, больших 5, для которых рекурсия в конце концов приводит к 6 и 7. Это числа вида 6k и 6k+1 (12, 13, 18, 19, ...).
real1ty: Спасибо большое за разъяснение.
Татьяна733: Здравствуйте. А если знаком только с паскалем. Как исправить ошибку выхода [pre2]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.[/pre2]
Поляков: Татьяна733 пишет: Как исправить ошибку выхода Посмотрите обсуждение здесь. Или ставить счётчик вложенных вызовов, или ловить исключение по переполнению стека.
Serov Sergej: Мне кажется, что условие этой задачи №3696 допускает и такое решение (без рекурсии, простой итерацией). Сначала заполняем в массиве все номера, которые делятся на 5. Затем те номера, которые не делятся на 5 и которые могут быть получены с номеров на 6 больших. Ответ в таком случае будет 464 (на этом номере появляется число 1054). По-моему такое решение не противоречит условию. [pre2] #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; } [/pre2]
Поляков: Serov Sergej пишет: Затем те номера, которые не делятся на 5 и которые могут быть получены с номеров на 6 больших. А там еще неправильные значения...
Serov Sergej: Хотя если номера, которые не делятся на 5, заполнять начиная от больших номеров ("обратным ходом"), то ответ будет 196. [pre2] #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; } [/pre2]
Поляков: Serov Sergej пишет: Хотя если номера, которые не делятся на 5, заполнять начиная от больших номеров ("обратным ходом"), то ответ будет 196. А если вы возьмете другое n, то получите другой результат.
Qwerty: До меня никак не доходит. Почему при n=6k, 6k+1. Как Вы догадались? И как обработали это исключение? Как можно решить на С++, используя именно рекурсию? Подскажите, плиз.
Поляков: 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, то есть мы свалились на первую "бесконечную" ветку". И как обработали это исключение? Как можно решить на С++, используя именно рекурсию? Вот вариант решения: [pre2] #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; } }[/pre2]
Serov Sergej: Понял! Действительно сначала нужно сделать анализ при каких значениях n эти рекуррентные формулы будут "ходить по кругу" (бесконечный цикл). И это действительно при n=6k, 6k+1. И тогда, исключив эти номера, рекурсия может заполнить все остальные. Ответ действительно 131! Будем надеяться, что на реальном ЕГЭ таких задач хотя бы этой весной не будет (за 1 балл неоправданно большая работа)..
Ксения1102: Добрый вечер, не идёт программа, выдаёт бесконечную ошибку, что не так???? номер 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
Винникова: Ксения1102 Посмотрите разбор подобной задачи здесь Причем к этой задаче подойдет именно решение Константина Юрьевича. Последнюю ветку игнорить в этой задаче нельзя.
полная версия страницы