РЕШУ ЕГЭ — информатика

Задания

Тип 23 № 7210 Добавить в вариант

Источник: ЕГЭ по информатике 05.05.2014. Досрочная волна. Вариант 1

Раздел кодификатора ФИПИ: 1.6.2 Вычислимость. Эквивалентность алгоритмических моделей

Оператор присваивания и ветвления. Перебор вариантов, построение дерева. Поиск количества программ по заданному числу

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

1.  прибавь 1,

2.  прибавь 10.

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

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

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

Решение. Для сложения справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.

Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 31  — 10  =  21. При этом минимальное количество команд  — 3, т. к. $дробь: числитель: 31 минус 10, знаменатель: 10 конец дроби = дробь: числитель: 21, знаменатель: 10 конец дроби ,$ округляя в большую сторону получаем 3.

Команд может быть 3, 12 или 21. Трём командам соответствует набор 221, 3 варианта расположения. Двенадцати командам  — набор 211111111111, 12 возможных вариантов расположения. Двадцати одной команде  — все единицы, то есть 1 программа. Всего имеем 16 программ.

Ответ: 16.

Приведём решение на языке PascalABC.

var a: array[-10..31] of integer;

i:integer;

begin

for i:=10 to 31 do begin

a[10]:=1;

a[i]:=a[i-1]+a[i-10];

end;

println(a[31]);

end.

Приведём другое решение на языке Python.

def f(x, y):

if x > y:

return 0

if x == y:

return 1

else:

return f(x + 1, y) + f(x + 10, y)

print(f(10, 31))

Ответ: 16

7210

Источник: ЕГЭ по информатике 05.05.2014. Досрочная волна. Вариант 1

Раздел кодификатора ФИПИ: 1.6.2 Вычислимость. Эквивалентность алгоритмических моделей

Ключ

№ п/п	№ задания	Ответ
1	7210	16