Просмотр исходного текста страницы Основы программирования — Осенний семестр; Михалкович С.С.; 2008; II

[[Категория:Конспекты]]
== Оператор присваивания := ==
=== Синтаксис ===
 <переменная> ''':=''' <выражение>

''<u>Пример</u> использования оператора присваивания.''
<source lang="Pascal">
a := (3 + 5) * 8; 
b := a + 2;
</source>

=== Семанитика ===
Вычисляется выражение в правой части, при этом, вместо имен переменных подставляются их значения. <br />
Затем результат вычисления записывается в переменную в левой части.

'''Ограничение.''' Тип выражения должен быть '''''совместим по присваиванию''''' с переменной. <br />
Например:
* одинаковые типы совместимы.
* выражение типа <tt>integer</tt> можно присвоить переменной типа <tt>real</tt>. Обратное неверно.

=== Операторы присваивания += и *= ===
''<u>Пример</u>.''
<source lang="Pascal">
d += 1; //прибавить 1 к d
d *= 2; //умножить d на 2
</source>

=== Примеры использования := ===
''<u>Пример 1</u>.'' Перемена местами двух значений.
Дано:  <tt>x, y</tt>;
<source lang="Pascal">
var x, y: integer;
begin
  read(x,y);
  var v := x;
  x := y;
  y := v;
  writeln(x, ' ', y);
end.
</source>

Это стандартное решение. 
В PascalABC.NET на основе этого алгоритма определена стандартная процедура <tt>'''Swap'''(x, y)</tt>.

Однако, существуют и другие решения. Например:
<source lang="Pascal">
var x, y: integer;
begin
  read(x, y);
  x := x + y;
  y := x - y;
  x := x - y;
  writeln (x, ' ', y);
end.
</source>

''<u>Пример 2</u>.'' Использование промежуточных переменных в вычислениях
Дано:  <tt>x: real</tt>;
Найти:  <tt>x<sup>15</sup></tt>;

<u>Решение 1</u>.
<source lang="Pascal">
y := x * x;
z := y * y;
t := z * z;
p := t * z;
q := p * x * y;
</source>

<u>Решение 2</u>.
<source lang="Pascal">
y := x * x;
z := y * x;
t := z * y;
p := t * t * t;
</source>

<u>Решение 3</u>.
<source lang="Pascal">
y := x * x;
x := x * y * y;
t := x * x * x;
</source>

