16 - Вычисление значения рекурсивной функции
Источники:
сайт Полякова (https://kpolyakov.spb.ru/)
демонстрационная версия станции КЕГЭ (https://kompege.ru/)
Embedded Files
1) (Е.Джобс - вариант 11022021) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n + 3, при n <= 3
F(n) = F(n - 2) + n, при п>3 и четном значении F(n-1),
F(n) = F(n - 2) + 2· n, при n > 3 и нечетном значении F(n-1)
Определите сумму значений, являющихся результатом вызова функции для значений в диапазоне [40; 50].
Решение
Вариант 1
def f(n):
global m
if n<=3: return n+3
else:
if m[n-1]%2==0: return m[n-2]+n
else: return m[n-2]+2*n
m=[];s=0
for i in range(0,51):m.append(f(i))
print(sum(m[40:]))
Вариант 2 (t=0.00099992 c.)
from functools import * # кэш результатов выполнения функций
@lru_cache() # кэш результатов выполнения функций
def f(n):
if n<=3: return n+3
elif f(n-1)%2==0: return f(n-2)+n
else: return f(n-2)+2*n
s=0
for i in range(40,51): s+=f(i)
print(s)
Вариант 3 (t=0.0009996 с.)
m=[0]*51
for n in range(51):
if n<=3: m[n]=n+3
elif m[n-1]%2==0:m[n]=m[n-2]+n
else:m[n]=m[n-2]+2*n
print(sum(m[40:]))
Ответ: 8508
2) (№ 2287) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n + 3, при n ≤ 18
F(n) = (n//3)*F(n//3) + n - 12, при n > 18, кратных 3
F(n) = F(n-1) + n*n + 5, при n > 18, не кратных 3
Здесь // обозначает деление нацело. Определите количество натуральных значений n из отрезка [1; 800], для которых все цифры значения F(n) чётные.
Решение
Вариант 1
def f(n):
if n<=18: return n+3
elif n%3:return f(n-1)+n*n+5
else: return (n//3)*f(n//3)+n-12
k=0
for i in range(1,800+1):
fl=1
for c in str(f(i)):
if c in '13579':
fl=0
break
if fl:k+=1
print(k)
Вариант 2
def f(n):
if n<=18: return n+3
elif n%3:return f(n-1)+n*n+5
else: return (n//3)*f(n//3)+n-12
k=0
for i in range(1,801):
x=str(f(i))
if not('1'in x or'3'in x or'5'in x or'7'in x or'9'in x): k+=1
print(k)
Ответ: 16
3) (Е.Джобс - вариант 15032021) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 3
F(n) = F(n–1) - F(n-2) + 3n, при n > 1
Чему равно значение функции F(40)? В ответе запишите только целое число.
Решение
Вариант 1
m=[0]*(40+1)
m[0]=1
m[1]=3
for i in range(2,40+1):
m[i]=m[i-1]-m[i-2]+3*i
print(m[40])
Вариант 2
from functools import *
@lru_cache()
def f(n):
if n==0:
return 1
elif n==1:
return 3
else:
return f(n-1)-f(n-2)+3*n
print(f(40))
Ответ: 126
4) (№ 4128 А.Богданов) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(0) = 0
F(n) = 1, когда 1 ≤ n < 3,
F(n) = F(n - 1) + F(n - 2), когда n ≥ 3.
Определите четыре последние цифры числа F(47).
Решение
Вариант 1
m=[0]*(47+1)
m[1]=1
m[2]=1
for i in range(3,47+1):
m[i]=m[i-1]+m[i-2]
print(str(m[47])[-4:])
Вариант 2
from functools import *
@lru_cache()
def f(n):
if n==0: return 0
elif n<3: return 1
else: return f(n-1)+f(n-2)
print(str(f(47))[-4:])
Ответ: 5073
5) (№ 3124) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n + 3 при n < 3
F(n) = (n + 2)·F(n–4), если n ≥ 3 и делится на 3,
F(n) = n + F(n–1) + 2·F(n–2), если n ≥ 3 и не делится на 3.
Чему равно значение функции F(20)?
Решение
from functools import *
@lru_cache()
def f(n):
if n<3: return n+3
elif n%3==0: return (n+2)*f(n-4)
else: return n+f(n-1)+2*f(n-2)
print(f(20))
Ответ: 1112057
6) (№ 3134) Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 1000000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.
def F( n ):
print(n+1)
if n > 1:
print(2*n)
F(n-1)
F(n-3)
Решение
def f( n ):
global s
s+=n+1
if n > 1:
s+=2*n
f(n-1)
f(n-3)
s=0
n=0
while not(s>1000000):
s=0
n+=1
f(n)
print(n,s)
Ответ: 30 1249317
7) (№ 2289) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n*n + 11, при n ≤ 15
F(n) = F(n//2) + n*n*n - 5*n, при чётных n > 15
F(n) = F(n-1) + 2*n + 3, при нечётных n > 15
Здесь // обозначает деление нацело.
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) содержит не менее трёх цифр 6.
Решение
def f(n):
if n<=15: return n*n+11
elif n%2:return f(n-1)+2*n+3
else: return f(n//2)+n**3-5*n
k=0
for i in range(1,1001):
if str(f(i)).count('6')>2: k+=1
print(k)
Ответ: 49
8) (№ 2288) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n + 15, при n ≤ 5
F(n) = F(n//2) + n*n*n - 1, при чётных n > 5
F(n) = F(n-1) + 2*n*n + 1, при нечётных n > 5
Здесь // обозначает деление нацело.
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) содержит не менее двух цифр 8.
Решение
def f(n):
if n<=5: return n+15
elif n%2:return f(n-1)+2*n*n+1
else: return f(n//2)+n**3-1
k=0
for i in range(1,1001):
if str(f(i)).count('8')>1: k+=1
print(k)
Ответ: 164
9) (№ 2279) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n*n*n + n, при n > 20
F(n) = 3*F(n+1) + F(n+3), при чётных n ≤ 20
F(n) = F(n+2) + 2*F(n+3), при нечётных n ≤ 20
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) не содержит цифру 1.
Решение
def f(n):
if n>20: return n**3+n
elif n%2==0: return 3*f(n+1)+f(n+3)
else:return f(n+2)+2*f(n+3)
k=0
for i in range(1,1001):
if not('1' in str(f(i))):k+=1
print(k)
Ответ: 384
10) (№2283) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n*n + 4*n + 3, при n > 25
F(n) = F(n+1) + 2*F(n+4), при n ≤ 25, кратных 3
F(n) = F(n+2) + 3*F(n+5), при n ≤ 25, не кратных 3
Определите количество натуральных значений n из отрезка [1; 1000], для которых сумма цифр значения F(n) равна 24.
Решение
Вариант 1
def f(n):
if n>25: return n*n+4*n+3
elif n%3:return f(n+2)+3*f(n+5)
else: return f(n+1)+2*f(n+4)
k=0
for i in range(1,1001):
s=0
for c in str(f(i)): s+=int(c)
if s==24:k+=1
print(k)
Вариант 2
def f(n):
if n>25: return n*n+4*n+3
elif n%3:return f(n+2)+3*f(n+5)
else: return f(n+1)+2*f(n+4)
k=0
for i in range(1,1001):
if sum(map(int,str(f(i))))==24:k+=1
print(k)
Ответ: 100
11) (№2282) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n*n + 5*n + 4, при n > 30
F(n) = F(n+1) + 3*F(n+4), при чётных n ≤ 30
F(n) = 2*F(n+2) + F(n+5), при нечётных n ≤ 30
Определите количество натуральных значений n из отрезка [1; 1000], для которых сумма цифр значения F(n) равна 27.
Решение
Вариант 1
def f(n):
if n>30: return n*n+5*n+4
elif n%2:return 2*f(n+2)+f(n+5)
else: return f(n+1)+3*f(n+4)
k=0
for i in range(1,1001):
s=0
for c in str(f(i)): s+=int(c)
if s==27:k+=1
print(k)
Вариант 2
def f(n):
if n>30: return n*n+5*n+4
elif n%2:return 2*f(n+2)+f(n+5)
else: return f(n+1)+3*f(n+4)
k=0
for i in range(1,1001):
if sum(map(int,str(f(i))))==27:k+=1
print(k)
Ответ: 137
12) (№2277) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2*n*n*n + n*n, при n > 25
F(n) = F(n+2) + 2*F(n+3), при n ≤ 25
Определите сумму цифр значения F(2).
Решение
def f(n):
if n>25: return 2*n**3+n*n
else: return f(n+2)+2*f(n+3)
print(sum(map(int,str(f(2)))))
Ответ: 33
13) (№ 4544) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(n) = 0 при n = 0
F(n) = F(n/2) - 1 при чётных n > 0
F(n) = 3 + F(n–1) при нечётных n > 0
Сколько различных значений может принимать функция F(n) для чисел n, меньших 1000?
Решение
def f(n):
if n==0: return 0
elif n%2: return 3+f(n-1)
else: return f(n//2)-1
d={} # создаем словарь
for i in range(1000): d[f(i)]=0
print(len(d))
Ответ: 26
14) (№ 4543) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(n) = 0 при n = 0
F(n) = F(n/2) - 1 при чётных n > 0
F(n) = 2 + F(n–1) при нечётных n > 0
Сколько существует чисел n, меньших 1000, для которых значение F(n) будет равно 3?
Решение
def f(n):
if n==0: return 0
elif n%2: return 2+f(n-1)
else: return f(n//2)-1
k=0
for i in range(1000):
if f(i)== 3: k+=1
print(k)
Ответ: 173
15) (№ 4495 А.Богданов) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(n) = 0 при n ≤ 2 или n = 8
F(n) = 1 при n = 3
F(n) = F(n–2) + F(n–1) при n > 3 и n ≠ 8
Для какого значения n значение F(n) будет равно 25?
Решение
def f(n):
if n<=0 or n==8: return 0
elif n==3: return 1
else: return f(n-2)+f(n-1)
n=0
while f(n)!=25: n+=1
print(n)
Ответ: 13
16) (№ 4192 П.Волгин) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 1
F(n) = F(n–1) + F(n–2), при чётном n > 0
F(n) = 1,5*F(n–1), при нечётном n > 0
Сколько различных цифр встречается в целой части значения функции F(15)?
Решение
def f(n):
if n==0: return 1
elif n%2: return 1.5*f(n-1)
else: return f(n-1)+f(n-2)
k={}
for i in str(int(f(15))): k[int(i)]=0
print(len(k))
Ответ: 3
17) (№ 4190 П.Волгин) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 3
F(n) = F(n–1), при 0 < n ≤ 15
F(n) = 2,5*F(n–3), при 15 < n < 95
F(n) = 3,3*F(n–2), при n ≥ 95
С какой цифры начинается целая часть значения функции F(70)?
Решение
def f(n):
if n==0: return 3
elif n<=15: return f(n-1)
elif n<95: return 2.5*f(n-3)
else: return 3.3*f(n-2)
print(str(f(70))[0])
Ответ: 1
18) (№ 4174 Е.Джобс) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 1, F(1) = 3
F(n) = F(n–1) – F(n–2) + 3n, при чётном n > 1
F(n) = F(n–2) – F(n–3) + 2n, при нечётном n > 1
Чему равно значение функции F(40)? В ответе запишите только целое число.
Решение
Вариант 1
def f(n):
if n==0: return 1
elif n==1: return 3
elif n%2: return f(n-2)-f(n-3)+2*n
else: return f(n-1)-f(n-2)+3*n
print(f(40))
Вариант 2
from functools import * # кэш результатов выполнения функций
@lru_cache() # кэш результатов выполнения функций
def f(n):
if n==0: return 1
elif n==1: return 3
elif n%2: return f(n-2)-f(n-3)+2*n
else: return f(n-1)-f(n-2)+3*n
print(f(40))
Ответ: 84
19) (№ 3493 Е.Джобс) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 1, при n < -100000,
F(n) = F(n–1) + 3·F(n–3) + 2, при n > 10,
F(n) = -F(n–1) для остальных случаев.
Чему равно значение F(20)?
Решение
def f(n):
if n<=10:
if n%2: return 1
else: return -1
else:return f(n-1)+3*f(n-3)+2
print(f(20))
Комментарий. Оператор F(n) = -F(n–1) передает значение меняя его знак. значение функции F(-100001) = 1 а F(-100000) = -1. Делаем вывод => При значении n<=10 все четные функции принимают значение -1 а нечетные 1.
Ответ: 136
20) (№ 4191 П.Волгин) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 3
F(n) = F(n–1), при 0 < n ≤ 15
F(n) = 2,5*F(n–3), при 15 < n < 100
F(n) = 3,3*F(n–2), при n ≥ 100
С какой цифры начинается дробная часть значения функции F(100)?
Решение
def f(n):
if n==0: return 3
elif n<=15: return f(n-1)
elif n<100: return 2.5*f(n-3)
else: return 3.3*f(n-2)
x=str(f(100))
print(x[x.find('.')+1])
Ответ: 6
21) (№ 2936 Апробация 19 февраля 2022 года, Москва) Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = 3 × n + F(n - 2), если n > 1 и при этом n нечётно,
F(n) = 4 × F(n / 2), если n > 1 и при этом n чётно.
Чему равно значение функции F(42)?
Решение
def f(n):
if n==1: return(1)
elif n%2: return 3*n+f(n-2)
else: return 4*f(n//2)
print(f(42))
Ответ: 1444
22) (№4733 А.Куканова) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n)=1 при n=1;
F(n)=(2n−1)×F(n−1), если n>1.
Чему равно значение выражения F(3516)/F(3513)?
Решение
m=[0]*3517
m[1]=1
for i in range(2,3517):
m[i]=(2*i-1)*m[i-1]
print(m[3516]//m[3513])
Ответ: 347280657273
23) (№11948 PRO100 ЕГЭ) Алгоритм вычисления функций F(n) и G(n), где n – целое число, задан следующими соотношениями:
F(n)=G(n–1)
G(n)=n, если n<10
G(n)=G(n–2)+1, если n≥10
Определите количество значений n на отрезке [1,100], для которых значение функции F(n) будет полным квадратом некоторого натурального числа.
Решение
def f(n): return g(n-1)
def g(n):
if n<10: return n
return g(n-2)+1
b=[]
for n in range(1,100+1):
fn=f(n)**0.5
if int(fn)==fn and fn>0: b.append(n)
print(len(b))
Ответ: 12 (0 - не является натуральным числом)
24) (№6187 Р.Сорокин) Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 5, если n ≤ 2
F(n) = F(n-2) + n, если n > 2.
Чему равно значение F(23023)?
Решение
n=23023
m=[5]*(n+1)
for i in range(3,n+1): m[i]=m[i-2]+i
print(m[n])
Ответ: 132526148
25) (№5996 А.Богданов) Обозначим частное от деления натурального числа a на натуральное число b как
a // b, а остаток как a%b. Например, 17//3 = 5, 17%3 = 2. Алгоритм вычисления функции F(n), где n – неотрицательное число, задан следующими соотношениями:
F(n) = 0, если n < 10
F(n) = F(n//10) + (n//10%10) – (n%10).
Найдите количество таких чисел, не превышающих 1010, для которых F(n) = 9.
Решение
def f(n):
if n<10:return 0
return f(n//10)+n//10%10-n%10
k=0
for n in range(10**2):
if f(n)==9: k+=1
print(k)
Ищем закономерность.
При изменении диапазона чисел получаем
10**2 - 1
10**3 - 11
10**4 - 111
10**5 - 1111
Вывод
10**10 - 111111111
Ответ: 111111111
26) (№7235 М.Паршиков) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n ≥ 3000,
F(n) = n + 2x + F(n + 2), если n < 3000.
При каком целом значении x выполняется равенство F(28) – F(34) = 324?
Решение
Ручной способ.
Распишем значение функций
F(28) = 28+2*x+F(30)
F(30) = 30+2*x+f(32)
f(32) = 32+2*x+F(34)
Подставим эти значения в уравнение F(28)-f(34) = 324
Получим
28+2*x+30+2*x+32+2*x+F(34)-F(34) = 324
сокращаем F(34) и решаем уравнение с одной неизвестной
28+2*x+30+2*x+32+2*x+F(34)-F(34) = 90 + 6*x = 324
x = (324 - 90)/6
Программный способ.
Вариант 1 (t=0.105c.)
def f(x):
m=[0]*3500
for n in range(2999,27,-1):
m[n]=n+2*x+m[n+2]
return m[28]-m[34]
x=0
while f(x)!=324:x+=1
print(x)
Вариант 2 (t=0.139c.)
from sys import *
setrecursionlimit(3100)
def f(n,x):
if n>=3000:return 0
return n+2*x+f(n+2,x)
x=0
while f(28,x)-f(34,x)!=324:x+=1
print(x)
Ответ: 39
Page updated
Google Sites
Report abuse