Основные алгоритмические конструкции
Министерство образования и науки Республики Казахстан
Западно-Казахстанский инженерно-гуманитарный университет
Институт языков и менеджмента «Евразия»
Деканат специальности «Информатика и ВТ»
КУРСОВАЯ РАБОТА
по предмету «Программирование на алгоритмических языках»
на тему:
Алгоритмическая конструкция Цикл. Цикл с постусловием
Выполнила: учащаяся 712-группы
Кусаинова Актоты
Проверил: магистр КозловМ.В.
Уральск 2013 г
Содержание:
I. ВВЕДЕНИЕ 1
1. Алгоритм 2
1.1Свойство алгоритма 3
1.2 Способы записи алгоритма 4
1.2.1 Словесно – формальный способ (запись на естественном языке) 5
1.2.2 Графический способ (с использованием графических примитивов, блок – схема) 6
1.2.3 Псевдокоды………………………………………………..
1.3 Основные алгоритмические конструкции…………………………..
1.3.1 Линейный алгоритм…………………………….
1.3.2 Ветвящийся алгоритм………………………….
1.3.3 Циклический алгоритм………………………….
1.4 Язык программирования Turbo Pascal…………………..
Цикл
Цикл с параметром
Цикл с предусловием
Цикл с постусловием
Заключение
Список литературы
Ссылки
Введение
Понятие алгоритм является одним из основных понятий современной математики и центральным понятием информатики. Еще на самых ранних ступенях развития математики (Древний Египет, Вавилон, Греция) в ней стали возникать различные вычислительные процессы чисто механического характера. С их помощью искомые величины ряда задач вычислялись последовательно из исходных величин по определенным правилам и инструкция. Со временем все такие процессы в математике получили название алгоритмов (алгорифмов).
|
|
|
Слово «алгоритм» возникло из названия латинского перевода книги арабского математика IX века Аль – Хорезми «Algoritmi de numero Indorum», что можно перевести как «Трактат Аль – Хорезми об арифметическом искусстве индусов», где были сформулированы выполнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.
В 1747 г. вместо слова алгоризм стали употреблять алгорисмус, смысл которого состоял в комбинации четырех операций арифметического исчисления – сложение, вычитание, умножение, деления.
К 1950 г. алгорисмус стал алгорифмом. Смысл алгорифма чаще всего связывался с алгорифмами Евклида – процессами нахождения наибольшего общего делителя двух натуральных чисел, наибольшей общей меры двух отрезков и т.п.
Термин алгоритм имеет следующие определения:
· последовательность действий со строго определенными правилами
|
|
|
выполнения;
· предписание, определяющее содержание и последовательность операций,
переводящих исходные данные в искомые результат;
· точное описание некоторого вычислительного процесса или любой иной
последовательности действий;
· точное и полное предписание о последовательности выполнения
конечного числа действий, необходимых для решения любой задачи данного типа.
Термин «цикл» был введен леди Адой Лавлейс (1815 - 1852), дочерью поэта Джорджа Байрона, которая считается первым программистом, точнее программисткой. Будучи соратником и спонсором Бэббиджа, она занималась разработкой программ для его машин и предложила ряд терминов и идей, которые используются в программировании и настоящее время. Среди этих идей следует упомянуть применение перфокарт, условие перехода, циклы, ячейки памяти. Бэббиджи Лавлейс подошли к таким важным понятиям, как подпрограмма, библиотека подпрограмм и некоторые другие. Термин «библиотека» был введен Бэббиджем, а термин «рабочая ячейка» и «цикл» - Адой Лавлейс.
В данной курсовой работе будут рассмотрены структуры алгоритмов, алгоритмические конструкции, циклы.
Алгоритм
Алгоритмом называют систему формальных правил (в виде последовательности арифметических и логических действий), однозначно определяющих процесс преобразования исходных данных в искомые результаты, т.е. однозначно приводящих к решению поставленной задачи.
|
|
|
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством – формальным исполнителем. Задача исполнителя – точная реализация уже имеющегося алгоритма. Формальный исполнитель не обязан вникать в сущность алгоритма, а возможно, и не способен его понять. Примером формального исполнителя может служить стиральная машина – автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может вступать в роли формального исполнителя, но в первую очередь формальным исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на конкретного исполнителя.
Каждый исполнитель может выполнять команды только из некоторого строго заданного списка – систем команд исполнителя. Для каждой команды должен быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие.
|
|
|
Свойство алгоритма
При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.
Однозначность алгоритма, под которой понимается единственность толкования исполнителем правила построения действий и порядок их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя.
Алгоритмам присущ ряд свойств, которые и объясняют, почему исполнитель может получить решение какой – либо задачи без особого труда. Большая часть этих свойств отмечена уже в определении алгоритма. Если какое – либо из свойств не выполняется, то такое описание последовательности действий над заданными объектами будем называть не алгоритмом, а предписанием.
Дискретность. Алгоритм состоит из последовательности законченных действий – шагов. Переход к следующему шагу возможен лишь после завершения предыдущего. Выполнять каждое отдельное действие исполнителю предписывает специальное указание записи алгоритма. Свойство алгоритма состоять из отдельных шагов называется дискретностью.
Определенность. Каждый алгоритм строится в расчете на некоторого исполнителя. Чтобы исполнитель мог решать задачу по заданному алгоритму, необходимо, чтобы каждая команда алгоритма всегда однозначно понималась и точно исполнялась. Это значит, что любая команда, выполненная много раз или различными исполнителями, имеющими эту команду в своей системе команд, при одних и тех же исходных условиях всегда должна давать один и тот же результат.
Массовость. Алгоритм решения задачи разрабатывается в общем виде, то есть он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
Результативность. Выполнение алгоритма должно приводить к конкретному результату – решению задачи – за конечное число шагов.
Способы записи алгоритма:
На практике наиболее распространены следующие способы представления алгоритмов:
Словесно – формальный способ (запись на естественном языке);
Словесно – формульный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Запись алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).
Алгоритм может быть следующим:
- Задать два числа;
- Если числа равны, то взять любое из них в качестве ответа и остановить, в противном случае продолжить выполнение алгоритма;
- Определить большее из чисел;
- Заменить большее из чисел разностью большего и меньшего из чисел;
- Повторить алгоритм с шага 2.
- Словесный способ не имеет широкого распространения, так как такие описания:
- Строго не формализуемы;
- Страдают многословностью записей;
- Допускают неоднозначность толкования отдельных предписаний.
Графический способ (с использованием графических примитивов, блок – схем);
Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок – схемы (в англоязычной литературе используют термин flowchart). Блок – схема алгоритма – это изображение алгоритма в виде связанных между собой с помощью линий перехода блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Для изображения основных алгоритмических структур и блоков на блок – схемах используют специальные графические символы (рис. 1).
| Символ | Наименование | Функция |
| 1. | Начало/конец алгоритма | Начало, конец, прерывание процесса обработки данных или выполнения программы |
| 2. | Процесс (блок вычисления) | Выполнение операции или группы операций, в результате которых изменяются значения, форма представления или расположение данных |
| 3. | Блок модификации | Выполнение операций, меняющих команды, или группы команд, меняющих программу |
 4.
