Методическая копилка

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

Вне зависимости от выбранной формы записи элементарные шаги алгоритма команды) при укрупнении объединяются в следующие алгоритмические конструкции: последовательные, ветвящиеся, циклические, рекурсивные. В 1969г. Эдсгер В. Дейкстра в статье «Структуры данных и алгоритмы» доказал. Что для записи любого алгоритма достаточно трёх основных алгоритмических структур:

1. Следование.
2. Ветвление.
3. Цикл.

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

      Ветвлением называется такая алгоритмическая структура, которой действие выполняется по одной из возможных ветвей решения задачи, в зависимости от значения логического выражения. Если логическое выражение принимает значение «истина» (true), то выход из соответствующего блока проверки условия происходит по ветке «да». Если логическое выражение принимает значение «ложь» (false), то выход из блока проверки условия происходит по ветке «нет».

Алгоритмическую структуру «ветвление» можно представить в четырех основных видах:

1. Вид «если-то».

4) Вид «выбор-иначе».

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

1. Цикл с предусловием (цикл вида «пока»).

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

2. Цикл с «постусловием» (цикл вида «до»)

Тело цикла выполняется «до» тех пор, когда логическое выражение принимает значение «истина». В этом виде цикла, в отличие от цикла с предусловием, тело цикла выполнится хотя бы один  раз.

       Если в цикле вида (1) выход «да» означает повторение тела цикла, то в цикле вида (2) выход «да» означает окончание повторения тела цикла.

       Существует и другое деление циклов. Так циклы можно подразделить на 2 типа:

1.   Цикл с заранее известным числом повторений (цикл по параметру). Этот цикл может быть представлен в следующем виде:  

  где:   i – переменная цикла, которая принимает целые значения;

          i0, ik, iΔ – параметры цикла, имеющие смысл:

                       i0 –  начальное значение переменной цикла;

                       ik –   конечное  значение переменной цикла;

                       iΔ – шаг по переменной цикла.

Если  iΔ=1, что бывает довольно часто, то в шестиугольном блоке заголовка цикла этот параметр просто не указывается.

       Здесь целая переменная цикла i принимает последовательность всех значений в диапазоне от i0 до ik.  При каждом значении i выполняется тело цикла. После последнего выполнения цикла при i= ik  происходит выход из цикла и дальнейшее продолжение алгоритма. Такой тип цикла встречается при решении задач на нахождение различного вида сумм и произведений, когда число слагаемых  в данной сумме или число сомножителей в данном произведении заранее известно. Также такой тип цикла применяется при решении разнообразных задач по обработке элементов одномерных и двумерных массивов.

2. Цикл с заранее неизвестным числом повторений

    (итерационный цикл).

Особенностью итерационного цикла является то, что число повторений действий, входящих в тело цикла, заранее неизвестно. При этом прекращение повторения тела цикла произойдет после того, как выполнится некоторое условие (цикл с постусловием). Или после того, как некоторое условие не выполнится (цикл с предусловием). На каком шаге выполнения тела цикла это произойдет заранее сказать невозможно. На каждом шаге вычислений происходит последовательное приближение и проверка условия достижения конечного результата. Алгоритм, в состав которого входит итерационный цикл называется итерационным алгоритмом. Такие итерационные циклы используются при вычислении различных бесконечных сумм с заданной точностью. Так как многие элементарные математические функции могут быть представлены в виде разложения в ряд, то это находит непосредственно практическое применение при вычислении значений этих функций. Кроме того, многие методы приближенных вычислений (численные методы) являются итерационными. При их применении необходимо обеспечить обязательное достижение условия выхода из цикла, т.е. сходимость итерационного вычислительного процесса. В противном случае может произойти зацикливание алгоритма, т.е. нарушится такое свойство алгоритма как результативность.

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

      Часто структура алгоритма такова, что внутри тела одного цикла необходимо организовать другой цикл. Такая структура получила название «цикл в цикле»  или «вложенный цикл». Глубина вложенности циклов при этом может быть и больше. Следует отметить, что два цикла могут быть расположены относительно друг друга только двумя различными способами:

1. Вложенные циклы.

2) Последовательные циклы.

