Решение 23 задачи проекта Эйлера на python
Решаю 23 задачу из проекта Эйлера. Моя идея состоит в том, что перебирая все числа от 1 до 28123, я нахожу среди них избыточные и добавляю в список, а затем проверяю, может ли число быть представлено, как сумма двух избыточных чисел из этого списка. Если может, то я вычитаю это число из суммы всех чисел от 1 до 28123. Таким образом, в сухом остатке я должен получить сумму чисел, которые не могут быть представлены как сумма двух избыточных чисел. Реализация на языке:
Во втором цикле я начинаю с числа 4, так как ни 1, ни 2, ни 3 — не избыточные числа, и не могут быть представлены как сумма двух избыточных чисел. А прописывать для них отдельные случаи я не вижу смысла.
Я понимаю, что мой код плохо оптимизирован, над этим я буду работать потом. Сейчас меня интересует, почему он выдает неправильный ответ? Верное решение — 4179871, мой код говорит, что 53218451, то есть разница огромная. В чем проблема?
мой код даёт 4179871
работает 26,2 сек, основная оптимизация сделана на определении суммы — я прохожу по всем избыточным числам, а затем проверяю, является ли разность избыточным числом (для множества поиск числа в списке выполняется за очень короткое время)
версия 2:
основное время уходит на составление списка избыточных чисел (O(n^2) сложность все таки)
главная оптимизация — множители надо считать только до половины числа, дальше множителей нет
второстепенная оптимизация — рассматривать первый множитель только до проверяемого числа и не больше, но для этого приходится использовать список, а не множество (так как нужны отсортированные числа, а множество это обеспечить не может)
Для красоты функцию is_redundant можно записать как
на скорость это никак не влияет 🙁
вариант 3:
основная оптимизация — иной подход к функции is_redundant определения избыточности числа (O(n^1.5) сложность)
проходим до множителя sqrt(value) включительно
если число i является множителем, то и value // i является множителем, учитываем и его, но. только 1 раз, для чего используется список всех чисел от 0 до value :
Как решать 23 задание на питоне
ЕГЭ по информатике 2023 — Задание 23 (Чудо шаблон!)
| Числа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| +3 | — | — | — | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| *2 | — | 1 | — | 2 | — | 3 | — | 4 | — | 5 |
| Кол. Прог. |
1 | 1 | 0 | 2 | 1 | 0 | 2 | 3 | 0 | 3 |
| Числа | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| +3 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| *2 | — | 6 | — | 7 | — | 8 | — | 9 | — | 10 | — | 11 | — | 12 | — |
| Кол. Прог. |
3 | 0 | 3 | 5 | 0 | 6 | 5 | 0 | 6 | 8 | 0 | 9 | 8 | 0 | 9 |
| Числа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 2x+1 | — | — | 1 | — | 2 | — | 3 | — | 4 | — | 5 | — |
| +1 | — | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| Кол. Прог. |
1 | 1 | 2 | 2 | 3 | 3 | 5 | 5 | 7 | 7 | 10 | 10 |
| Числа | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| +1 | — | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| *3 | — | — | — | — | 2 | — | — | 3 |
| +2 | — | — | 2 | 3 | 4 | 5 | 6 | 7 |
| Кол-во программ |
1 | 1 | 2 | 3 | 6 | 9 | 15 | 25 |
| Числа | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| +1 | — | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| *3 | — | — | — | — | — | — | 3 | — | — | — | — | — |
| +2 | — | — | 3 | 4 | 5 | 6 | 7 | — | 9 | 10 | 11 | 12 |
| Кол-во программ |
1 | 1 | 2 | 3 | 5 | 8 | 14 | 14 | 28 | 42 | 70 | 112 |
| Числа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| +1 | — | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| +3 | — | — | — | 1 | 2 | 3 | 4 | 5 | 6 | — | — | 9 | 10 | 11 | 12 | 13 | 14 |
| Кол-во программ |
1 | 1 | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 13 | 13 | 26 | 39 | 52 | 78 | 117 | 169 |
def ways(n, goal):
if n>goal: return 0
if n==goal: return 1
return ways(n+1,goal)+ways(n+3,goal)
def ways(n, goal):
if n<goal: return 0
if n==goal: return 1
return ways(n-2,goal)+ways(n-5,goal)
def ways(n, goal):
if n>goal: return 0
if n==goal: return 1
return ways(n+1,goal)+ways(n+2,goal)+ways(n*2,goal)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal, zapret)+ways(n+2,goal, zapret)+ways(n*2,goal, zapret)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal,zapret)+ways(n*2,goal,zapret)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)+ways(n*3,goal,zapret)
def ways(n, goal, zapret):
if n>goal: return 0
if n in zapret: return 0
if n==goal: return 1
return ways(n+1,goal,zapret)+ways(n+2,goal,zapret)+ways(n*3,goal,zapret)
def ways(n, goal, prog):
if n>goal: return 0
if n==goal:
if prog[-2]==’1′: return 1
else: return 0
return ways(n+1,goal,prog+’1′)+ways(n+2,goal,prog+’2′)
def ways(n, goal, lprog):
if n>goal: return 0
if n==goal:
if lprog==7: return 1
else: return 0
return ways(n+1,goal,lprog+1)+ways(n+4,goal,lprog+1)+ways(n*2,goal,lprog+1)
k=12
for i in range(2**k):
prog=bin(i)[2:]
if len(prog)<k: prog=’0’*(k-len(prog)) + prog
n=start
for j in range(k):
if prog[j]==’0′: n += 1
else: n=2*n-3
if not n in a: a.append(n)
k=12
start=3
a=[]
for i in range(2**k):
prog=bin(i)[2:]
if len(prog)<k: prog=’0’*(k-len(prog)) + prog
n=start
for j in range(k):
if prog[j]==’0′: n += 1
else: n=2*n-3
if not n in a: a.append(n)
print(len(a))
def f(n,l,k):
if l==k:
if not n in a: a.append(n)
return
f(n+1,l+1,k)
f(2*n-3,l+1,k)
return
def f(n,l,k):
if l==k:
if not n in a: a.append(n)
return
f(n+1,l+1,k)
f(2*n-3,l+1,k)
return
def ways(n, goal, zapret):
if n<goal: return 0
if n in zapret: return 0
if n==goal: return 1
if n%3==0: return ways(n-2,goal,zapret)
else: return ways(n-2,goal,zapret)+ways((n//3)*3,goal,zapret)
def makeprime(n):
n += 1
while True:
k=2
prime=True
while k*k<=n:
if n%k==0:
prime=False
break
k += 1
if prime: return n
n += 1
Как решать 23 задание на питоне
Конъю́нкция (от лат. conjunctio — «союз, связь») — логическая операция, по смыслу максимально приближенная к союзу «и»
Наиболее часто в заданиях будет отображаться как " /\ ", реже как " & ".
В питоне мы будем заменять на " and ".
Дизъю́нкция (от лат. disjunctio — «разобщение»), логи́ческое сложе́ние, логи́ческое ИЛИ, включа́ющее ИЛИ; иногда просто ИЛИ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу».
Наиболее часто в заданиях будет отображаться как " /\ ", реже как " & ".
В заданиях №2 отображается как " \/ ", иногда " || ".
В питоне мы будем заменять на " or ".
Отрица́ние (инве́рсия, от лат. inversio — переворот, логи́ческое «НЕ») в логике — унарная операция над суждениями, результатом которой является суждение, «противоположное» исходному. Обозначается знаком ¬ перед или чертой — над суждением.
В питоне если перед переменной ¬ или — над суждением ставим переменную в скобки и перед ней ставим " not( ) ".
Имплика́ция (от лат. implicatio «связь; сплетение») — бинарная логическая связка, по своему применению приближенная к союзам «если…, то…».
Импликация записывается как посылка ⇒ следствие; применяются также стрелки другой формы и направленные в другую сторону, но всегда указывающие на следствие.
В коде заменяем на " <= ".
Логическая равнозначность или эквиваленция (или эквивале́нтность[1]) — это логическое выражение, которое является истинным тогда, когда оба простых логических выражения имеют одинаковую истинность. Двуместная логическая операция обычно обозначается символом ≡ или ↔.
В питоне обозначаем двумя знаками равно " == ".
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌1) Прописываем print("x, y, z, w") — для того, чтобы когда мы видели, какая переменная
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌отвечает за какое значение.
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌2) Задаём каждой переменной значение, которое она может принимать — " 0 " или " 1 "
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ (пишем in range(2) потому, что учитывается интервал от 0 до 2 не включительно, то есть
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌᠌ ᠌можно просто написать в скобках 2, а не in range(0, 2)
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌3) Записываем условие с помощью " if ", дальше прописываем нашу функцию и значение
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌которое оно принимает:
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌* Если F = 0, то всё условие ставим в скобки и перед ними ставим not -> not(вся
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌функция). Также можно вставить функцию в скобки и написать после неё написать " ==
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌ ᠌False"
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌᠌ ᠌* Иначе F = 1, ничего не делаем с функцией; или ставим её в скобки, а в конце пишем "
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌ ᠌== True"
᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌ ᠌4) Пишем print(x, y, z, w) и запускаем код, выведенные значения сопоставляем с ᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌᠌ ᠌ ᠌ ᠌ ᠌таблицей ᠌и правильно вписываем, строки с таблице не должны повторяться!
Разбор 23 задания на Python | ЕГЭ по информатике 2021
А почему где надо пройти через конкретное число мы умножаем ?
Алексей Ёрочкин
Время: 9: 01
Вроде можно решить и так:
def f(a,b):
if a > b:
return 0
if a == b:
return 1
else:
return f(a+1,b) + f(a*3,b)
print(f(1,20))
Ответ : 12
eziazare
Блять, да он ебаный волшебник
я списал твое решение и угадай что оно выводиn 75 когда должно 120
сука я 4 часа сижу на двухминутном задание из- за тебя какого хуя я 1 в 1 rопирую в выводит разное ?
temachqa
не подскажите, а как поступить, если команда "возвести в квадрта"
Mr ERROR
А если например не прибавь следующее, а на оборот предыдущие?
Анатолий Анатолий
Последняя задача по аналогии с предпоследней решается, например, вот так:
n=set() # глобальный n можно не писать
def f(x,p):
if p==6:
if x>=34 and x<=59:
n.add(x)
else:
f(x+1,p+1)
f(x+2, p + 1)
f(x * 2, p + 1)
f(1,0)
print(len(n))
Иван Св
Благодарю за подробный разбор!
SUNDRY
Евгения Клочева
можно проще последнюю задачу:
s = set(range(34, 60))
print(len(rez&s))
Михаил Каташевцев
Иван Викторович, подскажите по поводу первого примера. Важен ли порядок команд? Ведь формально добавить сначала 1 а потом четыре, и наоборот сначала 4 а потом 1 — получим две разные программы. Вроде везде показывают что не важен, но мое нутро восстаёт. А за разбор огромное спасибо, отлично дополняет сайт Полякова =)
Python The Best
а если команда возведи в квадрат, то какое условие писать?
If . :
return
FILAMOR TEAM
Почему у меня программа не запускается?
Светлана Башкатова
Иван Викторович, прошу помощи в решении задачи из вопросов по тестированию учителей АСОУ.
Для рождения дочери Петр Петрович заказал крафтовое мороженное в виде земного шара радиусом 5 см. Продавец положил этот шарик мороженного в вафельный стаканчик в виде усеченного конуса с диаметрами верхнего и нижнего оснований 6 и 3 см соответственно и высотой 10 см. Петр Петрович, забирая заказ засомневался, точно ли выполнена модель Земли — он помнил из школьного курса, что форма нашей Земли геоид сплюснутый у полюсов.
Продавец возразил , что все корректно и что различия меньше 1 мм в модели отобразить невозможно.КТО ПРАВ?
-Петр Петрович
— Продавец
Оплату гарантирую. У меня есть свое решение, но .
С уважением Светлана Михайловна Башкатова
Владос гони полтос
там где последний return можно к иксу дописывать +1, *2 к примеру тоже самое получится, только короче
Yosh 25
Иван Викторович, какую литературу для изучения python3 можете посоветовать?