1. Прибавь 1,

2. Умножь на 2.

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

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

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

Ответ: ___________________________.

РЕШЕНИЕ 1

Число 23 не делится на 2, поэтому все программы будут заканчиваться командой 1.

Разные варианты программ получаются за счет разных последовательностей вычисления значений, кратных 2. Например, 6 из 3 получается либо программой 111, либо командой 2.

Рассмотрим сначала, какими способами из 3 можно получить небольшое число, например, 10. Изобразим последовательности команд на графе, обозначив команду +1 знаком «–», а команду *2 знаком «|».

3	–	4	–	5	–	62	–	72	–	82+1=3	–	93	–	104
						|				|				|
						3				4				5

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

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

3	–	62	–	83	–	104	–	124+2=6	–	146+2=8	–	168+3=11	–	1814	–
		|		|		|		|		|		|		|
		3		4		5		62		72		83		93
	–	2018	–	2222	–	2322
		|		|
		104		114

Ответ: 22

РЕШЕНИЕ 2

Пусть T(n) – число программ, с помощью которых можно получить значение n из числа 3. Очевидно, T(3) = 0; T(4) = T(5) = 1. Число 6 можно получить уже двумя способами за счет использования команды умножь на 2.

Заметим, что для нечетных значений n>6 выполняется равенство T(n) = T(n-1), поскольку от n-1 до n в программах можно добраться только с помощью команды прибавь 1.

Если n>6 четное, то появляются дополнительные варианты программ, основанные на том, что до значения n можно добраться и командой умножь на 2. Следовательно, будет выполняться равенство

T(n) = T(n-1) + T(n div 2)

Мы получили рекуррентное соотношение, которое позволит вычислить число нужных нам программ для n = 23.

C(7) =  C(6) = 2;

C(8) =  C(7) + C(4) = 3;

C(9) =  C(8) = 3;

C(10) =  C(9) + C(5) = 4;

C(11) =  C(10) = 4;

C(12) =  C(11) + C(6) = 6;

C(13) =  C(12) = 6;

C(14) =  C(13) + C(7) = 8;

C(15) =  C(14) = 8;

C(16) =  C(15) + C(8) = 11;

C(17) =  C(16) = 11;

C(18) =  C(17) + C(9) = 14;

C(19) =  C(18) = 14;

C(20) =  C(19) + C(10) = 18;

C(21) =  C(20) = 18;

C(22) =  C(21) + C(11) = 22;

C(23) =  C(22) = 22.

Ответ: 22

В14 (6 мин)

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

Бейсик	Паскаль
DIM A, B, T, M, R AS INTEGER A = -20: B = 20 M = A: R = F(A) FOR T = A TO B IF F(T) < R THEN M = T R = F(T) END IF NEXT T PRINT M FUNCTION F (x) F = 3 * (x - 8) * (x - 8) END FUNCTION	var a,b,t,M,R :integer; Function F(x:integer):integer; begin F := 3*(x-8)*(x-8); 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; write(M); END.
Си	Алгоритмический язык
int F(int x) { return 3*(x-8)*(x-8); } void main() { int a, b, t, M, R; a = -20; b = 20; M = a; R = F(a); for (t=a; t<=b; t++){ if ( F(t)<R ) { M = t; R = F(t); } } printf("%d", M); }	алг нач цел a, b, t, M, R a := -20; b := 20 M := a; R:= F(a) нц для t от a до b если F(t)< R то M := t; R := F(t) все кц вывод M кон алг цел F(цел x) нач знач := 3*(x-8)*(x-8) кон

Ответ: ___________________________.

РЕШЕНИЕ

Любой алгоритм может быть представлен как основная программа со вспомогательными алгоритмами.

Вспомогательный алгоритм оформляется в виде ПРОЦЕДУРЫ или ФУНКЦИИ. Он может располагаться в одном файле с основной программой или в отдельном файле.

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

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

Для передачи информации из основной программы в процедуру или функцию и для возвращения результатов в основную программу используются ПАРАМЕТРЫ.

Переменные, которые описываются в заголовке вспомогательного алгоритма, называются ФОРМАЛЬНЫМИ параметрами. Переменные, которые указываются при вызове вспомогательного алгоритма, называются ФАКТИЧЕСКИМИ параметрами. Фактические параметры – это переменные, описанные в основной программе.