ГЛАВА 5.  ОСНОВЫ ПРОГРАММИРОВАНИЯ НА ЯЗЫКЕ PASCAL.

       В этой главе будут кратко изложены основные конструкции алгоритмического языка высокого уровня Pascal, приведены примеры решения наиболее типичных задач. При этом алгоритмы решения этих задач будут представлены в виде подробных блок-схем состоящих из основных алгоритмических структур, которые были рассмотрены в предыдущей главе. Также будут представлены тексты программ на языке  Pascal,  соответствующие этим блок-схемам.

5.1   Компоненты алгоритмического языка высокого уровня и его основные понятия.

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

1. Алфавит.
2. Синтаксис.
3. Семантика.

Алфавит –   это фиксированный для данного языка набор основных

                     символов, так называемых «букв алфавита», из которых

                     должен состоять любой текст на этом языке. Никакие  

                     другие символы в тексте не допускаются.

Синтаксис – это правила построения фраз, позволяющие определить

                     правильно или неправильно написана та или иная фраза на

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

Семантика – это смысловое содержание конструкций, предложений

                     алгоритмического  языка. Являясь системой правил

                     истолкования отдельных языковых конструкций, семантика

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

Каждое понятие алгоритмического языка подразумевает некоторую синтаксическую конструкцию и определяемые ею свойства программных объектов или процесса обработки данных. Таким образом, понятие определяется во взаимодействии синтаксических и семантических правил. Синтаксические правила показывают, как образуется данное понятие из других понятий и букв алфавита, а          семантические правила определяют свойства данного понятия.

        Основными понятиями в любом алгоритмическом языке обычно являются следующие понятия:

1. Имена (идентификаторы). Идентификаторы употребляются для обозначения различных объектов программы (переменных, массивов, функций, подпрограмм и т.д.)
2. Операции. Обычно различают арифметические, логические, операции отношения и другие.
3. Данные. Данные – это величины, обрабатываемые программой. Можно выделить следующие основные виды данных:

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

4. Выражения. Выражения – это конструкции, которые предназначены для выполнения необходимых вычислений. Они состоят из констант, переменных указателей функций, объединенных знаками операций и скобок. Выражения могут быть арифметическими, логическими и символьными.
5. Операторы (команды). Операторы – это наиболее крупное и содержательное понятие алгоритмического языка. Каждый оператор представляет собой законченную фразу языка и определяет некоторый вполне законченный этап обработки данных. Операторы состоят из ключевых слов, данных и выражений. Операторы можно разделить на неисполняемые и исполняемые. Неисполняемые операторы предназначены для описания данных и структуры программы. Исполняемые операторы предназначены для выполнения различных действий (операторы присваивания, ввода и вывода, условный оператор, операторы цикла, операторы процедур и другие).

2. Краткие сведения о языке Pascal и его среде программирования.

Алгоритмический язык Pascal был создан в 1971 г. Его автор, швейцарский профессор Н. Вирт, разрабатывал Pascal как учебный язык структурного программирования. Наибольший успех в распространении языка Pascal был обусловлен появлением и последующим быстрым развитием персональных компьютеров. Фирма Borland International разработала систему программирования Turbo- Pascal для персональных компьютеров. Pascal – это не только язык программирования и транслятор с него, но еще и операционная оболочка, позволяющая пользователю удобно работать на языке Pascal. Транслятор – это системная программа, переводящая текст программы на некотором языке высокого уровня в текст эквивалентной программы на языке машинных команд. Постепенно Turbo – Pascal вышел за рамки учебного предназначения и стал языком профессионального программирования с универсальными возможностями. Транслятор с Turbo – Pascal оказался в числе лидеров по оптимальности создаваемых им программ. В силу этого в дальнейшем Pascal стал источником многих основных современных языков программирования (Ада, Модула – 2 и другие).

Реализовать тот или иной язык программирования на ЭВМ – это значит создать транслятор для этого языка для данной вычислительной машины. Существуют два принципиально различных метода трансляций. Они соответственно называются «компиляция» и «интерпретация». Для объяснения их различия можно предложить следующую аналогию: лектор должен выступить перед аудиторией на незнакомом ей языке. Перевод тогда можно организовать двумя способами:

1. Полный предварительный перевод. Лектор заранее передает текст выступления переводчику, тот записывает перевод, размножает его и раздает слушателям, после чего лектор может и не выступать.
2. Синхронный перевод. Лектор читает доклад, переводчик одновременно с ним предложение за предложением переводит выступление.

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

