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

  • Алгоритмические структуры

  • программирование_занятие_3. Цикл цикл со счетчиком



    Скачать 102.5 Kb.
    НазваниеЦикл цикл со счетчиком
    Анкорпрограммирование_занятие_3.doc
    Дата19.12.2017
    Размер102.5 Kb.
    Формат файлаdoc
    Имя файлапрограммирование_занятие_3.doc
    ТипДокументы
    #13129
    КатегорияИнформатика. Вычислительная техника

    название: Алгоритмические конструкции.
    изучается:

    Полное ветвление.

    Выбор.

    Цикл:

    цикл со счетчиком,
    базовый материал:

    Алгоритм, основные свойства алгоритма. (из 1 урока)

    Оформление программ: блок-схемы, языки программирования. (из 1 урока)

    Ввод-вывод информации, присваивание. (из 1 урока)

    Макрокоманда (несколько команд оформляется как одна). (из урока 2а)

    Линейный алгоритм. (из урока 2а)

    Неполное ветвление, условие. (из урока 2а)

    Циклы ДО и ПОКА, (из урока 2а)
    Алгоритмические структуры
    - Надеюсь, учащиеся хорошо знакомы с понятиями:

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

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

    Кроме того, было рассмотрена структура, называемая «линейный алгоритм», из определения которой, отказавшись от обязательности выполнения некоторых шагов, была получена структура «неполное ветвление», а отказавшись от выполнения шага только один раз, были получены циклы.

    Алгоритм назовем линейным, если

    1) выполняется каждый его шаг, и

    2) только один раз.


    Полное ветвление


    Вспомним, как выглядит НЕПОЛНОЕ ВЕТВЛЕНИЕ. В нем есть шаг и условие, определяющее выполнять этот шаг или нет.

    НЕПОЛНОЕ ВЕТВЛЕНИЕ

    Поменяв в некотором ветвлении условие на противоположное, получим ветвление, отмеченный шаг которого будет выполняться тогда, когда не выполнялся шаг исходного случая. Сами шаги при этом могут быть различными. Объединение этих двух результатов создает структуру, которая называется полным ветвлением, или альтернативой. При истинности условия выполняется один из имеющихся шагов, при ложности – другой.



    Следует отметить, что команда ветвления является "командой над командами".

    Не смотря на то, что в структуре могут присутствовать две совершенно различные команды, вся конструкция считается одной командой. Находящиеся внутри команды не должны иметь сигнала конца, так как они являются частью одной команды – команды ветвления.
    В языке программирования Pascal структура ветвления изображается оператором: IF <условие> THEN <команда 1> ELSE <команда 2>;

    Напомню, что в виде одной команды можно оформить несколько команд.

    Нет ничего удивительного в том, что и в многих других языках (basic, c, dBASE, …) ветвление оформляется точно так же.

    В языке basic, если команда в строку не умещается, она оформляется так же, как в языке dBASE.

    basic

    IF <условие> THEN <команда 1> ELSE <команда 2>
    pascal

    IF <условие> THEN <команда 1> ELSE <команда 2>;
    C

    IF <условие> THEN <команда 1> ELSE <команда 2>;
    dBASE

    IF <условие>

    <команды одной группы>

    ELSE

    <команды другой группы>

    ENDIF
    Если в тексте программы строка получается очень длинной, то команду ветвления оформляют в несколько строк с отступами:
    Вообще говоря, отступы и отдельные строчки компьютеру не нужны. Он поймет, если даже всю программу мы запишем в одну строку. Красивое оформление нужно человеку, для более быстрого обнаружения возможных ошибок.

    if <условие>

    then

    <команда 1>

    else

    <команда 2> ;
    Внутри команды ветвления может быть другое ветвление.
    Пример:

    Составить программу, которая, получив длины трех отрезков, сообщает, можно ли из этих отрезков сложить треугольник.
    Теория: длина любой стороны треугольника меньше суммы длин двух других сторон.
    Алгоритм выполняет проверку требования, что сумма длин любых двух сторон больше длины третьей и выдает ответ.
    var a,b,c:integer; {три переменных для хранения длин сторон}

    begin

    write('Введи длины трех отрезков через пробел '); readln(a,b,c);

    if a>b+c {проверка для стороны a}

    then

    writeln('треугольник построить нельзя')

    else

    if b>a+c {проверка для стороны b}

    then

    writeln('треугольник построить нельзя')

    else

    if c>a+b {проверка для стороны c}

    then

    writeln('треугольник построить нельзя')

    else {все проверки успешно пройдены}

    writeln('треугольник построить можно');

    end.
    Рассмотрим теперь в качестве примера использования полного ветвления алгоритм и программу вычисления отношения двух чисел с блокировкой деления на ноль и выводом соответствующего сообщения на экран монитора.
    VAR А,В,С: REAL;

    BEGIN

    WRITELN('Введи 2 числа'); READLN(A,B) ;

    IF В<>0 THEN

    BEGIN С:=А/В; WRITELN ( 'С = ',С) END

    ELSE WRITELN('ДЕЛЕНИЕ НА 0')

    END.
    В ряде случаев для работы алгоритма на исходные данные накладываются некоторые ограничения. В приведенном примере – переменная В не должна равняться нулю.

    Бывают случаи, когда требуется число, а не слово. Иногда числа должны быть только положительными и т. п. Получив неправильные данные программа остановится, результат алгоритма не будет получен. Для выяснения причины остановки применяются ветвления, альтернативная ветка которых выдает сообщение о неправильности данных. Программа сможет предложить повторить ввод данных и продолжить работу.


    Выбор


    Внутри команды ветвления может быть другая команда ветвления.

    Многократное выполнение ветвлений называют ВЫБОР

    (н)

    |

    + / \ -

    ┌──────┐

    │ \ / + / \ -

    │ ┌──────┐

    │ │ \ / + / \ -

    │ │ ┌── - -

    ┌─┴─┐ ┌─┴─┐ ┌─┴─┐\ /

    │ │ │ │ │ │

    └─┬─┘ └─┬─┘ └─┬─┘

    └───┬───┴───────┴─────── - -

    (к)
    Особенность структуры выбора состоит в том, что выбор выполняемых операторов здесь осуществляется не в зависимости от истинности или ложности логического выражения, а является вычислимым. Оператор выбора позволяет заменить несколько условных операторов (в силу этого его еще называют оператором множественного ветвления).



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

    100 on k goto 200,300,...,900
    Pascal

    case k of

    l : команда 1 ;

    2 : команда 2 ;

    ...

    99 : команда N ;

    else команда N+1

    end;
    C

    switch (k)

    {case l : команда 1; break;

    case 2 : команда 2; break;

    ...

    case 99 : команда N; break;

    default: команда N+1;}
    В алгоритмической структуре "выбор" вычисляется выражение k и выбирается ветвь, значение метки которой совпадает со значением k. После выполнения выбранной ветви происходит выход из конструкции выбора (в C, в отличие от Pascal, такой выход не осуществляется, а продолжают выполняться последующие операторы, поэтому для принудительного завершения оператора выбора применятся оператор break). Если в последовательности нет метки со значением, равным значению выражения k, то управление передается внешнему оператору, следующему за конструкцией выбора - (это происходит в случае отсутствия альтернативы выбора; если она есть, то выполняется следующий за ней оператор, а уже затем управление передается внешнему оператору).


    Цикл со счетчиком


    На прошлом занятии так же рассматривалось понятие цикла.

    Цикл состоит из тела – набора повторяющихся команд - и условия выхода.

    В зависимости от порядка исполнения: сначала условие, потом тело, или сначала тело, потом условие, определяются циклы типа «пока» и циклы типа «до».

    КЛАССИФИКАЦИЯ ЦИКЛОВ

    ПО ВЗАИМНОМУ ПОЛОЖЕНИЮ ЧАСТЕЙ

    (н) Цикл "ПОКА" (н)

    ┌───┤ ( сначала ├───┐

    │ / \ - "условие" ┌──┴─┐ │

    │ <усл>─┐ потом │тело│ │

    │ +\ / │ "тело" ) └──┬─┘ │

    │┌──┴─┐ │ / \ │

    ││тело│ │ Цикл "ДО" <усл>─┘

    │└──┬─┘ │ ( сначала \ /-

    └───┘ │ "тело" │+

    ┌───┘ потом (к)

    (к) "условие")
    Особый случай циклов получается, когда заранее, до начала выполнения цикла, известно, сколько раз выполнится тело цикла.

    Если заранее известно, сколько раз выполняется тело цикла, такой цикл называется ДЕТЕРМИНИРОВАННЫМ, или ЦИКЛ СО СЧЕТЧИКОМ.

    (В литературе обычно используется термин "цикл с параметром".)

    КЛАССИФИКАЦИЯ ЦИКЛОВ ПО ПРИЗНАКУ,

    ИЗВЕСТНО ИЛИ НЕИЗВЕСТНО ЧИСЛО ПОВТОРОВ

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


    В языке basic цикл со счетчиком оформляется так:
    FOR I=<начальное значение> TO <конечное значение> [STEP <шаг изменения>]

    <тело цикла>

    NEXT [I]
    Шаг, равный 1 можно не писать, это отмечено взятием в квадратные скобочки. Так же необязательно писать имя переменной-счетчика после слова NEXT.

    (Квадратные скобки только показывают, что эту часть команды можно не писать, сами скобки не пишутся.)
    Счетчиком всегда является переменная числового типа. Изменять счетчик можно на произвольное, в том числе и действительное, значение.
    На языке Паскаль для циклов со счетчиком команда выглядит:
    FOR < 1 >:=< 2 > TO < 3 > DO <тело цикла>;
    < 1 > - переменная-счетчик

    < 2 > - начальное значение переменной счетчика

    < 3 > - конечное значение переменной счетчика

    тело цикла выполняется при всех значениях переменной-счетчика от начального до конечного, очередное значение определяется по правилу «берем следующее значение». Для организации противоположного направления изменения счетчика (по правилу «берем предыдущее значение»), вместо слова TO используют слово DOWNTO
    FOR < 1 >:=< 2 > DOWNTO < 3 > DO <тело цикла>;
    В Паскале параметр цикла не обязательно целочисленный, но зато он должен являться порядковым (иметь возможность определения следующего и предыдущего значений).

    Использование вещественных значений в качестве счетчика невозможно, хотя бы потому, что для вещественных чисел не определены понятия «следующий» и «предыдущий»: в самом деле, какое значение следует после 1.1 - 1.2, 1.11 или 1.101?
    В языке Си цикл FOR еще более интересный.

    for (<действия до цикла, (начальное присваивание)>;
    <проверка условия>;
    <действия после каждой итерации (изменение счетчика)>)
    <(тело цикла)>;
    Его заголовок фактически содержит три части: действия по инициализации, действия по проверке окончания цикла и, наконец, действия после каждой итерации. Характерной особенностью является возможность иметь в каждой части произвольное количество операторов, включая вариант их отсутствия. Настолько общий подход позволяет вообще написать цикл без тела: например, сам оператор организации цикла

    for (s=0, i=1; i<11; s=s+i, i=i+1)

    уже вычисляет сумму первых 10 натуральных чисел.

    Ярые приверженцы языка Си последние два оператора никогда не напишут иначе, чем s+=i, i++, давая возможность компилятору составить чуть более эффективную программу.

    for (s=0, i=1; i<11; s+=i, i++);
    Примеры: нахождения суммы пяти чисел. Счетчиком цикла является переменная i, и нахождение суммы членов геометрической прогрессии с заданной точностью.
    нахождения суммы пяти чисел (pascal)

    var a,s:real; i:integer;

    begin

    s:=0; writeln('Введите 5 чисел');

    for i:=1 to 5 do

    begin readln(a); s:=s+a end;

    writeln('сумма пяти введенных чисел - ',s);

    end.
    найти сумму членов геометрической прогрессии с заданной точностью

    R = a + aq + aq2 + aq3 + aq4 + ...

    var a,q,s:real;

    begin

    s:=0;

    writeln('Введите начальный член и знаменатель q<1');

    readln(a,q);

    repeat

    s:=s+a; a:=a*q;
    until a<0.001

    writeln('сумма слагаемых, найденных с точностью до 0.001 - ',s);

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

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

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


    Заключение

    Что мы узнали на этом уроке? Обобщили структуру «неполное ветвление», рассмотрели получившиеся структуры «альтернатива» (=«полное ветвление») и выбор, рассмотрели еще одну классификацию циклов, по признаку известно число повторов тела или нет. Выделились циклы со счетчиками.
    Напомню, что все началось с определения линейного алгоритма.

    Алгоритм назовем линейным, если

    1) выполняется каждый его шаг, и

    2) только один раз.
    По окончании нашего урока, вы должны знать ответы на вопросы:
    * Какой алгоритм называется линейным?

    * Какой алгоритм называется алгоритмом с ветвлением?

    * Как выглядит оператор ветвления на языке Паскаль?

    * Как выглядит полное и неполное ветвления?

    * Что такое составной оператор?

    * Какой алгоритм называется алгоритмом с циклом?

    * Какие два типа циклов различают?

    * Как называется цикл с заранее известным числом повтора?

    * Как оформляются циклы ДО и ПОКА на языке Паскаль?

    * Как оформляется цикл со счетчиком на языке Паскаль?
    написать администратору сайта