Заметим, что в первом решении используется 6 операций умножения, в во 2м и 3м — 5. Возникает задача: '''''найти x<sup>n</sup> за минимальное число умножений.''''' <br />
Об этом читай [http://it.mmcs.sfedu.ru/forum?func=view&id=22350&catid=1 тему].

== Оператор ввода ==
=== Синтаксис ===
 '''read''' (<список переменных>) | '''readln''' (<список переменных>)

=== Семантика ===
Происходит считывание данных с клавиатуры и запись их в переменные из <tt><списка переменных></tt>. 
Вводить данные нужно либо через пробел, либо по нажатию <tt><Enter></tt>, при этом программа не перейдет к выполнению следующего оператора, пока не будут считаны все данные.

С процедурой ввода связан ряд '''''ошибок''''' (например, если переменная используется в качестве делителя, и вводится 0, или, если должно быть получено целое число, а вводится <tt>'ABC'</tt>). Эти ошибки нужно уметь обрабатывать.

== Оператор try/except и обработка ошибок ввода ==
Операторы, которые могут получать ошибку, заключаются специальный охранный блок - оператор <tt>'''try'''</tt>.

=== Синтаксис ===
<source lang="Pascal">
try
  ...
  readln(a);
  ...
except
  <обработка ошибки>
end;
<продолжение работы>
</source>

=== Семантика ===
Если внутри блока '''<tt>try</tt>''' происходит ''ошибка выполнения'', то все последующие операторы в блоке игнорируются, и выполнение программы переходит к блоку '''<tt>except</tt>'''. По выходе из '''<tt>except</tt>''' программа продолжает работу.

Если ошибки не происходит, то выполняются все операторы в блоке '''<tt>try</tt>''', блок '''<tt>except</tt>''' не выполняется, и программа продолжает работу.

== Оператор вывода ==
=== Синтаксис ===
 '''write'''(<список выражений>) | '''writeln'''(<список выражений>)

=== Семантика ===
Выражения в списке вычисляются, и их значения выводятся на экран. <br />
В случае <tt>writeln</tt> после вывода осуществляется переход на новую строку.

=== Форматы вывода ===
После каждого выражения в списке вывода можно использовать '''формат вывода''' в виде <tt>''':a'''</tt>, где <tt>'''a'''</tt> — выражение целого типа.<br />
После вещественного типа — <tt>''':a:b'''</tt> (<tt>'''a'''</tt> задает ширину поля вывода (выравнивание по правому краю), <tt>'''b'''</tt> — количество знаков в дробной части).

=== Вывод с помощью write[ln]Format ===
 '''writelnFormat'''('<форматная строка>', <список выражений>)

''<u>Пример</u> вывода с использованием форматной строки''.
<source lang="Pascal">
writelnFormat('{0} * {1} = {2}', a, b, a * b)
</source>

Будет выведено:
 a * b = '''a * b'''

В форматной строке тоже можно использовать формат вывода.
<br><tt>{0, 10}</tt>: 10 — это ширина поля вывода
<br><tt>{0, 10:f3}</tt>: 3 — это количество знаков в дробной части для вещественного числа (показывает это спецификатор <tt>'''f'''</tt>).

== Условный оператор ==
=== Синтаксис ===
 '''if''' <условие> '''then''' <оператор<sub>1</sub>>
              '''else''' <оператор<sub>2</sub>>

=== Семантика ===
[[Изображение: If.jpg]]

=== Примеры использования для решения задач ===
''<u>Пример 1</u>.'' Нахождение минимума
<br>Дано: <tt>x, y</tt>; 
<br>Найти: <tt>min</tt>;

<source lang="Pascal">
if x > y then
  min := y
else
  min := x;
</source>

''<u>Пример 2</u>.'' Упорядочение <tt>a, b</tt> по возрастанию.
<br>Ясно, что если a > b, — нужно [[Основы программирования — Осенний семестр; Михалкович С.С.; 2008; II#Примеры использования := | поменять их местами]]. <br />
Но тут одним оператором не обойтись.
Для этого можно использовать '''''составной оператор''''' — один или больше операторов, заключенных в операторные скобки <tt>'''begin'''  - '''end''';</tt>:
<source lang="Pascal">if a > b then
begin
  var v := b;
  b := a;
  a := v;
end;
</source>

''<u>Пример 3</u>.'' Вычисление функции по взаимоисключающим веткам <br />
<math>y = \begin{cases} x, & x < 2 \\ x^2, & 2 < x < 3 \\ 1-x, & x \ge\; 3 \end{cases}</math>
<source lang="Pascal">
if x < 2 then
  y := x
else
  if x < 3 then
    y := x * x
  else
    y := 1 - x;
</source>

'''Замечание.''' Если по ветви '''<tt>else</tt>''' располагается другой оператор '''<tt>if</tt>''', то говорят, что возникает '''''цепочка вложенных операторов <tt>if</tt>'''''.

''<u>Пример 4</u>.'' Найти среднее среди <tt>a, b, c</tt> (<tt>a, b, c</tt> попарно не равны) <br />
Эта задача имеет несколько вариантов решения.
<source lang="Pascal">
if a < b then
  if a < c then
    if b < c then
      sr := b
    else
      sr := c
  else
    sr := a
else
  if a > c then
    if b > c then
      sr := b
    else
      sr := c
  else sr := a;
</source>

Очевидно, это не самое лучшее решение. <br>
Можно воспользоваться стандартными функциями сравнения.
<source lang="Pascal">
sr := min(a,b);
if sr < c then
  sr := min(max(a,b), c);
</source>

''Самостоятельно.''
* Даны координаты вершин треугольника и точка M. Принадлежит ли M треугольнику.
* Является ли 4-угольник ABCD корректно заданным.

== Арифметические выражения ==
=== Основные сведения ===
Каждое выражение имеет '''тип'''. Выражение называется '''''арифметическим''''', если его тип — ''числовой''. <br />
Выражение строится посредством '''''операций''''' (унарных или бинарных) и '''''операндов'''''.

В арифметических выражениях если <tt>a</tt> и <tt>b</tt> — одного типа, то и <tt>a '''op''' b</tt> принадлежит к тому же типу. ''Исключением'' является операция "'''/'''":
:<tt>'''a / b'''</tt> — вещественное.

Если <tt>a</tt> и <tt>b</tt> принадлежат к различным типам, то выражение принадлежит к "'''''старшему'''''" типу. <br />
Например:
 byte < integer < int64
 integer < real

В арифметические выражения могут входить стандартные функции:
 '''exp'''(x)
 '''ln'''(x)
 '''abs'''(x)  // модуль x
 '''sin'''(x)
 '''cos'''(x)
 '''sqr'''(x)  // квадрат x
 '''sqrt'''(x) // корень из x 
 '''min'''(x,y) 
 '''max'''(x,y) 
 '''pow'''(x,y)// x в степени y

=== Порядок выполнения операций в арифметических выражениях ===
* Операции с большим приоритетом выполняются первыми
* Функции вычисляются до операций
* Выражение в скобках вычисляется раньше
* Операции с одинаковым приоритетом выполняются слева направо, если идут подряд.

=== Операции div и mod для целых ===
<tt>x '''div''' y = x / y, округленное до ближайшего целого по направлению к нулю.</tt> Это '''''результат''''' от ''целочисленного деления''. <br />
<tt>x '''mod''' y = x - (x div y) * y.</tt> Это '''''остаток''''' от ''целочисленного деления''.

''<u>Пример</u> использования'' <br />
Целочисленные операции часто применяются для определения '''четности''' числа:
 x '''mod''' 2 = 0   <->   x — четное
 x '''mod''' 2 <> 0   <->   x — нечетное

== Логические выражения ==
=== Основные сведения ===
Выражение назывется '''логическим''', если оно имеет тип <tt>'''boolean'''.</tt> <br />
''<u>Пример</u>''.
 x < 0
 a >= b
 a <> 3

Это простые логические выражения. Однако, с помщью '''логических операций''' можно составлять сложные.
  (бинарные)     (унарные)
   a '''and''' b         '''not''' a
   a '''or''' b
   a '''xor''' b

=== Таблицы истинности логических операций ===
 a | b | a '''and''' b | a '''or''' b | a '''xor''' b 
 
 T | T |    T    |   T    |    F
 T | F |    F    |   T    |    T
 F | T |    F    |   T    |    F
 F | F |    F    |   F    |    T

=== Сокращение вычислений логических выражений ===
Большинство современных компиляторов, в т.ч. PascalABC.NET производит '''''сокращенное вычисление логических выражений'''''. <br />
Это означает, что в выражении
 a '''and''' b
если a — ложно, то <tt>b</tt> не вычисляется, а в
 a '''or''' b
если <tt>a</tt> — истинно, <tt>b</tt> не вычисляется.

Это очень полезно при вычислении таких выражений, как, например,
 (y <> 0) '''and''' (x / y > 0)

Логически здесь все верно, однако, если бы не использовалось сокращенное вычисление, в случае равенства нулю <tt>y</tt>'а возникала бы ошибка деления на ноль.
=== Логические переменные ===
Можно описывать логические переменные (тип <tt>'''boolean'''</tt>). Им можно присваивать логические выражения. <br />
Эти переменные принимают одно из двух возможных значений:
:<tt>'''true'''</tt> (истина)
:<tt>'''false'''</tt> (ложь)

''<u>Пример</u> использования логических переменных'' <br />
Дано: прямоугольник со сторонами, параллельными осям координат, задан координатами абсцисс вертикальных сторон (<tt>x1, x2</tt>) и ординатами горизонтальных (y1, y2); точка M( x, y ); <br />
Найти: находится ли точка внутри прямоугольника, снаружи, или лежит на границе;

<source lang="Pascal">
var inside, outside, bound: boolean;
begin
  inside := (x > x1) and (x < x2) and (y > y1) and (y < y2);
  outside := (x < x1) or (x > x2) or (y < y1) or (y > y2);
  bound := not inside and not outside;
end.
</source>

== Побитовые операции ==
=== Побитовые операции and, or, xor ===
'''Замечание.''' Работают только с целыми.

Смысл такой — каждое целое переводится в ''двоичную'' систему счисления и производится '''''побитовое''''' применение этих операций. <br />
''<u>Пример</u>.''
 5 '''and''' 10
5<sub>10</sub> = 101<sub>2</sub> <br />
7<sub>10</sub> = 111<sub>2</sub>

 101
    ( '''and''' )
 111
 ———
 101<sub>2</sub> = 5<sub>10</sub>

=== Операции shl и shr ===
'''''Побитовый сдвиг влево''''' и '''''сдвиг вправо''''' соответственно.

<h4> shl </h4>
 x '''shl''' n = x * 2<sup>n</sup>

Сдвигает двоичное представление <tt>x</tt> на <tt>n</tt> позиций влево.

<h4> shr </h4>
 x '''shr''' n = x div 2<sup>n</sup>

Сдвигает двоичное представление <tt>x</tt> на <tt>n</tt> позиций вправо.

<h4> Примеры </h4>
 x = 5<sub>10</sub> = 101<sub>2</sub>
 
 x shl 2 = <—(<sup>2</sup>)101
              10100<sub>2</sub> = 20<sub>10</sub>
 
 x shr 2 = 101—>(<sup>2</sup>)
           001<sub>2</sub> = 1<sub>10</sub>

== Таблица приоритетов операций языка Object Pascal ==
# унарные <tt>'''+ - not'''</tt>
# имеющие смысл ''умножения'' <tt>'''* / div mod and shl shr'''</tt>
# имеющие смысл ''сложения'' <tt>'''+ - or xor'''</tt>
# операции ''отношения'' <tt>'''<> <= >= < > in'''</tt>

== Оператор case выбора варианта ==
=== Синтакстис ===
 '''case''' <переключатель> '''of'''
   {<список выбора>: <оператор>;}
   ['''else''' <оператор>[;]]
 '''end'''

=== Семантика ===
Вначале вычисляется выражение-<tt><переключатель></tt>, после чего его значение ищется в одном из <tt><списков выбора></tt>. <br />
Если значение попадает в какой-то <tt><список выбора></tt>, то выполняется соответствующий ему оператор, иначе, если есть ветвь '''<tt>else</tt>''', то выполняется оператор по ветке <tt>else</tt>.

=== Ограничения ===
* выражение-переключатель должно иметь так называемый '''''порядковый''''' тип:
:''целый''
:''символьный''
:''перечислимый''
НО НЕ строковый или вещественный.
* значения в <tt><списках выбора></tt> не должны пересекаться.

=== Примеры использования оператора выбора ===
''<u>Пример 1</u>.'' День недели
<source lang="Pascal">
case DayOfWeek of
  1..5: writeln('Будний');
  6, 7: writeln('Выходный');
  else  writeln('Ошибка');
end;
</source>

''<u>Пример 2</u>.'' Цифра или буква
<source lang="Pascal">
var c: char;
read(c);
case c of
  '0'..'9': writeln('Цифра');
  'A'..'Z', 'a'..'z', 'а'..'я', 'А'..'Я', 'ё', 'Ё': writeln('Буква');
end;
</source>

== Циклы с предусловием (while) и постусловием (repeat) ==
=== Синтаксис цикла while ===
 '''while''' <условие> '''do'''   <— '''''заголовок цикла'''''
   <оператор>   <— '''''тело цикла'''''
 
 <условие>::= <логическое выражение>

=== Семантика цикла while ===
[[Изображение:Цикл_while_м.png]]

=== Синтаксис цикла repeat ===
 '''repeat'''
   <операторы>
 '''until''' <условие>

=== Семантика цикла repeat ===
[[Изображение:Цикл_repeat_м.png]]

=== Зацикливание ===
'''Зацикливание''' происходит, если:
* условие цикла с ''предусловием'' всегда ''истинно''
''<u>Пример</u>.''
<source lang="Pascal">
while true do
  <оператор>
</source> 

* условие цикла с ''постусловием'' всегда ''ложно''
''<u>Пример</u>.''
<source lang="Pascal">
repeat
  <операторы>
until false
</source> 

'''Итерация''' — однократное повторение тела цикла.

<h4> Отличия между циклами while и repeat </h4>
'''''while'''''
:тело может не выполниться ни разу
'''''repeat'''''
:тело выполнится хотя бы один раз

<h4> Примеры </h4>
''<u>Пример 1</u>.'' Сумма нечетных двузначных чисел

''С использованием while''
<source lang="Pascal">
s := 0; 
x := 11;
while x < 100 do
begin
  s += x;
  x += 2;
end;
</source>

''С использованием repeat''
<source lang="Pascal">
s := 0; x := 11;
repeat
  s += x;
  x += 2;
until x = 99;</source>

''<u>Пример 2</u>.'' Факториал

''С использованием repeat''
<source lang="Pascal">
var n: integer;
read(n);
var x := n;
var p := 1;

repeat
  p *= x;
  x -= 1;
until x = 1;
</source>

''С использованием while''
<source lang="Pascal">
var n: integer;
read(n);
var x := n;
var p := 1;

while x > 1 do
begin
  p *= x;
  x -= 1;
end;
</source>

=== Моделирование repeat с помощью while ===
 '''repeat'''             ''Op''
  '' Op''       ——>     '''while''' '''not''' A '''do'''
 '''until''' A;           '''begin'''
                      ''Op''
                    '''end;'''

=== Моделирование while с помощью repeat  ===          
 '''while''' A '''do'''         '''if''' A '''then'''
   ''Op''         ——>     '''repeat'''
                       '' Op''
                      '''until not''' A

== Оператор цикла с параметром (for) ==
=== Синтаксис ===
 <заголовок цикла>
   <тело цикла>

 <заголовок цикла> ::= '''for''' <переменная>:=<выражение1> <направление> <выражение2> '''do'''
 <тело цикла> ::= <оператор> 
 <направление> ::= to | downto

=== Семантика ===
<source lang="Pascal">
var b := <выражение1>;
var e := <выражение2>;
  <переменная> := b;
 
while <переменная> <> e do
begin
  <оператор>
  <получить следующее значение переменной>
  <переменная> += 1; | <переменная> -= 1;
end;
</source>

 <получить следующее значение переменной> ::= <переменная> '''+'''= 1; | <переменная> '''-'''= 1;
<xh4> Ограничения: </xh4>
* выражения 1 и 2 должны быть совместимы по присваиванию с переменной
* переменная должна иметь порядковый тип (такой же, как и в case — целый, символьный или перечислимый)
* переменная цикла for не должна меняться внутри цикла for
* переменная цикла for должна быть описана в той же п/п, где используется цикл

=== Дополнительные возможности PascalABC.NET ===
Возможно '''''описание переменной цикла в его заголовке''''':
<source lang="Pascal">
for [var] i: integer := 1 to 5 do
  <оператор>
</source>

Возможно '''''автоопределение типа при описании''''':
<source lang="Pascal">
for var i := 1 to 5 do
  <оператор>
</source>

Переменная цикла, описанная в заголовке цикла, определена только внутри цикла. <br />
'''Замечание.''' Значение переменной цикла после завершения цикла не определено. Именно поэтому рекомендуется ''описывать переменную цикла в заголовке цикла''.

== Примеры использования циклов ==
=== Табулирование функции ===
Дана f(x) на [a; b], разбитая на N частей. <br />
Выдать таблицу значений в точках разбиения.

<source lang="Pascal">
var a, b: real;
var N: integer;
read(a, b, N);

assert(N <> 0);
assert(b > a);
var h := (b - a) / N;
</source>

''Дальнейшее решение с помощью '''for''''':
<source lang="Pascal">
for var i := 0 to N do
begin
  writelnFormat('{0,6:f2} {1,9:f4}', x, f(x));
  x += h;
end;
</source>

''Дальнейшее решение с помощью '''while''''':
<source lang="Pascal">
var eps := h / 2;
while x < (b + eps) do
begin
  writelnFormat('{0,6:f2} {1,9:f4}', x, f(x));
  x += h;
end;
</source>

'''Замечание.''' Вещественные числа в памяти компьютера представлены приближенно. Ошибка, которая возникает при ''представлении'' вещественного числа в памяти, называется '''ошибкой округления'''. <br />
Ошибка, которая возникает в результате ''вычислений'' с вещественными числами называется '''вычислительной погрешностью'''.

'''Вывод.''' Вещественные числа нельзя сравнивать на равенство, можно только на ''больше/меньше''.

=== Рекуррентные соотношения ===
Говорят, что последовательность данных 
 x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>,..., x<sub>n</sub>
является '''рекуррентной''', если
 x<sub>k + 1</sub> = f( x<sub>k</sub> ), k = 1, 2, 3...

=== Вывод степеней двойки ===
<source lang="Pascal">
var x := 1;
for var i := 1 to 10 do
begin
  writeln(x);
  x *= 2;
end;
</source>

=== Последовательность Фибоначчи ===
<math>\begin{cases} x_1 = 1, x_2 = 1 \\ x_{k+1} = x_k + x_{k-1}\end{cases}</math>

<source lang="Pascal">
var a := 1;
var b := 1;
write(a, ' ', b, ' ');
for var i := 3 to 20 do
begin
  c := a + b;
  write(c, ' ');
  a := b;
  b := c;
end;
</source>

=== Вычисление НОД (алгоритм Евклида) ===
<math>\begin{cases} x_1 = a \\ x_2 = b \\ x_{k+1} = x_{k-1} mod  x_k\end{cases}</math>

<source lang="Pascal">
var a, b: integer;
read(a, b);
assert((a > 0) and (b > 0));
repeat
  c := a mod b;
  a := b;
  b := c;
until c = 0;
writeln(a);
</source>

=== Суммирование рядов (конечных и бесконечных) ===
* <math>\sum_{i=1}^n  \frac{a^i}{i!}</math>

Найдем рекуррентную связь между <tt>a<sub>i</sub></tt>:
 x<sub>1</sub> = a
 x<sub>i</sub> = x<sub>i-1</sub> * a / i, i = 2, 3..

<source lang="Pascal">
read(a, n);
x := a;
s := x;
for var i := 2 to n do
begin
  x *= a / i;
  s += x;
end;
</source>

* <math>\sum_{i=1}^\infty  (-1)^i\frac{a^i}{i}</math>

Для вычисления суммы ''бесконечного ряда'' в простейшем случае используют следующий метод:
:задается некоторый малый <tt>'''eps'''</tt> и сумма <math>\sum_{i=1}^\infty  x_i</math> вычисляется, пока <math>|x_i| >\ eps</math>

<source lang="Pascal">
assert((a > 0) and (a < 1));
i := 1;
s := 0;
y := -a;
repeat
  s += y / i;
  i += 1;
  y *= -a;
until abs(y / i) < eps;
</source>

=== Нахождение max в последовательности чисел ===
<source lang="Pascal">
max := - real.MaxValue; // или max := real.MinValue;
for var i := 1 to n do
begin
  read(x);
  if x > max then
    max := x;
end;</source>

=== Разложение целого числа на простые множители ===
Будем делить <tt>x</tt> на <tt>p</tt>, начиная с <tt>''p = 2''</tt>. Если делится нацело, то <tt>p</tt> — множитель, если не делится, то увеличиваем <tt>p</tt> на 1, пока <tt>''x <> 1''</tt>.

<source lang="Pascal">
read(x);
p := 2;
repeat
  if x mod p = 0 then
  begin
    write(p, ' ');
    x := x div p;
  end
  else
    p += 1;
until x = 1;</source>

=== Операторы break и continue ===
'''break''' — оператор ''досрочного завершения цикла''.
[[Изображение:break_м.png|none]]

'''continue''' — оператор ''досрочного завершения текущей итерации'' цикла.
[[Изображение:continue_м.png|none]]

=== Поиск заданного значения среди введенных ===
<u>Решение 1</u>. С использованием оператора ''break''
<source lang="Pascal">
var exists: boolean := false;
for var i:=1 to n do
begin
  read(x);
  if x = k then
  begin
    exists := true;
    break;
  end;
end;</source>

<u>Решение 2</u>.
<source lang="Pascal">
var i := 1;
var exists: boolean:= false;
repeat
  read(x);
  if x = k then
    exists := true;
  i += 1;
until (i > n) or exists;</source>

=== Обработка последовательности, завершающейся нулем ===
Вводятся числа. Конец ввода — ноль. <br />
Найти сумму и произведение положительных чисел.
<source lang="Pascal">
s := 0;
p := 1;
while True do
begin
  read(x);
  if x = 0 then
    break; 
  if x < 0 then
    continue;  //фильтр
  s += x;
  p *= x;
end;
</source>

=== Вычисление значения многочлена. Схема Горнера ===
Необходимо вычислить
<math>\ a_0x^n + a_1x^{n-1} + ... + a_{n-1}x + a_n</math>
если
:a<sub>0</sub>...a<sub>n</sub> известны
:x дано

<u>Решение 1</u>.
<source lang="Pascal">
var p := 1.0;
var s := 0.0;
for var i := 0 to n do
begin
  read(a);
  s += p * a;
  p *= x;
end;
</source>
Это решение использует <tt>2(n + 1)</tt> умножений.

Однако есть и другое решение — '''схема Горнера'''.
Оно основана на том, что <br />
<math>\ a_0x^2 + a_1x + a_2 = ((a_0)x + a_1)x + a_2</math>

<u>Решение 2</u>.
<source lang="Pascal">
read(a);
var res: real := a;
for var i:=1 to n do
begin
  read(a);
  res *= x;
  res += a;
end;
</source>
Итого — всего <tt>n</tt> умножений.

===Пример 11. Поиск нуля функции на отрезке===
Требуется найти корень уравнения <tt>f( x ) = 0</tt>
*на отрезке <tt>[a; b]</tt>
*с заданной точностью eps
*<tt>f(x)</tt> непрерывна на этом отрезке
*имеет на нем ровно 1 корень, т.е. <tt>f(a ) * f( b ) < 0</tt>

Эта задача решается '''методом половинного деления'''.
<source lang="Pascal">assert(b > a);
var fa := f(a);
var fb := f(b);
assert(fa * fb < 0);

while b - a > eps do
begib
  var x := (b + a) / 2;
  var fx := f(x);
  if f(x) * f(a) > 0 then
  begin
    a := x;
    fa := fx;
  end
  else
    b := x;
end;</source>
<small>'''Лекция 8'''</small>

==Вложенные циклы==
<h3>Метод последовательной детализации</h3>
'''Задача.''' Вывести все простые числа <= n
<source lang="Pascal">writeln(2);
x := 3;
while x <= n do
begin
  Если число x — простое, то
    writeln(x);
  x += 2;
end;</source>
<h3>Метод окаймления</h3>
'''Задача.''' Вывести A<sup>k</sup>, A = 2..10

'''Метод окаймления''' заключается в том, что что мы окаймляем данный алгоритм внешним циклом, "''размораживая''" некоторый параметр.

Итак, пусть A — фиксировано( "''заморожено''" ).
<source lang="Pascal">var p := 1.0;
for var i:=1 to k do
  p *= A;
write(p);</source>
Теперь ''размораживаем'' A:
<source lang="Pascal">for A:=2 to 10 do
begin
  ...
end;</source>
<h3>Переборные задачи</h3>
Класс задач, в которых требуется перебрать множество вариантов и выбрать несколько оптимальных по каким-то критериям.

'''Задача'''
:Дано равенство: a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup>, a,b,c — целые
:Вывести все такие тройки (a, b, c), что: a<=100, b<=1000, c<=1000;
'''Решение'''
<source lang="Pascal">for var a:=1 to 1000 do
  for var b:=1 to 1000 do
    for var c:=1 to 1000 do
      if a*a + b*b = c*c then
        writeln(a, b, c);</source>
Однако, ясно, что
 a<sup>2</sup> + b<sup>2</sup> = c<sup>2</sup> <=> b<sup>2</sup> + a<sup>2</sup> = c<sup>2</sup>
'''Оптимизация'''
<source lang="Pascal">for var a:=1 to 1000 do
  for var b:=1 to a-1 do
  begin
    var c := round(sqrt(a*a + b*b));
    if a*a + b*b = c*c then
    begin
      writeln(a, b, c);
      writeln(b, a, c);
    end;
  end;</source>
'''Вывод.''' При наличии нескольких вложенных циклов нужно оптимизировать ''самый внутренний''.