Языковое программирование

for i:=1 to 10 do   begin     x2:=x; {Запоминаем последний  из вычисленных членов последовательности}      x:=f(x, y); {Вычисляем следующий  элемент}     y:=g(x2, y); {Для вычислений  используем запомненное значение}    end;

 

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

for i:=1 to 10 do   begin     x2:=f(x, y); {новый член последовательности  запоминается                   в дополнительной переменной x2}     y:=g(x, y);     x:=x2;   end;

 

Контрольная работа №4

1. Укажите 4-й член последовательности  заданной рекуррентным соотношением

 

    

2. Какими рекуррентными  соотношениями задаются последовательности

 

    а) 2, 4, 16, 256, …

 

    б) 2, 0.5, 2, 0.5, 2, …

 

    в) 2, 5, 8, 11, 14, …

 

    г) 2, -4, 16, -256, …

3. Какую функцию переменной x вычисляет программа? Укажите также  рекуррентные соотношения, в соответствии  с которыми происходят вычисления.

а)	readln(x);   y:=0;   p:=1;   sgn:=1;   for i:=2 to 4 do   begin     p:=p*x;     y:=y+sgn*p;     sgn:=-sgn;   end;   writeln(y);
б)	readln(x);   y:=0;   p:=1;   for i:=1 to 4 do   begin     p:=-p*x*x;     y:=y+p/i;   end;   writeln(y);
в)	readln(x);   y:=1;   p:=1;   for i:=1 to 4 do   begin     p:=p*(x-1);     y:=y+p;   end;   writeln(y);
г)	readln(x);   y:=1;   p:=1;   for i:=1 to 4 do   begin     p:=-p/x;     y:=y+p;   end;   writeln(y);

Контрольная работа №5

1. Каким рекуррентным соотношением  описывается последовательность:

 

    

2. Запишите рекуррентное  соотношение и первый член  последовательности, необходимые для  вычисления величины:

 

    а) 

 

    б) 

3. Запишите рекуррентные  соотношения необходимые для  вычисления функции:

 

    а) 

 

    б) 

 

    в) 

 

    г) 

4. Какую функцию переменной x вычисляет программа?

а)	readln(x);   y:=1;   p:=1;   for i:=-2 to 2 do   begin     if i<>0 then       p:=p*x*i/abs(i);     y:=y+p;   end;   writeln(y);
б)	readln(x);   y:=1;   for i:=0 to 3 do   begin     x:=1+1/x;     y:=y-x;   end;   writeln(y);

5. Имеется двумерное рекуррентное  соотношение 
      
Начальные условия  . Напишите программу, которая найдет   и  .

Задание 4. Вычисления с помощью рекуррентных соотношений

1. Последовательность определяется  соотношением:  , где  ,  . Найти  ,   и  .

2. Вычислите золотое сечение  по формуле

 

    

Сделайте 20 итераций. В каком знаке будут наблюдаться изменения, если сделать 30 итераций?

3. В 1674 году Г. Лейбниц показал, что число   Найдите приближенное значение числа  , просуммировав 100 членов этого ряда.

4. Составив соответствующие  рекуррентные соотношение, вычислите  значения выражений:

 

    1) 

 

    2) 

 

    3) 

4)
	n раз

 

 

    

 

    

5. Пользователь вводит 10 чисел. Определить, образуют ли они возрастающую  последовательность.

5.1. Вложенные циклы: теория

Циклы позволяют повторять выполнение любого набора операторов. В частности можно повторять много раз выполнение другого цикла. Такие циклы называются вложенными.

Пример 1. Напечатать числа в виде следующей таблицы

 

    3 3 3 3 3

 

    3 3 3 3 3

 

    3 3 3 3 3

 

    3 3 3 3 3

Данная таблица состоит из четырех строчек, в каждой из которых число 3 напечатано 5 раз. Строчку из пяти чисел можно напечатать с помощью одного цикла for:

for i:=1 to 5 do     write(3, '   ');

 

