Форум » Динамическое программирование » Ege-23 125 » Ответить
Ege-23 125
OksanaG: 125) (Е. Джобс) Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 2 2. Сделать простое Первая команда увеличивает число на экране на 2, вторая – получает ближайшее бóльшее простое число. Сколько существует программ, для которых при исходном числе 2 результатом является число 45 и при этом траектория вычислений содержит число 14 и не содержит числа 33? Не понятен смысл команды Сделать простое. Поясните, пожалуйста на примере.
Ответов - 5
EugeneJobs: Простые числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 Дальше читайте задание.
OksanaG: Спасибо! Простые числа мне известны. Вторая команда была не понятна. Разобралась. Ответ сошелся.
oval: И все-таки пояснения требуются :) При заданных условиях 17 получается 2 программами, 18 - одной Тогда 19 можно получить из 17 командой +2 и из 17 и 18 командой сделай простое т.е. 5 программ и общий ответ должен быть 881 Ответ 65 получается если считать, что 19 получается только из 17 и 18 командой сделай простое. со всеми следующими простыми числами ситуация аналогична Так почему для 19 не рассматривается команда 17 + 2? P.S. можно, конечно, считать что 19 получается из 17 командой +2 и из 18 командой сделай простое, но большее простое для 17 это 19, а не 17..... решение: [pre] N = 45 n_in = 14 n_out = 33 n_start = 2 df = [0] * (N+1) df[n_start] = 1 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43] for i in range(n_start, n_in + 1): if primes.__contains__(i): x = primes.index(i) for j in range(primes[x - 1], i): df[ i] += df[j] df[ i] += df[i - 2] for i in range(0, n_in): df[ i] = 0 for i in range(n_in+1, N+1): if primes.__contains__(i): x = primes.index(i) for j in range(primes[x - 1], i): df[ i] += df[j] else: # зачем нужен else? df[ i] += df[i - 2] df[n_out] = 0 # for i in range(N): # print((i, df[ i]), end=", ") print() print(df[N]) [/pre]
Timka: [pre2] def prost(z): for i in range(2,int(z**0.5)+1): if z%i==0: z+=1 return prost(z) else: return z def f( start, end ): if start ==end: return 1 if start > end or start ==33: return 0 return f(start+2,end)+ f(prost(start+1),end) print( f(2,14)*f(14,45) ) [/pre2]
oval: Timka пишет: print( f(2,14)*f(14,45) ) Эта программа тоже выдает число 881, видимо, это и надо считать верным ответом
полная версия страницы