Основные алгоритмические конструкции

Основные алгоритмические конструкции.   1. Структура следование. Образуется последовательностью действий, следующих одно за другим: Алгоритмический язык Блок­схема действие 1 действие 2 ... действие n Пример. Определить значение переменной c после выполнения фрагмента алгоритма. Алгоритмический язык Блок­схема a:=3 c:=4 c:=a+c/2 Ответ: 5   2. Структура ветвление. В зависимости от результата проверки условия («да» или «нет»)  осуществляет выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведёт к общему выходу, поэтому работа алгоритма будет продолжаться независимо от  того, какой путь будет выбран. Структура «ветвление» бывает четырёх видов: «если­то»;  «если­то­иначе»; «выбор»; «выбор­иначе».   Структура «если­то». Алгоритмический язык Блок­схема если условие то действия всё Пример 1. Определить значение переменной a после выполнения фрагмента алгоритма  при a=5 и a=10. Алгоритмический язык Блок­схема   Ввод а если a>5 то a:=a+20 всё Ответ:  5 и 30.   Структура «если­то­иначе». Алгоритмический язык Блок­схема если условие  то действия 1  иначе действия 2 всё Пример 2. Определить значение переменной a после выполнения фрагмента алгоритма  при a=5 и a=10. Алгоритмический язык Блок­схема Ввод а если a>5    то a:=a+20    иначе a:=a*10 всё Ответ: 50 и 30.   Структура «выбор». Алгоритмический язык Блок­схема выбор  при условие 1: действия 1  при условие 2: действия 2 …   при условие n: действия n всё Пример 3. Дано целое число в диапазоне 1–7. Составить строку — название дня недели,  соответствующее данному числу (1 — «понедельник», 2 — «вторник» и т. д.). Алгоритмический язык Блок­схема выбор при n=1: c:=«понедельник» при n=2: c:=«вторник» при n=3: c:=«среда» при n=4: c:=«четверг» при n=5: c:=«пятница» при n=6: c:=«суббота» при n=7: c:=«воскресенье» всё     Структура «выбор­иначе». Алгоритмический язык Блок­схема выбор   при условие 1: действия 1 при условие 2: действия 2   …   при условие n: действия n  иначе действия n+1 всё   Пример 4. Дано целое число n. Составить строку­описание оценки, соответствующей  числу n (1 — «плохо», 2 — «двойка», 3 — «тройка», 4 — «хорошо», 5 — «отлично»).  Если n не лежит в диапазоне 1–5, то вывести строку «ошибка» Алгоритмический язык Блок­схема   выбор при n=1: c:=«плохо» при n=2: c:=«двойка» при n=3: c:=«тройка» при n=4: c:=«хорошо» при n=5: c:=«отлично»    иначе c:=«ошибка» всё 3. Структура цикл. Обеспечивает многократное выполнение некоторой совокупности  действий, которая называется телом цикла. Циклы бывают трёх видов: с  предусловием «пока­делай», с постусловием «делай­пока», со счётчиком «для».   Цикл с предусловием («пока­делай» ). Предписывает выполнять тело цикла до тех пор,  пока выполняется условие, записанное после слова пока. Алгоритмический язык Блок­схема нц пока условие       тело цикла    кц Пример 1. Дано целое число N (> 0). Используя операции деления нацело, найти количество его  цифр. Алгоритмический язык Блок­схема   K:=0; нц пока N>0       N:=N div 10       K:=K+1       кц Цикл с постусловием («делай­пока»). Предписывает выполнять тело цикла до тех пор,  пока не выполняется условие (на Паскале until), записанное после слова пока. В отличие  от цикла,«пока­делай» тело цикла выполняется хотя бы один раз. Алгоритмический язык Блок­схема нц    тело цикла пока условие    кц Пример 2. Дано целое число N (> 1). Определить наименьшее из целых чисел K, для которых сумма  S= 1 + 2 + … + K будет больше N. Алгоритмический язык Блок­схема S:=0; K:=0 нц    K:=K+1    S:=S+K пока S>N    кц   Цикл со счетчиком («для»). Предписывает выполнять тело цикла для всех значений  переменной (параметр цикла) в заданном диапазоне. Алгоритмический язык Блок­схема нц для i от k до m    тело цикла кц Пример 3. Даны два целых числа A и B (A < B). Найти сумму S всех целых чисел  от A до B включительно. Алгоритмический язык Блок­схема S:=0 нц для i от A до B    S:=S+i    кц Основные алгоритмические конструкции Под алгоритмом понимают постоянное и точное предписание  (указание) исполнителю совершить определенную последовательность действий,  направленных на достижение указанной целиили решение поставленной задачи. Блок – схемы. Условные обозначения Начало ­ конец Процесс Ввод­вывод Типовой процесс Решение (услови е) Базовые алгоритмические структуры   Следование Ветвление Повторение (цикл) Алгоритм ­ это четко обозначенная последовательность действий конкретному  исполнителю для достижения конкретных целей или решения конкретной задачи.  Свойства алгоритмов:  понятность. В алгоритме должны быть лишь те инструкции, которые известны  исполнителю;  массовость. С помощью определенного алгоритма должен решаться целый класс  задач;  однозначность. Любой алгоритм должен быть описан так, что бы у исполнителя не  появлялось двузначных инструкций;  правильность. Выполнения алгоритма должно давать правильные результаты;  конечность. Полное выполнения алгоритма должно происходить за конечное число  шагов;  дискретность. Алгоритм должен состоять из отдельных операций, которые  выполняются последовательно;  еффективность. Алгоритм должен обеспечивать решение задачи за наиболее  короткое время и с использованием минимальных ресурсов компьютера. Те пользователи интернета, которые знакомы с программированием знают, что без  алгоритма невозможно написать любую программу. С этого следует, что в мире  компьютеров алгоритмы используются в основном в программировании. Далее  рассмотрим основные алгоритмические конструкции, которые есть основой любого  современного языка программирования. Данная информация будет особенно полезна  начинающим программистам. Все примеры, рассмотренные далее, написаны на языке Visual C. (Большинство других  языков есть производными от языка С, так что эти примеры можно использовать и в  других языках ­ php, java, c# и т. п.) Блок­схема ­ это способ представления алгоритмов в графической форме с помощью  геометрических фигур, которые соединяются между собой линиями. Каждая фигура­блок обозначает конкретное действие, текст всередине которой дает  обьяснение конкретной инструкции, а каждая линия должна иметь в себе стрелку,  которая говорит о направлении выполнения команд алгоритма. Способ представления алгоритма в виде блок­схемы упрощает алгоритм, дает визуальное  понимание его работы. Рассмотрим несколько правил построения блок­схем: блоки соединяются линиями, в каждый блок входит одна или больше линий, но непосредственно с блока может выходить только одна! линия. С логического блока всегда выходят две линии потока: одна в случае  выполнения условия, вторая в случае невыполнения. Желательно что бы линии не  пересекались. Рассмотрим основные графические изображения блоков: начало и конец алгоритма обозначается вот таким эллипсом;   все главные вычисления алгоритма обозначаются в блок­схеме в виде прямоугольника; ввод / вывод информации рисуется вот таким образом; ромб обозначает блок условия; потоки выполнения обозначают обычные линии; а вот это пересечение несвязанных линий потока; линии потока можно обьединить таким образом; Базовые алгоритмические конструкции ­ это способы управления обработкой  информации. На сегодняшний день существует всего 3 базовых конструкции (хотя в  будущем возможно кто­то придумает что­то новенькое :)): •   линейные алгоритмы; •   алгоритмы ветвления; •   циклические алгоритмы. Теперь подробнее о каждом. Линейным называется такой алгоритм, в котором блоки алгоритма исполняются линейно,  один за другим. Другими словами такой алгоритм в любом случае не будет иметь условных и безусловных переходов. Алгоритм ветвления нужен в том случае, когда для решения конкретной задачи нужно  проверить переменную на определенное условие. В таком случае в зависимости от  условия и значения переменной будут выполнятся различные действия, но при этом  каждая ветвь алгоритма (каждое действие) будет выполняться не более одного раза.  Перед рассмотрением циклических структур определим, что такое цикл. Цикл ­ это  команда исполнителю (компилятору или грубо говоря компьютеру в целом) повторить  некую последовательность действий определенное количество раз. Теперь становится  ясно, что циклический алгоритм являет собой структуру, где некоторые участки кода  могут выполняться более одного раза. Но нужно помнить, что количество повторений  цикла должно быть всегда конечное число, иначе произойдет зацикливание и решение  задачи не сможет закончиться. Оператор ветвления if {} else {} нужен для исполнения тех или иных действий в  зависимости от истинности либо ложности некоторого условия. Условие считается  ложным, если оно равняется нулю, а если условие не равно нулю, то оно считается  истинным. Еще нужно помнить, что бы условие, которое проверяется, всегда было  скалярным, то есть что бы его можно было проверить на равность нулю. Рассмотрим пример. В скобках {} выполняется блок программы, в зависимости от словия. int a=1; if (a==1) //условие истинно { } // если истинно, выполняем этот блок программы else     //условие ложно // если ложно, выполняем этот блок программы { } Нужно так же отметить, что блок else {} можно опускать, если нам не нужно что­либо  выполнять, когда условие ложно. a=1; if (a==1) //условие истинно { }  // если истинно, выполняем этот блок программы, если условие ложно,  то ничего не делаем а просто продолжаем выполнение программы Оператор ветвления if {} else {} нужен для исполнения тех или иных действий в  зависимости от истинности либо ложности некоторого условия. Условие считается  ложным, если оно равняется нулю, а если условие не равно нулю, то оно считается  истинным. Еще нужно помнить, что бы условие, которое проверяется, всегда было  скалярным, то есть что бы его можно было проверить на равность нулю. Рассмотрим пример. В скобках {} выполняется блок программы, в зависимости от словия. int a=1; if (a==1) //условие истинно { } // если истинно, выполняем этот блок программы else     //условие ложно // если ложно, выполняем этот блок программы { } Нужно так же отметить, что блок else {} можно опускать, если нам не нужно что­либо  выполнять, когда условие ложно. a=1; if (a==1) //условие истинно { }  // если истинно, выполняем этот блок программы, если условие ложно,  то ничего не делаем а просто продолжаем выполнение программы Оператор­переключатель switch используется для выбора одного из нескольких  альтернативных путей выполнения программы. Выполнение даного оператора начинается  с вычисления значения, которое идет после switch в скобках. После этого выполняется та  часть кода этого оператора, где значение условия совпадет с веткой case. После ветки  case обязательно идет оператор break, который обрывает дальнейшее выполнение  оператора switch и передает выполнение программы в точку, которая следует сразу после  блока switch. Для лучшего понимания рассмотрим пример. Эдесь вычисляемым значением будет целая  переменная а, в зависимости от значения переменной а, будет выполнятся та ветка case,  которая будет равна а. В случае, если ни одно из case не равно а, то выполнится ветка  default. int a=1; int b=100; switch (a)  //  вычисляем а = 1 {      case ­5:  // эта ветка не выполнится, так как 1 не равно ­5 b=­5; break; case 1:   // а эта ветка выполнится, 1 = 1 b=2;      //  после выполнения этой ветки b присвоится 2 break; default:   // эта ветка выполнится, если ни одна из веток case не выполнилась b=0;      } Следует добавить, что веток case в операторе switch может быть сколько угодно, а ветка  default может опускаться (не использоваться).  Основное назначение оператора switch ­ заменить оператор if, когда в нем есть множество  вложенных условий. Оператор while используется при реализации циклических алгоритмов, для выполнения  некоторых фрагментов кода энное число раз, пока выполняется условие. Цикл заканчивается в таких случаях: •   условие оператора принимает нулевое значение, то есть, условие становится ложным; •   в теле цикла появляется оператор break, который обрывает текущий цикл; •   в теле цикла был выполнен оператор return. В первых двух случаях управление передается оператору, который находится сразу после цикла, а в третем случае активная в тот момент функция завершает свою работу и  возвращает какое­то значение. Пример. int a = 1; while (a<10) // цикл будет выполняться, пока переменная а меньше 10 { } a++; // увеличиваем на единицу int b = 2; while (b>10) // а в этом случае цикл не выполнится ни разу, так как b меньше 10 { } b­­; Основной особенностью циклов с предусловием есть то, что они вначале проверяют  условие, а потом уже выполняют блок цикла. А это значит, что они могут вообще не  выполнится ни разу, если условие ложно. Если оператор цикла с предусловием сначала проверяет условие, а уж потом выполняет  тело цикла и в зависимости от условия может и не выполнится ни разу, то оператор цикла  с послеусловием делают все наоборот. Такой оператор сначала выполняет тело цикла, а  только потом проверяет условие. Отсюда становится ясно, что он выполнится хотя бы  один раз. Пример. int a=1; do { a++; } while (a<10); //будет выполняться, пока а<10 А тут хоть условие и не выполняется (ложно), но всеравно цикл выполнится один раз int a=1; do { a++;     // а = 2 } while (a<1); //а>1, условие не выполняется, но цикл выполнился один раз Оператор break служит для прерывания выполнения таких операторов как: do, for, while,  switch. Другими словами для прерывания выполнения текущего цикла, функции,  оператора. После прерывания работы любого из операторов, управление передается следующему  после прерванного оператору.  Пример. Break прерывает выполнение цикла while int a=1; while (a<100)    //благодаря break цикл выполнится всего раз { a++;             // хотя без break цикл выполнился бы 99 раз   break;       // прерывает и передает управление следующей далее функции } myfunc(5); Оператор безусловного перехода goto передает управление непосредственно на оператор,  перед которым расположенная метка. Код, который расположен между goto и меткой,  пропускается (не выполняется). Пример. int a=1; if(a==1) goto m1;   // пойдет на метку m1 a=a+100;            //не выполнится, если сработает goto m1: a=0; Ветвящиеся алгоритмы Далеко не все алгоритмы являются линейными. Существуют алгоритмы, в которых при  выполнении некоторого условия необходимо сделать одни действия, а в противном  случае (если условие не выполнилось) необходимо выполнить другие действия или ничего не делать. В таком случае говорят, что в алгоритме использована  ветвящаяся алгоритмическая конструкция. Пример 11. Алгоритм «Идти ли завтра в школу?»  Посмотреть на календарь.  ЕСЛИ завтра не суббота, и не воскресенье, и не красный день календаря, и не  каникулярный день, ТО завести будильник на 7:30, ИНАЧЕ проверить, что  будильник не заведен.  Лечь спать. Очевидно, результат выполнения алгоритма зависит от того, какой завтра день. Определение. Ветвящийся алгоритм – это алгоритм, в котором ход выполнения шагов  алгоритма зависит от истинности тех или иных условий. Запишем, как выглядит эта конструкция при записи алгоритма в виде блок­схемы: После того как мы проверили условие, алгоритм разделяется на две части, первая  выполняется в случае, если условие оказывается истинным, другая часть выполняется в  противном случае. Но нужно четко разделять понятие записи и выполнения  алгоритма. Записывая алгоритм, мы прописываем обе ветви ветвящейся конструкции: и то, что будет выполняться при истинном условии, и то, что будет выполняться  при ложном. Однако при выполнении алгоритма исполнитель выполнит только одну из  ветвей алгоритма, так как в зависимости от входных данных условие может быть либо  истинным, либо ложным, но не истинным и ложным одновременно. Именно потому что выполнение алгоритма после проверки условия разделяется на две  ветви, эта конструкция и носит название ветвящейся. Мы рассмотрели конструкцию, в которой какие­либо действия необходимо выполнять и  при ложном, и при истинном условии. Такое ветвление называется полным. Но не всегда  надо выполнять действия, если условие не выполняется. В таком случае одна из ветвей  алгоритма будет пустой, и такое ветвление называется неполным. Например, когда в дождливую погоду мы берем с собой зонтик, то мы не задумываемся,  что в течение дня будем выполнять неполный ветвящийся алгоритм. Пример 12. Алгоритм «Выход на улицу»  Посмотреть в окно.  Если идет дождь, то взять зонтик.  Выйти на улицу. Эту конструкцию можно изобразить следующей блок­схемой. 4.5.2. Реализация ветвящихся алгоритмов. Условный оператор В языках программирования ветвящиеся алгоритмические конструкции реализуются с  помощью специальных операторов: оператора условного перехода и оператора выбора. Синтаксис условных операторов во многих языках программирования схож. В общем  случае синтаксическое описание оператора условного перехода можно представить  следующим образом: if [(]<логическое выражение>[)] [then] <оператор 1> [else <оператор 2>] Здесь квадратные скобки используются для указания того, что элемент, стоящий в этих  скобках, может как присутствовать, так и отсутствовать в записи оператора. Семантика условного оператора такова: компьютер вычисляет логическое выражение.  Если вычисленное значение истинно, то выполняется первый оператор, в противном  случае выполняется второй оператор. Иногда алгоритм не подразумевает выполнение какого­либо оператора, если условие не  выполнилось. В таком случае можно использовать пустой оператор в ветви else. В  большинстве языков программирования предусмотрен неполный условный оператор, в  котором ветвь else просто отсутствует. Приведем пример программы на трех языках программирования с использованием  условного оператора. Пример 13. Фрагмент программы нахождения корней уравнения a ∙ x + b = 0: В отличие от линейного уравнения в уравнении такого вида коэффициент при x может  быть нулевым, поэтому не всегда корнем уравнения является дробь ­b/a. Basic INPUT "Введите коэффициенты уравнения a, b: ", a, b  IF a <> 0 THEN PRINT "Корень уравнения x=", (­1) * b / a  ELSE IF b <> 0 THEN PRINT "Корней нет"    ELSE PRINT "Корни – все действительные числа" Pascal write('Введите коэффициенты уравнения a, b:');  readln(a, b);  if a <> 0 then writeln('Корень уравнения x= ', (­1) * b / a)  else if b <> 0 then writeln('Корней нет')  else writeln(' Корни – все действительные числа ');  C printf("Введите коэффициенты уравнения a, b: ");  scanf("%f %f", &a, &b);  if (a != 0)    printf ("Корень уравнения x= %f", (­1) * b / a);  else    if (b != 0)      printf ("Корней нет");    else      printf ("Корни – все действительные числа"); Этот же алгоритм можно записать следующей блок­схемой: 4.5.3. Оператор выбора Иногда возникают ситуации, когда в алгоритме необходимо проверить не два варианта  значений, а несколько ( не просто проверить, истинно ли условие или ложно) и выполнять  различные действия, в зависимости от получаемого результата. Такую задачу можно  решить последовательно вызывая условные операторы и проверяя соответствующие  условия. Пример 14 Например, решим задачу: «На вход подается цифра, а на выходе должно быть название  этой цифры». Запишем решение этой задачи с использованием условных операторов (ниже приведен фрагмент кода программы на языке Pascal): readln(a);  if a = 0 then writeln('ноль') else    if a = 1 then writeln('один') else      if a = 2 then writeln('два') else        if a = 3 then writeln('три') else          if a = 4 then writeln('четыре') else            if a = 5 then writeln('пять') else              if a = 6 then writeln('шесть') else                if a = 7 then writeln('семь') else                  if a = 8 then writeln('восемь') else                    if a = 9 then writeln('девять'); Код получился слишком громоздким. В некоторых языках программирования  предусмотрены операторы выбора, или так называемые переключатели, смысл которых  заключается в проверке совпадения значения выражения с одной из заданных констант и  соответствующем ветвлении. На языке Pascal и C эти операторы выглядят следующим образом: Pascal case <выражение> of    Значение1 [,значение11]: оператор1;    [Значение2 [,значение21]: оператор2;]    . . .    [else: операторElse1;]  end; C switch (выражение)  {[case значение1]: [список­операторов1]  [case значение2: [список­операторов2]]  [default: [ список операторов ]]  } Запишем фрагмент программы из примера 14 с использованием оператора выбора на двух  языках Pascal и C. Readln(a);  Case a of  0: writeln('ноль');  1: writeln('один');  2: writeln('два');  3: writeln('три'); 4: writeln('четыре'); 5: writeln('пять'); 6: writeln('шесть'); 7: writeln('семь'); 8: writeln('восемь'); 9: writeln('девять'); end; scanf("%d", &a);  switch (a)  {  Pascal C case 0: printf("ноль"); break; case 1: printf("один"); break; case 2: printf("два"); break; case 3: printf("три"); break; case 4: printf("четыре"); break; case 5: printf("пять"); break; case 6: printf("шесть"); break; case 7: printf("семь"); break; case 8: printf("восемь"); break; case 9: printf("девять"); break; } Так как в языке С после нахождения требуемого варианта будут выполняться все  операторы подряд до конца switch, в конце каждого из вариантов в большинстве случаев  необходимо добавлять оператор break. Основные алгоритмические конструкции. Наиболее понятно структуру алгоритма можно представить с помощью блок­схемы, в  которой используются геометрические фигуры (блоки), соединенные между собой  стрелками, указывающими последовательность выполнения действий. Приняты  определенные стандарты графических изображений блоков. Например, команду  обработки информации помещают в блок, имеющий вид прямоугольника, проверку  условий ­ в ромб, команды ввода или вывода ­ в параллелограмм, а овалом обозначают  начало и конец алгоритма. Структурной элементарной единицей алгоритма является простая команда,  обозначающая один элементарный шаг переработки или отображения информации.  Простая команда на языке схем изображается в виде функционального блока. Данный блок имеет один вход и один выход. Из простых команд и проверки условий образуются составные команды, имеющие более сложную структуру и тоже один вход и  один выход.  Структурный подход к разработке алгоритмов определяет использование только базовых  алгоритмических структур (конструкций): следование, ветвление, повторение, которые  должны быть оформлены стандартным образом. Рассмотрим основные структуры алгоритма. Команда следования состоит только из простых команд. На рисунке простые команды  имеют условное обозначение S1 и S2. Из команд следования образуются линейные  алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел,  введенных с клавиатуры. Команда ветвления ­ это составная команда алгоритма, в которой в зависимости от  условия Р выполняется или одно S1, или другое S2 действие. Из команд следования и  команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления).  Примером разветвляющегося алгоритма будет нахождение большего из двух чисел,  введенных с клавиатуры. Команда ветвления может быть полной и неполной формы. Неполная форма команды  ветвления используется тогда, когда необходимо выполнять действие S только в случае  соблюдения условия P. Если условие P не соблюдается, то команда ветвления завершает  свою работу без выполнения действия. Примером команды ветвления неполной формы  будет уменьшение в два раза только четного числа. Команда повторения ­ это составная команда алгоритма, в которой в зависимости от  условия Р возможно многократное выполнение действия S. Из команд следования и  команд повторения составляются циклические алгоритмы (алгоритмы повторения). На  рисунке представлена команда повторения с предусловием. Называется она так потому,  что вначале проверяется условие, а уже затем выполняется действие. Причем действие  выполняется, пока условие соблюдается. Пример циклического алгоритма может быть  следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы. Команда повторения с предусловием не является единственно возможной.  Разновидностью команды повторения с предусловием является команда повторения с  параметром. Она используется тогда, когда известно количество повторений действия. В  блок­схеме команды повторения с параметром условие записывается не в ромбе, а в  шестиугольнике. Примером циклического алгоритма с параметром будет нахождение  суммы первых 20 натуральных чисел. В команде повторения с постусловием вначале выполняется действие S и лишь затем,  проверяется условие P. Причем действие повторяется до тех пор, пока условие не  соблюдается. Примером команды повторения с постусловием будет уменьшение  положительного числа до тех пор, пока оно неотрицательное. Как только число  становится отрицательным, команда повторения заканчивает свою работу. С помощью соединения только этих элементарных конструкций (последовательно или  вложением) можно "собрать" алгоритм любой степени сложности. Каждая указанная конструкция может быть без изменений в структуре реализована на  любом языке программирования, например, на Паскале и Бейсике. Поэтому необходимо  грамотно составить алгоритм с помощью блок­схемы, а уже затем, зная, как записываются команды на конкретном языке программирования, набрать программу на компьютере и  получить результат, запустив ее на исполнение. Линейный алгоритм. Приведем пример записи алгоритма в виде блок­схемы, псевдокодов и на языке Паскаль.  Ручное тестирование и подбор системы тестов выполняются аналогично предыдущему  заданию. Разветвляющийся алгоритм. Приведем пример записи разветвляющегося алгоритма для нахождения наибольшего из  двух чисел.  Циклический алгоритм. Рассмотрим алгоритм нахождения суммы первых натуральных нечетных чисел до n.  Представим запись алгоритма тремя способами: в виде блок­схемы, школьного  алгоритмического языка и на языке программирования Pascal. Блок­схема состоит из следующих базовых структур: две составные команды (команда  следования и команда повторения с предусловием), далее простая команда. Все команды  соединены последовательно. Конструкции оформлены стандартным образом, поэтому их  легко распознать и перевести на язык программирования. Каждая конструкция имеет  один вход и один выход. Пунктирные стрелки в таблице отражают последовательность выполнения  технологической цепочки. После записи алгоритма в виде блок­схемы каждая команда  переводится на школьный алгоритмический язык, а уже затем на язык программирования. Запишем алгоритм вычисления суммы первых n натуральных чисел. Для этого  воспользуемся циклом с параметром, поскольку заранее известно сколько раз будет  выполняться команда нахождения суммы. Во всех звеньях цепочки поменяем цикл "пока"  на цикл "для" и приведем пример перевода алгоритма с языка блок­схем на школьный  алгоритмический язык и на язык программирования Pascal. Рассмотрим нахождение количества натуральных чисел, сумма которых не больше  заданной. Для этого воспользуемся командой повторения с постусловием. Цель урока: составление программ с помощью алгоритмических структур. Задачи урока:  научится правильно составлять структуры;  развитие логического мышления и аккуратности у учащихся;  обучение работе с компьютерными тестами. Тип урока: изучение нового материала. Методы урока:  словесный;  практический;  самостоятельной работы. Форма урока: групповая, индивидуальная. Средства ведения урока: компьютеры, электронный учебник, схемы, тесты. Ход занятия 1. Организационный момент. Приветствие учащихся. Отметка явки на занятие. Сообщение темы и цели занятия. 2. Знакомство с новым материалом. Основные алгоритмические структуры План:  Последовательная алгоритмическая конструкция;  Ветвящаяся алгоритмическая конструкция;  Циклическая алгоритмическая конструкция. Элементарные шаги алгоритма при укреплении объединяются в алгоритмические  конструкции: последовательные, ветвящаяся, циклические, рекурсивные. В 1969 году  Эдсгер В. Дийкстра в статье «Структуры данных и алгоритмы доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций:  последовательных, ветвящихся, циклических. Последовательная алгоритмическая конструкция Алгоритм Р реализирован последовательную алгоритмическую конструкцию, если  каждые шаги алгоритма Р выполняются один раз, причем после каждого i­го шага  выполняются (i +1)­й шаг, если i­й шаг – не конец алгоритма. Ветвящаяся алгоритмическая конструкция Алгоритм Р реализован через ветвящуюся алгоритмическую конструкцию, если от  входных данных зависит, какие шагибудут выполнятся (последовательность  выполнения шагов алгоритма зависит от входных данных). При каждом конкретном  наборе входных данных ветвящаяся алгоритмическая конструкция сводится к  последовательной алгоритмической конструкции. Циклическая алгоритмическая конструкция Алгоритм Р реализован с использованием циклической алгоритмической конструкции,  если некая, подряд идущая группа шагов алгоритма может выполнять несколько раз в  зависимости от входных данных. Любая циклическая алгоритмическая конструкция  содержит в себе элементы ветвящейся алгоритмической конструкции. Количество повторений тела цикла может быть известно или нет. Если неизвестно  количество повторений тела цикла, завершение его работы происходит по достижению  определенного условия. Таким образом, циклы делятся на циклы с параметром и  условием. В цикле с параметром задается переменная, выполняется роль параметра цикла , её  начальное и конечное значения, приращение (шаг изменения значения параметра цикла). Блок­схема алгоритма цикла с параметром представлена на рисунке: Рис. Блок­схема алгоритма цикла с параметром. Условные циклы предназначены для организации итерационных вычислительных  процессов. Они подразделяются на циклы с предусловием и циклы с постусловием. В  цикле с предусловием перед выполнением тела цикла осуществляется проверка значения логического выражения или переменной логического типа, если значение этих величин  удовлетворяют условию работы цикла, то выполняется тело цикла, в противном случае,  выполняется следующий за циклом оператор. Таким образом, операторы тела цикла с  постусловием могут быть не выполнены ни одного раза. На рис. Представлена блок­схема  алгоритма цикла с постусловием. Цикл с постусловием предназначен для организации циклических алгоритмов, в которых  проверка условия работы цикла выполняется после исполнения операторов тела цикла.  По этой причине, операторы тела цикла всегда будут выполнены хотя бы один раз. На  рисунке представлена блок­схема алгоритма цикла с постусловием. Рис. Блок­схема алгоритма цикла с предусловием. Рис. Блок­схема алгоритма цикла с постусловием. 3. Закрепление материала. Работа на компьютере с электронными учебниками. 4. Самостоятельная работа. Вопросы и задания.  Приведите примеры алгоритмов, использующих последовательные алгоритмические конструкции.  Приведите примеры алгоритмов, использующие ветвящиеся алгоритмические  конструкции.  Приведите примеры алгоритмов, использующие циклические алгоритмические  конструкции.  Составить алгоритм нахождения суммы конечного ряда в виде блок­схемы.  Составить алгоритм нахождения факториала числа N в виде блок­схемы.  Составить алгоритм нахождения N­ой степени числа x в виде блок­схемы.  При каких начальных значениях переменных алгоритм закончит работу. 1. А= ­2; С=­3; 2. А=­3; С=­2; 3. А=­3; С=­3; 4. А=­2; С=­1; 5. А=­4, С=­3.  Определите выходные значения переменных А и С после выполнения алгоритма 1. 1, 7 2. 0, ­4 3. 1, 3 4. 0, ­5 5. Зацикливание  Укажите, какие из приведенных схем алгоритмов могут быть отнесены к основным  (типовым) схемам:  Найдите значение переменной F входных данных 1, 1, 3, вычисленное по блок­схеме  Найдите значение переменной F для входных данных 3, 3, 1 вычисленное по блок­ схеме 5. Продолжение изучения нового материала. АЛГОРИТМ И ЕГО СВОЙСТВО. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ  БЛОК­СХЕМ. План:  Алгоритм и его свойстваж  Описание алгоритма с помощью блок­схем. Алгоритм и его свойства Алгоритм – это точная конечная система правил, определяющая содержание и порядок  действий исполнителя над некоторыми объектами (исходными и промежуточными  данными) для получения (после конечного числа ходов) искомого результата. Приведенное выше определение не является формальным, это довольно подробное  описание понятия алгоритма, раскрывающее его сущность. Любой алгоритм не существует сам по себе, а предназначен для определенного  исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм  будет выполнять. Объекты, над которым исполнитель может совершать действия  образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен  алгоритм. Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ.  Однако любой алгоритм в отличие от рецепта или способа, обязательно обладает  следующими свойствами. 1. Выполнение алгоритма разбивается на последовательность законченных действий –  шагов. Каждое действие должно быть закончено исполнителем прежде, чем он  приступит к исполнению следующего действия. Это свойство алгоритма называется  дискретностью. Произвести каждое отдельное действие исполнителю предписывает  специальное указание в записи алгоритма, называемое командой. 2. Детерминированность – на каждом шаге однозначно определено преобразование  объектов среды исполнителя, полученной на предыдущих шагах алгоритма. Если  алгоритм многократно применяется к одному и тому же набору исходных данных,  то на выходе он получает каждый раз один и тот же результат. Замечание. Свойство детерминированности объединяет в себе одновременное  выполнение свойств точности и понятности. Поясним эти свойства. Точность – запись алгоритма должна быть такой, чтобы на каждом шаге его выполнения  было известно, какую команду надо выполнять следующей. Понятность (для данного исполнителя)­ алгоритм не должен содержать предписаний,  смысл которых может восприниматься неоднозначно. Это означает, что одно и то же  предписание после исполнителя должно давать один и тот же результат. То есть запись  алгоритма должна быть насколько четкой и полной, чтобы у исполнителя не возникало  потребности в принятии каких­либо самостоятельных решений, не предусмотренных  составителем алгоритма. Алгоритм всегда рассчитан на выполнение «не  размышляющего» исполнителя. Рассмотрим известный пример «бытового» алгоритма­ алгоритма перехода улицы:  «посмотрим налево. Если машины нет – дойти до середины улицы. Если есть – подожди,  пока они проедут». И т.д. представьте себе ситуацию, машина слева есть, но она не едет –  у нее меняют колесо. Если вы думаете, что надо ждать, то вы поняли этот алгоритм. Если  же вы решили, что улицу переходить можно, считая алгоритм подправленным ввиду  непредвиденных (по вашему мнению!)обстоятельств, то вы не усвоили понятие алгоритма. 3. Результативность – каждый шаг (и алгоритм в целом) после своего завершения  дает среду, в котором все объекты однозначно определены. Если по каким­либо причинам невозможно, то алгоритм должен сообщать, что решение задачи не  существует. При точном исполнении команд алгоритма процесс должен  прекратиться за конечное число шагов, и при этом должен быть получен ответ на  вопрос задачи. В качестве одного возможных ответов может быть и установление  того факта, что задача решений не имеет. 4. Конечность – завершение работы алгоритма за конечное число шагов.  Информатика оперирует только с конечными объектами и конечными процессами,  поэтому вопрос о рассмотрении бесконечных алгоритмов остается за рамки теории  алгоритмов. 5. Массовость – алгоритм правильно работает на некотором множестве исходных  данных, которое называется областью применимости алгоритма, т.е. алгоритм  пригоден для решения любой задачи из которого класса задач. Это свойство не  следует понимать как возможность решить много задач. Дадим уточненное понятие алгоритма, которое более формально описывает понятие  алгоритма, раскрывающее его сущность. Алгоритм – это конечная система правил, сформулированная на языке исполнителя,  которая определяет последовательность перехода от допустимых исходных данных к  конечному результату и которая обладает свойствами дискретности,  детерминированности, результативности, конечности и массовости. Описание алгоритм с помощью блок­схем При блок­схемном описании алгоритма изображается геометрическими фигурами  (блоками), связанными по управлению линиями (направлениями тока) со стрелками. В  блоках записывается последовательность действий. Данный способ по сравнению с другими способами записи алгоритма имеет ряд  преимуществ. Он наиболее нагляден: каждая операция вычислительного процесса  изображается отдельной геометрической фигурой. Кроме того, графическое изображение  алгоритма наглядно показывает разветвление путей решения задачи в зависимости от  различных условий, повторение отдельных этапов вычислительного процесса и другие  детали. Условные обозначения блоков схем алгоритмов Наименование Обозначения Функции Процесс Ввод­вывод Решение Предопределенный  процесс Документ Пуск­останов Выполнение операции или группы операций, в  результате которых изменяется значение,  форма представления или расположение  данных. Преобразование данных в форму, пригодную  для обработки (ввод) или отображения  результатов обработки (вывод). Выбор направления выполнения алгоритма в  зависимости от некоторых переменных  условий. Использование ранее созданных и отдельно  написанных программ (подпрограмм). Вывод данных на бумажный носитель. Начало, конец, прерывание процесса обработки  данных. Линии, соединяющие блоки и указывающей последовательность связей между ними,  должны проводится параллельно линиям рамки. Стрелка в конце линии может не  ставится, если линия направлена слева направо или сверху вниз. В блок может входить  несколько линий, то есть блок может являться преемником любого числа блоков. Из  блока (кроме логического) может выходить из двух блоков, и из него выходят две линии.  Если на схеме имеет место слияние линий, то место пересечения выделяются точкой. В  случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить. Схему алгоритма следует выполнять как единое целое, однако в случае необходимости  допускается обрывать линии, соединяющие блоки. Блок­схема должна содержать все разветвления, циклы и обращения к подпрограммам,  содержащиеся в программе. 6. Домашнее задание. Выучить конспект и подготовиться к тесту.