Форум » Динамическое программирование » Задача 103. Ограничение на количество команд » Ответить
Задача 103. Ограничение на количество команд
Коробко: Здравствуйте! Подскажите, пожалуйста, правильный алгоритм решения новых задач, например з.103 из ЕГЭ-23. Все путается и каждый раз ответ разный. Заранее большое спасибо.
Ответов - 15
gravy: Если не трудно - выложите кто-нибудь код для задач 103-107, в которых есть привязка на кол-во команд, на python или pascal, а то java какая-то мутная.
appendix: Если не трудно - выложите кто-нибудь код для задач 103-107, в которых есть привязка на кол-во команд, на python или pascal, а то java какая-то мутная. #103.Сколько существует программ, состоящих из 6 команд, для которых при исходном числе 1 результатом является число 20? [pre2] n = 1 a = [] b = [] #первое действие a.append(n+1) a.append(n+2) a.append(n*2) #действий на одно меньше for k in range(5): n = len(a) for i in range(n): a.append(a[0]+1) a.append(a[0]+2) a.append(a[0]*2) a.remove(a[0]) #удаляем оригинал после всех действий print(a.count(20)) #сбор всех результатов в массив и подсчёт в нём 20.[/pre2] Если нужно подсчитать количество различных элементов, можно создать второй массив из неповторяющихся эл-ов первого: [pre2] for i in a: if i not in b: b.append(i)[/pre2]
Поляков: Вот решение задачи 105 на Python: [pre2] TARGET = 25 def rec( n, remains ): if remains == 0: if n == TARGET: return 1 return 0 return rec( n+1, remains-1 ) + \ rec( n+3, remains-1 ) + \ rec( n*2, remains-1 ) print( rec(2, 7) ) [/pre2]
OlgaChe1: Поляков пишет: return rec( n+1, remains-1 ) + \ А что такое + \ ? Все, понятно: + сумма \ - перевод строки
polyakovss: OlgaChe1 пишет:А что такое + \ ? "\" - продолжение на следующей строке. Получаем: return rec( n+1, remains-1 ) + rec( n+3, remains-1 ) + rec( n*2, remains-1 ).
mskorotkov: Возможно кому-нибудь полный список программ поможет дойти до решения 1 → 2 → 3 → 4 → 5 → 10 → 20 1 → 2 → 3 → 4 → 8 → 10 → 20 1 → 2 → 3 → 6 → 8 → 10 → 20 1 → 2 → 4 → 6 → 8 → 10 → 20 1 → 2 → 4 → 8 → 9 → 10 → 20 1 → 2 → 4 → 8 → 9 → 18 → 20 1 → 2 → 4 → 8 → 16 → 18 → 20 1 → 2 → 4 → 6 → 8 → 10 → 20 1 → 2 → 4 → 8 → 9 → 10 → 20 1 → 2 → 4 → 8 → 9 → 18 → 20 1 → 2 → 4 → 8 → 16 → 18 → 20 1 → 3 → 4 → 6 → 8 → 10 → 20 1 → 3 → 4 → 8 → 9 → 10 → 20 1 → 3 → 4 → 8 → 9 → 18 → 20 1 → 3 → 4 → 8 → 16 → 18 → 20 1 → 3 → 5 → 6 → 8 → 10 → 20 1 → 3 → 5 → 7 → 8 → 10 → 20 1 → 3 → 5 → 7 → 9 → 10 → 20 1 → 3 → 5 → 7 → 9 → 18 → 20 1 → 3 → 6 → 7 → 8 → 10 → 20 1 → 3 → 6 → 7 → 9 → 10 → 20 1 → 3 → 6 → 7 → 9 → 18 → 20 1 → 3 → 6 → 8 → 9 → 10 → 20 1 → 3 → 6 → 8 → 9 → 18 → 20 1 → 3 → 6 → 8 → 16 → 18 → 20 1 → 2 → 3 → 4 → 5 → 10 → 20 1 → 2 → 3 → 4 → 8 → 10 → 20 1 → 2 → 3 → 6 → 8 → 10 → 20 1 → 2 → 4 → 6 → 8 → 10 → 20 1 → 2 → 4 → 8 → 9 → 10 → 20 1 → 2 → 4 → 8 → 9 → 18 → 20 1 → 2 → 4 → 8 → 16 → 18 → 20 1 → 2 → 4 → 6 → 8 → 10 → 20 1 → 2 → 4 → 8 → 9 → 10 → 20 1 → 2 → 4 → 8 → 9 → 18 → 20 1 → 2 → 4 → 8 → 16 → 18 → 20
mskorotkov: В спешке набросал решение на Java. Может кому пригодится. https://gist.github.com/mskorotkov/80342ce0794cd97dc1d5bd54967dfb22
Маслов Евгений: Доброго! Вижу, я не первый, судя по форуму, задаю вопрос по задачам 23 (номера 103-107 из тренинга)... Во вложении рекурсивная программа на С++ из ваших материалов, решающая задачу 103, но ищущая полное количество путей… Вопрос: какие дополнения в программу на C++ нужно внести, чтобы она искала только «программы», состоящие из 6 команд? [pre2] #include <iostream> using namespace std; int Prog( int start, int x) { int K; if( x < start) return 0; if( x == start) return 1; K = Prog( start, x-1); K+=Prog(start, x-2); if(x % 2 == 0 ) K+=Prog(start,x/2); return K; } int main() { cout << Prog(1,20) << endl; } [/pre2]
Поляков: Маслов Евгений пишет: какие дополнения в программу на C++ нужно внести, чтобы она искала только «программы», состоящие из 6 команд? Нужно добавить в рекурсивную функцию один параметр, который обозначает количество оставшихся свободных шагов. Пример на Питоне есть выше.
Anvikm: Решение задачи 23 105 [pre2] def f(x,t,l): if x==t and l==7: return 1 elif x>t: return False else: return f(x+1,t,l+1) +f(x+3,t,l+1) +f(x*2,t,l+1) print(f(2,25,0)) [/pre2]
luckymeeee: спасибо
Маслов Евгений: Спасибо, всем, кто помог конструктивными советами... Теперь задачи 103-107 на C++ оформлены в едином стиле!!! 103 прилагается... [pre] #include <iostream> using namespace std; int Prog( int start, int x, int l) { int K; if( x < start) return 0; if( x == start and l==0) return 1; K = Prog( start, x-1,l-1); K+=Prog(start, x-2,l-1); if(x % 2 == 0 ) K+=Prog(start,x/2,l-1); return K; } int main() { cout << Prog(1,20,6) << endl; } [/pre]
mousoh01: А как это работает на Паскале?
x-ile: С программой понятно. А есть красивое объяснение без использование программы?
Поляков: x-ile пишет: А есть красивое объяснение без использование программы? Пока нет.
полная версия страницы