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

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

для учащихся 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)?

Ответы

Примечание

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

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