Прибавь 3,

Вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?

-2

-1

+3

Решение (1 способ, построение полного графа решения):

1) будем строить дерево решений следующим образом: выясним, какое число можно получить из начального значения 1 за 1 шаг:

2)

-2

-1

+3

-3

теперь посмотрим, что удается получить за 2 шага; учитывая, что
(-2+3) = (+3-2), одно из значений повторяется: мы можем получить
-1 + 3 = 2 и 4 – 2 = 2, то есть получается не дерево, а граф. Так с помощью программ, содержащих ровно 2 команды, можно получить 3 различных числа

3)

-2

-1

+3

-3

-5

строим еще уровень: программы из 3-х команд дают 4 разных числа.

Обратим внимание, что числа на каждом уровне отличаются друг от друга на 5 =(+3-(-2), то есть они не могут повторяться

4)

-2

-1

+3

-3

-5

-2

-7

четвертый уровень дает 5 различных чисел:

 

5)

-2

-1

+3

-3

-5

-2

-7

-4

-9

и пятый – 6 решений:

 

6) Ответ: 6.

Решение (2 способ, краткий):

1) как следует из приведенных построений, если система команд исполнителя состоит из двух команд сложения/ вычитания, то все возможные программы, содержащие ровно N команд, дают N+1 различных чисел

2) Ответ: 6.

Решение (3 способ, Л.В. Зенцова, лицей № 36 ОАО "РЖД" г.Иркутска):

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

2) поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки):
11111
11112
11122
11222
12222
22222

3) Ответ: 6.

B14 (повышенный уровень, время – 6 мин)

Тема: Анализ программы с подпрограммами.

Что нужно знать:

· функция – это вспомогательный алгоритм, который возвращает некоторое значение-результат

· в Паскале функция располагается выше основной программы и оформляется следующим образом:

function F(x: integer):integer;

function T(a: integer; b: integer):integer;

function K(i, z: integer):integer;

Begin

...

F:= < результат функции >;

End;

· следующая программа ищет наименьшее значение функции F(x) на интервале [a,b], просматривая значения от a до b с шагом 1:

M:=a; R:=F(a);

for t:=a to b do

if F(t) < R then begin

R:=F(t); M:=t;

End;

· если функция представляет собой квадратный трехчлен вида , то абсцисса, соответствующая точке минимума, вычисляется по формуле

этот результат можно получить (вывести, если забыли), например, так:

§ в критической точке (точке минимума, точке максимума или точке перегиба) производная функции обращается в 0;

§ находим производную

§ приравниваем ее к нулю: .

· если квадратный трехчлен задан в виде , то абсцисса, соответствующая точке минимума, вычисляется по формуле

Пример задания:

Определите, какое число будет напечатано в результате выполнения следующего алгоритма:

Var a,b,t,M,R:integer;

Function F(x:integer):integer;

Begin

F:=4*(x-1)*(x-3);

End;

BEGIN

a:=-20; b:=20;

M:=a; R:=F(a);

for t:=a to b do begin

if (F(t)<R)then begin

M:=t;

R:=F(t);

End;

End;