Назовите максимальное значение n для которого возможно вычислить f n
F ( n ) = 4 при n = 1, n = 2 и n = 3;
F(11) = 2F(10) + 4 × 11 = 2624 + 44 = 2668
F(13) = 2F(12) + 4 × 13 = 6360 + 52 = 6412
F(14) = 2F(13) + 4 × 14 = 12824 + 56 = 12880
F(15) = 2F(14) + 4 × 15 = 25760 + 60 = 25820
F(16) = 5F(13) = 32060
F ( n ) = 1 при n = 1;
F ( n ) = n + 2 F ( n – 1), если n четно;
F ( n ) = 0 при n = 1;
F ( n ) = 1 при n = 2;
F ( n ) = 
, если n > 2 и при этом четно;
F ( n ) = 
, если n > 2 и при этом нечетно.
Максимальное значение n для которых задача может быть решена за время t
Ниже приведена таблица, строки которой соответствуют различным функциям f(n), а столбцы — значениям времени t.
Заполните таблицу максимальными значенимя n, для которых задача может быть решена за время t, если предполагается, что время работы алгоритма, необходимое для решения задачи, равно f(n) микросекунд.
Таблица
Решение
Первым делом нужно понять вопрос. Допустим, на интересует столбец Минута что туда писать?
Найти максимальное n, при котором задача решается за минуту.
По сути мы решаем уравнение
Где n в микросекундах, то есть правую часть тоже нужно перевести в микросекунды
Минута это 60 * 1000000 = 6 * 10^7 микросекунд
Важно начать решать эту задачу с самого простого задания. Составители специально спрятали его в середину таблицы.
Самый простой случай это f(n) = n
Получается, что строку с f(n) = n заполнить очень леко — нужно просто перевести все временные отрезки в микросекунды
Советую перенести строку с n в верх таблицы.
Теперь рассмотрим f(n) = n^2
Начнём с секунды
n^2 = 60 * 10^6
n = sqrt(60) * 10^3 = sqrt(15) * 2 * 10^3 = 3.872983346 * 2000 = 7745.966692415
В задаче не сказано, что n должно быть целым, но для единообразия ответов сделаем такое допущение. Если есть возможность — лучше уточнять у задающего.
округляем в нижнюю сторону (*), так как нужно максимальное n которое меньше заданного времени.
(*) NB: n могло бы равняться не 7745.966692415 а немного другому занчению — это зависит от точности, с которой был вычислен квадратный корень из 15.
Если вы уверены в этой точности — можете быть спокойны. Если в похожем примере будет очень близкое значение — понять куда округлять будет непросто.
Все задания с простыми степенями можно решить с помощью Python скрипта
Рассмотрим f(n) = 2^n
2^n = 1000000
n = log2(1000000)
Решение на Python
# Для вызова pow() импортируем math import math # Временные отрезки в микросекундах times = [ 1000000 , 60000000 , 3600000000 , 86400000000 , 2592000000000 , 31536000000000 , 3153600000000000 ] # Степени: 0.5 это квадратный корень deg = [ 1 , 0.5 , 1 / 3 , 2 ] for d in deg: print (f "f(n) = n^
Рассмотрим f(n) = lg(n)
Здесь надо понимать, что ,например, при n = 10 время работы = 1 микросекунде
10^lg(n) = 10^60000000
n = 10^6000000
Функцию f(n) = n ^ n полезно рассмотреть до решения задачи с функцией f(n) = n * lg(n)
Написать функцию, которая будет вычислять n довольно легко на Python
import math # n * lg(n) # Решаем задачу n^n = time # где time это наши значения из списка times = [ 1000000 , 60000000 , 3600000000 , 86400000000 , 2592000000000 , 31536000000000 , 3153600000000000 ] # Точность, с которой хотим получить время # 1 значит, что для 1000000 и 999999 и 1000001 # будут считаться достигнутым результатом precision = 1 def nn (n, incr, bestdelta, bestn, goal, prec, step, steps): while step < steps: step += 1 if step >= steps: return (bestn, bestdelta) algtime = pow (n, n) # print(f"n =
n * lg(n)
Рассмотрим f(n) = n * lg(n)
n * lg(n) = 1000000
10^(n * lg(n)) = 10^1000000
10^(n * lg(n)) = 10^60000000
n^n = 10^6000000
Получается задача аналогичная f(n) = n^n но для больших чисел. Причём настолько больших, что предыдущий скрипт не осилит даже секунду.
Нужен другой подход, пробуем подставить lg в основание
n * lg(n) = 1000000
lg(n * lg(n)) = lg(1000000)
Такую задачу решить численно гораздо проще
import math times = [ 1000000 , 60000000 , 3600000000 , 86400000000 , 2592000000000 , 31536000000000 , 3153600000000000 ] lgtimes = [math.log(t, 10 ) for t in times] # print(math.log(32, 2)) x = 12.22343383838 print (math.log(x, 2 )) a = 1 n = 10 incr = 10 precision = 0.001 steps = 9999999999 def findn (lgt, steps): a = 1 n = 1000 incr = 10000000000 precision = 0.1 while a < steps: l = math.log(n, 10 ) # print(type(l)) # print(l) ll = math.log(l, 10 ) suml = l + ll delta = lgt — suml # print(f"n =
Результаты для секунды минуты и часа, того же порядка, но отличаются от результатов wolframalpha 153200 6964830 335412040
16 задача ЕГЭ часть 1
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции F(26)?
Вопрос 5
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 3*F(n–1) — F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.
Вопрос 6
(№ 3698) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
Информатика 10 КЛАСС
Назовите количество значений n на отрезке [1;100], для которых F(n) определено и больше 100.
Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
Назовите максимальное значение n, для которого возможно вычислить F(n).
Определите, сколько символов * выведет эта процедура при вызове F(40):
def F ( n ):
print (‘*’)
if n >= 1:
print (‘*’)
F ( n -1)
F ( n -3)
print (‘*’)
