Главная страница
Навигация по странице:

  • При каких значениях a оператор начнет работу

  • : Каково минимальное положительное значение ε

  • : Как без дополнительных запросов (и переменных) прекратить считы- вание входных данных и закончить выполнение цикла

  • Простое число

  • В каком случае программа будет работать неверно

  • Чему равно значение индекса «нач»

  • Лекциям по курсу Информатика


    Скачать 3.84 Mb.
    НазваниеЛекциям по курсу Информатика
    Анкорlekcii_shiryaevoy.pdf
    Дата11.07.2018
    Размер3.84 Mb.
    Формат файлаpdf
    Имя файлаlekcii_shiryaevoy.pdf
    ТипЛекция
    #19640
    страница5 из 9
    1   2   3   4   5   6   7   8   9
    При каких значениях a оператор начнет работу?
    ? ? ?
    Тест: a = −1 (
    бесконечный цикл
    )
    a проверка условия a < 1
    −1
    +
    −2
    +
    −4
    +
    Исправление ситуации:
    перед запуском цикла проверить условие, при ко- тором цикл не будет бесконечным:
    ? ? ?
    Пример 5.2. Дан оператор цикла while a < 0
    do a := a - 1;

    При каких значениях a оператор начнет работу?
    ? ? ?
    Исправление ситуации:
    ? ? ?
    120

    8.6
    Решение задач
    8.6.1
    Организация диалога с пользователем
    Пример 6.1. Будем в цикле проверять готовность пользователя продолжать пользоваться программой.
    Решение. var Ch: Char;
    Цикл с предусловием
    (* см. конспект *)
    Цикл с постусловием
    (* см. конспект *)
    Результат:
    Continue? (y, n) [> y
    Continue? (y, n) [> y
    Continue? (y, n) [> n
    Bye
    8.6.2
    Контроль ввода исходных данных
    Пример 6.2. Программа начнет работать только в случае ввода верных ис- ходных данных (например, > 0).
    Решение.
    Цикл с предусловием
    (* см. конспект *)
    Результат:
    Input a > 0 [> 0
    Error: a <= 0
    Input a > 0 [> -1
    Error: a <= 0
    Input a > 0 [> 1
    Start program
    121

    8.6.3
    Вычисление конечных сумм и произведений n
    i=1
    a i
    = a
    1
    + a
    2
    + . . . + a n
    ;
    n i=1
    a i
    = a
    1
    · a
    2
    · . . . · a n
    a i
    зависит от постановки задачи.
    Алгоритм вычисления суммы:
    1. S := 0.
    2. В цикле (n-раз для конечных сумм): S := S + a.
    Алгоритм вычисления произведения:
    1. P := 1.
    2. В цикле (n-раз): P := P * a.
    Пример 6.3. Вычислить сумму первых 10 натуральных чисел:
    1 + 2 + 3 + . . . + 10 =
    10
    i=1
    i.
    Программа с использованием цикла с предусловием
    1
    (* см. конспект *)
    Результат работы программы:
    Sum = 55
    Цикл с постусловием
    3
    (* см. конспект *)
    Встроенные средства пакета Maple
    [> Sum(i, i=1..10) = sum(i, i=1..10);
    Результат работы:
    10
    i=1
    i = 55
    Для вычисления произведения вида n
    i=1
    a i
    = a
    1
    · a
    2
    · . . . · a n
    с помощью пакета Maple предназначена команда product():
    122

    Встроенные средства пакета Maple
    [> Product(i, i=1..5) = product(i, i=1..5);
    Результат работы:
    5
    i=1
    i = 120 123

    8.6.4
    Вычисление бесконечных сумм
    (15.10.2010)
    Пример 6.4. Вычислить приближенное значение бесконечной суммы
    1 +
    1 2
    2
    +
    1 3
    2
    +
    1 4
    2
    + . . . =

    i=1
    y i
    =

    i=1 1
    i
    2
    (6.2)
    Вычисления продолжать до тех пор пока очередное слагаемое не окажется по модулю меньше числа ε = 10
    −5
    , т. е.
    |y i
    | < ε.
    (6.3)
    . Условие окончания процесса вычисления суммы (
    6.3
    ) означает, что неко- торое слагаемое будет давать вклад, несущественный по сравнению с нашей суммой, и его учитывать уже не надо.
    Продемонстрируем это на примере результатов вычисления y i
    в сумме (
    6.2
    ) для
    ε = 0.01
    Трассировочная таблица i
    y
    Sum
    -----------------------
    1 1.000 1.000 2
    0.250 1.250 3
    0.111 1.361 4
    0.063 1.424 5
    0.040 1.464 6
    0.028 1.491 7
    0.020 1.512 8
    0.016 1.527 9
    0.012 1.540 10 0.010 1.550
    -----------------------
    11 0.008 0
    4 8
    12 0.02 0.04 0.06 0.08 10 6
    ε = 0,01
    y i
    i
    Рис. 6.7. Значения y i
    , i = 4, . . . , 11 124

    Решение. Общий член суммирования y
    i
    =
    1
    i
    2
    ,
    i = 1, 2, . . .
    Для вычисления используется цикл while-do.
    До начала цикла необходима инициализация значений i и y i
    (строка 5), а также переменной для хранения результата суммирования (строка 6).
    Вычисление

    i=1 1
    i
    2 1
    (* см. конспект *)
    Результат работы программы:
    Ответ: 1,64177.
    Количество членов суммирования 316.
    125

    Сравним результат работы программы с результатом, полученным с помощью пакета Maple.
    Встроенные средства пакета Maple
    [> Sum(1/(i*i), i=1..infinity) = sum(1/(i*i), i=1..infinity);
    Результат работы Maple:

    i=1 1
    i
    2
    =
    π
    2 6
    Встроенные средства пакета Maple
    [> Sum(1/i^2, i=1..infinity) = evalf(sum(1/i^2, i=1..infinity));
    Результат работы Maple:

    i=1 1
    i
    2
    = 1.644934068
    Напомним результат работы программы:
    Ответ: 1,64177.
    Количество членов суммирования 316.
    . В общем случае условие |y i
    | < ε не означает, что разность между «точным»
    значением и приближенным значением суммы равна ε.
    i i
    0 4
    8 10 1
    1.2 1.4 1.6
    «точное» значение
    Рис. 6.8. Сравнение значений суммы для разных i со значением, посчитанным программой
    Maple. Случай: ε = 0.01 126

    Осторожно:
    если в программе вместо выражения y := 1 / i / i написать y := 1 / (i * i),
    то программа может неадекватно отреагировать на очень большое число,
    которое получается при умножении i * i. В частности, при количестве членов суммирования 316
    i
    2
    = 99 856.
    Напомним, что при работе с переменными типа Integer в 16-ти разрядных системах неприятности возникают для чисел больших 32 767).
    Проверьте в Delphi работоспособность программы со стр.
    125
    при ε = 10
    −10
    ,
    используя оба способа определения y:
    1) y := 1 / i / i
    2) y := 1 / (i * i).
    127

    8.6.5
    Числовые последовательности
    Последовательность
    — это набор элементов некоторого множества, про- нумерованный натуральными числами.
    Пример 6.5. Дана последовательность (x i
    )
    N
    i=1
    N целых чисел. Подсчитать число элементов, следующих после первого нулевого.
    Алгоритм:
    пока не достигнут конец последовательности и не найден нулевой элемент выполнять
    1) ввод элемента последовательности;
    2) наращивание счетчика элементов.
    Число элементов последовательности
    1
    (* см. конспект *)
    Результаты работы программы:
    0
    j = 4 1
    3 0
    j = 2 1
    2 3
    4 5
    j = 0 128

    8.6.6
    Вычисление машинного ε
    Машинный ноль (computer zero)
    — представление нуля в вычисли- тельной системе. Это фундаментальное свойство машинных вычислений с плавающей точкой. Зависит от точности типа данных.
    Машинный эпсилон

    маш
    ) — наименьшее положительное число ε:
    1.0 + ε = 1.0
    Число ε
    маш
    , чуть менее корректно, также называют машинным нулем, посколь- ку при прибавлении к единице оно ведет себя как ноль, т. е.
    1.0 + ε
    маш
    = 1.0
    Величина машинного эпсилона характеризует точность операций компьютера.
    Ранее рассматривался вопрос о сравнении вещественных чисел с некоторой точностью (см., например, стр.
    38
    ). Напомним, что вещественные числа x и y равны с точностью ε, если |x − y|
    ε.
    ?

    : Каково минимальное положительное значение ε?
    Алгоритм состоит в том, что уменьшая значение переменной eps, проверяем насколько велик вклад этого значения в значение переменной E (=1).
    Машинный ε
    1
    (* см. конспект *)
    Результат:
    eps_mash = 2.22044604925031E-0016 (при eps: Real)
    eps_mash = 1.08420217248550E-0019 (при eps: Extended)
    129

    8.6.7
    Действия над целыми числами
    Пример 6.6. Подсчитать количество цифр в записи натурального числа.
    Решение. Для подсчета количество цифр числа будем последовательно его де- лить нацело на 10 до тех пор пока результат деления не станет равным нулю,
    подсчитывая при этом количество произведенных операций деления. Напри- мер,
    Для трехзначного числа
    Для четырехзначного числа
    358 div 10 = 35 (1);
    35 div 10 = 3
    (2);
    3 div 10 = 0
    (3).
    4500 div 10 = 450 (1);
    450 div 10 = 45
    (2);
    45 div 10 = 4
    (3);
    4 div 10 = 0
    (4).
    Подсчет количества цифр в числе
    1
    (* см. конспект *)
    (стиль программирования). В приведенной программе нарушен очень важный принцип
    «данные пользователя портить нельзя»: сведения о введенном пользователем числе хранятся в переменной m, которая в данной программе используется также для хранения результатов деления.
    130

    Если заменить оператор вывода следующим
    Вывод ответа и данных пользователя
    11
    WriteLn(’Количество цифр числа ’, m, ’ = ’, Col);
    то получим ответ в виде
    Данные пользователя испорчены
    Введите натуральное число [> 457
    Количество цифр числа 0 = 3
    Исправление ситуации: сохранить значение m в другую переменную и уже с но- вой переменной можно делать все, что угодно, не боясь испортить данные,
    которые программа получает от пользователя.
    Исправьте программу, приведенную на стр.
    130
    так, чтобы новый оператор вывода
    WriteLn(’Количество цифр числа ’, m, ’ = ’, Col);
    позволял печатать правильный ответ.
    131

    8.6.8
    Использование сигнальной метки
    Пример 6.7. Вычислить сумму всех экзаменационных оценок студента.
    Решение. Количество экзаменов заранее неизвестно. Необходимо осуществлять ввод оценок до тех пор, пока программа не получит информацию об окончании ввода. Можно организовать вывод запроса о необходимости продолжения ввода информации.
    Введение дополнительной переменной
    1
    var Mark,
    { экз. отметка }
    2
    Sum
    : Integer;
    { сумма баллов }
    3
    Ch
    : char;
    4
    begin
    5
    Sum := 0;
    { инициализация суммы баллов }
    6
    Write(’Start (y - yes)? ’);
    ReadLn(Ch);
    7
    while Ch = ’y’ do
    8
    begin
    9
    Write(’Input mark [> ’);
    ReadLn(Mark);
    10
    Sum := Sum + Mark;
    11
    Write(’Continue (y - yes)? ’);
    ReadLn(Ch);
    12
    end;
    13
    WriteLn(’Sum = ’, Sum);
    14
    end.
    Результат работы программы:
    Start (y - yes)? y
    Input mark [> 4
    Continue (y - yes)? y
    Input mark [> 5
    Continue (y - yes)? n
    Sum = 9
    ?

    : Как без дополнительных запросов (и переменных) прекратить считы- вание входных данных и закончить выполнение цикла?
    Для окончания ввода данных пользователь может ввести уникальное значение,
    называемое сигнальной меткой
    132

    Условие продолжения цикла проверяет каждый введенный элемент данных и в случае ввода сигнальной метки, инициирует выход из цикла. Для сигналь- ной метки необходимо выбирать значение, никогда не встречающееся среди элементов данных.
    Сигнальная метка
    1
    var Mark, Sum
    : Integer;
    2
    begin
    3
    Sum := 0;
    4
    WriteLn(’Exit: -1’);
    5
    Write(’Input mark [> ’);
    ReadLn(Mark);
    6
    while Mark <> -1 do
    7
    begin
    8
    Sum := Sum + Mark;
    9
    Write(’Input mark [> ’);
    ReadLn(Mark);
    10
    end;
    11
    WriteLn(’Sum = ’, Sum);
    12
    end.
    Результаты работы программы:
    Exit: -1
    Exit: -1
    Input mark [> 3
    Input mark [> -1
    Input mark [> 4
    Sum = 0
    Input mark [> -1
    Sum = 7 133

    Пример 6.8. Вычисление среднего балла из экзаменационных оценок. Коли- чество экзаменов заранее неизвестно.
    Решение. Сигнальная метка: значение -1 (такой оценки быть не может).
    Средний балл =
    Сумма баллов
    Число экзаменов
    Сигнальная метка
    1
    var Mark, Sum,
    { экз. отметка и сумма баллов }
    2
    Count
    : Integer; { число экзаменов }
    3
    begin
    4
    Sum := 0;
    5
    Count := 0; { инициализация счетчика экзаменов }
    6
    WriteLn(’Exit: -1’);
    7
    Write(’Input mark [> ’);
    ReadLn(Mark);
    8
    { проверка на случай, если пользователь сразу решит выйти }
    9
    if Mark <> -1 then
    10
    begin
    11
    while Mark <> -1 do
    12
    begin
    13
    Sum := Sum + Mark;
    14
    Count := Count + 1;
    15
    Write(’Input mark [> ’);
    ReadLn(Mark);
    16
    end;
    17
    WriteLn(’Average mark = ’, Sum / Count :5:2);
    18
    end
    19
    else
    WriteLn(’Data is absent’);
    20
    end.
    . Проверка условия Mark <> -1 (строка 9) понадобилась для того, чтобы защититься от ошибки «division by zero» (деление на ноль) при вычисле- нии значения выражения Sum / Count. Эта ситуация возникнет в случае, если пользователь сразу введет значение -1.
    134

    8.6.9
    Циклы, управляемые флагами
    Флаг
    — это Boolean-переменная, значение которой указывает, произошло ли определенное событие.
    Значение флага должно быть первоначально установлено в False (True), а затем изменено на True (False), когда ожидаемое событие станет фактом (на- рушится). Цикл будет функционировать до тех пор, пока не случится соответ- ствующее событие.
    Пример 6.9. Программа обрабатывает целые числа, вводимые пользователем.
    Ввод должен прекратиться как только введенное ненулевое число будет чет- ным.
    Использование флага var Value : Integer; { вводимое число }
    Stop
    : boolean; { флаг }
    begin
    (* см. конспект *)
    end.
    Результат работы программы:
    Input number [> 3
    Input number [> 0
    Input number [> 8 8 - even & <> 0 135

    8.6.10
    Перебор делителей
    Перебор делителей
    — алгоритм факторизации или тестирования про- стоты числа путем полного перебора всех возможных потенциальных де- лителей.
    Пусть n — факторизуемое число.
    Перебор делителей заключается
    — в переборе всех целых чисел от
    2 до

    n и в вычислении остатка от деления n на каждое из этих чисел.
    Если остаток от деления на некоторое число m равен нулю, то m является делителем n.
    При этом:
    При тестировании простоты числа n:
    Число n объявляется составным и ал- горитм заканчивает работу.
    При факторизации n:
    число n сокращается на m и процедура повторяется.
    По достижении

    n и невозможности сократить n ни на одно из меньших чисел, n объявляется простым.
    136

    8.6.11
    Тест простоты числа
    Тест простоты числа
    — алгоритм, который по заданному натуральному числу определяет, простое ли это число.
    Простейший тест простоты это перебор делителей.
    Пример 6.10. Проверить, является ли натуральное число n простым.
    Решение. Напомним, что простым числом называется натуральное чис- ло, имеющее только два делителя: единицу и само это число. Число 1 не является простым.

    Простое число?
    1
    (* см. конспект *)
    Результаты работы программы:
    Input number (>1) [> 15
    Input number (>1) [> 7
    Prime number: FALSE
    Prime number: TRUE
    . Условный оператор (строка 9) можно заменить оператором присваивания
    Flag := n mod k <> 0;

    В каком случае программа будет работать неверно?
    Модифицировать программу так, чтобы она выдавала верный результат для всех натуральных чисел.
    137

    8.6.12
    Факторизация заданного числа
    Факторизация
    — разложение данного натурального числа на простые множители.
    Пример 6.11. Разложить натуральное число n на простые множители.
    Решение:
    Разложение числа на простые множители
    1
    (* см. конспект *)
    Результат работы программы:
    Input number [> 60 60 =
    2 2
    3 5
    138

    8.6.13
    Вычисление квадратного корня по формуле Герона
    Пример 6.12. Итерационная формула Герона для вычисления

    a (a > 0)
    имеет вид:
    x i+1
    =
    1 2
    x i
    +
    a x
    i
    ,
    i = 0, 1, 2, . . .
    (6.4)
    x
    0
    — любое число (> 0).
    Для компьютерных вычислений формулу (
    6.4
    ) удобно записать в форме Ньютона–Рафсона:
    x i+1
    = x i
    − ∆
    i
    ,

    i
    =
    1 2
    x i

    a x
    i
    ,
    i = 0, 1, 2, . . .
    (6.5)
    Решение. Процесс итераций закончим, как только невязка ∆
    i
    = |x i+1
    −x i
    | станет по модулю
    ε.
    Вычисление

    2.1 по формуле Герона
    1
    const eps = 1e-6;
    2
    var x,a,xp: Real;
    3
    begin
    4
    a := 2.1;
    5
    x := (1+a)/2;
    (* начальное приближение *)
    6
    xp := (x + a / x) / 2;
    (* первое приближение *)
    7
    while
    Abs(xp - x) > eps do
    8
    begin
    9
    xp := x;
    10
    x := (xp + a / xp) / 2;
    11
    end;
    12
    Writeln(’Dano: a = ’, a);
    13
    Writeln(’Geron(a) = ’, x);
    14
    Writeln(’sqrt(a)
    = ’, sqrt(a)); (* для проверки *)
    15
    end.
    Результат:
    Dano: a =
    2.10000000000000E+0000
    Geron(a) =
    1.44913767461894E+0000
    sqrt(a)
    =
    1.44913767461894E+0000 139

    На рисунке приведен результат работы программы при разных начальных при- ближений: слева — x
    0
    = (1 + a)/2 (четыре итерации для достижения точно- сти ε = 10
    −6
    ); справа — и x
    0
    = a (пять итераций для достижения точности
    ε = 10
    −6
    ).
    0 1
    2 3
    4 1.44 1.48 1.52 1.56
    √2.1
    Формула Герона x
    y
    0 1
    2 3
    4
    √2.1
    Формула Герона x
    1.4 1.6 1.8 2
    2.2
    y
    Рис. 6.9. Иллюстрация метода Герона для вычисления

    a, a = 2.1 (x
    0
    = (1 + a)/2, слева и x
    0
    = a, справа)
    140

    8.6.14
    Рекуррентные соотношения. Вычисление бесконечных сумм
    Формула Герона x
    i+1
    =
    1 2
    x i
    +
    a x
    i
    ,
    i = 0, 1, 2, . . . ,
    (x
    0
    > 0 — любое число).
    является рекуррентной, так как она позволяет выразить (i + 1)-й член после- довательности приближений через предыдущий, i-й.
    Рекуррентные соотношения используются при вычислениях степенных функ- ций x
    n
    = x n−1
    x,
    факториала n! = (n − 1)!n и т. п.
    Пример 6.13. Имеется сумма
    1 +
    x
    1!
    +
    x
    2 2!
    +
    x
    3 3!
    + . . . = y
    0
    + y
    1
    + y
    2
    + . . .
    (6.6)
    Выпишем члены суммирования y
    0
    = 1;
    x
    1!
    ;
    x
    2 2!
    ;
    x
    3 3!
    ;
    Видно, что каждый следующий член получается из предыдущего умножением на дробь x
    i
    . Значит для вычисления любого члена суммирования в (
    6.6
    ) можно использовать соотношения y
    0
    = 1,
    y i
    =
    x i
    y i−1
    ,
    i = 1, 2, . . .
    (6.7)
    141

    Общий вид рекуррентного соотношения
    :
    y i
    = C · y i−1
    (6.8)
    Его необходимо дополнить информацией о начальном значении y
    нач
    = C
    нач
    (6.9)
    и об интервале изменения индексов i = i нач+1
    , i нач+2
    ,. . .
    (6.10)

    Чему равно значение индекса «нач»?
    Зависит от постановки задачи: как правило, это 0 или 1.
    Формулы для определения членов суммирования в примере
    6.13
    можно запи- сать в виде (
    6.7
    )
    y
    0
    = 1,
    y i
    =
    x i
    y i−1
    ,
    i = 1, 2, . . .
    (
    6.7
    )
    или в виде y
    1
    = 1,
    y i
    =
    x i − 1
    y i−1
    ,
    i = 2, 3, . . .
    (6.11)
    Покажите, что формулы (
    6.7
    ) и (
    6.11
    ) позволяют получить один и тот же набор выражений:
    1;
    x
    1!
    ;
    x
    2 2!
    ;
    x
    3 3!
    ;
    Коэффициент C
    y i
    = C · y i−1
    (
    6.8
    )
    можно получить из общих соображений (как в примере
    6.13
    ), а можно восполь- зоваться очевидным равенством, вытекающим из (
    6.8
    )
    C =
    y i
    y i−1
    (6.12)
    142

    Используя равенство C =
    y i
    y i−1
    , получим рекуррентное соотношение для членов суммирования (
    6.6
    ):
    y
    0
    = 1;
    y
    1
    =
    x
    1!
    ;
    y
    2
    =
    x
    2 2!
    ;
    Любой член этой последовательности можно найти по формуле y
    i
    =
    x i
    i!
    Вид этой же формулы для члена y i−1
    :
    y i−1
    =
    x i−1
    (i − 1)!
    Подставим эти выражения в (
    6.12
    )
    C =
    y i
    y i−1
    =
    x i
    i!
    x i−1
    (i − 1)!
    =
    x i
    i!
    ·
    (i − 1)!
    x i−1
    =
    x · x i−1
    i(i − 1)!
    ·
    (i − 1)!
    x i−1
    =
    x i
    Итак, рекуррентная формула имеет вид y
    i
    =
    x i
    y i−1
    Для вычисления на компьютере она должна быть дополнена интервалом из- менения индексов и начальным условием:
    i = 1, 2, . . .
    y
    0
    = 1
    Доказать, что для вычисления суммы sin x = x −
    x
    3 3!
    +
    x
    5 5!

    x
    7 7!
    + . . .
    можно использовать соотношения:
    y
    0
    = x,
    y i
    = −
    x
    2 2i(2i + 1)
    y i−1
    ,
    i = 1, 2, . . .
    143

    Пример 6.14. Вычислить приближенное значение бесконечной суммы

    i=0
    x i
    i!
    = 1 +
    x
    1!
    +
    x
    2 2!
    + . . . = e x
    (6.13)
    Вычисления проводить до тех пор пока очередное слагаемое не станет мень- ше числа ε = 10
    −5
    (это слагаемое не учитывать). На печать вывести ответ и количество членов суммирования, потребовавшихся для достижения заданной точности.
    . Значение n! с увеличением n быстро растет. В частности, для любого x можно найти n такое, что n! > x n
    Решение. Были получены соотношения (см. стр.
    143
    )
    y
    0
    = 1
    (6.14)
    y i
    = y i−1
    x i
    ,
    i = 1, 2, . . .
    (6.15)
    Программа пишется (
    строго
    ) по этим соотношениям.

    i=0
    x i
    i!
    1
    const
    Eps = 1E-5;
    2
    var x, y, Sum : Real;
    3
    i
    : Integer;
    4
    begin
    5
    Write(’Введите число x [> ’);
    ReadLn(x);
    6
    i := 0;
    y := 1;
    { нач. усл. (5.14)
    }
    7
    Sum := 0;
    { для нахождения суммы }
    8
    while abs(y) >= Eps do
    9
    begin
    10
    Sum := Sum + y;
    { нахождение суммы
    }
    11
    i := i + 1;
    { i=1,2,...
    }
    12
    y := y * x / i;
    { рек. формула
    }
    13
    end;
    14
    WriteLn(’Число шагов цикла = ’, i);
    15
    WriteLn(’Сумма =’, Sum:10:6);
    16
    WriteLn(’Проверка: Exp(’, x:5:2, ’)=’, Exp(x):10:6);
    17
    end.
    144

    При выполнении программы переменные Sum, i, y последовательно принимают значения i
    0,
    1,
    2,
    . . . ;
    y
    1,
    x
    1!
    ,
    x
    2 2!
    ,
    . . . ;
    Sum
    0,
    1,
    1 +
    x
    1!
    ,
    1 +
    x
    1!
    +
    x
    2 2!
    ,
    Можно для контроля вычислений в тело цикла добавить оператор печати
    WriteLn(i, Sum:10:6, y:10:6, abs(y) >= Eps:8);
    При x = 0,1 на экран будет выведен текст
    1 1.000000 0.100000
    TRUE
    2 1.100000 0.005000
    TRUE
    3 1.105000 0.000167
    TRUE
    4 1.105167 0.000004
    FALSE
    На шаге 4 условие abs(y) >= Eps
    (4 · 10
    −6 10
    −5
    )
    нарушилось и цикл закончил работу.
    Результат:
    Число шагов цикла = 4
    Сумма =
    1.105167
    Проверка: Exp( 0.10)=
    1.105171 145

    8.6.15
    Алгоритм Евклида
    Пример 6.15. Найти НОД(m, n), используя алгоритм Евклида.
    Наибольшим общим делителем двух положительных целых чисел на- зывается наибольшее целое число, которое делит каждое из них без остатка.
    Обозначение:
    НОД(m, n); gcd(m, n) (от англ. Greatest Common Divisor)
    Пример:
    НОД(70, 105) = 35;
    НОД(45, 72) = 9.
    Рис. 6.10. Евклид. Древнегреческий математик (III в. до н.э.)
    Свойства НОД
    ,
    на которые опирается алгоритм Евклида:
    Пусть m > n.
    1

    . НОД(m, n) = НОД(m − n, n);
    2

    . НОД(m, m) = m;
    3

    . НОД(m, 0) = m.
    . Наименьшее общее кратное чисел m, n ∈ N: НОК(m, n) =
    mn
    НОД(m, n)
    Решение.
    Алгоритм Евклида:
    НОД(m, n) =









    I вариант
    II вариант m,
    m,
    m = n,
    НОД(m − n, n),
    НОД(m mod n, n), m > n,
    НОД(m, n − m). НОД(m, n mod m) m < n.
    146

    Алгоритм Евклида для вычисления НОД — I вариант
    1
    program NOD_A;
    2
    (* см. конспект *)
    Алгоритм Евклида для вычисления НОД — II вариант
    6
    (* см. конспект *)
    Результаты работы программ:
    m = 45;
    n = 72
    (количество шагов цикла одинаковое)
    I
    II
    gcd = 9
    gcd = 9
    Count = 4
    Count = 4
    m = 12;
    n = 78
    (II вариант дает выигрыш почти в 4 раза)
    gcd = 6
    gcd = 6
    Count = 7
    Count = 2
    m = 1000;
    n = 4
    (II вариант значительно эффективнее I)
    gcd = 4
    gcd = 4
    Count = 249
    Count = 1
    В обеих программах замените цикл с постусловием на цикл с предусловием.
    Проверьте, что будут выдавать обе программы при m = n. В случае непра- вильной работы программ предложите способ исправления.
    Ниже приведен еще один способ реализации алгоритма Евклида (без ис- пользования условного оператора) (см. кн.: Г. Джонстон. Учитесь программи- ровать. М., 1989. С. 276).
    147

    Алгоритм Евклида для вычисления НОД — III вариант
    1
    program NOD_C;
    2 3
    repeat
    4
    r := m mod n;
    5
    m := n;
    6
    n := r;
    7
    until n = 0;
    8
    gcd := m;
    9
    WriteLn(’gcd = ’, gcd);
    10 1) Проведите тестирование программы для всех предложенных выше случаев чисел m и n;
    2) Подсчитайте число шагов цикла.
    148

    8.7
    К вопросу об эффективности программ
    Ясность важнее эффективности; не делайте вашу программу запутанной ради экономии нескольких миллисекунд или незначительного объема памя- ти; это может дорого обойтись при изменениях программы в дальнейшем.
    Г. Джонстон
    Эффективной назовем программу, которая экономит время и память.
    Часто попытка сократить время исполнения программы приводит к увеличе- нию объема памяти (и наоборот).
    Выбор правильного алгоритма — один из ключевых вопросов оптимизации компьютерной программы. Он влияет на время исполнения программы и на объем занимаемой памяти.
    Программа реализует алгоритм на конкретном языке программирования. Один и тот же алгоритм можно реализовать различными способами, используя раз- ные языки программирования или разные свойства одного языка.
    Пример 7.1. Сравним все три варианта реализации алгоритма Евклида для значений параметров m = 1 000 000;
    n = 2
    Вид операции
    I вариант II вариант III вариант присваивания
    500000 2
    4
    аддитивные
    499999 2
    0
    мультипликативные
    0 1
    1
    сравнения
    999998 3
    1
    Общее число операций
    1999997 8
    6
    Вывод:
    программы II и III работают значительно быстрее первой.
    149
    m = 2;
    n = 1 000 000
    Вид операции
    I вариант II вариант III вариант присваивания
    500000 5
    7
    аддитивные
    499999 2
    0
    мультипликативные
    0 1
    2
    сравнения
    999998 3
    2
    Общее число операций
    1999997 8
    11
    I и II варианты не зависят от условия m > n. А число операций в случае вари- анта III зависит от условия m > n — в случае его нарушения число операций увеличивается (ср. с набором данных m = 1 000 000, n = 2).
    Подсчитайте число операций для всех предложенных выше случаев чисел m и n, т. е. для m
    n
    45 72 12 78 1000 4
    Количество вычислений, необходимых для получения значения выраже- ния, будем называть его сложностью
    (* см. конспект *)
    150

    8.8
    Оператор цикла с параметром
    Оператор цикла с параметром применяется в тех случаях, когда заранее из- вестно число шагов, необходимое для достижения результата. Во всех осталь- ных случаях необходимо применять один из операторов цикла с условием.
    for перем.
    :=
    выражение to downto do оператор имя выражение
    <цикл с параметром ::= for <параметр цикла> :=
    <список цикла> do <оператор>
    <список цикла> ::= <нач значение> to <кон значение> |
    <нач значение> downto <кон значение>
    <параметр цикла> ::= <имя>
    <нач значение> ::= <выражение>
    <кон значение> ::= <выражение>
    for i := A to B do ОПЕРАТОР
    Здесь i — счетчик (параметр, управляющая переменная) цикла;
    A и B — константы, выражения или переменные, принадлежащие тому же по- рядковому типу, что и счетчик (например, Integer, Char), причем A <= B;
    ОПЕРАТОР — оператор, представляющий собой тело цикла. Если операторов несколько, то они заключаются в операторные скобки.
    for i := A downto B do ОПЕРАТОР
    Шаг изменения параметра здесь равен −1, т. е. переменная i последователь- но принимает значения A, A-1, A-2,. . . , B и для каждого из них выполняется
    ОПЕРАТОР. Если же A < B, то ОПЕРАТОР не выполняется ни разу.
    151

    Заголовок цикла for for i := A to B
    (8.16)
    или for i := A downto B
    осуществляет ВСЕ манипуляции с переменной-счетчиком:
    — инициализацию счетчика значением начало (i := A);
    — проверку условия счетчик <= конец (i <= B) для цикла for-to-do;
    счетчик >= конец (i >= B) для цикла for-downto-do;
    — изменение значения счетчика перед каждым шагом цикла увеличение (i := i + 1) для цикла for-to-do;
    уменьшение (i := i - 1) для цикла for-downto-do.
    
    
    ¨
    ©
    Вручную изменять параметр цикла в теле цикла for нельзя.
    В случае вложенных циклов имена переменных, используемых как пара- метры цикла for, должны быть разными
    :
    Вложенные циклы for i := 1 to 5 do for j := 1 to 5 do
    WriteLn(i*j);
    152

    Особенности использования цикла с параметром for i:=A to B do S
    1. Значение счетчика i не должно модифицироваться в операторе S.
    2. Конечное значение B вычисляется один раз перед началом цикла. Измене- ние конечного значения в теле цикла никак не влияет на число итераций.
    3. В Turbo Pascal после выхода из цикла, переменная счетчик сохраняет зна- чение, присвоенное ей во время последней итерации. В стандартном Pascal значение переменной счетчик считалось неопределенным.
    Пример 8.1. Пусть переменная T отвечает за верхний предел изменения па- раметра цикла.
    Демонстрация особенностей 2 и 3 — плохая практика
    1
    program Demo;
    2
    var k, T : Integer;
    3
    begin
    4
    T := 4;
    5
    WriteLn(’k | T’);
    WriteLn(’-----’);
    6
    for k := 1 to T do
    7
    begin
    8
    WriteLn(k, ’ | ’, T);
    { печать № итерации и значения T }
    9
    T := T - 1;
    { изменяем значение T -- плохо!
    }
    10
    end;
    11
    WriteLn(’-----’);
    WriteLn(’k = ’, k);
    12
    end.
    Результат работы программы:
    k | T
    -----
    1 | 4 2 | 3 3 | 2 4 | 1
    ----- k = 4
    Особенность 2: Несмотря на то, что пара- метр T изменяется в теле цикла, цикл про- должает выполняться столько раз, сколько было сказано в заголовке (4 раза).
    Особенность 3: По окончании цикла зна- чение счетчика k равно последнему значе- нию.
    153

    Переменные-счетчики типа Char и Boolean
    Счетчики типа Char var Ch : Char;
    begin for Ch := ’A’ to ’Z’ do
    Write(Ch);
    end.
    Результат работы программы:
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    Счетчики типа Boolean var b: Boolean;
    begin
    For b := False to True do Write(b:7);
    WriteLn;
    for b := True downto False do Write(b:7);
    end.
    Результат работы программы:
    FALSE
    TRUE
    TRUE
    FALSE
    154

    8.8.1
    Примеры решения задач (29 октября 2010)
    Пример 8.2 (табулирование функций). Вывести таблицу значений функции sin x в виде x
    sin x
    −0.2 −0.1987
    −0.1 −0.0998 0.0 0.0000
    · · ·
    · · ·
    где x принимает значения −0,2; −0,1;. . . ; 0,2.
    Табулирование функции
    1
    (* см. конспект *)
    Результат работы программы:
    x
    | Sin(x)
    ----------------
    -0.2 | -0.1987
    -0.1 | -0.0998 0.0 |
    0.0000 0.1 |
    0.0998 0.2 |
    0.1987 155

    Пример 8.3. Определить наименьшее из чисел y
    k
    = k sin n +
    k n
    ,
    k = 1, 2, . . . , n.
    1 2
    3 4
    5
    -2
    -1.6
    -1.2 1
    2 3
    4 5
    -1 0
    1 2
    k k
    y k
    y k
    Тестовый пример.
    n = 5. Из левого рисунка видно, что min k
    y k
    ≈ −1,9
    при k = 3.
    n = 6. Из правого рисунка видно, что min k
    y k
    ≈ −0,1
    при k = 1.
    156

    Вычисление наименьшего из...
    (* см. конспект *)
    Результат работы программы:
    I тест (n = 5, y
    3
    ≈ −1,9.)
    Вв. натур. число [> 5
    kMin = 3
    Min = -1.894
    II тест (n = 6, y
    1
    ≈ −0,1.)
    Вв. натур. число [> 6
    kMin = 1
    Min = -0.116
    Добавление в программу соответствующих операторов печати позволит оце- нить правильность выбора значения для ответа:
    k |
    y k |
    y
    -----------
    -----------
    1 | -0.883 1 | -0.116 2 | -1.546 2 |
    0.100 3 | -1.894 3 |
    0.645 4 | -1.858 4 |
    1.497 5 | -1.397 5 |
    2.614 6 |
    3.942 157

    Пример 8.4. Дано натуральное n. Вычислить:
    n i=1
    (−1)
    i
    2i + 1
    Решение.
    i
    1 2
    3 4 . . .
    (−1)
    i
    −1 1 −1 1 . . .
    n i=1
    (−1)
    i
    2i+1 1
    (* см. конспект *)
    158

    Пример 8.5. Дано натуральное n. Вычислить n!.
    Решение. Факториалом целого положительного числа n называется выраже- ние n! = 1 · 2 · 3 · . . . · n
    (0! = 1).
    На практике данную формулу следует применять лишь при небольших значениях n.
    Факториалы больших чисел могут быть найдены при помощи формулы Стирлинга n! =
    n e
    n

    2πn
    1 +
    1 12n
    +
    1 288n
    2
    + . . .
    (8.17)
    Результат вычисления n! следует хранить в переменной вещественного типа из- за возможного переполнения при использовании целого типа данных Integer:
    для 16-разрядных систем MaxInt = 32 767:
    7! = 5 040,
    8! = 40 320 > MaxInt;
    для 32-разрядных систем MaxInt = 2 147 483 647:
    12! < MaxInt < 13!.
    n! (for-to)
    1
    program NFact;
    2
    var i, n : Integer;
    3
    fact : Real;
    4
    begin
    5
    Write(’Вв. натур. число [> ’);
    ReadLn(n);
    6
    fact := 1;
    (* 1 *)
    7
    for i := 2
    to n do fact := fact * i;
    (* 2 *)
    8
    WriteLn(n,’! = ’, fact);
    9
    end.
    n! (for-downto)
    5
    fact := n;
    (* 1 *)
    6
    for i := n-1 downto 2 do fact := fact * i;
    (* 2 *)
    159

    Пример 8.6. Дано натуральное n. Получить n!! по схеме:
    n!! =
    1 · 3 · . . . · n, если n — нечетное;
    2 · 4 · . . . · n, если n — четное.
    Решение:
    четные:
    2i (i = 1, 2, . . . , n div 2),
    нечетные: 2i − 1, i = 1, 2, . . . , n div 2+1.
    Общая формула
    2i - j,
    i = n div 2 +j,
    j =
    0, n — четное,
    1, n — нечетное.
    n!!
    1
    (* см. конспект *)
    Результаты работы программы:
    n = 6
    n = 9 2 4 6 1 3 5 7 9 6!! = 48 9!! = 945
    Вычислить n! для максимально возможного целого n (до переполнения ре- зультата n!).
    160

    Пример 8.7. Определить является ли последовательность n целых чисел воз- растающей.
    Решение. {a i
    }
    n i=1
    возрастающая, если a i−1
    < a i
    ∀ i.
    В программе необходимо предусмотреть хранение предыдущего члена после- довательности, так как получаемое с клавиатуры значение текущего члена по- следовательности будет уничтожать предыдущее.

    1   2   3   4   5   6   7   8   9
    написать администратору сайта