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

  • 0.005 = 0.0051 FALSE0.001TRUE0.0001 TRUE|x-y| =9.9999999996E-05Результат в Turbo Delphi (x,y: Real):0.005 = 0.0051

  • 0.005 = 0.0051

  • Round(4.5) =

  • — Чем программист отличается от обычного смертного — А тем, что он в состоянии ответить на вопрос, в котором уже заключён ответ.— Это как же

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


    Скачать 3.84 Mb.
    НазваниеЛекциям по курсу Информатика
    Анкорlekcii_shiryaevoy.pdf
    Дата11.07.2018
    Размер3.84 Mb.
    Формат файлаpdf
    Имя файлаlekcii_shiryaevoy.pdf
    ТипЛекция
    #19640
    страница3 из 9
    1   2   3   4   5   6   7   8   9
    1 0.05 = 0.0501?
    2
    FALSE
    3 0.001
    TRUE
    4 0.0001 TRUE
    5 0.00001 FALSE
    6
    |x-y| =
    9.9999999975E-05
    Результат в Turbo Delphi:

    1 0.05 = 0.0501?
    2
    FALSE
    3 0.001
    TRUE
    4 0.0001 TRUE
    5 0.00001 FALSE
    6
    |x - y| =
    9.99999999999959E-0005 38

    Значения выражения |x − y| разные!
    Тип
    Реализация языка
    Точность
    Формат
    Real
    Borland Pascal 7.0 11–12 знаков 6 байт
    Real
    Delphi
    15–16 знаков 8 байт
    Real48 Delphi
    11–12 знаков 6 байт
    Результат в Turbo Delphi при описании var x, y : Real48;
    |x - y| =
    9.99999999748979E-0005
    Результат в Borland Pascal при описании var x, y : Real;
    |x-y| =
    9.9999999975E-05.
    39

    Пример 2.
    Сравним два числа x = 0,005; y = 0.0051. Обратим внимание, что их разность |x − y| = 0.0001
    Сравнение вещественных чисел
    1
    var x, y: Real;
    2
    begin
    3
    x := 0.005; y := 0.0051;
    4
    Writeln(x:5:3, ’ = ’, y:6:4, ’? ’);
    5
    Writeln(x = y);
    6
    Writeln(’0.001
    ’, abs(x - y) <= 0.001);
    7
    Writeln(’0.0001 ’, abs(x - y) <= 0.0001);
    8
    Writeln(’|x-y| = ’, abs(x - y));
    9
    end.
    Результат в Borland Pascal 7.0:

    0.005 = 0.0051?
    FALSE
    0.001
    TRUE
    0.0001 TRUE
    |x-y| =
    9.9999999996E-05
    Результат в Turbo Delphi (
    x,y: Real
    ):

    0.005 = 0.0051?
    FALSE
    0.001
    TRUE
    0.0001 FALSE
    |x - y| =
    1.00000000000000E-0004
    Результат в Turbo Delphi (
    x,y: Real48
    ):

    0.005 = 0.0051?
    FALSE
    0.001
    TRUE
    0.0001 TRUE
    |x - y| =
    9.99999999962142E-0005 40

    Типы данных в Delphi делятся на две категории:
    Основная (фундаментальная)
    Общая

    Формат и диапазон значений типов зависит от разрядности про- цессора и используемой ОС?
    НЕТ
    ДА
    Integer
    Real
    Целые типы данных (кол-во байт, ± — знаковый тип)
    Тип
    Borland Pascal 7.0 Delphi
    ShortInt
    1 (±)
    1 (±)
    Integer
    2 (±)
    4 (±)
    Smallint

    2 (±)
    LongInt
    4 (±)
    4 (±)
    Byte
    1 1
    Word
    2 2
    Вещественные типы данных (кол-во байт)
    Тип
    Borland Pascal 7.0 Delphi
    Real
    6 8
    Single
    4 4
    Real48

    6
    Double
    8 8
    Extended
    10 10 41

    Операции над вещественными числами
    (продолжение)
    +
    -
    *
    /
    Trunc
    Round
    Синтаксис функций Trunc и Round:
    function Trunc(X: Real): Longint;
    function Round(X: Real): Longint;
    Примеры:
    Trunc(3.14) = 3,
    Trunc(-3.64) = −3,
    Trunc(5.7) = 5.
    Round(3.14) = 3,
    Round(-3.64) = −4,
    Round(5.7) = 6.
    §
    ¦
    ¤
    ¥

    Round(4.5) = ?
    Borland Pascal 7:
    Round(3.5) = 4,
    Round(4.5) = 5,
    Round(-3.5) = −4,
    Round(-4.5) = −5.
    Delphi («банковское округление»):
    Round(3.5) = 4,
    Round(4.5) = 4,
    Round(-3.5) = −4,
    Round(-4.5) = −4.
    42

    Пример БНФ.
    Синтаксис конструкции <число без знака>:
    < число без знака > ::= < целое без знака > |
    < вещественное без знака >
    < целое без знака > ::= < цифра > {< цифра >}
    < цифра > ::= 0|1|2|3|4|5|6|7|8|9
    < вещественное без знака > ::=
    <целое без знака>.<цифра> {<цифра>} |
    <целое без знака>.<цифра> {<цифра>} E <порядок> |
    <целое без знака> E <порядок>
    < порядок > ::= < целое без знака > |
    < знак > < целое без знака >
    < знак > ::= +|-
    Пример БНФ.
    Синтаксис конструкции <число>:
    < число
    > ::= < целое число > | < вещественное число >
    < целое число > ::= [< знак >] < целое без знака >
    < вещественное число > ::=
    [< знак >] < вещественное без знака >
    43

    4.1.7
    Символьный тип (Char)
    Синтаксис конструкции < символ >:
    < символ > ::= < буква >|< цифра > | ( | ) | [ | ] | + | . . .
    Значениями символьного типа Char являются элементы конечного и упорядо- ченного множества символов.
    < символьная константа > ::= ’< символ >’
    ASCII (American Standard Code for Information Interchange), см. стр.
    165
    В компьютере переменная типа Char занимает один байт памяти.
    Операции над переменными типа Char:
    чтение с клавиатуры, вывод на экран, сравнение между собой.
    Пример. Пусть имеется описание c: Char c := ’*’;
    c := ’A’;
    c := ’ф’;
    c := ’1’;
    Пример. Использование ASCII-кода символа:
    c := #65; { код символа A }
    Writeln(c, ’R’, c);
    Результат.
    ARA
    При выполнении программы переменная типа Char вводится без кавычек.
    Write(’Input symbol [> ’);
    Readln(c);
    Результат.
    Input symbol [> y
    Пример. Значение переменной c — один символ «кавычка»:
    c := ’’’’;
    Writeln(c, ’a’, c);
    Результат.
    ’a’
    В рамках типа Char десятичные цифры упорядочены в соответствии с их чис- ленными значениями (например: ’5’<’6’). Буквы упорядочены в алфавитном порядке (например: ’A’<’B’).
    44

    4.1.8
    Строковый тип (string)
    Тип данных string предназначен для хранения последовательности символов
    (элементов типа Char). Строка символов должны быть заключена в апострофы:
    < строковая константа > ::= ’{< символ >}’
    Пример. Пусть имеется описание s: string s := ’кошка Масяня’;
    s := ’1234’;
    Строка ’1234’
    число 1234
    Над строкой ’1234’ нельзя выполнять арифметических операций.
    Число элементов в строке называется длиной строки.
    Максимальная длина строки — 255 символов. Каждый символ строки занимает
    1 байт памяти.
    Область памяти, выделяемая под строку символов, всегда на 1 байт больше запрашиваемой при объявлении переменной (1 байт отводится дополнительно на хранение информации о длине строки).
    байт длины символ символ символ . . .
    Операции над переменными типа string:
    ввод с клавиатуры, вывод на экран, конкатенация (операция сцепления строк), сравнение строк между собой.
    Строки сравниваются в лексикографическом порядке. Например, строки считаются равными, если они имеют одинаковую длину и коды всех символов с одинаковыми индексами совпадают:
    Writeln(’ab’ = ’ab’);
    Writeln(’ab’ = ’Ab’);
    Writeln(’ab’ = ’ba’);
    Writeln(’aba’ = ’ab’);
    Writeln(’aba’ > ’ab’);
    TRUE
    FALSE
    FALSE
    FALSE
    TRUE
    Пример. Пусть имеется описание s: string s := ’кошка’;
    s := s + ’ Масяня’;
    кошка Масяня
    45

    4.1.9
    Логический тип (Boolean)
    Беседуют два программиста.

    — Чем программист отличается от обычного смертного?
    — А тем, что он в состоянии ответить на вопрос, в котором уже заключён ответ.

    — Это как же?
    — Ну, например, ответь на вопрос: сколько будет 2 * 2 = 4?
    — TRUE.
    True (истина) и False (ложь)
    False < True
    Ord(False) = 0
    Ord(True) = 1
    Succ(False) = True
    Pred(True) = False
    Переменные типа Boolean занимают 1 байт памяти.
    Операции над переменными типа Boolean:
    §
    ¦
    ¤
    ¥
    Вводить клавиатуры с данные логического типа нельзя.
    вывод на экран, операции сравнения, логические операции (and, or, not, xor).
    Теоретически значения Succ(True) и Pred(False) считаются неопреде- ленными, но в Turbo Pascal:
    Succ(True) = True
    Pred(False) = True
    Логические операции
    Операция
    Действие not (отрицание, операция «НЕ»)
    инверсия or (сложение, операция «ИЛИ»)
    дизъюнкция and (умножение, операция «И»)
    конъюнкция xor исключающее «ИЛИ»
    Логические операции дают логические результаты:
    not
    False = True;
    not
    True = False;
    46

    False and
    False
    = False
    False and
    True
    = False
    True and
    False
    = False
    True and
    True
    = True
    False or
    False = False
    False or
    True
    = True
    True or
    False = True
    True or
    True
    = True
    False xor
    False = False
    False xor
    True
    = True
    True xor
    False = True
    True xor
    True
    = False
    4.1.10
    Интервальный тип (тип-диапазон)
    Min..Max;
    Min, Max — левая и правая границы диапазона. Диапазон значений задается на основе любого порядкового типа, за исключением вещественного.
    Примеры правильных диапазонов:
    1..MaxInt
    ’A’..’Z’
    ’R’..’z’
    -15..15
    Примеры неправильных диапазонов:
    Диапазон
    Тип ошибки
    15..-15
    левая граница диапазона больше правой
    1.5..2.5
    границы — не порядкового типа
    0..’9’
    разные типы границ диапазона
    ’ACE’..’HAT’ границы — не порядкового типа
    Операции над переменными типа диапазон:
    те же, что и для базового типа, т. е. типа, на основе которого создан диапазон.
    47

    4.2
    Функциия SizeOf
    Пример. Использование функции
    SizeOf()
    :
    1
    WriteLn(’SizeOf(Boolean) = ’, SizeOf(Boolean));
    2
    WriteLn(’SizeOf(Char)
    = ’, SizeOf(Char));
    3
    WriteLn(’SizeOf(Integer) = ’, SizeOf(Integer));
    4
    WriteLn(’SizeOf(Real)
    = ’, SizeOf(Real));
    5
    WriteLn(’SizeOf(’’cat’’) = ’, SizeOf(’cat’));
    6
    WriteLn(’SizeOf(32)
    = ’, SizeOf(32));
    позволит определить объем памяти, выделяемый на данные (в байтах).
    Результат.
    SizeOf(Boolean) = 1
    SizeOf(Char) = 1
    SizeOf(Integer) = 4
    SizeOf(Real) = 8
    SizeOf(’cat’) = 4
    SizeOf(32) = 1
    Какая среда программирования использовалась для получения данного ре- зультата — Borland Pascal или Delphi? Для каких строк программы будет на- блюдаться различие в результатах?
    48

    Глава 5
    Структура программы на языке Pascal заголовок блок
    БНФ:
    < программа > ::= [< заголовок программы >]
    < блок >
    5.1
    Заголовок программы
    БНФ:
    < заголовок программы > ::= program
    < имя >;
    Примеры заголовков:
    program Perimetr;
    program p3_1;
    5.2
    Раздел для подключения модулей
    < раздел подкл. модулей > ::=
    [ uses
    < имя модуля >{, < имя модуля >}; ]
    49
    заголовок раздел uses блок
    Пример использования раздела uses program DemoUnit;
    uses Crt, Math0;
    begin
    ClrScr;
    (* процедура из станд. модуля Crt *)
    Calculate; (* процедура из нестанд. модуля Math0 *)
    end.
    5.3
    Оператор присваивания
    Оператор присваивания
    < оператор присваивания > ::= < имя переменной > := < выражение > |
    < имя функции > := < выражение >
    <имя переменной> ::= < имя >
    <имя функции> ::= < имя >
    Примеры операторов присваивания
    Sum := Sum + Value;
    NewX := X;
    NewX := -X;
    X := -X;
    Значение переменной (функции), стоящей слева от знака :=, должно совпадать со значением выражения, стоящего справа от знака :=.
    Пример 3.1. Пусть в программе описаны переменные var R : Real;
    I : Integer;
    C : Char;
    S : String;
    B : Boolean;
    50

    Верные операторы присваивания:
    1
    R := I;
    2
    I := Round(R);
    3
    C := ’2’;
    4
    S := С + С;
    5
    B := True;
    6
    B := ’3’ < ’2’;
    Неверные операторы присваивания:
    1
    I := R;
    2
    I := Pi * 3;
    3
    I := 4 / 2;
    4
    C := ’2’ + ’2’;
    5
    C := S;
    6
    B := ’False’;
    Таблица приоритетов
    Очередность выполнения операций Операции
    1
    not, унарный +, унарный -
    2
    *, /, div, mod, and
    3
    +, -, or, xor
    4
    in, >, <, =, <>, >=, <=
    Подряд идущие операции одного приоритета вычисляются в последовательно- сти «слева направо».
    Бинарные операции требуют двух операндов:
    a + b;
    B1 or B2.
    Унарные операции требуют одного операнда:
    -b;
    not B1.
    Все унарные операции (+, -, not) имеют высший (первый) приоритет.
    51

    Пример.
    Выражение
    3 *
    c +
    2 *
    (x
    + pi
    / 2);
    Очередность
    3 5
    4 2
    1 5.4
    Функции
    Функция
    самостоятельный элемент программы, вычисляющий един- ственный результат (возвращаемое значение).
    При вызове функции указывается имя функции и список фактических пара- метров, заключенный в скобки:
    y := sin(x);
    z := Pi;
    y := sin(x + y);
    Вызов функции не может быть самостоятельным оператором, потому что воз- вращаемое значение нужно куда-то записывать.
    Вызов функции может указываться либо в качестве аргумента оператора про- цедуры
    (например, печати):
    Writeln( sin(pi/2) );
    либо в составе арифметического выражения
    :
    y := Exp(n * Ln(x));
    //
    y := x^n
    Замечание: Вызов любой функции имеет более высокий приоритет, чем все внешние относительно этого вызова операции. Выражения, являющиеся аргу- ментами вызываемой функции, вычисляются в момент вызова.
    Пример.
    Выражение
    - sin(x +
    pi)
    *
    (x
    + 2);
    Очередность
    3 2
    1 5
    4
    
    
    ¨
    ©
    Побочный эффект функции:
    возвращение функцией более одного значения.
    52

    5.5
    Операторы процедур
    Оператор процедуры запускает на выполнение некоторую подпрограмму, зада- ющую последовательность действий, составляющих суть процедуры.
    5.5.1
    Процедуры ввода
    Процедура ввода Read
    Read(переменная1,..., переменнаяN);
    переменная1,..., переменнаяN называются параметрами процедуры.
    При выполнении операторов ввода переменным присваиваются значения ис- ходных данных.
    Значения вводимых переменных (входной поток)
    должны соответствовать типам переменных
    , указанным в разделе описания переменных.
    Пример 5.1. Пусть описаны переменные:
    var c1, c2, c3 : Char;
    r, s
    : Real;
    n
    : Integer;
    Имеется оператор ввода:
    Read(c1, c2, c3, r, s, n)
    (5.1)
    Пример ввода пользователем корректных данных:
    (Символом
    _
    обозначено положение курсора)
    ABC 1.5 5 25_
    В программе имеются вышеописанные переменные и оператор ввода
    Read(c1, c2, c3, r, n)
    Неопытный пользователь при вводе данных допустил досадные ошибки
    F O X 1.5 5_
    Исправьте предложенный набор данных.
    53

    Процедура ввода Readln
    ReadLn(переменная1,..., переменнаяN);
    Неверное использование процедуры ввода
    Read(a);
    { a: Integer }
    Write(’Continue? (y/n) ’);
    ReadLn(d); { d: Char }
    Writeln(’d = ’, d);
    Результат: (
    ответ не печатается!
    )
    3
    Continue? (y/n) [> d =
    Процедура ввода Readln без параметров
    ReadLn;
    Клавиша — код #13#10
    Ожидание нажатия Enter
    1
    program Demo;
    2
    begin
    3 4
    ReadLn; (* возврат в редактор после нажатия клавиши Enter *)
    5
    end.
    54

    5.5.2
    Процедуры вывода
    Процедуры вывода Write и Writeln
    Write(выражение1,..., выражениеN);
    Writeln(выражение1,..., выражениеN);
    Процедура вывода без параметров
    Writeln;
    Демонстрация работы процедуры вывода
    1
    var Name: string;
    2
    begin
    3
    Write(’Введите имя [> ’);
    Readln(Name);
    4
    WriteLn(’Привет, ’, Name);
    5
    end.
    На экране: (Символом
    _
    обозначено положение курсора)
    Введите имя [> Ваня
    Привет, Ваня
    _
    Демонстрация работы процедуры вывода
    4
    Write(’Привет, ’, Name);
    На экране:
    Введите имя [> Масяня
    Привет, Масяня_
    55

    Использование форматного вывода
    Разные способы вывода
    1
    var i: Integer;
    2
    begin
    3
    for i := -5 to 5 do
    4
    Writeln(i, ’ ’, Sin(i), ’ ’, i*i);
    5
    //
    Writeln(i:2, Sin(i):8:3, i*i:4);
    6
    end.
    На экране:
    Использование оператора 4
    -5 9.58924274663138E-0001 25
    -4 7.56802495307928E-0001 16
    -3 -1.41120008059867E-0001 9
    -2 -9.09297426825682E-0001 4
    -1 -8.41470984807897E-0001 1 0
    0.00000000000000E+0000 0 1
    8.41470984807897E-0001 1 2
    9.09297426825682E-0001 4 3
    1.41120008059867E-0001 9 4 -7.56802495307928E-0001 16 5 -9.58924274663138E-0001 25
    Использование оператора 5
    -5 0.959 25
    -4 0.757 16
    -3
    -0.141 9
    -2
    -0.909 4
    -1
    -0.841 1
    0 0.000 0
    1 0.841 1
    2 0.909 4
    3 0.141 9
    4
    -0.757 16 5
    -0.959 25
    Процедура вывода Write (WriteLn) с указанием формата вывода
    1
    Write(выражение1:n1:m1, выражение2:n2:m2, ...);
    2
    Write(выражение1:n1, выражение2:n2, ...);
    n1, n2 — общее кол-во позиций в числах;
    m1, m2 — кол-во позиций в дробной части этих чисел.
    Оператор вида 1 применим только к данным вещественного типа.
    56

    Пример 5.2. Демонстрация форматного вывода данных разного типа.
    Управление форматом вывода program Test;
    var a : Real;
    n : Integer;
    b : Boolean;
    begin a := 23.746;
    n := 145;
    b := n = 146;
    WriteLn(’a=’,a,
    ’ n=’,n);
    { 1 }
    WriteLn(’a=’,a:7:3, ’ n=’,n:4); { 2 }
    WriteLn(’a=’,a:11,
    ’ n=’,n:3); { 3 }
    WriteLn(’a=’,a:10);
    { 4 }
    WriteLn(’a=’,a:8);
    { 5 }
    WriteLn(’a=’,a:5);
    { 6 }
    WriteLn(’b=’,b:6);
    { 7 }
    end.
    Результат:
    1) a=␣2.3746000000E+01␣n=145 2) a=␣23.746␣n=␣145 3) a=␣2.3746E+01␣n=145 4) a=␣2.375E+01 5) a=␣2.4E+01 6) a=␣2.4E+01 7) b=␣FALSE
    57

    Глава 6
    Линейные алгоритмы
    Линейный алгоритм
    — алгоритм, в котором отдельные предписания вы- полняются в порядке записи, независимо от значений исходных данных и промежуточных результатов.
    Рис. 0.1. Размещение блоков в ли- нейном алгоритме
    Значения фигур в блок-схеме:
    скругленный прямоугольник
    — тер- минатор; блок начала/конца алгорит- ма;
    параллелограмм — блок ввода/вывода данных;
    прямоугольник — процесс; арифметиче- ский блок (обработка данных).
    58

    6.1
    Реализация линейных алгоритмов
    Пример 1.1. Дан треугольник со сторонами a, b, c. Вычислить периметр и площадь треугольника.
    Решение. Формула Герона: S =
    p(p − a)(p − b)(p − c), где p — полупериметр треугольника.
    Вычисление площади треугольника (Pascal)
    1
    program Triangle;
    2
    uses Crt;
    3
    var a, b, c,
    (* стороны треугольника *)
    4
    p,
    (* периметр *)
    5
    S
    : Real; (* площадь треугольника *)
    6
    begin
    7
    ClrScr;
    (* процедура очистки экрана *)
    8
    Write(’Введите длины сторон треугольника [> ’);
    9
    ReadLn(a, b, c);
    10
    p := a + b + c;
    (* периметр треугольника *)
    11
    WriteLn(’Периметр треугольника равен ’, p:5:2);
    12
    p := p / 2;
    (* полупериметр треугольника *)
    13
    S := Sqrt(p * (p - a) * (p - b) * (p - c));
    14
    WriteLn(’Площадь треугольника равна ’, S:5:2);
    15
    ReadLn;
    16
    end.
    Консольные приложения в Delphi program Triangle;
    {$APPTYPE CONSOLE}
    uses
    SysUtils;
    var a, b, c,
    // стороны треугольника end.
    59

    Пример № 1 плохого оформления кода program Triangle;
    var a,b, c, p,
    S:Real;
    begin
    Write(’Введите длины сторон треугольника [>’);ReadLn(a,b,c);
    p:=a+b+c;WriteLn(’Периметр треугольника равен’,p:5:2);p:=p/2;
    S:= Sqrt (p*(p-a)*(p-b)*(p-c));
    WriteLn(’Площадь треугольника равна’,S:5:2);ReadLn;end.
    Пример № 2 плохого оформления кода program Triangle;
    var a, b, c, p, S: Real;
    begin
    Write(’Введите длины сторон треугольника [>’);
    ReadLn(a,b,c);
    p:=a+b+c;
    WriteLn(’Периметр треугольника равен’,p:5:2);
    p:=p/2;
    S:= Sqrt (p*(p-a)*(p-b)*(p-c));
    WriteLn(’Площадь треугольника равна’,S:5:2);
    ReadLn;
    end.
    60

    Еще один нехороший пример
    1
    program Triangle;
    2 3
    WriteLn(’S = ’, Sqrt(p * (p - a) * (p - b) * (p - c));
    Рис. 1.2. Действие оператора печати
    Рис. 1.3. Действие оператора присваивания
    61

    6.2
    Проверка правильности программы
    Прежде, чем использовать созданную программу для решения задачи, ее необ- ходимо отладить.
    Напомним (см. стр.
    14
    ), что отладка программы является самым трудоемким этапом при решении задачи на компьютере и занимает около 60 % всего време- ни, затрачиваемого на решение задачи.
    Отладка
    — работа по обнаружению и устранению ошибок программиро- вания, а также доказательство правильности программы.
    . Конечно, ошибки могут быть внесены и на математическом, и на алго- ритмическом уровнях процесса решения задачи. Сейчас нас интересует только компьютерный уровень.
    Ошибки бывают синтаксические и семантические (смысловые).
    Синтаксические ошибки
    Могут возникнуть из-за плохого знания языка программирования или из-за небрежного ввода кода с клавиатуры. Выявляются на стадии компиляции про- граммы. Компилятор выдает сообщение о типе и месте ошибки.
    Рис. 2.4. Сообщение о синтаксической ошибке в Delphi
    62

    Семантические ошибки
    К семантическим ошибкам относятся:
    — ошибки, связанные с недостаточным знанием программистом языка про- граммирования;
    — логические ошибки и ошибки кодирования;
    — ошибки при выполнении синтаксически правильных операторов (например,
    деление на нуль или извлечение квадратного корня из отрицательного числа);
    — ошибки, вызванные неверными данными.
    Пример 2.1 (неверная программа). Даны целые числа a, b. Значение пере- менной b изменить по правилу:
    b =
    b div a, a = 0;
    a,
    a = 0.
    Например,

    a b
    Ответ
    1 3
    16 5
    2 0
    16 0
    Семантически неверная программа № 1 (Delphi, BP7.0)
    1
    var a, b : Integer;
    2
    begin
    3
    a := 3;
    b := 16;
    // (1 вариант)
    4
    { a := 0;
    b := 16;} // (2 вариант)
    5
    Writeln(a, ’ ’, b);
    6
    if a <> 0 then b := b div a else;
    7
    b := a;
    8
    Writeln(’b = ’, b);
    9
    end.
    Ошибка:
    неверное использование конструкции if-then-else.
    Первый набор входных данных:
    3 16
    b = 3
    Второй набор входных данных:
    0 16
    b = 0 63

    Семантически неверная программа № 2 (Delphi, BP7.0)
    1 2
    begin
    3
    b := 16;
    4
    if a <> 0 then b := b div a else;
    5
    b := a; ...
    6
    end.
    Ошибки:
    1) неверное использование конструкции if-then-else;
    2) неопределенное входное данное a.
    Delphi:
    b = 2147348480
    BP 7.0:
    b = 0
    Семантические ошибки самые неприятные — они могут проявиться на любом этапе решения задачи (от постановки задачи до сдачи готовой программы за- казчику).
    64

    Правильной будем называть программу, которая успешно прошла этап трансляции (в ней нет синтаксических ошибок) и для всех возможных вход- ных данных обеспечивает получение правильного результата.
    Программа (алгоритм)
    не является правильной
    , если для некоторых исходных данных она дает неправильные результаты, сбои или не дает ни- каких результатов вообще.
    Для проверки правильности программ используют формальную верификацию тестирование доказательство с помощью фор- мальных методов правильности или неправильности алгоритмов и программ в соответствии с фор- мальным описанием их свойств.
    проверка того, что программа ре- шает именно поставленную зада- чу и выдает правильные результа- ты для любого набора возможных входных данных
    1
    Тестирование доказывает наличие ошибок,
    но не их отсутствие
    Эдсгер Дейкстра — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии
    Тестирование программы проводят:

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

    в экстремальных условиях
    : используют входные данные, являющиеся
    «пограничными» для данной программы.
    Для каждой программы экстремальные данные индивидуальны. Как пра- вило, это очень малые или очень большие числа; числа, близкие к грани- цам интервала области определения или множества значений функции;

    в исключительных условиях
    : используют входные данные, значения которых лежат вне области определения функции; при выходе за границы массивов и т. п.
    65

    Тестирование программы (пример
    1.1
    )
    В линейном алгоритме нет возможности обходить подводные камни типа «деле- ние на нуль» или «вычисление корня из отрицательного числа», поэтому будем проводить тестирование кода из примера
    1.1
    только в нормальных условиях.
    Для решения примера
    1.1
    , т. е. нахождения площади треугольника по трем сторонам, было предложено использовать формулу Герона:
    S =
    p(p − a)(p − b)(p − c),
    где p — полупериметр треугольника.
    Тестовый пример: при a = 3, b = 4, c = 5 полупериметр треугольника p =
    a + b + c
    2
    = 6,
    =⇒
    S =
    6(6 − 3)(6 − 4)(6 − 5) = 6.
    Подставив эти данные (a = 3, b = 4, c = 5) в качестве входных при выполнении программы, должны получить ответ 6.
    Результат работы программы:
    Введите длины сторон треугольника [> 3 4 5
    Периметр треугольника равен 12.00
    Площадь треугольника равна 6.00
    Для тестирования алгоритма (программы) в нормальных условиях выбираются такие входные данные, для которых известен результат. Далее алгоритм (про- грамма) выполняется с этими выбранными данными и полученный результат сравнивается с заранее известным правильным результатом.
    66

    ?:
    Удачен ли набор данных a = 3,
    b = 4,
    c = 5
    для тестирования программы из примера
    1.1
    ?
    С точки зрения проверки на наличие ошибок кодирования —
    НЕТ
    . При выбранных значениях сторон треугольника совпали значения полупериметра и площади треугольника:
    p = S = 6.
    Если программист, например, ошибся в операторе вывода (см. программу из примера
    1.1
    ):
    14
    WriteLn(’Площадь треугольника равна ’, S:5:2);
    указав вместо S имя переменной p, то этот тестовый пример не позволит обна- ружить ошибку.
    С точки зрения проверки алгоритма вычисления —
    ДА
    , так как позво- ляет проверить правильность вычислений — треугольник с такими сторонами является прямоугольным
    3 2
    + 4 2
    = 5 2
    и его площадь можно вычислить еще и по формуле
    S =
    1 2
    ab =
    3 · 4 2
    = 6.
    67

    Одним из способом выявления семантических ошибок является использование трассировочных таблиц.
    Трассировка
    — это процесс тщательной пошаговой имитации на бумаге выполнения алгоритма компьютером.
    Трассировочная таблица содержит указание значений переменных в ви- де таблицы, которые устанавливаются после выполнения каждой команды присваивания или ввода.
    Пример 2.2. Обменять значениями переменные a и b.
    Обмен-1 с использованием третьей переменной
    1
    var x, y, z : Integer;
    2
    begin
    3
    x := 6;
    4
    y := 7;
    5
    Writeln(x, y:3);
    6
    z := x;
    7
    x := y;
    8
    y := z;
    9
    Writeln(x, y:3);
    10
    end.
    Трассировочная таблица:
    Команда x
    y z
    x := 6;
    6


    y := 7;
    6 7

    Writeln(x, y:3);
    6 7

    z := x;
    6 7
    6
    x := y;
    7 7
    6
    y := z;
    7 6
    6
    Writeln(x, y:3);
    7 6
    6 68

    Обмен-2 без использования третьей переменной
    1
    var x, y : Integer;
    2
    begin
    3
    x := 6;
    4
    y := 7;
    5
    Writeln(x, y:3);
    6
    y := x + y;
    7
    x := y - x;
    8
    y := y - x;
    9
    Writeln(x, y:3);
    10
    end.
    Трассировочная таблица:
    Команда x
    y x := 6;
    6

    y := 7;
    6 7
    Writeln(x, y:3);
    6 7
    y := x + y;
    6 13
    x := y - x;
    7 13
    y := y - x;
    7 6
    Writeln(x, y:3);
    7 6
    . Данный алгоритм опасен для систем, которые перехватывают переполне- ние целого и прерывают выполнение программы.
    69

    Обмен при помощи исключающего ИЛИ
    (англ. Xor swap algorithm,
    кзор-своп алгоритм) — алгоритм, который использует операцию исключа- ющего ИЛИ (XOR) для обмена значений переменных, имеющих один и тот же тип данных без использования временной переменной.
    В основе алгоритма лежит свойство XOR: A XOR A = 0 для всех A.
    Обмен-3 с использованием побитовых операций
    1
    var x, y : Integer;
    2
    begin
    3
    x := 6;
    4
    y := 7;
    5
    Writeln(x, y:3);
    6
    x := x xor y;
    7
    y := x xor y;
    8
    x := x xor y;
    9
    Writeln(x, y:3);
    10
    end.
    Трассировочная таблица:
    Команда x
    y x := 6;
    6

    y := 7;
    6 7
    Writeln(x, y:3);
    6 7
    x := x xor y;
    1 7
    y := x xor y;
    1 6
    x := x xor y;
    7 6
    Writeln(x, y:3);
    7 6
    70

    6.3
    Решение задач
    Пример 3.1. Вычислить число π по формуле:
    π = 16 arctg k
    1
    − 4 arctg k
    2
    ,
    (3.1)
    где k
    1
    =
    1 5
    , k
    2
    =
    1 239
    . В ответе выдавать семь знаков после запятой.
    Нахождение π
    1
    program NumberPi;
    2
    var k1, k2, Pi2 : Real;
    3
    begin
    4
    k1 := 1/5;
    k2 := 1/239;
    5
    Pi2 := 16 * arctan(k1) - 4 * arctan(k2);
    6
    WriteLn(’My Pi = ’, Pi2:9:7);
    7
    WriteLn(’
    Pi = ’, Pi:9:7);
    8
    end.
    Результат работы программы:
    My Pi = 3.1415927
    Pi = 3.1415927
    π ≈ 3,14159265336
    . Значение π можно определить и по формуле arctg 1 =
    π
    4 71

    Пример 3.2. Даны x, y. Вычислить u, v, если:
    u =

    e x+y
    ,
    v = −
    ln(e x+y
    + e − 1)
    2

    e x+y
    (3.2)
    Решение. Обозначим t = e x+y
    — выражение, трижды повторяющееся в (
    3.2
    ).
    Вычисление по формулам program CalcUV;
    var x, y, u, v, t: Real;
    begin x := -2;
    y := 2;
    (* значения для теста *)
    t := Exp(x + y);
    u := Sqrt(t);
    v := -Ln(t + Exp(1) - 1) / 2 / u;
    WriteLn(’u = ’, u:5:2);
    WriteLn(’v = ’, v:5:2);
    end.
    Для тестирования программы выберем значения x = −2, y = 2, подставим их в выражения для u и v:
    u =

    e
    −2+2
    =

    e
    0
    =

    1 = 1 ⇒ u = 1,
    v = −
    ln(e
    −2+2
    + e − 1)
    2

    e
    −2+2
    = −
    ln(e
    0
    + e − 1)
    2

    e
    0
    = −
    ln e
    2
    = −
    1 2
    ⇒ v = −0,5.
    Результат работы программы:
    u = 1.00
    v = -0.50 72

    Пример 3.3. Записать двузначное число в обратном порядке (34 → 43).
    Решение. Известно, что любое десятичное n-значное целое число A можно представить в виде суммы:
    A = a n−1
    · 10
    n−1
    + a n−2
    · 10
    n−2
    + . . . + a
    2
    · 10 2
    + a
    1
    · 10 + a
    0
    ,
    (3.3)
    где a i
    (i = 0, . . . , n − 1) — коэффициенты (целые числа от 0 до 9) при соответ- ствующих степенях числа десять. Например,
    273 = 2 · 10 2
    + 7 · 10 + 3.
    Перестановка цифр в числе
    1
    program Ex1_5;
    2
    var x, y : Integer;
    3
    begin
    4
    x := 34;
    5
    y := (x mod 10) * 10 + x div 10;
    6
    WriteLn(’x = ’, x);
    7
    WriteLn(’y = ’, y);
    8
    end.
    Результат работы программы:
    x = 34
    y = 43 73

    6.4
    Арифметическое переполнение
    Арифметическое переполнение
    (в компьютерной арифметики) — си- туация, когда при арифметическом действии результат становится больше максимально возможного значения для переменной, использующейся для хранения результата.
    Компьютерная арифметика имеет особенности из-за того, что целочисленная арифметика происходит в ограниченном числе разрядов. При выполнении ариф- метических действий с целыми числами могут возникнуть следующие ситуа- ции:
    • старшие (левые) цифры результатов, выходящие за отведенное количество разрядов оказываются утерянными;
    Представьте число 200 100
    = 1 1001 0000 2
    в 8 разрядах со знаком!
    • при сложении или умножении двух положительных чисел, имеющих зна- ковое представление, можно получить отрицательное число, если в резуль- тате сложения (умножения) в левом знаковом бите окажется единица.
    Пример 4.1. Выполним сложение
    100 10
    + 51 10
    в знаковом 8-разрядном представлении. В этом представлении числа 100 10
    и
    51 10
    имеют вид:
    100 10
    = 0111 0100 2
    51 10
    = 0011 0011 2
    0111 0100 2
    + 0011 0011 2
    = 1001 0111 2
    Знаковый разряд (самая левая цифра) указывает на то, что в 8 разрядах за- писано отрицательное число.
    Напомним, что все отрицательные числа в машине представляются дополни- тельным кодом и для восстановления десятичного значения этого отрицатель- ного числа надо воспользоваться алгоритмом получения исходного числа по его дополнительному коду. В результате получим число
    −105
    !
    74

    Пример 4.2. Один из способов восстановления модуля исходного десятичного отрицательного числа по его дополнительному коду:
    1) получение обратного кода (из дополнительного кода вычтем 1):
    1001 0111 − 1 = 1001 0110 2) получение модуля отрицательного числа (инвертирование полученного ко- да):
    1001 0110 → 0110 1001 3) перевод из 2-чной системы счисления в 10-чную:
    0110 1001 2
    = 2 6
    + 2 5
    + 2 3
    + 1 = 105
    Ответ: −105 75

    Пример 4.3 (
    проблема переполнения
    ). Сложение двух больших целых чисел.
    Решение.
    Неверный алгоритм
    1
    program DemoOverfull;
    2
    var i1, i2 : Integer;
    3
    S
    : Real;
    4
    begin
    5
    i1 := High(Integer);
    i2 := MaxInt;
    6
    S := i1 + i2;
    7
    WriteLn(’i1
    = ’, i1);
    WriteLn(’i2
    = ’, i2);
    8
    WriteLn(’i1+i2 = ’, S);
    9
    end.
    i1 = 32767
    i2 = 32767
    u = i1+i2 = -2.0000000000E+00
    Замена 6-ой строки
    6
    S := i1;
    S := S + i2;
    Результат работы измененной программы (верный ответ):
    i1 = 32767
    i2 = 32767
    i1+i2 = 6.5534000000E+04
    В Delphi:
    i1 = 2147483647
    i2 = 2147483647
    i1+i2 = -2.00000000000000E+0000
    i1 = 2147483647
    i2 = 2147483647
    i1+i2 = 4.29496729400000E+0009
    Постройте трассировочную таблицу для алгоритма, реализованного в про- грамме на стр.
    69
    . Входные данные:
    a := MaxInt;
    b := 10;
    76

    Глава 7
    Операторы для организации ветвления
    7.1
    Логические выражения
    . О логическом типе данных см. также п.
    4.1.9
    на стр.
    46
    Выражения
    Number >= 1000
    и
    Number < 1000
    взаимно дополняют друг друга.
    Операция сравнения
    <
    <=
    >
    >=
    =
    <>
    Операция в дополняющем выражении
    >=
    >
    <=
    <
    <>
    =
    Дополнение к
    Boolean-выражению — not Boolean-выражение
    Пример. Если Stop: Boolean; Ch: Char, то
    Выражение
    Дополняющее выражение
    Stop not Stop
    (Ch >= ’a’) and (Ch <= ’z’) not ((Ch >= ’a’) and (Ch <= ’z’))
    (Ch >= ’a’) and (Ch <= ’z’) (Ch < ’a’) or (Ch > ’z’)
    Законы де Моргана:
    если S1, S2 — некоторые логические выражения, то not (S1 and S2) = (not S1) or (not S2)
    not (S1 or S2) = (not S1) and (not S2)
    77

    Рис. 1.1. Auguste De Morgan
    7.2
    Примеры логических выражений
    Пример 2.1. Записать условие: заданное целое число x двузначное.
    Математическая запись условия:
    x ∈ [10, 99].
    Запись условия на языке Паскаль: (x >= 10) and (x <= 99)
    Пример 2.2. Записать условие: x ∈ [a, b] или y ∈ (2a, 2b);
    Общий вид логического выражения:
    условиеN1 or условиеN2;
    (2.1)
    где условиеN1
    (x ∈ [a, b]):
    (x >= a) and (x <= b);
    условиеN2
    (y ∈ (2a, 2b)): (y > 2 * a) and (y < 2 * b).
    (2.2)
    (
    2.2
    ) → (
    2.1
    ):
    (x >= a) and (x <= b) or (y > 2 * a) and (y < 2 * b).
    78

    Пример 2.3. Записать условие: два вещественных числа равны между собой.
    Математическая запись условия: |a − b|
    ε (где ε — некоторое малое число,
    например, ε = 0,0001).
    На языке Паскаль:
    Abs(a - b) <= 0.0001
    Был пример var x, y: Real;
    begin x := 0.005;
    y := 0.0051;
    Writeln(’x = y? ’, x = y);
    Writeln(’x = y? ’, abs(x - y) <= 0.001);
    Writeln(’x = y? ’, abs(x - y) <= 0.0001);
    end.
    Результат (Delphi).
    x = y? FALSE
    x = y? TRUE
    x = y? FALSE
    Результат (Borland Pascal).
    x = y? FALSE
    x = y? TRUE
    x = y? TRUE
    Writeln(’x = y? ’, abs(x - y) <= 0.0001000001);
    Пример 2.4. Записать дополнение условия not (x < Pi/2) or EventFlag и преобразовать его, используя законы де Моргана:
    Дополняющее условие:
    not (not (x < Pi/2) or EventFlag).
    С учетом not (not A) = A, имеем ответ:
    (x < Pi / 2) and not EventFlag.
    79

    7.3
    Выбирающие операторы
    Ветвящимся
    (разветвляющимся) называется алгоритм, в котором в зави- симости от исходных данных или промежуточных результатов вычисления реализуются по одному из нескольких заранее предусмотренных направле- ний. Такие направления называются ветвями вычислений.
    <выбирающий оператор> ::= <условный оператор> |
    <оператор варианта>
    7.4
    Оператор условного перехода
    Оператор условного перехода
    (условный оператор) предназначен для выбора одной из двух альтернативных ветвей алгоритма в зависимости от значения некоторого проверяемого условия. Существуют условные опера- торы с одной и двумя ветвями.
    условие операторы операторы
    +

    условие операторы
    +

    БНФ-нотация:
    <условный оператор> ::= if <выражение> then <оператор> |
    if <выражение> then <оператор>
    else <оператор>
    выражение if then оператор else оператор
    Рис. 4.2. Условный оператор (синтаксическая диаграмма)
    80

    Операторы if
    Синтаксис условного оператора с одной ветвью
    (оператор if-then):
    if условие then оператор
    ;
    условие — любое логическое выражение.
    Пример 4.1. Если введенное число четное, то уменьшить его в два раза, иначе оставить без изменения.
    Решение. Условие четности числа: x mod 2 = 0.
    Проверка четности числа program Ex3_1;
    var x : Integer;
    begin
    Write(’Введите любое целое число [> ’);
    ReadLn(x);
    if x mod 2 = 0
    then x := x div 2;
    WriteLn(’x = ’, x);
    end.
    Синтаксис условного оператора с двумя ветвями
    (if-then-else):
    if условие then оператор1
    else оператор2
    ;
    Если условие соблюдается, то выполняется оператор1,
    иначе выполняется оператор2.
    (
    стиль оформления кода
    ).
    if x >= 0 then
    WriteLn(’Неотрицательное число’)
    else
    WriteLn(’Отрицательное число’);
    if x >= 0 then
    WriteLn(’Неотрицательное число’)
    else
    WriteLn(’Отрицательное число’);
    81

    Осторожно бессмыслица if условие then
    ;
    оператор;
    if условие then оператор else
    ;
    оператор;
    Осторожно ошибка if условие then оператор
    ;
    else оператор;
    Осторожно неопытность
    Пусть Found : Boolean if A = B then Found := true else Found := false;
    Замена:
    Found := A = B;
    82

    7.5
    Поиск максимального/минимального из двух выражений
    Постановка задачи: даны выражения x и y. Найти max(x, y),
    min(x, y).
    Решение.
    I способ: IF-THEN-ELSE
    { max(x,y) }
    if x > y then Max := x else Max := y;
    { min(x,y) }
    if x < y then Min := x else Min := y;
    II способ: IF-THEN
    { max(x,y) }
    Max := x;
    if y > Max then Max := y;
    { min(x,y) }
    Min := x;
    if y < Min then Min := y;
    III способ: без использования условного оператор max(x, y) =
    x + y + |x − y|
    2
    ,
    min(x, y) =
    x + y − |x − y|
    2 7.6
    Поиск максимального/минимального из трех выражений
    Постановка задачи: даны выражения x, y, z. Найти max(x, y, z),
    min(x, y, z).
    Решение.
    1) max_xy := max(x, y),
    2) max(max_xy, z).
    83

    7.7
    Составные операторы в операторах if
    БНФ-нотация:
    <составной оператор> ::= begin <оператор> {; <оператор>} end
    (begin end; — операторные скобки.)
    Составной оператор в if-then:
    if условие then begin оператор1;
    оператор2;
    ...;
    end;
    Составной оператор в if-then-else:
    if условие then begin
    (* начало первого составного оператора *)
    оператор1;
    оператор2;
    ...;
    end
    (* конец первого составного оператора *)
    else begin
    (* начало второго составного оператора *)
    операторA;
    операторB;
    ...;
    end;
    (* конец второго составного оператора *)
    84

    Пример 7.1. Дано: x, y ∈ Z. Найти p1 := max(x, y), p2 := min(x, y).
    Решение. Условие разветвления: x > y.
    I способ: IF-THEN-ELSE
    1
    var x, y, p1, p2 : Integer;
    2
    begin
    3
    ... { ввод x и y }
    4
    if x > y then
    5
    begin
    6
    p1 := x;
    7
    p2 := y;
    8
    end
    9
    else
    10
    begin
    11
    p1 := y;
    12
    p2 := x;
    13
    end;
    14
    ... { вывод p1 и p2 }
    15
    end.
    II способ: IF-THEN
    1 2
    p1 := x;
    p2 := y; { предполагаем случай x > y }
    3
    if x < y then
    4
    begin
    5
    p1 := y;
    p2 := x;
    6
    end;
    7 85

    7.8
    Вложенные условные операторы условие операторы
    +

    условие операторы операторы
    +

    условие операторы
    +

    условие операторы
    +

    Рис. 8.3. Примеры вложенных операторов условного перехода
    Пример 8.1. Пусть x ∈ Z. Вычислить y y =





    −50, если x < 0;
    5, если x = 0;
    100, если x > 0.
    Решение
    1
    if x < 0 then y := -50 2
    else { т.е. x >=0 }
    3
    if x = 0 then y := 5 4
    else { x > 0 }
    5
    y := 100;
    Плохое решение
    1
    if x < 0 then y := -50;
    2
    if x = 0 then y := 5;
    3
    if x > 0 then y := 100;
    86

    Рис. 8.4. В норе живет только один зверь (мышь, заяц или лиса)!
    Ищем зайца (вложенные условные операторы)
    1
    if зверь = заяц then
    2
    Writeln(’Даем морковку’)
    3
    else { т.е. зверь не заяц, а мышь или лиса }
    4
    if зверь = мышь then
    5
    Writeln(’Даем сыр’)
    6
    else { т.е. зверь не заяц и не мышь, зверь = лиса }
    7
    Writeln(’Даем мясо’);
    ?:

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