В задании используется вспомогательный алгоритм – функция. Ее имя F, один параметр x. Функция получает на вход значение (оно обозначено формальным параметром x) и вычисляет величину F = 3*(x-8)*(x-8). Это запись квадратичной зависимости результата от входной величины.

В основной программе обращение к этой функции выполняется однократно в операторе R := F(a) и многократно в цикле в операторе R := F(t).

При каждом обращении к функции происходит замена формального параметра на фактический параметр, и, таким образом, вычисления производятся с использованием конкретных значений. Например, в операторе R := F(a) будет вычислено значение функции 3 * (–20 – 8) * (–20 – 8).

Значения, вычисляемые в цикле в операторе R := F(t), будут разными, поскольку изменяется значение фактического параметра t. Переменная t является параметром цикла for с границами от –20 до 20. На рисунке показаны некоторые точки графика заданной квадратичной зависимости:

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

M	t	F(t)	R	F(t) < R
–20			F(–20)
	–20	F(–20)		нет
	–19	F(–19)		да
–19			F(–19)
	–18	F(–18)		да
–18			F(–18)
Условие F(t) < R станет ложным, когда функция начнет возрастать. Минимум функции в точке 8.
			F(7)
	8	F(8)		да
8			F(8)
	9	F(9)		нет

Ответ: 8

C1 (30мин)

Требовалось написать программу, при выполнении которой с клавиатуры считывается координата точки на прямой (x – действительное число) и определяется принадлежность этой точки одному из выделенных отрезков B и D (включая границы). Программист торопился и написал программу неправильно.

Бейсик	Паскаль
INPUT x IF x >= -3 THEN IF x <= 9 THEN IF x>1 THEN PRINT "не принадлежит" ELSE PRINT "принадлежит" ENDIF ENDIF ENDIF END	var x: real; begin readln(x); if x>= -3 then if x<= 9 then if x>1 then write('не принадлежит') else write('принадлежит') end.
Си	Алгоритмический язык
void main(void){ float x; scanf("% f ",&x); if (x>= -3) if (x<= 9) if (x>1) printf("не принадлежит"); else printf("принадлежит"); }	алг нач вещ x ввод x если x>= -3 то если x>= 9 то если x>1 то вывод 'не принадлежит' иначе вывод 'принадлежит' все все все кон

Последовательно выполните следующее.

1. Перерисуйте и заполните таблицу, которая показывает, как работает программа при аргументах, принадлежащих различным областям (A, B, C, D и E). Границы (точки –3, 1, 5 и 9) принадлежат заштрихованным областям (B и D соответственно).

Область	Условие 1 (x >= -3)	Условие 2 (x <= 9)	Условие 3 (x > 1)	Программа выведет	Область обрабатывается верно
A
B
C
D
E

В столбцах условий укажите "Да", если условие выполнится; "Нет" если условие не выполнится; "—" (прочерк), если условие не будет проверяться; «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце "Программа выведет" укажите, что программа выведет на экран. Если программа ничего не выводит, напишите "—" (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв». В последнем столбце укажите "Да" или "Нет".

2. Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

РЕШЕНИЕ

1. Заполнение таблицы предполагает выполнение программы в уме для точек, принадлежащих каждой отдельной области. Задано 5 областей, значит, нужно «выполнить» программу для 5 точек.

Область	Условие 1 (x >= -3)	Условие 2 (x <= 9)	Условие 3 (x > 1)	Программа выведет	Область обрабатывается верно
A	Нет	–	–	–	Нет
B	Да	Да	Нет	принадлежит	Да
C	Да	Да	Да	не принадлежит	Да
D	Да	Да	Да	не принадлежит	Нет
E	Да	Нет	–	–	Нет

2. Лучший способ доработки программы – написать ее заново самостоятельно. Области на числовой оси лучше проверять последовательно от меньших значений к большим.

Один из вариантов правильной программы:

var x: real;

begin

readln(x);

if ((x>= -3) and (x<=1)) or ((x>=5) and (x<=9)) then

write('принадлежит')

else write('не принадлежит')

end.