Алгоритмизация математических процессов на компьютере

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

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

·  Линейный алгоритм - набор команд (указаний), выполняемых последовательно во времени друг за другом.

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

·        Циклический алгоритм - алгоритм, предусматривающий  многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К  циклическим алгоритмам сводится большинство  методов вычислений, перебора вариантов.

        Цикл программы - последовательность  команд (серия, тело цикла), которая  может выполняться многократно  (для новых исходных данных) до  удовлетворения некоторого условия.

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

        На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.

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

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

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

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

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

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

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

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

         Вот в этом - “объяснение и  понимание” - и кроется различие  между понятиями “алгоритм”  и “способ”, “метод”, “правило”.  Правила выполнения арифметических  операций - это именно правила  (или способы), а не алгоритмы. Конечно, эти правила можно изложить в виде алгоритмов, но толку от этого не будет. Для того чтобы человек смог считать по правилам арифметики, его нужно научить. А если есть процесс обучения, значит, мы имеем дело не с алгоритмом, а с методом.

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

          
 
 
 
 

Блок-схемы. 

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

           Основным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. В начале обучения программированию, целесообразно не привязываться сразу к какому-либо языку, разрабатывать алгоритмы без записи на ЯПВУ, а, например, с помощью блок-схем или иным аналогичным способом. После такой "чистой" алгоритмизации учащимся или студентам проще перейти к записи того же алгоритма на определённом языке программирования. В настоящей публикации продемонстрирован именно такой подход. Основными алгоритмическими структурами (ОАС) являются следование, развилка и цикл. В более сложных случаях используются суперпозиции (вложения) ОАС.

Ниже  приведены графические обозначения (обозначения на блок-схемах) ОАС.                                                          Неполная развилка           Структура “следование”           Полная развилка                                  Неполная развилка

             

Цикл  с предусловием            Цикл с постусловием         Цикл с параметром

(цикл ПОКА)                                        (цикл ДО) 

На схемах СЕРИЯ обозначает один или несколько  любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла  с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.

     Начало  и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые  переменные записываются в параллелограмме.

Линейные  алгоритмы

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

Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?

       

          1. Ввести v1, v2, v3, t1, t2, t3.

          2. S1 := v1 * t1.

          3. S2 := v2 * t2.

          4. S3 := v3 * t3.

          5. S := S1 + S2 + S3.

          6. Вывести значение S.  

         7. Конец. 

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

Пример 2. Дано натуральное трехзначное  число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: "число n кратно каждой своей цифре", и ЛОЖЬ — в противном случае. 

        1. Ввести число n

           2. A := n mod 10 {разряд единиц}

           3. B := n div 100 {разряд сотен}

           4. C := n div 10 mod 10 {десятки}

           5. L := (n mod A=0) and (n mod      

                B=0) and (n mod C=0)

           6. Вывод L

           7. Конец 

На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.

Развилка

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

Пример 1. Вычислить значение функции  

        1. Ввести x.

           2. Если x£–12, то y:=–x2

           3. Если x<0, то y:=x4

           4. y := x–2

           5. Вывести y

           6. Конец 
 
 

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

Пример 2. Дано натуральное число n. Если число  нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое  число со знаком), удвоить его, иначе  — оставить без изменения. Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.

 

      1. Ввести число n

          2. Если число n нечетное и меньше 16384, то n := n * 2

          3. Вывод n

          4. Конец 
 

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

                               

Циклы

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

Пример 1. Подсчитать количество нечетных цифр в записи

натурального числа n.

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