Методическая разработка "ЗАДАНИЕ КИМ 16 КЕГЭ. ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ РЕКУРСИВНОЙ ФУНКЦИИ"

МЕТОДИЧЕСКАЯ РАЗРАБОТКА

ЗАДАНИЕ КИМ 16 КЕГЭ. ВЫЧИСЛЕНИЕ ЗНАЧЕНИЙ РЕКУРСИВНОЙ ФУНКЦИИ

Панычева С.Б. – преподаватель информатики

кадетский корпус (инженерная школа) г. Воронеж

Оглавление

1. Простое вычисление заданного значения рекуррентной последовательности. 1

1.1.     Ручные вычисления. 1

1.2. Вычисление заданного члена рекуррентной последовательности с использованием  рекурсивной функции с помощью языка программирования. 2

2. Использование цикла с параметром в теле программы.. 4

3. Использование двух рекурсивных функций. 5

ХРАНЕНИЕ ЦЕЛЫХ ЧИСЕЛ В КОМПЬЮТЕРЕ.. 7

4. Использование цикла while… в теле программы.. 7

5. Использование двух функций – рекурсивной и не рекурсивной. 9

6. Почему нельзя?. 10

ИЗМЕНЕНИЕ СОСТОЯНИЯ СТЕКА ПРИ ВЫПОЛНЕНИИ ПРОГРАММЫ... 11

7. Еще немного математики*. 14

8. Функции двух переменных*. 15

9. Рекурсивные процедуры*. 16

ПОРЯДОК РАБОТЫ С ФАЙЛОМ В ПАСКАЛЕ.. 19

Используемая литература. 22

1. Простое вычисление заданного значения рекуррентной последовательности

Рекомендуется повторить определение числовой последовательности и способы ее задания. Удобно, например, воспользоваться образовательной платформой ЯКласс: https://www.yaklass.ru/p/algebra/9-klass.

1.1. Ручные вычисления

№ 16 (вариант 4) [1]

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

F(n) = 4 при n = 1, n = 2 и n = 3;

F(n) = 5F(n – 3), если n делится на 4 нацело;

F(n) = 2F(n – 1) + 4n, если n > 3 и не делится на 4 нацело.

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

Решение.

F(1) = 4

F(2) = 4

F(3) = 4

F(4) = 5F(1) = 20

F(5) = 2F(4) + 4×5 = 40 + 20 = 60

F(6) = 2F(5) + 4×6 = 120 + 24 = 144

F(7) = 2F(6) + 4×7 = 288 + 28 = 316

F(8) = 5F(5) = 300

F(9) = 2F(8) + 4×9 = 600 + 36 = 636

F(10) = 2F(9) + 4×10 = 1272 + 40 = 1312

F(11) = 2F(10) + 4×11 = 2624 + 44 = 2668

F(12) = 5F(9) = 3180

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

Ответ: 32060

№ 16 (вариант 1) [1]

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

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

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

F(n) = 1 + 3F(n – 2), если n > 1 и нечетно.

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

Ответ: 9841

№ 16 (вариант 14) [1]

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

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

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

F(n) = , если n > 2 и при этом четно;

F(n) = , если n > 2 и при этом нечетно.

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

Примечание. Квадратные скобки в выражении [х] применяются для обозначения целой части числа х.

Ответ: 91080

1.2. Вычисление заданного члена рекуррентной последовательности с использованием
рекурсивной функции с помощью языка программирования

Важнейшим методологическим приемом программирования на таких языках, как Паскаль, является разбиение решаемой задачи на подзадачи – более простые, с точки зрения программирования, части исходной задачи. Алгоритмы решения таких задач называются вспомогательными алгоритмами – подпрограммами. В Паскале различаются два вида подпрограмм – процедуры и функции. [2]

Обучаясь решению заданий № 16 КЕГЭ, мы повторим применение обоих типов подпрограмм. Причем, рекурсивных, т.е. таких, что обращаются сами к себе. Но начнем с функций. При этом пока не будем особо обращать внимание на то, что функции рекурсивные. Использование функции для нахождения заданного члена рекуррентной последовательности рассмотрим на примере.

Далее, если не сказано иначе, задачи берутся с сайта К.Е. Полякова https://kpolyakov.spb.ru/school/ege.htm.

№ 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)?

Решение.

Выше мы видим структуру программы.

1.      Заголовок программы.

2.      Раздел описаний.

3.      Тело программы.

В данной задаче раздел описаний содержит только описание функции. Рассмотрим описание функции подробно:

function f(n:integer):real; - заголовок функции.

Содержит: имя функции (в данном случае f);

