 |
Чем отличается программный способ записи алгоритмов от других?
|
|
|
|
Тема: Основные алгоритмические конструкции и соответствующие им конструкции языка программирования QBasic
Выполнила: ученица 11 класса «А» Калашникова Анна
Руководитель: учитель информатики Карева И. Г.
Москва, 2004 год
Содержание:
Введение.
Алгоритм. Свойства алгоритма.
3. Способы записи алгоритма:
Словесно-формульный способ
Графический способ
Псевдокоды
Формальные языки
Основные алгоритмические конструкции
Линейный алгоритм
Ветвящийся алгоритм
Циклический алгоритм
Выводы
Список используемой литературы
Введение
Само слово «алгоритм» возникло из названия латинского перевода книги арабского математика IX века Аль-Хорезми «Algoritmi de numero Indoru», что можно перевести как «Трактат Аль-Хорезми об арифметическом искусстве индусов».
. Алгоритмы встречаются и в повседневной жизни, причем на каждом шагу, под названиями «инструкция», «рецепт», «метод решения». Однако не всякое предписание является алгоритмом. Инструкция «действуй по обстановке» или известное из мира сказок «пойди туда - не знаю куда, принеси то - не знаю что» не есть алгоритмы, так как они не точны, не указывают на конкретную последовательность действий. Алгоритм должен предусмотреть обработку любых ситуаций при его исполнении, и однозначно сказать, что делать в каждой из них.
Алгоритм.
Алгоритм - это точная последовательность предписаний, исполнение которых позволяет посредством конечного числа шагов получить решение задачи, однозначно определяемое исходными данными
Свойства алгоритма.
При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.
|
|
|
Однозначность алгоритма, под которой понимается единственность толкования исполнителем правила построения действий и порядок их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя.
Конечность алгоритма – обязательность завершения каждого из действий, составляющих алгоритм, и завершимость выполнения алгоритма в целом.
Результативность алгоритма, предполагающая, что выполнение алгоритма должно завершиться получением определённых результатов.
Массовость, т. е. возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. Для того чтобы алгоритм обладал свойством массовости, следует составлять алгоритм, используя обозначения величин и избегая конкретных значений.
Правильность алгоритма, под которой понимается способность алгоритма давать правильные результаты решения поставленных задач.
Эффективность – для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объём оперативной памяти и т. д.).
Способы записи алгоритмов:
На практике наиболее распространены следующие способы представления алгоритмов:
· Словесно-формульный способ (запись на естественном языке);
Словесно-формульный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).
Алгоритм может быть следующим:
1. задать два числа;
2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
3. определить большее из чисел;
4. заменить большее из чисел разностью большего и меньшего из чисел;
|
|
|
5. повторить алгоритм с шага 2.
Словесный способ не имеет широкого распространения, так как такие описания:
ü строго не формализуемы;
ü страдают многословностью записей;
ü допускают неоднозначность толкования отдельных предписаний.
· Графический способ (с использованием графических примитивов, блок-схем);
Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flow-chart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рисунке:
Начало/конец алгоритма
Блок вычислений
Начало (заголовок) цикла
Проверка условий
Ввод/Вывод данных
· псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой строны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
|
|
|
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г. Кушниренко и др. "Основы информатики и вычислительной техники", 1991. Этот язык в дальнейшем мы будем называть просто "алгоритмический язык".
Пример записи алгоритма на школьном АЯ:
алг Сумма квадратов (арг цел n, рез цел S)
дано | n > 0
надо | S = 1*1 + 2*2 + 3*3 +... + n*n
нач цел i
ввод n; S:=0
нц для i от 1 до n
S:=S+i*i
кц
вывод "S = ", S
Кон
· Формальные языки (QBasic, Pascal и тд.).
Пример:
'Вывод выражений с помощью оператора PRINT
PRINT "Вывод чисел:"
PRINT 23.4
PRINT-10.2
PRINT
PRINT
PRINT "Вычислим (10+4) - 4*(2-3'^2)"
PRINT (10 + 4)-4* (2-3^2)
PRINT
PRINT "В заключение объединим отдельные"
PRINT
PRINT "слова в текст:"
PRINT "Сегодня" + " " + "хорошая" + " погода"
'Конец программы
Основные алгоритмические конструкции:
Линейный алгоритм.
В алгоритмическом языке линейным является алгоритм, состоящий из команд, выполняющихся одна за другой. Они в записи алгоритма располагаются в том порядке, в каком должны быть выполнены предписываемые ими действия. Такой порядок выполнения называется естественным. Последовательность команд образует составную команду «цепочка», которая в записи блок-схемой имеет вид, приведенный на рисунке 1.
 | ||
 | ||
Рис.1 Блок-схема линейного алгоритма.
В математике к линейным алгоритмам относятся алгоритмы, представленные формулами. Они наиболее просты для программирования. Заметим, что естественный способ кодировки формул делает программу легкочитаемой, но нередко приводит к лишним вычислениям, поэтому, чтобы избежать повторных вычислений и сократить общее количество операций выполняйте тождественные преобразования выражений. С другой стороны, надо знать, что не всегда следует осуществлять оптимизацию, поскольку она является не правилом, а исключением. Этому есть три причины, главная из которых состоит в том, что оптимизация ухудшает наглядность программ, вторая - выгоды от оптимизации должны быть существенными и третья - современные системы, как правило, имеют удовлетворительные оптимизирующие компиляторы.
|
|
|
Основные алгоритмические конструкции:
Ветвящийся алгоритм.
При исполнении алгоритмов приходится не только находить значения величин, но и анализировать их свойства, сравнивать их друг с другом и в зависимости от результата сравнения выбирать ту или иную ветвь алгоритма. Алгоритмы, имеющие несколько ветвей, называются нелинейными. К таким относятся разветвляющиеся и циклические алгоритмы. Для их записи применяются составные команды.
Базовая структура "ветвление". Определяет выполнение действий в зависимости от выполнения условия. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
| Язык QBasic | Язык блок-схем |
| Неполное IF Условие THEN действия | 
|
| Полное IF Условие THEN действия 1 ELSE действия 2 | 
|
Пример алгоритма ветвления на алгоритмическом языке QBasic:
INPUT «1 или 2?»
IF=1 OR I=2 THEN
PRINT “Ок”
ELSE
PRINT “Вне диапазона”
END IF
Основные алгоритмические конструкции:
Циклический алгоритм.
Повторяющееся выполнение действий (групп действий),зависящее от выполнения условия, называется циклом.
Любой цикл состоит из трех частей: начала, проверки и тела цикла. Начало – всегда первая часть цикла. Главная его функция – подготовить цикл. Проверка определяет момент выхода из цикла.
Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:
| Язык QBasic | Язык блок-схем |
| Цикл типа пока. | |
| Do Until условие тело цикла (последовательность действий) Loop | 
|
| Do While условие тело цикла (последовательность действий) Loop |
|
| Цикл типа для. | |
| For i=i1 to i2 тело цикла (последовательность действий) Next i | 
|
Пример алгоритма цикл на алгоритмическом языке QBasic:
FOR I=1 TO 15
PRINT I
NEXT I
FOR I=7 TO –6 STEP –3
PRINT I
NEXT I
I=0
PRINT «Значение I в начале равно»; I
DO WHILE I<10
I=I+1
LOOP
PRINT “Значение I в конце цикла равно”; I
Выводы:
Чем отличается программный способ записи алгоритмов от других?
При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм.
|
|
|
Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем.
Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования.
|
|
|