При компиляции в память ЭВМ загружается программа-компилятор. Она воспринимает текст программы на языке программирования высокого уровня как исходную информацию. После завершения компиляции получается программа на языке машинных команд. Затем в памяти остается только программа на языке машинных команд, которая выполняется и получаются конечные результаты.

Интерпретатор в течение всего времени работы программы находится во внутренней памяти компьютера. В оперативной памяти помещается и программа на языке программирования высокого уровня. Интерпретатор в последовательности выполнения алгоритма считывает очередной оператор программы, переводит его в команды и тут же выполняет эти команды. Затем переходит к переводу и выполнения следующего оператора. При этом результаты предыдущих переводов в памяти не сохраняются. При повторном выполнении одной и той же команды она снова будет транслироваться. При компиляции исполнение программы разбивается на два этапа: трансляция и выполнение. При интерпретации, поскольку трансляция и выполнение совмещены, программа на компьютере проходит в один этап. Однако откомпилированная программа выполняется быстрее, чем интерпретируемая. Поэтому использование компиляторов удобнее для больших программ, когда требуется быстрый счет. Программы на языках Фортран, Си, Паскаль как правило компилируются. Бейсик чаще всего реализован в виде интерпретатора.

Среда программирования языка Pascal является совокупностью системных программ, предназначенных для создания, отладки и выполнения Pascal – программы. Эта среда обеспечивает удобную операционную обстановку для работы программиста. Но ее назначение не общее, а специализированное: предоставлять пользователю необходимые средства работы с Pascal – программой.

Турбо-Паскаль, как язык программирования и как операционная оболочка значительно изменился за историю своего существования. Первый вариант Турбо-Паскаля фирма Borland выпустила в середине 80-х годов. К сегодняшнему дню создано шесть модификаций системы, известных как версии 3.0, 4.0, 5.0, 5.5, 6.0 и 7.0. Каждая из них представляет усовершенствование предыдущей версии. Все они создавались для семейства машин IBM PC и совершенствовались вместе с компьютерами. Если говорить о последней версии 7.0, то она не содержит каких-то принципиальных новшеств по сравнению с предыдущей версией 6.0. Введены некоторые расширения языка программирования, а также дополнительные сервисные возможности системной оболочки.

Программа на языке Pascal проходит три этапа обработки:

1. Создание текста программы.
2. Компиляция.
3. Выполнение откомпилированной программы.

В соответствии с этими функциями среда языка Pascal включает в себя три главные компоненты:

1. Редактор текстов.
2. Компилятор.
3. Исполнительную систему.

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

< имя файла >. pas

pas – это стандартное расширение имени файла, созданного системным редактором. Имя файла задается пользователем. Обращение к текстовому редактору происходит по команде Edit. 

Компилятор переводит программу с языка Pascal на язык машинных команд. При этом осуществляется контроль правильности программы с точки зрения правил языка программирования (синтаксический и семантический контроль). При обнаружении ошибки на этом этапе компиляции компьютер выдает о ней сообщение пользователю и прекращает работу. Программа, полученная в результате успешной компиляции, сохраняется на диске в файле с именем < имя файла >. exe.

Работа компилятора инициируется системной программой Compile.

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

В старших версиях языка Pascal имеется система отладки программ (Debug). С ее помощью можно просмотреть на экране значение любой переменной, найти значение любого выражения, установить новые значения переменной. Можно прерывать выполнение программы в указанных программистом местах, которые называются контрольными точками, а также выполнять программу пошагово оператор за оператором. Система отладки существенно облегчает программисту поиск ошибок на этом этапе выполнения программы.

3. Простейшие элементы языка Pascal.

Алфавит языка Pascal состоит из множества символов, включающих в себя буквы, цифры и специальные символы.

1. Используются латинские буквы от A до Z (заглавные) и от a до z (строчные).

ГЛАВА 4.  ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ    И ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.

4.1   Понятие алгоритма и его свойства

Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин.

Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

Алгоритм формулируется  в расчете на конкретного исполнителя, например, человека или особую машину – автомат. Алгоритм является руководством к действию для исполнителя, поэтому значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание».

Можно дать следующее неформальное определение понятие «алгоритм»:

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

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