тип аргумента (параметра функции n:integer)

и тип возвращаемого значения :real

В теле функции (заключенном между операторными скобками begin и end; ) описывается алгоритм вычисления значения функции.

Параметр n называется формальным: то есть мы понимаем, что в теле программы функции будет передаваться какое-то целое число, подлежащее обработки.

В теле программы функция вызывается в данном случае в составе стандартной процедуры вывода с фактическим параметром 15.

Запустив программу на выполнение, мы получим результат 915.52734375.

Ответ: 3

(№ 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)?

Ответ: 6

Обратите внимание! В задачах № 4192 и 4191 мы имели дело с вещественной функцией целого аргумента. В дальнейшем, в основном, мы будем иметь дело с целой функцией целого аргумента.

(№ 4173) (Е. Джобс) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:

F(0) = 1, F(1) = 3
F(n) = F(n–1) - F(n-2) + 3n, при n > 1.

Чему равно значение функции F(40)? В ответе запишите только целое число.

Ответ: 126

2. Использование цикла с параметром в теле программы

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

F(0) = 0
F(n) = F(n/2), при чётном n > 0
F(n) = F(n - 1) + 3, при нечётном n > 0

Сколько существует значений n, принадлежащих отрезку [1; 1000], для которых F(n) равно 18?

Решение.

 

Обратите внимание! Раздел описаний содержит описание переменных (которые будут использоваться в теле основной программы) и описание функции. В теле основной программы вызов функции осуществляется при проверке условия (фактическим параметром является параметр цикла i).

Ответ. 209

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

F(n) = 1, при n < 2,
F(n) = F(n/3) - 1, когда n ≥ 2 и делится на 3,
F(n) = F(n - 1) + 17, когда n ≥ 2 и не делится на 3.

Назовите количество значений n на отрезке [1;100000], для которых F(n) равно 43.

Ответ. 201

(№ 4172) (Е. Джобс) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:

F(n) = n + 3, при n ≤ 3
F(n) = F(n – 2) + n, при n > 3 и четном значении F(n-1),
F(n) = F(n – 2) + 2×n, при n > 3 и нечетном значении F(n-1).

Определите сумму значений, являющихся результатом вызова функции для значений n в диапазоне [40; 50].

Указания к решению.

Программу на Паскале, аналогичную той, что написана для решения № 3985, написать можно. Однако работает она долго. Дело в том, что у рекурсивных алгоритмов высокая временная сложность. Почему – посмотрим далее. На своем компьютере (правда, он слабенький), я ждала 5 минут и не дождалась результата. Значения F(40), F(41), F(42) вычислялись у меня 13 секунд. А, чем больше аргумент, тем время вычисления больше. F(50) я уже тоже не дождалась.

Какие варианты?

1-й вариант. Не считать в теле программы сумму. Вычислить F(40) и F(41) (как в задачах раздела 1.2), а потом вручную посчитать остальные значения  F(42), F(43), F(44), F(45), F(46), F(47), F(48), F(49), F(50) (как в задачах раздела 1.1). А потом посчитать сумму. В принципе, можно отдельно считать значения F(i), пока оно считается за разумное время. Чем больше i, тем время расчета больше.

2-й вариант. Использовать MS EXCEL.

Алгоритм решения.

1)      В столбце А запишем значения n от 1 до 50 с помощью функции автозаполнения.

2)      В столбце В будем вычислять значения F(n).

-        В В1 введем формулу = А1 + 3 и с помощью автозаполнения скопируем ее в ячейки В2 и В3 (рисунок 1).

-        В В4 введем формулу =B2+A4 (рисунок 2)

-        В В5 введем формулу =B3+2*A5 (рисунок 3)

-        Выделим ячейки В4 и В5 (обе) и с помощью автозаполнения скопируем их до ячейки В50.

-        Выделим диапазон ячеек В40 : В50 и выполним для них операцию автосуммирования.

Рисунок 1	Рисунок 2

                                 Рисунок 3

Ответ:  8508.

3. Использование двух рекурсивных функций

№ 3929. (А. Богданов) Алгоритмы вычисления функций 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?

Указания. Если вы усвоили все предыдущие разделы, то тут просто.

·         В разделе описаний описываете сначала функцию F, а потом функцию G (так как функция G использует функцию F)

·         В теле основной программы, используя цикл с параметром, вычисляете требуемую сумму.

Ответ: 450

