Статья Автор: Щурова Ольга

ЕГЭ 16

Методы:

написать рекурсию, увеличив её глубину
решить методом ДП (динамического программирования) снизу-вверх

Наш Фома заявил, что он не знает/помнит как увеличивать глубину рекурсии и её увиличение тоже имеет ограничения.
На второе предложение он возразил тем, что переписать задачу на вариант снизу-вверх не всегда получиться (надо думать, можно ошибиться)
В итоге, решено использовать рекурсию с мемоизацией.

cash={1:1}

def F(n):
    if n in cash:
        return cash[n]
    cash[n]=F(n-1)*(n-1)
    return cash[n]
    
    

#Программа выше будет работать при а<1000. Но как заставить её работать при больших значениях?

F(500) # от 2 до 500
F(1000)# от 500 до 1000
F(2000)# от 1000 до 2000
F(3000)

answer=(cash[2024]+2*cash[2023])//cash[2022]

print(answer)

# Или

for i in range(2,1112):
    F(i)
    
ans=(F(2024)+F(1112)*F(1113))//F(2022)

print(ans)

'''Алгоритм вычисления функции F(n) задан следующими соотношениями:

                  F(n) = 1 при n = 1

              F(n) = 2·F(n–1), если n чётно,

              F(n) = 5n + F(n–2), если n нечётно.

Чему равно значение функции F(64)?'''

cash={1:1}

def F(n):
  if n in cash:
    return cash[n]
  if n%2==0: 
    cash[n]=F(n-1)*2
  else:
    cash[n]=F(n-2)+5*n
    
  return cash[n]



print(F(64))

Задача 5 ( Tasks for classwork)

Алгоритм вычисления функции F( n) задан следующими соотношениями:

F( n) = n при n ≤ 3;

F( n) = n * n * n + F(n – 1), если n > 3 и дает остаток 0 при делении на 3

F( n) = 4 + F(n // 3), если n > 3 и дает остаток 1 при делении на 3

F( n) = n * n + F(n – 2), если n > 3 и дает остаток 2 при делении на 3

Здесь // обозначает деление нацело. В качестве ответа на задание выведите значение F(100).

def F(n):
    if n in cash:
        return cash[n]
    
    if n%3==0: cash[n]=F(n-1)+n*n*n
    
    elif n%3==1: cash[n]=F(n//3)+4
    
    else: cash[n]=F(n-2)+n*n
    
    return cash[n]


print(F(100))

Задача 8( Tasks for classwork)

Алгоритмы вычисления функций F(n) и G(n) заданы следующими соотношениями (здесь // – операция деления нацело, % – остаток от деления):

F(n) = n, при n < 10,

F(n) = F(G(n)), при n ≥ 10,

G(n) = n, при n < 10,

G(n) = n % 10 + G(n // 10), при n ≥ 10.

Чему равно значение F(12345678987654321)?

cashf={1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}
cashg={1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}

def F(n):
    if n in cashf:
        return cashf[n]
    
    cashf[n]=F(G(n))
    
    return cashf[n]
    
    
def G(n):
    
    if n in cashg:
        return cashg[n]
    
    cashg[n]=G(n//10)+n%10
    
    return cashg[n]
        
    
print(F(12345678987654321))

Задача 9( Tasks for classwork)

Алгоритмы вычисления функций F( n) и G( n) заданы следующими соотношениями (здесь // – операция деления нацело, % – остаток от деления):

F( n) = n, при n < 10,
F( n) = n % 10 + F(n // 10), при n ≥ 10.
G( n) = n, при n < 10,
G( n) = G(F( n)), при n ≥ 10,

Чему равна сумма значений функции G(n) для всех двузначных n?

cashf={1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}
cashg={1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}

def F(n):
    if n in cashf:
        return cashf[n]
    
    cashf[n]=F(n//10)+n%10
    
    return cashf[n]
    
    
def G(n):
    
    if n in cashg:
        return cashg[n]
    
    cashg[n]=G(F(n))
    
    return cashg[n]
        
    
for i in range(1,100):
  G(i)

s=0
for n in range(10,100):
    s+=cashg[n]

print(s)


#Чему равна сумма значений функции G(n) для всех двузначных n?

Task 7,at=2

df={1:1}
dg={1:1}

def f(n):
  if n in df:
    return df[n]

  if n>1: df[n]=f(n-1)-2*g(n-1)
  
  return df[n]
                  
                                   
def g(n):
  if n in dg:
    return dg[n]
            
  if n>1: dg[n]=f(n-1)+2*g(n-1)
              
  return dg[n]  

print(g(21))

Task 10,at=2


d={}

def f(n):
    if n in d: return d[n]
    if n<=3: d[n]=n-1
    if n>3 and n%2==0: d[n]=f(n-2)+n//2-f(n-4)
    if n>3 and n%2!=0: d[n]=f(n-1)*n+f(n-2)
    
    return d[n]
    
f(300)    
f(1000)
f(3000)
print(f(4952)+2*f(4958)+f(4964))

Task=10,at=1

import sys

sys.setrecursionlimit(2000)
d={}

def f(n):
    if n in d: return d[n]
    if n<7: d[n]=7
    if n>=7 and n%3!=0: d[n]=5-f(n-1)
    if n>=7 and n%3==0: d[n]= 3+f(n-1)
    return d[n]

f(1500)
f(2000)
f(3000)
print(f(3015))

Задачи с третьей попытки тренировки 16(практика за 27.01.25)

df={1:1}
dg={1:1}

def f(n):
    if n>1 and n not in df: df[n]=2*g(n-1)+5*n
    return df[n]

def g(n):
    if n>1 and n not in dg: dg[n]=f(n-1)+2*n
    return dg[n]

print(f(4)+g(4))
print(f(4))
print(dg[4])

d={}

def f(n):
    if n in d: return d[n]
    if n<100: d[n]=n*n
    if n>99 and n%2==0: d[n]=f(n-1)//2
    if n>99 and n%2!=0: d[n]=2*f(n-1)
    
    return d[n]

f(300)

for x in range(1000,17_001,1000):
  f(x)
  
print(1000*f(16_384)//f(7777))

print(d[16_384],d[7777])

d={}

def f(n):
    if n in d: return d[n]
    if n<2: d[n]=1
    if n>=2 and n%2==0: d[n]=f(n//2)+1
    if n>=2 and n%2==1: d[n]=f(n-3)+3
    return d[n]


n=1

while f(n)!=31:
    n+=1
    
print(n)

print(f(893))

Чтобы оставить комментарий нужна авторизация

Печать