Значение слова «алгоритм» очень схоже по смыслу со значением слов «метод», «способ». Однако любой алгоритм, в отличие от метода или способа, обязательно должен обладать следующими свойствами:

1. Массовость.

Алгоритм имеет некоторое число входных величин – аргументов, задаваемых до начала его работы. Цель выполнения алгоритма это получение результатов, имеющих вполне определенное отношение к исходным данным. Можно сказать, что алгоритм указывает последовательность действий по переработке исходных данных в результаты. Для алгоритма можно брать различные наборы входных данных, т.е. можно применять один и тот же алгоритм для решения целого класса однотипных задач, различающихся набором исходных данных. Это свойство алгоритма называют массовостью. Можно считать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда свойство массовости означает применимость алгоритма ко всем объектам данного класса. Множество объектов данного класса называют областью применимости алгоритма.

2. Понятность.

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

3.  Дискретность.

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

4. Конечность.

Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут повторяться многократно. Однако исполнение алгоритма все же закончится за пусть очень большое, но конечное число шагов. При этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть и установление того факта, что задача решения не имеет.

В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Так как, например, можно сформулировать процедуру вычисления числа π. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же прервать ее искусственно, например, введением условия вида: «Закончить вычисление после получения n десятичных знаков числа π», то эта вычислительная процедура приобретет свойство конечности. На этом принципе основано получение многих вычислительных алгоритмов. Строится бесконечный, сходящийся к искомому решению, процесс. Он обрывается на некотором шаге при выполнении определенного условия, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближенного решения зависит от числа выполненных шагов.

5. Определенность.

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

6. Эффективность.

Каждый шаг алгоритма должен быть выполнен точно и за конечное время. В этом смысле говорят, что алгоритм должен быть эффективным, т.е. действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Поэтому, например, указание вида: «Если любое целое число, большее 6, можно представить в виде суммы трех простых чисел, то значение счетчика увеличить на 1, иначе счетчик уменьшить на 1», – неэффективно, так как неизвестен способ доказательства истинности или ложности утверждения, содержащегося в нем. Следовательно, исполнитель не может выполнить этот шаг алгоритма, пока не будет найдено соответствующее доказательство.

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

Приведем примеры двух алгоритмов из области математики, которые обладают всеми указанными выше свойствами.

Пример 1. Рассмотрим алгоритм нахождения всех простых чисел в интервале от 1 до некоторого заданного N.         

Этот алгоритм носит название «Решето Эратофена», по имени древнегреческого ученого, впервые предложившего данный алгоритм.

1. Выпишем подряд все натуральные числа от 1 до N.
2. Возьмем первое число, большее 1 (это будет число 2), и зачеркнем каждое второе число, начиная отсчет со следующего за двойкой числа.
3. Возьмем первое оставшееся незачеркнутым число в данной числовой последовательности(при первом выполнении пункта 3 это будет число 3) и зачеркнем каждое третье число, начиная отсчет с числа следующего за этим числом (при первом выполнении пункта 3 это будет число 4), при этом ранее зачеркнутые числа участвуют в счете.
4. Если это незачеркнутое число окажется больше , то выполнение алгоритма закончено, иначе перейти к выполнению пункта 3.

В результате применения этого алгоритма в анной числовой последовательности от 1 до N незачеркнутыми останутся все простые числа.

Пример 2. Дано положительное действительное число Р. Требуется вычислить его квадратный корень с заданной точностью, например, с m знаками после запятой.

Алгоритм вычисления квадратного корня можно записать в следующем виде:

1. Запись числа Р разделить на группы Рi по 2 цифры влево и вправо от запятой . Заметим при этом, что самая левая и самая правая группы Р1 и Рn могут состоять из одной цифры. Группу Рn в этом случае дополнить до двух цифр, приписав 0 справа.
2. Подобрать такую цифру х, квадрат которой не превосходит Р1. Записать х в качестве первой цифры результата.
3. Вычислить .
4. Если нерассмотренных групп в числе Р больше нет и r=0 (т.е. корень вычислен точно) или если r≠0, но точность вычисления достигнута(т.е. у искомого числа получено m знаков после запятой), то выполнение алгоритма закончено.
5. Если нерассмотренные группы есть, или точность вычисления не достигнута, то к r дописать справа цифры очередной Рi группы; получившееся число обозначить через b. При этом возможны следующие варианты:

1. если очередная группа Рi стоит в записи числа первой после запятой, то дописать справа от х десятичную запятую;
2. если все группы в записи числа уже обработаны, то в качестве очередной группы Рi взять 00, при этом если число Р было целым, то дописать справа от х десятичную запятую.

6. Подобрать такую максимальную цифру у, что , где – целое число, совпадающее по записи с х без учета десятичной запятой. Тогда у будет очередной цифрой искомого числа.
7. Вычислить .
8. Приписать у справа к результату. Получившееся число обозначить через х.
9. Перейти к пункту 4.

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

Дадим более уточненное понятие алгоритма, которое также не является определением в математическом смысле слова, но более точно и формально описывает это понятие, раскрывая его суть.

Алгоритм – это конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами массовости, понятности, дискретности, конечности,  определенности и эффективности.

2. Формы записи алгоритмов

Существую различные способы для описания одного и того же алгоритма. На практике наиболее распространены следующие формы представления алгоритма:

1. Словесная или текстовая форма записи (примеры 1 и 2).
2. Графическая (запись в виде блок-схем).
3. Псевдокоды (например, запись алгоритмов на алгоритмическом языке в русской нотации).
4. Программная (запись алгоритма на каком-либо алгоритмическом языке высокого уровня).

Текстовая форма записи представляет собой описание последовательных этапов обработки данных и задается в произвольном изложении на естественном языке. Эта форма записи алгоритмов не имеет широкого распространения из-за своих недостатков:

а) такие описания строго не формализуемы;

б) эти описания страдают многословностью записей;

в) они часто допускают неоднозначность толкования отдельных

    предписаний.

Графическая форма записи алгоритма является более компактной и наглядной по сравнению с текстовой. Алгоритм в этом случае изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий (операторов). Такое графическое представление называется блок-схемой алгоритма. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условия, управлению повторением действий, окончанию обработки данных и т.д.) соответствует геометрическая фигура блока, представленная в виде блочного символа. Блочные символы при этом соединяются линиями переходов с указанием в виде стрелок направления движения, и тем самым определяющими очередность выполнения действий. Существуют следующие стандартные блоки, с помощью которых можно построить любой алгоритм и подробно изобразить его в виде блок-схемы:

1. Блоки начала и конца записи алгоритма.

Блок «начало» имеет один выход.

Блок «конец» имеет один вход.

Эти блоки являются указателями соответственно начала и конца записи алгоритма.

2. Блок ввода данных.

Имеет один вход и один выход. Внутри блока перечислены те переменные, которые в результате выполнения этого блока получили некоторые исходные значения, причем эти значения могут быть введены как с клавиатуры компьютера, так и из некоторого файла или с других внешних устройств ввода. После выполнения этого блока переменные (a, b, c), перечисленные в этом списке, будут иметь вполне конкретные значения.

3. Блок ввода данных.

Имеет один вход и один выход. Внутри блока перечислены те переменные, значения которых в результате выполнения этого блока будут выведены на экран монитора, в файл или любое другое внешнее устройство вывода.

4. Блок вычислений.

Имеет один вход и один выход. Действие блока заключается в том, что вычисляется значение выражения, стоящего справа от знака «=», и это значение присваивается переменной, стоящей слева от знака «=». Здесь следует сделать два важных замечания:

а) Для того, чтобы можно было однозначно вычислить значения выражения, стоящего справа, все переменные (a, b, c), которые присутствуют в этом выражении к этому моменту, должны иметь вполне конкретные числовые значения, т.е. либо введены с помощью блока ввода, либо вычислены через другие переменные. В частности, это выражение может состоять только из имени одной переменной или одной константы.

б) Слева от знака «=» может стоять только одно имя некоторой переменной, но не может быть константы или арифметического выражения. Это связано с тем, что знак «=» в блок-схемах понимается в смысле знака присваивания, а не в привычном для нас смысле знака математического равенства. Если математическая запись a=b эквивалентна записи b=a, что означает «левая часть a равна правой части b», или, что то же самое «левая часть b равна правой части a», то в блоке вычислений запись a=b означает, что значение переменной b присваивается переменной a. При этом старое значение переменной a пропадает. Запись b=a означает, что, наоборот, значение переменной a присваивается переменной b. В первом случае, в результате выполнения такого блока, переменные a и b будут иметь одно и то же значение, а именно то, которое до этого имела переменная b. Во втором случае переменные a и b также будут иметь одно и то же значение, но только то, которое до этого имела переменная a. Так, в вычислительном блоке часто можно встретить запись вида k=k+1, что означает увеличение значения переменной k (счетчик) на 1. Тогда как в математике запись k=k+1 просто неверна, т.к. эквивалентна 0=1. Чтобы подчеркнуть это различие, в некоторых книгах в блоке вычислений в качестве знака присваивания используется знак «:=».