Чтобы повторить вывод строчки 4 раза, вставляем этот цикл внутрь другого:

for k:=1 to 4 do   {4 раза делаем то, что  написано между begin’ом и end’ом}   begin     for i:=1 to 5 do       write(3, '   ');  {Выводим одну строку}      writeln;    {Переводим курсор на следующую строку}   end;

 

Типичная ошибка, когда в качестве счетчиков вложенных циклов (i и k в приведенном примере) используется одна и та же переменная. То есть нельзя в каждом из циклов использовать одну переменную i. Помнить об этом особенно важно, поскольку данная ошибка не обнаруживается на этапе компиляции. Ваша программа запустится, но делать будет вовсе не то, что вы от нее ждете. В приведенном примере (если допустить ошибку, заменив переменную k на i) внешний цикл выполнится всего 1 раз вместо 4-х. Возможна также ситуация, когда такая ошибка приведет к зацикливанию: внешний цикл будет выполняться бесконечно долго – программа зависнет.

Рассмотрим еще один пример.

Пример 2. Напечатайте числа в виде следующей таблицы:

 

    1  2  3  4

 

    5  6  7  8

 

    9  10 11 12

 

    13 14 15 16

Снова используем внешний цикл для вывода строк, а внутренний для отдельных чисел в одной строке. Используем также отдельную переменную-счетчик n, в которой будет храниться выводимое число.

n:=1;   for i:=1 to 4 do   begin     for k:=1 to 4 do     begin       write(n, '   ');       n:=n+1;     end;     writeln;   end;

 

Дополнительная переменная-счетчик (n) здесь введена для большей прозрачности алгоритма. Заметив, что всегда выполняется n = (i-1)*4+k, можно обойтись без нее.

Разумеется, ту же задачу можно решить без вложенных циклов (вообще говоря, обойтись без них можно всегда). Например, заметив, что числа, стоящие в конце каждой строки делятся на 4, делаем так:

for n:=1 to 16 do   begin     write(n, '   ');     if n mod 4 = 0 then       writeln;   end;

 

Однако решения, основанные на вложенных циклах, как правило, интуитивно понятнее, их проще придумывать. Это связано с такой фундаментальной идеей программирования как разделение задачи на подзадачи. Выделяется отдельная часть решения задачи (вывод одной строки в приведенных примерах), затем с помощью внешнего цикла она выполняется много раз.

Типичные ошибки при написании вложенных циклов:

1. Наиболее частая ошибка  – использование одной и той  же переменной-счетчика для внешнего  и внутреннего циклов. Выше она  уже упоминалась.

2. При решении некоторых  задач необходимо, чтобы одна  переменная-счетчик на каждом  шаге увеличивалась, а другая  при этом уменьшалась. Следуя  непостижимыми (для человека наделенного  формально-логическим складом ума) путями интуитивного мышления  многие студенты для решения  этой задачи приходят к конструкции  вида:

for i:=1 to n do     for k:=n downto 1 do …

 

Если вы хоть что-то поняли про вложенные циклы, то вам должно быть очевидно, что к решению поставленной задачи эта конструкция не имеет никакого отношения.

Напомним, что в качестве пределов изменения переменной-счетчика цикла можно использовать произвольное выражение, дающее результат целого типа:

for i:=<произвольное выражение> to <произвольное выражение> do …

 

В частности, если речь идет о вложенных циклах, то пределы изменения переменной во внутреннем цикле могут зависеть от значения переменной внешнего цикла. Например:

Пример 3: Напечатайте числа в виде следующей таблицы:

 

    1 2 3 4  5

 

    3 4 5 6  7

 

    5 6 7 8  9

 

    7 8 9 10 11

Решение:

for i:=1 to 4 do   begin     for k:=2*i-1 to (2*i-1)+4 do       write(k, '   ');     writeln;   end;

 

Поскольку внутри цикла может находиться все, что угодно, то ничто не мешает разместить там два цикла. Например, так:

