end; в заголовке функции записывают имя функции, в скобках – список параметров, далее через двоеточие – тип возвращаемого значения; в приведенном примере функция F принимает один целый параметр, к которому внутри функции нужно обращаться по имени x , и возвращает целое число " width="640"
Ege 21 ( повышенный уровень, время – 6 мин)
Умение анализировать программу, использующую процедуры и функции
Что нужно знать :
- функция – это вспомогательный алгоритм, который возвращает некоторое значение–результат
- в Паскале функция располагается выше основной программы и оформляется следующим образом (вместо многоточия могут быть любые операторы):
function F ( x : integer ): integer ;
begin
...
F := результат функции
end;
- в заголовке функции записывают имя функции, в скобках – список параметров, далее через двоеточие – тип возвращаемого значения;
- в приведенном примере функция F принимает один целый параметр, к которому внутри функции нужно обращаться по имени x , и возвращает целое число
- результат функции записывается в специальную переменную, имя которой совпадает с именем функции
объявлять эту переменную не нужно
- если параметров несколько, для каждого из них указывают тип:
function F(x: integer; y: integer):integer;
- если несколько соседних параметров имеют одинаковый тип, можно их объединить в список:
function F(x, y: integer):integer;
- следующая программа ищет наименьшее значение функции F(x) на интервале [a,b] , просматривая значения от a до b с шагом 1:
M:=a; R:=F(a);
for t:= a to b do
if F(t) then
begin
R:=F(t); M:=t;
end;
- если функция представляет собой квадратный трехчлен вида
то абсцисса, соответствующая точке минимума , вычисляется по формуле
- если квадратный трехчлен задан в виде
то абсцисса, соответствующая точке минимума , вычисляется по формуле
1 then f := x mod 2 * f ( x div 2 ) else f := x ; end; begin k := 0; readln( a ); for i := 1 to a do if f( i ) =1 then k:=k+1 ; writeln( k ); end. ( x mod 2 ) – младшая цифра двоичного представления числа х в двоичной системе счисления ( x div 2 ) – число х без младшей своей цифры в двоичном представлении т.е. функция находит произведение цифр числа в двоичной СС 4. Программа, в целом, находит количество чисел, произведение цифр в двоичной СС, которых равно 1 , т.е. таких чисел, двоичная запись которых не содержит нулей. " width="640"
Пример I:
Напишите в ответе количество различных значений входной переменной a из интервала от 1 до 100 (включая границы), при которых программа выдаёт тот же ответ, что и при входном значении a = 20 . Значение a = 20 также включается в подсчёт различных значений a .
Решение:
var i, k,a: integer;
function f (x: integer): integer;
begin
if x 1 then
f := x mod 2 * f ( x div 2 )
else
f := x ;
end;
begin
k := 0;
readln( a );
for i := 1 to a do
if f( i ) =1 then k:=k+1 ;
writeln( k );
end.
- ( x mod 2 ) – младшая цифра двоичного представления числа х в двоичной системе счисления
- ( x div 2 ) – число х без младшей своей цифры в двоичном представлении
- т.е. функция находит произведение цифр числа в двоичной СС
4. Программа, в целом, находит количество чисел, произведение цифр в двоичной СС, которых равно 1 , т.е. таких чисел, двоичная запись которых не содержит нулей.
5 . такие числа можно представить, как 2 n -1 , где n – натуральное число.
6. В диапазоне от 1 до 20 таких чисел 4 : 1, 3, 7, 15.
7. А в диапазоне от 1 до 100 – 6 : 1, 3, 7, 15, 31, 63.
Т.е. искомые числа – это числа от 15 до 30 .
Ответ: 16
0 then f := x mod 2 + f(x div 2 ) else f := 0; end; begin k := 0; for i := 0 to 1023 do if f(i mod 32) = 1 then if f(i div 32) = f(i mod 32) then k := k + 1; writeln(k); end. 1. ( x mod 2 ) – младшая цифра двоичного представления числа х в двоичной системе счисления 2. ( x div 2 ) – число х без младшей своей цифры в двоичном представлении 3. ( i mod 32 ) - число, составленное из пяти младших битов двоичной записи числа i 4. ( i div 32 ) – число, составленное из пяти старших битов двоичной записи числа i . 5. т.е. функция считает сумму цифр двоичной записи аргумента " width="640"
Пример II:
Какое число будет напечатано в результате выполнения программы?
Решение:
var i, k: integer;
function f(x: integer): integer;
begin
if x 0 then
f := x mod 2 + f(x div 2 )
else
f := 0;
end;
begin
k := 0;
for i := 0 to 1023 do
if f(i mod 32) = 1 then
if f(i div 32) = f(i mod 32) then
k := k + 1;
writeln(k);
end.
1. ( x mod 2 ) – младшая цифра двоичного представления числа х в двоичной системе счисления
2. ( x div 2 ) – число х без младшей своей цифры в двоичном представлении
3. ( i mod 32 ) - число, составленное из пяти младших битов двоичной записи числа i
4. ( i div 32 ) – число, составленное из пяти старших битов двоичной записи числа i .
5. т.е. функция считает сумму цифр двоичной записи аргумента
6. В основной части программы рассматриваются числа от 1 до 1023 , счетчик увеличивается на 1 , если сумма цифр в младших пяти разрядах двоичного представления числа равна 1 , и сумма цифр в старших пяти разрядах двоичного представления числа тоже равна 1 .
7. Таким образом, необходимо найти количество чисел , в двоичной записи которых в младших пяти разрядах и в старших пяти разрядах находится ровно по одной единице.
8. Дополняя двоичное представление чисел до 10 битов, получим, что старшая единица может располагаться на 5 позициях
9. в каждом таком случае младшая единица может тоже располагаться на пяти позициях.
10. Тогда количество таких чисел равно 5*5=25.
Ответ: 25
Пример III:
Сколько существует таких четырехзначных натуральных чисел, что при вводе их программа выведет такое же число, что и при вводе числа 1133 . Значение 1133 также включается в подсчёт.
Решение:
function f (x: integer): integer;
begin
if x mod 2 =1 then
f := x mod 10 + f ( x div 10 )
else
f := 0;
end;
var n: integer;
begin
readln(n);
writeln( f (n));
end.
- заметим, что функция рекурсивная
остаток от деления х на 2
- Если на вход функции подается число, младшая цифра которого четная, то функция возвращает 0, иначе она возвращает сумму этой цифры и значения функции от аргумента без последней цифры
число х без последней своей цифры
- т.е. функция f возвращает сумму первой непрерывной последовательности нечетных цифр числа х , начиная с младшей
4. Для входного числа 1133 значение функции равно 8
5. Найдем в требуемом диапазоне числа, у которых сумма непрерывной последовательности нечетных цифр, начиная с младшей, равна 8 .
- Сумма состоит не более, чем из четырех слагаемых.
Покажем, что при разложении числа 8 на нечетные слагаемые могут возникнуть суммы только из двух или четырех цифр:
- Если сложить три нечетных числа, то и сумма будет нечетной, а единственное нечетное число не может быть равным 8 .
6. Сначала найдем разложение числа 8 на сумму четырех нечетных цифр: 8=1+1+3+3 . Количество чисел, состоящих из этих цифр, равно 6 .
- используем формулу для вычисления числа перестановок с повторениями ; для двух разных символов она выглядит так:
– количество букв А,
– количество «*»
7. Другое разложение: 8=5+1+1+1 ; количество чисел, составленных из этих цифр, равно 4 .
8 . Далее, найдем разложения числа 8 на два нечетны х слагаемых: 8=5+3 и 8=7+1
- Старшая цифра в искомых числах может принимать 9 значений (от 1 до 9 ), вторая цифра – любое четное значение ( 5 штук)
9 . Таким образом, количество чисел с последовательностью нечетных цифр, начиная с младшей, длиной 2 и суммой 8 есть 9*5*2*2=180
10 . Общее количество чисел, удовлетворяющих условию:
6+4+180=190
Ответ: 190
Пример IV:
Напишите в ответе наименьшее значение входной переменной k , при котором программа выдаёт тот же ответ, что и при входном значении k = 10 .
Решение:
var k, i : longint;
function f (n: longint): longint;
begin
f := n*n*n;
end;
function g (n: longint): longint;
begin
g := 2*n + 3;
end;
begin
readln( k );
i := 1;
while f ( i ) g ( k ) do
i := i +1;
writeln( i )
end.
1. заметим, что функция f возвращает куб переданного ей числа, а функция g – результат вычисления 2*n+3
2. при некотором i работа цикла останавливается: это происходит при нарушении условия
f (i) g (k) , то есть при выполнении обратного условия f (i) g (k)
3. на предыдущем шаге цикла (для i-1 ) условие его работы выполнялось, то есть
f (i-1) g (k) , откуда получаем
f (i-1) g (k) f (i)
4. Так как f (i)=i 3 , делаем вывод, что g (k ) должно быть между кубами двух соседних чисел: (i-1) 3 g (k) i 3
5. для заданного k=10 находим g (10)=2·10+3=23 , так что i=3 :
(2) 3 g (k)=23 3 3
6. осталось проверить, при каких k выполняется условие
8 g (k)=2k+3 27
7 . решая двойное неравенство относительно k получаем
2,5 12
8. таким образом, минимальное целое число, соответствующее условию – 3 .
Ответ: 3
Пример V:
Напишите в ответе число, равное количеству различных значений входной переменной k, при которых приведённая ниже программа выводит тот же ответ, что и при входном значении k = 10 . Значение k = 10 также включается в подсчёт различных значений k .
Решение:
var k, i : longint;
function f (n: longint) : longint;
begin
f := n * n * n ;
end;
begin
readln( k );
i := 1;
while f(i) do
i := i +1;
if f(i)-k then
writeln( i )
else writeln( i-1 );
end.
1. функция f возвращает куб переданного ей числа
2. после ввода k работает цикл, который увеличивает i до тех пор, пока значение куба f(i) не станет больше или равно k
– тогда нарушится условие f(i) и цикл завершится
3. построим таблицу значений функции f(i) (кубов чисел):
i
1
f(i)
Цикл завершается для …
1
2
k=1
3
8
k=2,...,8
27
k=9,...,27
4. таким образом, при k=10 цикл завершится при i=3
5. – в условном операторе:
if f(i)-k k-f(i-1) then
writeln( i )
else writeln( i-1 );
при k=10 и i=3 условие
f(i)-k
27-10
17
неверно , из-за этого выводится на экран не i , а i-1 , то есть 2
6. Тогда нужно найти, сколько значений k дадут на выходе 2
7. условие f(i)-k k-f(i-1) преобразуем к виду
f(i)+f(i-1)
8. тогда при выполнении обратного условия,
2k
k
выводится число i-1 вместо i
9. составим еще одну таблицу:
i
(f(i)+f(i-1))/2
2
Выводится i-1 для …
3
4,5
Выводится i для …
k=2,...,4
17,5
k=5,...,8
k=9,...,17
k=18,...,27
10. в этой задаче подходят числа в диапазоне [ 5;17 ]
всего их 17-5+1 = 13
Ответ: 13
R ) then begin M := t ; R := F (H, t) end end; write( R ) END. 1. величина H передаётся в функцию и влияет на значение функции 2. анализируя программу, можно сделать вывод, что цикл ищет максимум функции F(H,t) на интервале от a до b R 3. график функции – парабола с ветвями, направленными вверх (коэффициент при x 2 = 11 0) a b " width="640"
Пример VI:
Определите, какое значение H нужно ввести, чтобы число, напечатанное в результате выполнения следующего алгоритма, было наименьшим .
Решение:
var a,b,t,M,R,H :integer;
Function F (H, x: integer):integer;
begin
F := 11*(x-H)*(x-H)+13 ;
end;
BEGIN
readln(H);
a := -10; b := 30;
M := a; R := F(H, a);
for t := a to b do begin
if ( F(H, t) R ) then begin
M := t ;
R := F (H, t)
end
end;
write( R )
END.
1. величина H передаётся в функцию и влияет на значение функции
2. анализируя программу, можно сделать вывод, что цикл ищет максимум функции F(H,t) на интервале от a до b
R
3. график функции – парабола с ветвями, направленными вверх (коэффициент при x 2 = 11 0)
a
b
4. вершина параболы находится в точке x = H , ветви идут симметрично влево и вправо вверх
5. при изменении H парабола двигается влево или вправо
6. итак, мы ищем максимальное значение квадратичной функции, и хотим, чтобы это значение было наименьшим
7. Если подвигать параболу в пределах отрезка [ a; b ], то видно, что минимальное значение максимума будет тогда,
когда вершина параболы будет расположена точно в середине отрезка [ a; b ]
R
R
R
a
a
b
a
b
b
8. требуемое значение H равно среднему арифметическому между a = –10 и b = 30 :
Ответ: 10
H = (–10 + 30) / 2 = 10
0 ) and ( F (i) K ) do i:=i-1 ; writeln( i ) end. 1. Вычислим значения функции F при i =0,1,2,3… i=0: f(0)=2 i=1: f(1)=7 i=2: f(2)=16 i=3: f(3)=29 i=4: f(4)=46 2. Заданное значение К=35 попадает в отрезок [ 29;46 ]. всего 45-29+1=17 чисел Ответ: 17 " width="640"
Пример VII:
Напишите в ответе число различных значений входной переменной 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.
1. Вычислим значения функции F при i =0,1,2,3…
i=0: f(0)=2
i=1: f(1)=7
i=2: f(2)=16
i=3: f(3)=29
i=4: f(4)=46
2. Заданное значение К=35 попадает в отрезок [ 29;46 ].
всего 45-29+1=17 чисел
Ответ: 17
0 ) and ( f ( i )= k ) do i:=i-1 ; writeln( i ) end. 1. функция выводит первое натуральное значение i , квадрат которого меньше, чем введённое с клавиатуры значение переменной k 2. при k = 64 программа выведет значение 7 , поскольку это наибольшее натуральное число, квадрат которого меньше, чем 64 3. т.е. нужно ответить на вопрос: сколько есть таких чисел k , которые 8 2 = 64 и 7 2 = 49 в диапазоне [ 50;64 ] всего 64-50+1 = 15 чисел, Ответ: 15 " width="640"
Пример VIII:
Напишите в ответе число различных значений входной переменной 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 ( i0 ) and ( f ( i )= k ) do
i:=i-1 ;
writeln( i )
end.
1. функция выводит первое натуральное значение i , квадрат которого меньше, чем введённое с клавиатуры значение переменной k
2. при k = 64 программа выведет значение 7 , поскольку это наибольшее натуральное число, квадрат которого меньше, чем 64
3. т.е. нужно ответить на вопрос: сколько есть таких чисел k , которые 8 2 = 64 и 7 2 = 49
в диапазоне [ 50;64 ] всего 64-50+1 = 15 чисел,
Ответ: 15
0 ) and ( F(i) K ) do i := i -1; writeln( i ); end. 1. цикл while останавливается, когда переменная i становится равна нулю или значение функции F(i) становится меньше или равно K 2. таким образом, требуется найти количество натуральных чисел в диапазоне [ 1..12 ], куб которых больше, чем K = 24 3. определим, у скольких чисел куб ; это все числа, т.е. только числа 1 и 2; 4. программа выведет 2 – первое число, куб которого 24, при 27-8 = 19 чисел Ответ: 19 " width="640"
Пример IX:
Определите, количество чисел K , для которых следующая программа выведет такой же результат, что и для K = 24 :
Решение:
var i, k: integer;
function F(x:integer):integer;
begin
F:=x*x*x;
end;
begin
i := 12 ;
readln( K );
while ( i0 ) and ( F(i) K ) do
i := i -1;
writeln( i );
end.
1. цикл while останавливается, когда переменная i становится равна нулю или значение функции F(i) становится меньше или равно K
2. таким образом, требуется найти количество натуральных чисел в диапазоне [ 1..12 ], куб которых больше, чем K = 24
3. определим, у скольких чисел куб ;
т.е. только числа 1 и 2;
4. программа выведет 2 – первое число, куб которого 24, при
27-8 = 19 чисел
Ответ: 19
0 ) and ( F(i) K ) do i:=i-1; writeln( i ); end. 1. рекурсивная функция F(x) вычисляет факториал переданного ей числа, то есть произведение x!=1 2 3 ... (x-1) x 2. Как и в предыдущей задаче, определяем, что функция выведет количество нат.чисел, факториалы K 3. выпишем факториалы первых натуральных чисел: 1!=1, 2!=2, 3!=6, 4!=24 , 5!=120, 6!= 720, … при K=24 функция выведет число 4 4. программа выведет именно 4 при всех K, при которых в этот диапазон входит 120-24 = 96 чисел Ответ: 96 " width="640"
Пример X:
Определите, количество чисел K , для которых следующая программа выведет такой же результат, что и для K = 24 :
Решение:
var i, k: integer;
function F(x:integer):longint;
begin
if x = 1 then
F:=1
else F:=x*F(x-1) ;
end;
begin
i := 15;
readln( K );
while ( i0 ) and ( F(i) K ) do
i:=i-1;
writeln( i );
end.
1. рекурсивная функция F(x) вычисляет факториал переданного ей числа, то есть произведение x!=1 2 3 ... (x-1) x
2. Как и в предыдущей задаче, определяем, что функция выведет количество нат.чисел, факториалы K
3. выпишем факториалы первых натуральных чисел:
1!=1, 2!=2, 3!=6, 4!=24 , 5!=120, 6!= 720, …
при K=24 функция выведет число 4
4. программа выведет именно 4 при всех K, при которых
в этот диапазон входит 120-24 = 96 чисел
Ответ: 96
P ) then begin N := N+1 ; end; end; write( N ); END. 1. N – это счётчик точек с целочисленными значениями на отрезке [-25;25 ], в которых значение функции 130 2. график функция 16*(9-x)*(9-x)+127 – парабола с ветвями вверх, мин.значение в точке x = 9 равно 127 3. значение функции при x = 8 и x = 10 (рядом с точкой минимума) равны 16+127 = 143 , поэтому только в одной точке x = 9 не выполняется условие F(t) P 4. всего на интервале [-25;25] есть 51 точка в которых, за исключением одной точки, условие F(t) P выполняется Ответ: 50 " width="640"
Пример XI:
Какое число будет напечатано в результате выполнения программы?
Решение:
var a, b, t, N, P :integer;
Function F(x: integer):integer;
begin
F := 16*(9-x)*(9-x)+127;
end;
BEGIN
a := -25; b := 25;
P := 130;
N := 0;
for t := a to b do begin
if ( F(t) P ) then begin
N := N+1 ;
end;
end;
write( N );
END.
1. N – это счётчик точек с целочисленными значениями на отрезке [-25;25 ], в которых значение функции 130
2. график функция 16*(9-x)*(9-x)+127 – парабола с ветвями вверх,
- мин.значение в точке x = 9 равно 127
3. значение функции при x = 8 и x = 10 (рядом с точкой минимума) равны 16+127 = 143 , поэтому только в одной точке x = 9 не выполняется условие F(t) P
4. всего на интервале [-25;25] есть 51 точка в которых, за исключением одной точки, условие F(t) P выполняется
Ответ: 50
Пример XII:
Какое число будет напечатано в результате выполнения программы?
Решение:
Var a,b,t,M,R:integer;
Function F(x:integer):integer;
begin
F:=(x*x-4)*(x*x-4)+6;
end;
BEGIN
a: =-10; b :=10;
M :=a; R :=F(a);
for t := a to b do begin
if ( F(t) )then begin
M :=t;
R :=F(t);
end;
end;
write( M+6 );
END.
1. цикл ищет миниму м функции F(t) на интервале от a до b , и после выполнения цикла в переменной M оказывается значение аргумента t , при котором функция достигает минимума на заданном интервале ([- 10, 10 ])
2. график функции – парабола с ветвями вверх,
- она имеет два минимума в точках
3. будет найдет первый минимум
4. на экран выводится M+6 , поэтому результат будет (-2)+6=4
Ответ: 4
Пример XIII:
Какое число будет напечатано в результате выполнения программы?
Решение:
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) ) then begin
M :=t;
R: =F(t);
end;
end;
write( M );
END.
1. программа ищет значение t , при котором функция F(t) принимает минимальное значение на интервале от a до b
2. запишем функцию в виде квадратного трёхчлена:
3. найдем абсциссу точки минимума , которая совпадает с абсциссой точки минимума функции
Ответ: 2
Пример XIV:
Какое число будет напечатано в результате выполнения программы?
Решение:
Var a,b,t,M,R:integer;
Function F(x:integer):integer;
begin
F:=4*(x-1)*(x-3);
end;
BEGIN
a :=-20; b :=0;
M :=a; R :=F(a);
for t := a to b do begin
if ( F(t) ) then begin
M :=t;
R: = F (t);
end;
end;
write( M );
END.
- однако это значение не входит в интервал [-20; 0 ], поэтому нужно проверить значения функции на концах отрезка и выбрать из них наименьшее; ответом будет соответствующее значение t .
- при t=-20 получаем F(-20)=4*(-21)*(-23)=1932
- при t=0 получаем F(0)= 4*(-1)*(-3)=12
Ответ: 0
R ) then begin M :=t; R: = F (t); end; end; write( R ); END. 1. программа ищет F(t) наибольшее значение функции на интервале от a до b 2. график заданной функции – это парабола, ветви которой направлены вверх , то есть она имеет точку минимума, но не точку максимума 3. поэтому нужно проверить значения функции на концах отрезка и выбрать из них наибольшее при t=-10 получаем F(t)=68 при t=10 получаем F(t)=148 Ответ: 148 " width="640"
Пример XV:
Какое число будет напечатано в результате выполнения программы?
Решение:
Var a,b,t,M,R:integer;
Function F (x:integer):integer;
begin
F:=x*x+4*x+8;
end;
BEGIN
a :=-10; b :=10;
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( R );
END.
1. программа ищет F(t) наибольшее значение функции на интервале от a до b
2. график заданной функции – это парабола, ветви которой направлены вверх , то есть она имеет точку минимума, но не точку максимума
3. поэтому нужно проверить значения функции на концах отрезка и выбрать из них наибольшее
- при t=-10 получаем F(t)=68
- при t=10 получаем F(t)=148
Ответ: 148
ДЕМО - 2017
Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма
var a, b, N, t: integer;
function F (x: integer):integer;
begin
F := ( x - 16 )*( x + 25 )
end;
begin
a := -100; b := 100;
N := 0;
for t := a to b do
begin
if ( F (t) ) then
N := N + 1
end;
write( N )
end.
F (t)
t [-25;16 ]
N=25+1+16=42
Ответ: 42
16