5. Логический блок (блок проверки условия)

Блок имеет один вход и два выхода, помеченных словами «да» и «нет» (иногда «+» и «–» или «1» и «0»). Действие блока таково, что если вычисленное значение логического выражения равно «истине» (true), то выход осуществляется по ветке «да», если значение логического выражения равно «ложь» (false), то выход осуществляется по ветке «нет».

6. Блок организации цикла.  

Блок имеет один вход и один выход. Этот блок реализует один из возможных видов цикла, а именно «цикл с заранее известным числом  повторений». При этом переменная i называется переменной цикла, а in, ik, ih – параметры цикла, где in – начальное значение переменной цикла, ik – конечное значение переменной цикла,  ih – шаг по переменной цикла.

Тело цикла представляет собой некоторую последовательность действий, которая повторяется многократно. Действие этого блока заключается в том, что сначала переменная i принимает значение in, и при этом значении выполняется тело цикла. Затем i принимает значение in+ ih, и вновь выполняется тело цикла, и так далее, пока i не примет значение ik. С этим значением i последний раз выполнится тело цикла и произойдет выход из цикла. При этом закон изменения переменной i полностью задан его параметрами, т.е. не может быть изменен внутри тела цикла.

7. Блок подпрограммы.

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

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

1. Использование процедурного стиля программирования.
2. Последовательная детализация алгоритма решения задачи сверху вниз.

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

Процесс построения алгоритма методом последовательной детализации состоит в следующем. Сначала алгоритм формулируется в «крупных» блоках (командах), которые могут быть непонятны исполнителю (не входят в систему его команд) и записываются как вызовы вспомогательных алгоритмов. Затем происходит детализация, и все вспомогательные алгоритмы подробно расписываются с использованием команд, уже понятных исполнителю.

Запись алгоритма с помощью псевдокода занимает промежуточное место между записью алгоритма на естественном языке и его записью на формальном языке программирования высокого уровня. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. С одной стороны он близок к обычному естественному языку, поэтому алгоритмы на нем могут записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам программирования высокого уровня, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде так же, как и в формальных языках, есть служебные слова, смысл которых определен заранее. Единого псевдокода нет, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных базовых конструкций. В качестве примера можно привести псевдокоды, которые использовались для записи различных алгоритмов в учебнике по информатике авторов А.Г. Кушниренко и другие, а также авторов А.П. Ершов и другие.

Программная форма записи алгоритма представляет собой запись алгоритма на каком-нибудь языке программирования высокого уровня. В данном учебном пособии будут представлены записи некоторых алгоритмов на языке программирования Pascal.

МБОУ лицей № 180

МЕТОДИЧЕСКАЯ РАЗРАБОТКА УРОКА ПО ТЕМЕ

«Защита индивидуальных проектов»

Разработала: Сухова М.А., учитель  информатики

Н.Новгород

2015 г

Тема урока:

Подготовительная работа к занятию:

Проект - самостоятельная проблемная, исследовательская работа, творческая по самой своей сути.

Данный проект – краткосрочный, на его реализацию ушло 3 недели.

Задачи проекта:

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

Этапы работы над проектом:

Подготовительный

Цель: Мотивация, целеполагание участников проектировочной деятельности.

Содержание деятельности: Осознание проблемной ситуации, выбор темы проекта. Постановка цели. (Анализ дает ответ на вопрос, все ли основные компоненты есть для выполнения проекта)

Проектировочный

Цель: Планирование.

Содержание деятельности: Построение плана деятельности. Продумывание хода деятельности, распределение заданий в работе с учетом выбранной позиции. (Реально ли выполнение проекта в отведенные сроки)

Практический

Цель: Получение продукта, результата проектной деятельности за счет выполнения определенных действий

