Погода
Календарь
Март 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123
45678910
11121314151617
18192021222324
25262728293031
Страницы сайта

Анализ программ с циклами и подпрограммами.

Для решения необходимо повторить следующие темы:

  • использование функций в качестве подпрограмм;
  • ниже представлен пример программы для поиска наименьшего значения функции 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;
  • если функция имеет вид F(x) = ax2 + bx + c, то абсцисса (x), соответствующая точке минимума, вычисляется по следующей формуле:
  • если квадратное уравнение задано таким образом: F(x) = a(x-p)(x-q), то абсцисса, соответствующая точке минимума, вычисляется по формуле:

Графики функций

  • при a>0 ветви параболы направлены вверх, при a<0 ветви параболы направлены вниз:
ветви параболы

  • вершина параболы вычисляется по формуле:

Решение заданий

Задание 1. Напишите в ответе количество различных значений входной переменной 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.

Решение:

  1. Рассмотрим, как работает функция, приведенная в программе. Заметим, что (x mod 2) – младшая цифра двоичного представления числа х в двоичной системе счисления, (x div 2) – число х без младшей своей цифры в двоичном представлении.
  2. Таким образом, функция находит произведение цифр числа в двоичном представлении. Программа в целом находит количество чисел, произведение цифр в двоичной записи которых равно 1, то есть таких чисел, двоичная запись которых не содержит нулей.
  3. В общем виде такие числа можно представить, как 2n-1, где n – натуральное число. В диапазоне от 1 до 20 таких чисел 4: 1, 3, 7, 15. А в диапазоне от 1 до 100 – 6: 1, 3, 7, 15, 31, 63.
  4. Таким образом, искомые числа – это числа от 15 до 30.

Ответ: 16.

Задание 2. Напишите в ответе наименьшее значение входной переменной 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)

  • в то же время на предыдущем шаге цикла (для i-1) условие его работы выполнялось, то есть

f(i-1) < g(k), откуда получаем

f(i-1) < g(k) <= f(i)

  • вспоминая, что f(i)=i3, делаем вывод, что g(k) должно быть между кубами двух соседних чисел: (i-1)3 < g(k) <= i3
  • для заданного k=10 находим g(10)=2·10+3=23, так что i=3:

(2)3 < g(k)=23 <= 33

  • осталось проверить, при каких k выполняется условие

8< g(k)=2k+3 <= 27

  • решая двойное неравенство относительно k получаем

2,5< k <= 12

  • таким образом, минимальное целое число, соответствующее условию – 3.

Ответ: 3.

Задание 3. Определите, какое значение 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. что в программе есть цикл, в котором переменная t принимает последовательно все целые значения в интервале от a до b:

for t:=a to b do begin

  …

end;

  • до начала цикла в переменную M записывается значение a, а в переменную R – значение функции в точке a:

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

  • внутри цикла есть условный оператор, в котором вычисляется значение функции F(t) и сравнивается со значением переменной R:

if (F(H,t) > R)then begin

  M:=t;

  R:=F(H,t)

end;

если новое значение функции больше, чем значение R, в R записывается значение функции в точке t, а в переменной M запоминается само значение t (аргумент функции, соответствующий значению в R)

  • в результате анализа пп. 1-3 можно сделать вывод, что цикл ищет максимум функции F(H,t) на интервале от a до b
  • заметим, что выводится значение R, а величина M не выводится и не влияет на вычисление R, поэтому можно не обращать на неё внимания
  • функция F вычисляет значение

F:=11*(x-H)*(x-H) + 13;

  • график этой эта функции – парабола с ветвями, направленными вверх (коэффициент при x2 = 11 > 0)
  • вершина параболы находится в точке x = H, ветви идут симметрично влево и вправо вверх
  • при изменении H парабола двигается влево или вправо (но не вверх-вниз!)
  • итак, мы ищем максимальное значение квадратичной функции, и хотим, чтобы это значение было наименьшим
  • давайте подвигаем параболу в пределах отрезка [a; b]:
  1. видно, что минимальное значение максимума будет тогда, когда вершина параболы будет расположена точно в середине отрезка [a; b]
  2. отсюда требуемое значение H равно среднему арифметическому между a = –10 и b = 30:

H = (–10 + 30) / 2 = 10

Ответ: 10.

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

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
  2. в программе значение N сначала обнуляется, а затем на каждом шаге цикла увеличивается на 1 при условии, что значение функции F(t) больше значения P = 130; таким образом, N – это счётчик точек с целочисленными значениями на отрезке [-25;25], в которых значение функции больше, чем 130
  3. график функция 16*(9-x)*(9-x)+127 – парабола с ветвями вверх, минимальное значение в точке x = 9 равно 127
  4. значение функции при x = 8 и x = 10 (рядом с точкой минимума) равны 16+127 = 143, поэтому только в одной точке x = 9 не выполняется условие F(t) > P
  5. всего на интервале [-25;25] есть 51 точка с целочисленными координатами; во всех, за исключением одной условие F(t) > P выполняется, то есть счётчик  увеличивается на 1

Ответ: 50

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

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;

  write(M);

END.

Решение:

  • заметим, что в программе есть цикл, в котором переменная t принимает последовательно все целые значения в интервале от a до b:

for t:=a to b do begin

  …

end;

  • до начала цикла в переменную M записывается значение a, а в переменную R – значение функции в точке a:

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

  • внутри цикла есть условный оператор, в котором вычисляется значение функции F(t) и сравнивается со значением переменной R:

if (F(t)<R)then begin

  M:=t;

  R:=F(t);

end;

если новое значение функции меньше, чем значение R, в R записывается значение функции в точке t, а в переменной M запоминается само значение t (аргумент функции, соответствующий значению в R)

  • в результате анализа можно сделать вывод, что цикл ищет минимум функции F(t) на интервале от a до b, и после выполнения цикла в переменной M оказывается значение аргумента t, при котором функция достигает минимума на заданном интервале (здесь это интервал [-20, 20])
  • функция F вычисляет значение

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

  • перебираем все значения t от a до b, и для каждого вычисляем соответствующее значение функции:
  • по таблице находим, что минимальное значение –4 достигается при t=2

Ответ: 2.

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

Var a,b,t,M,R :integer;
Function F(x:integer):integer;
begin
    F:=4*(x-5)*(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;
    write(R);
END.

Решение:
1. Алгоритм предназначен для поиска наименьшего значения функции F(t) на отрезке от a до b.
2. F(x) = 4*(x — 5) * (x+3) Квадратный трехчлен F(t) с положительным старшим коэффициентом пересекает ось абсцисс в точках 5 и −3 и, следовательно, наименьшее значение достигается в вершине 1 и равно F(1) = −64.
Ответ: -64

Top