| Условие (логический блок) | Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий |
 5.
| Ввод/вывод | Преобразование данных в форму, пригодную для обработки (ввод) или отображение результатов обработки (вывод) |
 6.
| Предопределенный процесс | Использование ранее созданных и отдельно описанных алгоритмов или программ |
 7.
| Соединитель | Указание связи прерванными линиями между потоками информации в пределах одного листа |
 8.
| Межстраничный соединитель | Указание на наличие связи между разъединенными частями схем, расположенных на разных листах |
Правила выполнения схем алгоритмов регламентирует ГОСТ 19.002 – 80 (единая система программной документации).
Пример записи алгоритма блок – схемой (рис 2.):
Составим алгоритм нахождения минимального числа М в последовательности из 
чисел 
Рис 2. Блок – схема алгоритма нахождения минимума в последовательности чисел
нет
нет
Псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
Псевдокодом представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритм могут на нем записываться и читаться как обычный текст. С другой стороны в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присуще формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г.Кушниренко и др. «Основы информатики и вычислительной техники» , 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 "Сегодня" + " " + "хорошая" + " погода"
'Конец программы
Основные алгоритмические конструкции
Линейный алгоритм
В алгоритмическом языке линейным является алгоритм, состоящий из команд, выполняющихся одна за другой. Они в записи алгоритма располагаются в том порядке, в каком должны быть выполнены предписываемые ими действия. Такой порядок выполнения называется естественным. Последовательность команд образует составную команду «цепочка», которая в записи блок-схемой имеет вид, приведенные ниже: a, b, c.
a)
| Алгоритмический язык | Блок-схема |
| действие 1 действие 2 ... действие n | 
|
b)
c)Определить значение переменной c после выполнения фрагмента алгоритма.
| Алгоритмический язык | Блок-схема |
| a:=3 c:=4 c:=a+c/2 |  
|
Ответ: 5
В математике к линейным алгоритмам относятся алгоритмы, представленные формулами. Они наиболее просты для программирования. Заметим, что естественный способ кодировки формул делает программу легкочитаемой, но нередко приводит к лишним вычислениям, поэтому, чтобы избежать повторных вычислений и сократить общее количество операций выполняйте тождественные преобразования выражений. С другой стороны, надо знать, что не всегда следует осуществлять оптимизацию, поскольку она является не правилом, а исключением. Этому есть три причины, главная из которых состоит в том, что оптимизация ухудшает наглядность программ, вторая - выгоды от оптимизации должны быть существенными и третья - современные системы, как правило, имеют удовлетворительные оптимизирующие компиляторы.
Ветвящийся алгоритм
Разветвляющимся называется алгоритм, в котором действие выполняется по одной из возможных ветвей решения задачи, в зависимости от выполнения условий. В отличие от линейных алгоритмов, в которых команды выполняются последовательно одна за другой, в разветвляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий).
В качестве условия в разветвляющемся алгоритме может быть использовано любое понятное исполнителю утверждение, которое может соблюдаться (быть истинно) или не соблюдаться (быть ложно). Такое утверждение может быть выражено как словами, так и формулой. Таким образом, алгоритм ветвления состоит из условия и двух последовательностей команд.
Структура «ветвление» бывает четырёх видов: «если – то», «если – то – иначе», «выбор», «выбор – иначе» .
Структура «если – то».
| Алгоритмический язык | Блок-схема |
| еслиусловие то действия всё | 
|
Пример 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 всё | 
|
Структура «выбор – иначе».
| Алгоритмический язык | Блок-схема |
| выбор приусловие 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:=«ошибка» всё | 
|
Циклический алгоритм
Циклическим называется алгоритм, в котором некоторая часть операции (тело цикла – последовательность команд) выполняется многократно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности – получения результата за конечное число шагов.
Перед операцией цикла осуществляется операции присвоения начальных значений тем объектам, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры: блок проверки условия и блок, называемый телом цикла.
Циклы бывают трёх видов: с предусловием «пока – делай», с постусловием «делай – пока»,со счётчиком «для».
Цикл с предусловием («пока-делай»). Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.
| Алгоритмический язык | Блок-схема |
| нц покаусловие тело цикла кц | 
|
Пример 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 Кц | 
|
Дата добавления: 2018-02-18; просмотров: 1860; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!