Содержание деятельности: Исследование. Сбор и обработка данных. Интерпретация результатов. Графическое представление результатов.

Аналитический

Цель: Рефлексия

Содержание деятельности: Сравнение планируемых и реальных результатов, обобщение, выводы

Контрольно-коррекционный

Цель: Коррекция

Содержание деятельности: Анализ успехов и ошибок, поиск способов коррекции ошибок

Заключительный

Цель: Защита проекта

Содержание деятельности: Представление содержания работы, обоснование выводов

Обучающимися представлены сайты, созданные средствами языка разметки гипертекста и краткие тезисы свей работы. Содержание сайтов - темы из радела программы «Коммуникационные технологии».  

Ход занятия:

1. Вступительное слово.
2. Защита проектных заданий.
3. Подведение итогов.

1. Вступительное слово.

Перед выполнением проекта  при изучении раздела «Телекоммуникационные технологии» мы рассмотрели все темы данного раздела.

Сегодня повторим изученные нами темы и подведем некоторые итоги в форме защиты проекта.

Хочу сказать несколько слов из истории метода проектов.

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

С начала XX в. метод проектов становится необыкновенно популярным в американской школе. Он как нельзя лучше соответствует духу и укладу жизни предприимчивых и жизнелюбивых жителей Соединенных Штатов. Американцы назвали метод проектов - «наш метод школьной работы».

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

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

В экспериментальной школе, работавшей под руководством Коллингса исключительно по методу проектов, за один первый год работы было задумано, проработано и доведено до конца самими детьми 58 «экскурсионных проектов»; 54 «проекта игр»; 92 «конструктивных проекта»; 396 «повествовательных проектов». Руководила всеми шестьюстами проектами единственная учительница этой школы.

На рубеже 1910-20-х гг. метод проектов входит в практику отечественной школы. Это история, полная драматизма. Сначала - «перспективный», а вскоре и «универсальный метод». Через пять с небольшим лет -«легкомысленное прожектерство». Так колебались оценки метода проектов в официальной педагогике. 

Под руководством русского педагога С.Т.Шацкого в 1905 году  была организована небольшая группа сотрудников, пытавшаяся активно использовать проектные методы в практике преподавания. Позднее эти идеи стали довольно широко, но недостаточно продуманно и последовательно внедряться в школу.

Современные исследователи истории педагогики отмечают, что использование «метода проектов» в советской школе в 1920-е гг.

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

1. отсутствие подготовленных педагогических кадров, способных работать с проектами;
2. слабая разработанность методики проектной деятельности;
3. гипертрофия «метода проектов» в ущерб другим методам обучения;
4. сочетание «метода проектов» с педагогически неграмотной идеей «комплексных программ».

В результате постановлением ЦК ВКП (б) в 1931 году метод проектов был осуждён. С тех пор и до недавнего времени в России не предпринималось сколько-нибудь серьёзных попыток возродить его в школьной практике.

Вместе с тем в зарубежной школе он активно и весьма успешно развивался ( в США, Великобритании, Бельгии, Израиле, Финляндии, Германии, Италии и др. метод проектов нашёл широкое распространение и приобрёл большую популярность за счёт рационального сочетания теоретических знаний  и их практического применения для решения конкретных проблем). « Я знаю, для чего мне надо всё, что я познаю. Я знаю, где и как я могу это применить» - вот основной тезис современного понимания метода проектов.

Система оценки проектной работы

Жюри должно оценивать работу группы по следующим критериям:

1. Актуальность и значимость темы.
2. Глубина исследования проблемы.
3. Оригинальность предложенных решений.
4. Качество выполнения продукта.
5. Убедительность презентации.
6. Артистизм и выразительность выступления.
7. Ответы на вопросы – умение отвечать.

Проекты обучающихся:

Вставить ссылки на проекты и первые страницы

Самоанализ занятия

Защита проектов – заключительное занятие. Его провести непросто: темы проектов различны, надо как-то связать их между собой. Подготовка требует и у учащихся , и у меня много времени, компетентности – надо суметь привлечь учеников к работе, организовать её. Урок показал, на что способны обучающиеся: они умеют ориентироваться в информационном пространстве, самостоятельно конструировать свои знания, умеют сравнивать, анализировать, проводить исследования, опыты, делать выводы, могут самостоятельно подготовить презентацию своей работы, умеют выступить перед аудиторией. Все работы носят творческий, проблемный, исследовательский характер. Урок достиг целей: мы побудили интерес к изучению информатики и показали ее нужность в реальной жизни.