(№ 3492) (Е. Джобс) Алгоритмы вычисления функций F(n) и G(n) заданы следующими соотношениями (// – операция деления нацело):

F(n) = n, при n < 50,
F(n) = 2·G(50–n//2), при n > 49,
G(n) = 10, при n > 40,
G(n) = 30 + F(n + 600 // n), при n < 41.

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

Решение.

Особенностью этой задачи является то, что функция F обращается к функции G, а функция G – к функции F. В этом случае используется опережающее объявление подпрограммы, состоящее из ее заголовка, за которым следует ключевое слово forward. Выглядит это так:

   function G(n: integer):integer; forward;   //Опережающее объявление
                                               функции G

function F(n: integer): integer;

  begin

    if n < 50 then

      F := n

    else

      F :=  2*(g(50 - n div 2));

  end;

  function G(n: integer): integer;

  begin

    if n > 40 then

      G := 10

    else

      G := 30 + F(n + 600 div n);

 end;

 begin

   writeln(f(80));

 end.

Ответ: 812

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

F(1) = G(1) = 1
F(n) = 3·F(n–1) + G(n–1) – n + 5, если n > 1
G(n) = F(n–1) + 3·G(n–1) – 3·n, если n > 1

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

Ответ: 37282721

№ 3928. (А. Богданов) Алгоритмы вычисления функций 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)?

Ответ: 9

Указание к решению задачи 3928. Вроде бы все просто. Но, если вы, как и в предыдущих задачах объявите тип аргументов и значений функций F и G  integer, ответ не совпадет. Почему? Давайте вспомним принципы хранения целых чисел в компьютере.

ХРАНЕНИЕ ЦЕЛЫХ ЧИСЕЛ В КОМПЬЮТЕРЕ

Для хранения целого числа может выделяться 1, 2, 4, 8, … байт. Существует два формата хранения целого числа – со знаком и без знака. От количества выделенных для хранения числа байт и формата хранения зависит диапазон целых чисел данного типа. Подробно принципы хранения целых чисел (в том числе и явление переполнения)  рассматриваются в § 27 [3].

Посмотрим в справочную систему язык PascalABC.Net.

Вообще говоря, при изучении любого нового языка программирования, даже при переходе к другой версии языка, с которым вы давно работаете, надо начинать со знакомством с типами данных.

Итак, максимальное значение переменной типа integer  2147483647. А у нас что надо найти?  12345678987654321 > 2147483647. Возникает переполнение, в результате чего результат искажается. То есть в этой задаче везде, вместо типа integer надо использовать другой целый тип –  int64.

Пробуйте!

Конечно, вопросы отслеживания переполнения актуальны. Но в школьный курс отработка таких действий не входит. Что можно посоветовать? Если возникают какие-то сомнения, использовать «длинные» типы данных, как в описанном выше примере.

4. Использование цикла while… в теле программы

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

F(n) = 1, при n < 2,

F(n) = F(n/3) - 1, когда n ≥ 2 и делится на 3,

F(n) = F(n - 1) + 17, когда n ≥ 2 и не делится на 3.

Назовите минимальное значение n, для которого F(n) равно 110.

Решение.

program N3821_P;

var i: integer;

function F(n: integer): integer;

  begin

    if n < 2 then F := 1

    else if n mod 3 = 0 then f:= f(n div 3)- 1

         else F :=  f(n-1)+17;

  end;

 begin

  i:=1;

  while f(i)<>110 do

    i:=i+1;

  writeln(i);

  end.

Ответ: 59102.

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

F(1) = 1

F(n) = F(n/2) + 1, когда n ≥ 2 и чётное,

F(n) = F(n - 1) + n, когда n ≥ 2 и нечётное.

Назовите минимальное значение n, для которого F(n) равно 19.

Ответ: 448

№ 3139.  (Д.Ф. Муфаззалов) Определите наибольшее трехзначное значение n, при котором значение F(n), будет больше числа 7. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующее значение F(n).

Паскаль	C++
function F(n:   integer): integer; var m,d: byte; begin  if n < 10 then F:=n  else begin    m:= F(n div 10);    d:= m mod 10;    if m < d then F:=d    else F := m  end end;	int F(int n) { if(n < 10)    return n; else {  int m = F(n/10),         d = m%10;  if( m < d )    return d;  else   return m;   } }

Указание. В теле программы двигайтесь от большего i к меньшему.

Ответ: 999 9

№ 3138. (Д.Ф. Муфаззалов) Определите наименьшее значение n, при котором значение F(n), будет больше числа 320. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующее значение F(n).

Паскаль	C++
function F (n: integer): integer; begin  if n > 0 then   F:= n mod 10*F(n div 10)   else     F:= 1; end;	int F(int n) { if( n )   return n%10*F(n/10); else   return 1; }

Ответ: 499 324

5. Использование двух функций – рекурсивной и не рекурсивной

№ 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.

Решение.

program N_2289_P;

var count, i:integer;

function f(n: integer): integer;

begin

  if n<=15 then f:= n*n + 11

  else if n mod 2 = 0 then f:=f(n div 2) + n*n*n - 5*n

       else f := f(n-1) + 2*n + 3

end;

function K_6(n: integer): integer;

var k: integer;

begin

  k := 0;

  while n>0 do

    begin

      if n mod 10 = 6 then k:=k+1;

      n:= n div 10

    end;

  K_6:=k;[1] 

end;

begin

  count := 0;

  for i:= 9 to 1000 do

    if K_6(f(i))>=3 then count := count+1;

  writeln(count);

end.

Ответ: 49

№ 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) чётные.

Ответ: 16

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

F(n) = 2*n*n + 4*n + 3, при n ≤ 15
F(n) = F(n-1) + n*n + 3, при n > 15, кратных 3
F(n) = F(n-2) + n - 6, при n > 15, не кратных 3

Определите количество натуральных значений n из отрезка [1; 1000], для которых все цифры значения F(n) нечётные.

Ответ: 27

№ 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.

Ответ: 137

6. Почему нельзя?

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

F(n) = 1, при n ≤ 1,
F(n) = 3 + F(n / 2 – 1), когда n > 1 и чётное,
F(n) = n + F(n + 2) , когда n > 1 и нечётное.

Назовите минимальное значение n, для которого F(n) = 19.

Решение.

Попробуйте написать программу, аналогичную тем, что писали для решения задач раздела 4. Запустите на выполнение. И?..

Я в окне вывода увидела следующее сообщение: «Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека».

Давайте разбираться, в чем дело. Вот теперь мы должны понять, КАК ИМЕННО РАБОТАЕТ РЕКУРСИВНАЯ ФУНКЦИЯ – функция, которая в процессе вычисления обращается сама к себе. Совершенно не так, как рассмотрено в примерах раздела 1.1. А как? Рассмотрим еще раз пример № 16 (вариант 4) [1].

№ 16 (вариант 4) [1]

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

F(n) = 4 при n = 1, n = 2 и n = 3;

F(n) = 5F(n – 3), если n делится на 4 нацело;

F(n) = 2F(n – 1) + 4n, если n > 3 и не делится на 4 нацело.

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

Здесь первая строка описывает базовые случаи – то есть условие остановки рекурсии. Вторая и третья строки – переход к следующему шагу.

Программу для вычисления F(16) мы писать умеем:

function f(n: integer): integer;

begin

  if n<=3 then f:=4

  else if n mod 4 = 0 then f:=5*f(n -3)

       else f:=4*n + 2*f(n-1)

end;

begin

    writeln(f(16))

      end.

ПРОТОКОЛ РАБОТЫ ПРОГРАММЫ (1 часть)

А: Вызывается f(16). Так как при вычислении  f(16) используется f(13),

Б: Вызывается f(13). Так как при вычислении  f(13) используется f(12),

В: Вызывается f(12). Так как при вычислении  f(12) используется f(9),

Г: Вызывается f(9). Так как при вычислении  f(9) используется f(8),

Д: Вызывается f(8). Так как при вычислении  f(8) используется f(5),

Е: Вызывается f(5). Так как при вычислении  f(5) используется f(4),

Ж: Вызывается f(4). Так как при вычислении  f(4) используется f(1),

З: Вызывается f(1). А это базовый случай. Значение f(1) известно.

 

ИЗМЕНЕНИЕ СОСТОЯНИЯ СТЕКА ПРИ ВЫПОЛНЕНИИ ПРОГРАММЫ

Один из регистров процессора называется указателем стека (англ. stack pointer, SP) – в нем записан адрес последней занятой ячейки стека. При вызове процедуры в стек помещаются значения всех ее параметров, адрес возврата и выделяется место под локальные переменные [4].

На рисунке 1, А показано начальное состояние стека, серым цветом выделены занятые ячейки. Когда функция f вызывается из основной программы с параметром 16, в стек записывается значение параметра, затем – адрес возврата A_V, и выделяется место для локальной переменной, в которую будет записан результат.

SP ¯

А:

SP ¯

Б:

16

A_V

рез.

SP ¯

В:

16

A_V

рез.

13

A_V

рез.

…………………………………………….

SP ¯

З:

16

A_V

рез.

13

A_V

рез.

…..

1

A_V

рез. (4)

Рисунок 1. Изменение состояния стека при вычислении значения рекурсивной функции

Когда выполняется возврат из процедуры, состояние стека меняется в обратную сторону:
З – Ж – Е – Д – Г – В – Б – А.

Из данной схемы следует, что с каждым новым вызовом расходуется дополнительная стековая память. Если вложенных вызовов будет очень много, эта память закончится, и программа завершится аварийно (вот вам «Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека»).

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

ПРОТОКОЛ РАБОТЫ ПРОГРАММЫ (2 часть)

З: результат = 4

Ж: результат = 20

Е: результат = 60

Д: результат = 300

Г: результат = 636

В: результат = 3180

Б: результат = 6412

А: результат = 32060

 

ВОЗВРАЩАЕМСЯ К ЗАДАЧЕ

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

F(n) = 1, при n ≤ 1,
F(n) = 3 + F(n / 2 – 1), когда n > 1 и чётное,
F(n) = n + F(n + 2) , когда n > 1 и нечётное.

Назовите минимальное значение n, для которого F(n) = 19.

Решение. (придется вручную)

F(0) = 1

F(1) = 1

F(2) = 3 + F(0) = 4

F(3) = 3 + F(5) = 3 + 3 + F(7) = …

Мы видим, что при нечетных аргументах наша функция не вычисляется, так как при работе рекурсивного алгоритма происходит удаление от базового случая. Базовый случай при нечетном аргументе не может быть достигнут.

Да и не при каждом четном аргументе функция может быть вычислена. Например,

F(8) = 3 + F(3) = …

Придется смотреть на эту задачу глазами математика (что всегда полезно).

Итак, мы должны прийти к базовому случаю. То есть на k-м шаге n = 0 или n = 1. Поскольку нам нужно наименьшее значение k, считаем:

k-й шаг: n = 0. F(0) = 1 < 19. Предыдущее n было таким, что n : 2 – 1 = 0 Þ n = 2

(k – 1)-й шаг: n = 2. F(2) = 3 + F(0) = 4 < 19. Предыдущее n было таким, что n : 2 – 1 = 2 Þ n = 6

(k – 2)-й шаг: n = 6. F(6) = 3 + F(2) = 7 < 19. Предыдущее n было таким, что n : 2 – 1 = 6 Þ n = 14

(k – 3)-й шаг: n = 14. F(14) = 3 + F(6) = 10 < 19. Предыдущее n было таким, что n : 2 – 1 = 14 Þ n = 30

(k – 4)-й шаг: n = 30. F(30) = 3 + F(14) = 13 < 19. Предыдущее n было таким, что n : 2 – 1 = 30 Þ n = 62

(k – 5)-й шаг: n = 62. F(62) = 3 + F(30) = 16 < 19. Предыдущее n было таким, что n : 2 – 1 = 62 Þ n=126

(k – 6)-й шаг: n = 126. F(126) = 3 + F(62) =  19.

Ответ: 126

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

F(n) = n, при n ≤ 1,
F(n) = 1 + F(n / 2), когда n > 1 и чётное,
F(n) = 1 + F(n + 2) , когда n > 1 и нечётное.

Назовите минимальное значение n, для которого F(n) = 16.

Ответ: 32768

№ 3467[2]. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n + 1 при n < 3
F(n) = F(n-2) + n - 2, если n ≥ 3 и чётно,
F(n) = F(n+2) + n + 2, если n ≥ 3 и нечётно.

Сколько существует чисел n, для которых значение F(n) определено и будет пятизначным?

Решение.

1.      Понятно, что для n ≥ 3 и нечетных F(n) не определено. Значит, нам надо рассмотреть функцию

F(n) = n + 1 при n < 3

F(n) = F(n-2) + n - 2, если n ≥ 3 и чётно.

И определить количество n, для которых 10 000 £ F(n) < 100 000.

2.      Программу составить можно, но время ее выполнения велико – решения не дождемся. С помощью MS EXCEL тоже решать неудобно. Значит, опять посмотрим глазами математика.

3.      Составим таблицу.

n	F(n)	k = (n – 2)/2
1	2	-
2	3	-
4	F(2) + 2 = 3 + 2	1
6	F(4) + 4 = 3 + 2 + 4	2
8	F(6) + 6 = 3 + 2 + 4 + 6	3
……….

То есть, начиная с n = 4, мы получаем последовательность {G_k}, где

G_k = 3 + S_k, (S_k сумма первых k четных чисел). А последовательность четных чисел – это арифметическая прогрессия с первым членом 2 и разностью 2.

Согласно формулы первых членов арифметической прогрессии,

 (проверьте правильность преобразований)

10 000 £ F(n) < 100 000

10 000 £ 3 + k×(k + 1) < 100 000

99 997 £ k×(k +1) < 999 997

А вот здесь соответствующие квадратичные неравенства решать не следует. Очень неудобно и долго. Лучше подобрать нужные значения k.

k×(k +1) ≥ 99 997

Очевидно, что 100 × 101 = 10 100, а 99 × 100 = 9 900. Следовательно, k ≥ 100.

Подбор нужного k для решения неравенства k×(k +1) < 999 997 продемонстрирован на рисунке 2. Получается, что k £ 315.

Рисунок 2. Подбор решения неравенства с помощью MS EXCEL

Итак, 100 £  k £ 315. Это неравенство имеет 315 – 100 + 1 = 216 целых решений.

Ответ: 216

№ 3466. (Е. Джобс) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n + 1 при n < 3
F(n) = n + 2·F(n+2), если n ≥ 3 и чётно,
F(n) = F(n–2) + n - 2, если n ≥ 3 и нечётно.

Сколько существует чисел n, для которых значение F(n) определено и будет трехзначным?

Замечание. В принципе, тут можно составить программу для расчета. Можно воспользоваться MS Excel (значения аргументов и диапазон значений F(n) не такие большие, как в предыдущей задаче). Но, мне кажется, в данном случае все равно лучше решить задачу аналитически: меньше вероятность ошибки.

Ответ: 22

7. Еще немного математики*

№ 3469. (Е. Джобс) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при n = 0
F(n) = 2·F(1-n) + 3·F(n-1) + 2, если n > 0,
F(n) = - F(-n), если n < 0.

Чему равна сумма цифр значения F(50)?

Решение.

Конечно, прежде всего мы попробуем написать программу, в которой описывается рекурсивная функция F, а в теле программы – единственный оператор: writeln(F(50); Сумму цифр получившегося числа дешевле посчитать вручную.

Как вы уже догадались, программа начнет работать, но результата ее работы мы не дождемся.

Посмотрим на функцию глазами математика. Заметим:

·         если n = 1, то 1 – n = n – 1 = 0, и F(1) = 7

·         если n > 1, то 1 – n  < 0 и 1 – n = – ( n – 1). Поэтому F(1 – n) = – F(n – 1)

n – 1 > 0 Þ 2·F(1– n) + 3·F(n – 1) + 2 = –2·F(n –1) + 3·F(n – 1) + 2 = F(n – 1) + 2

В результате вместо данной функции можно задать эквивалентную ей:

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

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

F(n) = F(n-1) + 2, если n > 1

А вот теперь пишите программу.

Ответ: 6

8. Функции двух переменных*

№ 3145.  (Д.Ф. Муфаззалов) Определите количество различных значений n таких, что n и m – натуральные числа, а значение F(n, m) равно числу 30.

Паскаль	C++
function F(n, m:  integer): integer; begin  if m == 0 then    F:= 0  else    F:= n + F(n,m-1) end;	int F(int n, int m) { if( m == 0 )   return 0; else   return n+F(n,m-1); }

Решение.

program N_3145_P;

var k, i, j:integer;

function f(n,m: integer): integer;

begin

  if m=0 then f:= 0

  else f:= n + f(n,m-1)

end;

begin

  k := 0;

  for i:= 1 to 50 do

    for j:=1 to 50 do

     begin

      writeln ('f(',i,',',j,')=',f(i,j));[3]

      if f(i,j)=30 then k:=k+1

     end;

  writeln;

  writeln(k);

end.

Ответ: 8

(№ 3143) (Д.Ф. Муфаззалов) Определите количество различных значений n таких, что n и m – натуральные числа, находящиеся в диапазоне [100; 1000], а значение F(n, m) равно числу 30.

Паскаль	C++
function F(n,m: integer): integer; begin  if m = 0 then    F:= n  else    F:= F(m, n mod m) end;	int F(int n; int m) { if( m == 0 )   return n; else   return F(m, n%m); }

Ответ: 30

№ 3140. (Д.Ф. Муфаззалов) Определите наименьшее значение n такое, что последнее выведенное число при вызове F(n) будет больше числа 32. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующее значение F(n).

Паскаль	C++
function F(n:integer): integer; var d:integer; begin  writeln(N);  if n > 0 then begin    d := n mod 10+ F(n div 10);    writeln(d);    F := d  end  else F:= 0; end;	int F(int n) { cout << n << endl; if (n){   int d = n % 10           + F(n/10);     cout << d << endl;   return d;   } else return 0; }

Ответ: 30

6999 33

9. Рекурсивные процедуры*

Процедуры, как и функции, являются вспомогательными алгоритмами. Отличия процедур от функций следующие.

-        В любом языке программирования процедура просто выполняет последовательность операторов (принимая входные значения, или не принимая), а функция возвращает значение, которое можно присвоить переменной;

-        Различен синтаксис описания процедур и функций.

-        Различен способ вызова процедур и функций в теле основной программы.

Чтобы представить себе, как работает рекурсивная процедура, рассмотрим пример.

Пример. Ниже за­пи­сан ре­кур­сив­ный ал­го­ритм F.

Пас­каль	Си
procedure F(n: integer); begin    writeln(n);      if n < 5 then        begin          F(n + 1);          F(n + 3)       end end	void F(int n) {     printf("%d\n", n);       if (n < 5) {              F(n + 1);              F(n + 3);    } }

Чему равна сумма всех чисел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(1)?

Решение:

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

F(1) выполнит следующие действия: Вывод числа 1, вызов F(2), вызов F(4)

F(2) выполнит следующие действия: Вывод числа 2, вызов F(3), вызов F(5)

F(4) выполнит следующие действия: Вывод числа 4, вызов F(5), вызов F(7)

F(3) выполнит следующие действия: Вывод числа 3, вызов F(4), вызов F(6)

F(5) выполнит следующие действия: Вывод числа 5

F(5) выполнит следующие действия: Вывод числа 5

F(7) выполнит следующие действия: Вывод числа 7

F(4) выполнит следующие действия: Вывод числа 4, вызов F(5), вызов F(7)

F(6) выполнит следующие действия: Вывод числа 6

F(5) выполнит следующие действия: Вывод числа 5

F(7) выполнит следующие действия: Вывод числа 7

Просуммируем все числа, выведенные на экран: 1+2+4+3+5+5+7+4+6+5+7 = 49

Ответ: 49

№ 3137. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 3200000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

Паскаль	C++
procedure F(n: integer); begin   writeln(n*n);   if n > 1 then begin     writeln(2*n+1);     F(n-2);     F(n div 3);   end; end;	void F( int n ) {   cout << n*n << endl;   if( n > 1 ) {     cout << 2*n+1 << endl;     F(n-2);     F(n/3);     } }

Конечно, вручную искать ответ на поставленный вопрос мы будем долго. Как же нам может помочь владение информационными технологиями?

Опыт 1. Напишем такую программу.

program N_3137_P_1;

 

begin

  F(40)

end.

Запустим программу на выполнение. Получим:

Как же нам найти сумму выведенных чисел?

Есть вариант выделить весь столбик полученных чисел (Установите курсор перед самым первым числом, нажмите сочетание клавиш CTRL+SHIFT+END, и у вас выделятся все числа в окне вывода). Затем копируете их в буфер обмена (CTRL+С), вызываете MS EXCEL, делаете текущей ячейку А1. С помощью сочетания клавиш CTRL+V заносите получившиеся числа в ячейки и, не снимая выделения, применяете автосумму. Всего-то у нас получается 16 171. Тяжело будет подбирать. Долго.

Опыт 2. Попробуем добавить автоматизации в расчетах:

1.      Изменим процедуру процедуру таким образом, чтобы вывод осуществлялся не на экран, а в текстовый файл.

2.      Будем читать числа, записанные в файле и находить их сумму.

Теоретический материал, достаточный для выполнения данной задачи, изложен в § 68 [4].

Итак, текст программы:

var fin:text;

    a, s: integer;

procedure F(n: integer);

begin

  writeln(fin,n*n);              //Вывод в файл

  if n > 1 then begin

    writeln(fin,2*n+1);          //Вывод в файл

    F(n-2);

    F(n div 3);

  end;

end;

begin

  //Вызов процедуры и запись результатов ее работы в файл

  assign(fin, 't.txt');

  rewrite(fin);

  f(40);

  close(fin);

  //Чтение чисел из файла и нахождение их суммы

  reset(fin);

  s:=0;

  while not EOF(fin) do

   begin

     readln(fin, a);

     s:=s+a;

   end;

  close(fin);

  //Вывод суммы на экран

  writeln(s);  

end.

Запустите программу на выполнение, убедитесь, что получилось то же самое число 16 171. Откройте файл t.txt с помощью программы Блокнот и посмотрите его содержимое.

Теперь подбор осуществить будет легче. Предлагаю действовать по принципу бинарного поиска.

f(40) = 16171 – мало!

f(100) = ?

f(200) = ?

f(150) = ?

f(175) = ?

и т.д.

Возможно, еще что-то можно придумать, чтобы усилить автоматизацию решения задачи. Дерзайте!!!

Ответ: 199  3238315

№ 3135. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 5000000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

Паскаль	C++
procedure F(n: integer); begin   writeln(2*n+1);   if n > 1 then begin     writeln(3*n-8);     F(n-1);     F(n-4);   end; end;	void F( int n ) {   cout << 2*n+1 << endl;   if( n > 1 ) {     cout << 3*n-8          << endl;     F(n-1);     F(n-4);     } }

Ответ: 40 6791973

№ 3133. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 1000000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

Паскаль	C++
procedure F(n: integer); begin   writeln(n+1);   if n > 1 then begin     writeln(n+5);     F(n-1);     F(n-2);   end; end;	void F( int n ) {   cout << n+1 << endl;   if( n > 1 ) {     cout << n+5 << endl;     F(n-1);     F(n-2);     } }

Ответ: 24 1114369

№ 3132. Определите, сколько символов * выведет эта процедура при вызове F(140):

Паскаль	C++
procedure F( n: integer ); begin   write('*');   if n >= 1 then begin     write('*');     F(n-1);     F(n div 2);   end; end;	void F( int n ) {   cout << '*';   if( n >= 1 ) {     cout << '*';     F(n-1);     F(n/2);     } }

Решение. Идея та же. Только вот звездочки в файл будут записываться не одна под другой, а подряд.

Текст программы.

program N_3131;

var fin:text;

    s: integer;

    a: string;

procedure F( n: integer );

begin

  write(fin,'*');

  if n >= 1 then begin

    write(fin,'*');

    F(n-1);

    F(n div 2);

  end;

end;

begin

 //Вызов процедуры и запись результатов ее работы в файл

  assign(fin, 't.txt');

  rewrite(fin);

  f(140);

  close(fin);

  //Чтение чисел из файла и нахождение их суммы

  reset(fin);

  s:=0;

  while not EOF(fin) do

   begin

     readln(fin, a);    //читаем из файла сразу целую строку звездочек

     s:=s+length(a);  //стандартная функция length(a) вычисляет длину
                         строки, в нашем случае – количество звездочек в строке

   end;

  close(fin);

  //Вывод суммы на экран

  writeln(s);  

 end.

Ответ: 3279892

№ 3130. Определите, сколько символов * выведет эта процедура при вызове F(40):

Паскаль	C++
procedure F( n: integer ); begin   write('*');   if n >= 1 then begin     write('*');     F(n-1);     F(n-3);     write('*');   end; end;	void F( int n ) {   cout << '*';   if( n >= 1 ) {     cout << '*';     F(n-1);     F(n-3);     cout << '*';     } }

Ответ: 22947841

Используемая литература

1.      ЕГЭ. Информатика и ИКТ : типовые экзаменационные варианты : 20 вариантов / С.С. Крылов, Т.Е. Чуркина. – М. : Издательство «Национальное образование», 2021. – 256 с. – (ЕГЭ, ФИПИ – школе).

2.      Семакин И.Г. Информатика. Базовый уровень : учебник для 10 класса  / И.Г. Семакин,
Е.К. Хеннер, Т.Ю. Шеина. – М. : БИНОМ. Лаборатория знаний, 2018. – 264 с.

3.      Поляков К.Ю. Информатика. 10 класс. Углубленный уровень : в 2 ч. Ч. 1 / К.Ю. Поляков,
Е.А. Еремин.  – М. : БИНОМ. Лаборатория знаний, 2019. – 344 с.

4.      Поляков К.Ю. Информатика. 10 класс. Углубленный уровень : в 2 ч. Ч. 2 / К.Ю. Поляков,
Е.А. Еремин.  – М. : БИНОМ. Лаборатория знаний, 2019. – 304 с.

---

[1] Обратите внимание! В теле функции обязательно должен быть оператор Имя функции := значение;

K_6:=k; - это именно такой оператор. При описании рекурсивных функций фактически все тело функции состояло из оператора Имя функции := значение;

[2] Методы, применяемые при решении данной задачи, аналогичны методам, применяемым при решении задач № 6 КИМ КЕГЭ.

[3] Эта команда нужна, чтобы определиться с верхними границами изменения параметров циклов. Обсудите данный вопрос с преподавателем.

Краткое описание документа:

В методической разработке дан необходимый теоретический материал и примеры решения заданий КИМ 16 КЕГЭ. В основном, рассмотрены задачи с сайта К.Е. Полякова. Задачи сгруппированы по типам и приведены в порядке возрастания сложности. Для организации самопроверки приведены ответы к каждой задаче.