Задачи на рекурсию

  • Контроль знаний
  • docx
  • 11.05.2020
Публикация в СМИ для учителей

Публикация в СМИ для учителей

Бесплатное участие. Свидетельство СМИ сразу.
Мгновенные 10 документов в портфолио.

Подборка заданий по теме "Рекурсия" для сдающих ЕГЭ по информатике
Иконка файла материала Самостоятельная работа по теме Рекурсии.docx

 

 

 

 

 

 

 

 

Самостоятельная работа

по теме «Рекурсии»

 

 

 

 

для учащихся 10-11 классов,

планирующих сдавать ЕГЭ по информатике

 

 

 

 

 

 

 

 


 

Вариант 1

1)        Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+2);

   F(n+3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

 

2)  Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 20:

var i, k: integer;

function F(x:integer):integer;

begin

  if x < 3 then

       F:= 1

  else F:= F(x-1) + F(x-2);

end;

begin

  i := 21;

  readln(K);

  while (i > 0) and (F(i) > K) do

    i:=i-1;

  writeln(i); 

end.

 

3) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 1,5

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число

в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 1 преобразуют в число 20?

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

F(1) = 1

F(n) = F(n–1) * (n + 1), при n > 1

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

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n > 2 then

    F := F(n - 1) + F(n - 2)

  else

    F := n;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)?

 


 

Вариант 2

1) Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 7 then begin

   writeln(n);

   F(n+1);

   F(n+2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2).

 

2) Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 30:

var i, k: integer;

function F(x:integer):integer;

begin

  if x < 3 then

       F:= 1

  else F:= 2*F(x-1) + F(x-2);

end;

begin

  i := 15;

  readln(K);

  while (i > 0) and (F(i) > K) do

    i:=i-1;

  writeln(i); 

end.

3) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 1,5

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число

в 1,5 раза, если число чётное. К нечётным числам вторая команда неприменима. Сколько есть программ, которые число 2 преобразуют в число 22?

 

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

F(1) = 1

F(n) = F(n–1) * (n + 2), при n > 1

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

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n > 3 then

    F:= F(n - 1) * F(n - 2)

  else

    F:= n;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?

 

 


 

Вариант 3

1) Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+1);

   F(n+2);

   F(n*2)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

 

2) Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 36:

var i, k: integer;

function F(x:integer):integer;

begin

  if x < 2 then

       F:= 1

  else F:= F(x-1) + 2*F(x-2);

end;

begin

  i := 28;

  readln(K);

  while (i > 0) and (F(i) > K) do

    i:=i-1;

  writeln(i); 

end.

 

3)  У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. сделай чётное

3. сделай нечётное

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16?

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

F(1) = 1

F(n) = F(n–1) * (2*n + 1), при n > 1

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

 

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n >= 3 then

    F:= F(n-3) + F(n-2)*F(n-1)

  else

    F:= n;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(7)?


 

Вариант 4

1)  Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+1);

   F(n*2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(2).

 

2) Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 45:

var i, k: integer;

function F(x:integer):integer;

begin

  if x < 2 then

       F:= 1

  else F:= 2*F(x-1) + F(x-2);

end;

begin

  i := 0;

  readln(K);

  while F(i) < K do

    i:=i+1;

  writeln(i); 

end.

3) У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. сделай чётное

3. сделай нечётное

4. умножь на 10

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1, четвертая умножает на 10. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 15?

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

F(1) = 1

F(n) = F(n–1) * (2*n - 1), при n > 1

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

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n < 5 then

    F:= F(n+2) + F(n+3) + F(n+1)

  else

    F:= n;

end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(2)?


 

Вариант 5

1) Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 7 then begin

   writeln(n);

   F(n+2);

   F(n*2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

 

2) Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 120:

var i, k: integer;

function F(x:integer):integer;

begin

  if x < 1 then

       F:= 1

  else F:= F(x-1) +3*F(x-2);

end;

begin

  i := 0;

  readln(K);

  while F(i) < K do

    i:=i+1;

  writeln(i); 

end.

3) У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. сделай чётное

3. сделай нечётное

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 3 преобразуют в число 18?

 

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

F(1) = 1

F(n) = F(n–1) * (3*n - 2), при n > 1

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

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n < 5 then

    F:= F(n*3) + F(n+3) + F(n+1)

  else

    F:= n div 2;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(2)?


 

Вариант 6

1) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n > 1 then

    F:= 2*n + F(n-3) + F(n-2)

  else

  F:= n + 5;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?

 

2) При каком наименьшем значении входной переменной k программа выдаёт тот же ответ, что и при входном значении k = 90?

var k, i : longint;

function f(n: longint) : longint;

begin

  f := n * n * n - 30

end;

begin

  readln(k);

  i := 12;

  while (i>0) and (f(i)> k) do

    i := i-1;

  writeln(i)

end.

 

3) У исполнителя Калькулятор три команды, которым присвоены номера:

1. прибавь 1

2. прибавь 4

3. прибавь 5

Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 30 преобразуют в число 46?

 

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

F(0) = 1, F(1) = 1

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

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

 

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n < 5 then

    F:= F(n+3) + F(2*n) + F(3*n div 2)

  else

    F:= n + 2;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?

 

 

 

 

 

 

 

Вариант 7

1)    Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

  writeln(n);

  if n < 5 then begin

    F(n + 1);

    F(n + 3)

  end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

 

2) Напишите в ответе число различных значений входной переменной k, при которых программа выдаёт тот же ответ, что и при входном значении k = 35. Значение k = 35 также включается в подсчёт различных значений k.

var k, i : longint;

function F(x: longint) : longint;

begin

  F:=2*x*x+3*x+2

end;

begin

  i := 15;

  readln(K);

  while (i> 0) and (F(i) > K) do

    i:=i-1;

  writeln(i)

end.

 

3) Исполнитель преобразует число, записанное на экране. У исполнителя

три команды, которым присвоены номера:

1. прибавь 1

2. прибавь 2

3. прибавь 4

Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 2, а третья – на 4. Программа для исполнителя – это последовательность команд. Сколько есть программ, которые число 21 преобразуют в число 30?

 

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

F(1) = 1; G(1) = 1;

F(n) = F(n – 1) – G(n – 1),

G(n) = F(n–1) + G(n – 1), при n >=2

Чему равно значение величины F(5)/G(5)?

В ответе запишите только целое число.

 

5) Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n > 3 then

    F:= F(n - 1) * F(n - 2)

  else

    F:= n;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?

Вариант 8

1)     Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   F(n+2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

 

2)   Напишите в ответе число различных значений входной переменной k, при которых программа выдаёт тот же ответ, что и при входном значении k = 64. Значение k = 64 также включается в подсчёт различных значений k.

var k, i : longint;

function f(n: longint) : longint;

begin

  f := n * n

end;

begin

  readln(k);

  i := 12;

  while (i>0) and (f(i)>=k) do

    i := i-1;

  writeln(i)

end.

 

3) У исполнителя Утроитель две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 3

Первая из них увеличивает число на экране на 1, вторая – утраивает его.

Программа для Утроителя – это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 20?

 

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

задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * n, при n > 1

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

В ответе запишите только целое число.

 

5)     Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n > 2 then

    F := F(n - 1) + F(n - 2)

  else

    F := n;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)?

 


 

Вариант 9

1)     Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

 writeln('*');

 if n > 0 then begin

   F(n-2);

   F(n div 2)

 end

end;

 Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?

 

2) Определите, количество чисел K, для которых следующая программа выведет такой же результат, что и для K = 24:

var i, k: integer;

function F(x:integer):integer;

begin

  F:=x*x*x;

end;

begin

  i := 12;

  readln(K);

  while (i>0) and (F(i) > K) do

    i:=i-1;

  writeln(i); 

end.

 

3) У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

Сколько есть программ, которые число 1 преобразуют в число 16?  

 

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

F(0) = 1, F(1) = 1

F(n) = 2*F(n–1) + F(n-2), при n > 1

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

 

5)     Дан рекурсивный алгоритм:

function F(n: integer): integer;

begin

  if n < 6 then

    F:= n+F(n+3) * F(2*n)

  else  

    F:= n*2;

end;

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?


 

 

Ответы

Варианты


Задания

1

2

3

4

5

6

7

8

9

1

60

425

530

169

426

56

49

79

21

2

8

24

22

58

120

34

17

15

19

3

32

44

40

84

30

301

96

12

36

4

360

840

315

945

280

21

1

120

99

5

8

108

749

52

23

43

108

8

147

 

 


Примечание

При составлении вариантов использовались задания с сайта Константина Полякова http://kpolyakov.spb.ru/school/ege.htm


 

Скачано с www.znanio.ru