for i:=1 to 10 do   begin     …     for k:=1 to 10 do     begin       ...     end;     for n:=1 to 10 do     begin       ...     end;     …   end;

 

Или так:

for i:=1 to 10 do     for k:=1 to 10 do       for n:=1 to 10 do …

 

В заключение небольшое замечание, касающееся правильного стиля написания программы, содержащей множество циклов (в частности вложенных). Следует избегать одновременного использования в качестве счетчиков пар переменных с именами i и j, а также p и q. На вид они очень похожи, что часто приводит к трудно обнаруживаемым ошибкам.

Контрольная работа №6

1. Какое значение примет  переменная x после выполнения программ:

а)	x:=0;  for i:=1 to 10 do    for k:=i+1 to 10 do      x:=x+1;	б)	x:=0;  for i:=1 to 10 do    for k:=i+1 to 10-i do      x:=x+1;
в)	x:=0;  for i:=1 to 5 do    for k:=i-1 to i+1 do      x:=x+k;	г)	x:=10;  for i:=1 to 5 do    for k:=0 to i do      x:=x+(k-i);

2. Что выведут программы?

а)

for i:=1 to 4 do  begin    if i mod 2 = 0 then      n:=i+1    else      n:=i;    for k:=1 to n do      write(n-i, '   ');    writeln;  end;

б)

for i:=1 to 3 do    for k:=3 downto 1 do      for n:=i-k to (i+k) div 2 do        write(n, '   ');

Задание 5: Вложенные циклы

1. Из мат. анализа известно, что последовательность сумм  вида:

 

сходится к функции  . Исследуйте зависимость от   точности приближения синуса десятым членом последовательности. Для этого рассчитайте величину   в 20 точках в диапазоне от 0 до  .

2. «Рисование» символами.

(а) Выведите на экран  числа в следующем виде:   1   2  2   3  3  3   4  4  4  4   5  5  5  5  5 и т.д. (б) Выведите на экран  числа в следующем виде:   7  6  5  4  3  2   6  5  4  3  2   5  4  3  2   4  3  2   3  2   2 (в) Выведите на экран  числа в следующем виде:   1   3   2  2   4  4   3  3  3   5  5  5   4  4  4  4   6  6  6  6 (г) Выведите звездочки  «полуелочкой» (рис. справа). (д) Превратите «полуелочку»  в полную елочку.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * и т.д. Заданное количество раз.

 

6.1. Перебор вариантов: теория

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

Пример 1: Поиск делителей целого числа N.

Целое число K является делителем N, если остаток от деления N на K равен 0. Чтобы найти все делители достаточно перебрать все числа от 1 до N и проверить, являются ли они делителями. Данный алгоритм можно реализовать с помощью программы:

readln(n);   for i:=1 to n do     if n mod i = 0 then       write(i, '   ');

 

На этом простейшем примере ясна общая структура решения задач на перебор вариантов. Для организации перебора используется цикл, каждый шаг выполнения которого соответствует рассмотрению одного из вариантов. Внутри цикла стоит проверка, подходит ли данный вариант под условие задачи.

Решая задачи методом перебора, всегда следует подумать, а нельзя ли каким-то образом сократить количество перебираемых вариантов. В данном случае заметим, что любое число делится само на себя и на 1. Поэтому эти варианты можно исключить из перебора. Более того, наибольшим делителем, отличным от самого числа N может быть только N/2, а все числа, большие N/2 заведомо делителями не являются. Учет этих особенностей приводит к более эффективной программе:

readln(n);   write(1, '   ');   for i:=2 to n div 2 do     if n mod i = 0 then       write(i, '   ');   write(n);

 

Продолжая размышления о сокращении перебора (спасибо комментарию Владимира), заметим, что если iявляется делителем, то частное от деления на i — тоже делитель. Таким образом, выводя делители парами, можно ограничится перебором до корня из n:

readln(n);   writeln(1, '  ', n);   m:=trunc(sqrt(n));   for i:=2 to m do     if n mod i = 0 then       writeln(i, '  ', n div i);