1. Повторение основных понятий и определений из курса математики, на которых будет построена работа учащихся на уроке.

•  Дайте определение  функции
• Продолжите запись n!= …
• Запишите формулу вычисления числа  сочетаний из «n»  по «m»
• Запишите формулу Герона

2. Используя возможности интерактивной доски учащиеся собирают блок-схему, отображающую процесс решения задачи с использованием  компьютера

3. Анализ текстов программ (учащиеся работают в группах  )

{Преобразование целого числа в строку восьмеричного представления}

Procedure OctString(Nmb: integer; var S: string);

{Заголовок процедуры со списком формальных параметров;

 nmb- исходное целое число;

 S- строка для записи результатов преобразования }

Var

         P: integer;{объявление локальной переменной P}

Begin

          P:= Abs(Nmb);

          S:= ‘’;{пустая строка}

          Repeat

            S:= chr (p mod 8) +s;

            P:=p div 8;

         Until p=0;

         If  nmb<0 then

                 S:=’-’ + s;

End;

Begin

Writeln(‘введите число’);

Readln(InpNmb);

OctString(InpNmb, RezultString);

RezultString:= ‘Число ’+ str(InpNmb)+’ в восьмеричной с.с. равно’+ RezultString;

End.

4.  Используя электронный плакат учащиеся повторяют различные способы представления алгоритма

5. Учащимся предлагается рассмотреть иллюстрации и сделать вывод о том что их объединяет

6.      Ввести понятие рекурсии и рассмотреть на примере                  

     Программа должна прочитать n и найти n!                              

(Требуется рекурсивный алгоритм)

Решение:       n! = n*(n - 1)!            ;        0! = 1                    

Программа будет раскладывать n! на n*(n - 1)!                                   до тех пор, пока n не станет равно нулю, тогда по заданному  равенству 0! = 1, обратно умножит на «отделенные»                                                                                   множители и выведет результат.

Например:                                                                                       5! = 5*(5-1)! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! =                                = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 5*4*3*2*1 = 5*4*3*2 = 5*4*6 = 5*24 = 120                                

Программа:

var

   n: byte;

function Fact (n: byte): longint;

  begin

     if n=0 then  Fact := 1

               else   Fact := n*Fact(n-1);

  end;

begin

    readln(n);

    writeln(Factorial(n));

end.

7. Требуется написать программу, которая по заданному n находила бы n-ный член последовательности Фибоначчи (работа в группах при распределении ролей: постановка задачи, написание основной программы и рекурсивной функции с использованием различных типов циклов)

Рекурсивный алгоритм будет опираться на правила:                

Fib(n) = Fib(n-1)+Fib(n-2)

Fib(0)=0

Fib(1)=1

program fib;

var

n: byte;

(* Функция нахождения n-го числа Фибоначчи*)

function Fibona44i (n: byte): longint;

begin

if (n=0) then Fibona44i := 0

else if (n<3) then Fibona44i := 1

else

{ рекурсивныйвызов }

Fibona44i := Fibona44i(n-1)+Fibona44i(n-2);

end;

begin

write('Введите n'); readln(n);

writeln('Fib(',n,') = ',Fibona44i(n));

readln;

end.

8. Анализ термина recursio — «возвращение»

В некий день

один поэт с мозгами набекрень

поэму сел писать, начавши:    «В некий день

                                                       один поэт с мозгами набекрень

                                                       поэму сел писать, начавши:  «В некий день

9. Выводы урока

При построении проекта и написании программного кода программисты стараются не просто решить саму поставленную перед ними задачу, но и

• найти эффективное решение,
• сократить время на решение задачи,
• облегчить в будущем чтение программного кода.

Появление в программировании аппарата подпрограмм помогло решать программистам эти вспомогательные задачи.

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

На основе нисходящего структурного программирования – программирования по технологии «сверху вниз» – была разработана технология коллективной разработки больших программных комплексов.

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

10. Домашнее задание 

Подсчитать сумму ряда  11 + 22 + 33 + …nn.

Для решения этой задачи удобно использовать функцию вычисления степени числа.