Алгоритмические структуры

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ

ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ М. Е. ЕВСЕВЬЕВА»

Факультет физико-математический

Кафедра информатики и вычислительной техники

РЕФЕРАТ

АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

Автор работы _______________________________________В.Н. Слугина
Направления подготовки 44.03.05 Педагогическое образование
Профиль Математика. Информатика

Руководитель работы

канд. физ.-мат. наук, доцент__________________________ Т.В. Кормилицына

Оценка __________

Саранск 2022

Содержание

1.	Введение	3
2.	О происхождении слова «Алгоритм»	4
3.	Понятие алгоритма	6
4.	Классификация понятия «Алгоритм»	6
5.	Свойства алгоритмов	7
6.	Способы записи алгоритма	8
7.	Линейная алгоритмическая структура	9
8.	Алгоритмическая структура «Ветвление» Полная развилка Неполная развилка	10 11 12
9.	Алгоритмическая структура «Цикл» Циклический алгоритм с предусловием Цикл «Пока . . .» Цикл «Для . . .» Циклический алгоритм с постусловием	14 14 14 16 17
10.	Вспомогательный алгоритм	18
11.	Заключение	21
12.	Список используемой литературы	22
13.	Приложение	23

Введение

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

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

Решение любой задачи включает в себя следующие этапы:

1. Запись на формальном языке.

2. Построение блок-схемы.

3. Составление программы.

Чаще всего в литературе большое внимание уделяется первому и третьему этапам решения. Я же самым важным этапом считаю именно второй, т.к. это самый наглядный и доступный способ.

Цели моей работы:

• дать понятие алгоритма;

• провести классификацию алгоритмических структур на основе диалектической логики;

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

2. О происхождении слова «алгоритм»

Известно, что в раннем средневековье слово algorism использовали для обозначения способа арифметических вычислений на бумаге без применения счетных досок (абаков). Именно в таком значении оно вошло в некоторые европейские языки. Например, в авторитетном словаре английского языка «Webster s New World Dictionary», изданном в 1957 г., оно снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр.

Несмотря на то, что известно, когда появился термин «алгоритм», лингвисты по-разному пытались толковать его происхождение. Одни выводили algorism из греческих «алгирос» - «больной» и «арифмос» - «число». Правда, не понятно, почему числа «больные»? Другие склонялись к еще более экстравагантному объяснению, связывая слово с неким мифическим древним испанским правителем King Algor of Castil. Свой вариант предлагает и Энциклопедический словарь Брокгауза и Ефрона (1890 г.). В нем «алгортфм» производится от арабского слова «Аль-Горетм», то есть корень.

Н о истину удалось остановить не лингвистам, а историкам математики. Они доказали, что слово происходит от имени великого среднеазиатского ученого, автора популярнейшего на протяжении многих веков учебника по математике, аль-Хорезми, жившего в первой половине IX в. В латинской транскрипции его имя означает «Мухаммад, сын Муссы, отец Абдулы, родом из Хорезма». Хорезм – это историческая область на территории современного Узбекистана, центром которой является древний город Хива.

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

Позднее оно, в свою очередь, неоднократно подвергалось искажениям, последнее из которых, скорее всего, связано со словом arithmetic, имеющим греческое происхождение. Уже в новом написании оно встречается XVIII в. в одном из германских математических словарей «Vollstandiges mathematisches Lexicon», изданном в Лейпциге в 1747 г.

Постепенно все старинные значения вышли из употребления. К началу XX в. слово «алгоритм» уже означало «всякий арифметический или алгебраический процесс, который выполняется по строго определенным правилам», именно так оно объясняется в Большой Советской Энциклопедии (1926 г.).

То, что алгоритм воспринимался как термин сугубо специальный и малозначительный подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности его нет даже в десятитомной Малой советской энциклопедии, не говоря об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании БСЭ «алгоритм» характеризуется как одно из основных понятий (категорий) математики. За 40 лет из понятия, знакомого лишь узкому кругу специалистов, превратился в одно из ключевых понятий математики.

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

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

3 Понятие алгоритма

Алгоритм –

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

• это описание конечной последовательности действий, строгое исполнение которых приводит к решению задачи за конечное число шагов.

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

Свойства алгоритмов

Мир алгоритмов разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает каждый алгоритм. Основные свойства алгоритмов следующие:

• Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.

• Дискретность (прерывность, раздельность) — т.е. алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).

• Детерменированность — т.е. каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче.

• Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

Способы записи алгоритмов

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

• словесная (записи на естественном языке);

• графическая (изображения из графических символов);

Назначение	Обозначение
Начало блок-схемы
Ввод данных
Простая команда
Условие
Цикл с параметром
Конец блок-схемы

• программная (тексты на языках программирования).

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

• Линейный алгоритм – алгоритм, в котором команды выполняются однократно одна за другой.

• Задача:

Найти скорость, если известна масса и ускорение.

Дано: Решение:

m, a Находим скорость с помощью формулы

второго закона Ньютона.

Найти:

F

Блок-схема:

Программа: Cls Rem «Нахождение скорости» Input m, a F=m*a Print F End

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

• Условие – высказывание, которое может быть либо истинным, либо ложным.

Вспомним сюжет русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Направо пойдешь – коня потеряешь, налево пойдешь – пропадешь...»

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

• Если пошел дождь, то надо открыть зонтик.

• Если болит голова, то прогулку следует отменить.

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

Условные выражения могут быть простыми и сложными. Простое условие включает в себя два числа, две переменных или два арифметических выражения, которые сравниваются между собой с использованием операций сравнения (больше, меньше, равно и пр.). Например, 53, 2*8=4*4)

Сложное условие – это последовательность простых условий, объединенных между собой знаками логических операций. Например, 53 and 2*8=4*4 и т.д.

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

• Разветвляющийся алгоритм – алгоритм, в котором в зависимости от выполнения условия выполняется либо одна, либо другая последовательность действий.

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

Полный разветвляющийся алгоритм

• Задача:

Даны два числа. Найдите большее из двух чисел.

Дано: Решение:

а, b 1.Сравнить два числа.

Найти: 2.Записать большее.

m (большее из а и b)

• Блок-схема:

Вывод m

• Программа:

CLS

Rem «Найти большее из двух чисел»

Input a, b

If a b Then m = a Else m = b’ (реализация полной развилки (формы))

Print m

End

В разветвляющемся алгоритме при невыполнении условия действия могут не предусматриваются. Тогда это будет неполная форма, в которой действия пропускаются: «если условие, то …».

Неполный разветвляющийся алгоритм

• Задача:

Вычислите значения составной функции.

x³, при x ≤ 0

y= - x, при 0 x ≤ 4

4, при x 4

• Программа:

CLS

Rem «Вычисление значения составной функции

I nput x

If x ≤ 0 Then y = x³

If 0 x ≤ 4 Then y = x (реализация неполной развилки)

If x 0 Then y = 4

Print y

End

• Блок-схема:

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

• Циклический алгоритм – алгоритм с условием, в котором действия повторяются многократно.

По расположению команды проверки условия циклические алгоритмы делятся на:

1. Алгоритм с предусловием – алгоритм, в котором условие проверяется до выполнения команд – тела цикла.

2. Алгоритм с постусловием – алгоритм, в котором условие проверяется после выполнения команд – тела цикла.

Алгоритм с предусловием

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

• Цикл «Пока»:

• Задача:

Найдите наибольший общий делитель, с помощью алгоритма Евклида.

Дано: Решение:

х, y Пока два числа не равны, большее

число заменять разностью большего

Найти: и меньшего. Когда числа станут равны.

НОД Любое из них можно считать НОД-ем.

• Блок-схема:

• Программа:

Cls

Input x, y

Wheil xy

If xy Then x=x-y Else y=y-x

Wend

Print y

End

• Цикл «Для…»

• Задача:

Найти факториал числа.

Дано: Решение:

Факториал числа – это произведение

N натуральных чисел от 1 до этого числа.

Найдем факториал по определению.

Найти:

F

• Блок-схема:

• Программа:

Cls

Rem «Нахождение факториала числа»

F=1

For i to N

F=F * i

Next

Print F

End

Алгоритм с постусловием

• Задача:

Найдите наибольший общий делитель, с помощью алгоритма Евклида.

Дано: Решение:

х, y Делим большее число на меньшее с

остатком и заменяем его на получен-

ный остаток до тех пор пока остаток

не станет равным нулю. НОД-ем будет

Найти: являться последний остаток не равный

НОД нулю.

• Блок-схема:

• Программа:

Cls

Input x, y

Do

If xy Then x=x mod y Else y=y mod x

Loop Until x=0 or y=0

Print x+y

Допустим, вы хотите научиться жонглировать двумя или тремя мячами. Если внимательно приглядеться к действиям профессионального артиста и попытаться понять, как это ему удаётся делать, то оказывается – секрет в том, что надо научиться искусно, выполнять несколько определённых движений, которым присвоено следующие названия:

Бросок левой – подбросить мяч левой рукой.

Бросок правой – подбросить мяч правой рукой.

Захват левой – поймать мяч левой рукой.

Захват правой – поймать мяч правой рукой.

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

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

• Задача:

Найдите большее из трех чисел.

Дано: Решение:

а, b, с Сравнить первые два числа. Выбрать

большее. Теперь это большее

Найти: М сравнить с третьим числом. Выбрать

(большее) большее. Записать ответ.

• Блок-схема:

• Программа:

CLS

Rem «Найти большее из трех чисел»

Input a, b

X=a: y=b

Gosub 1

Print M

End

1.Rem «Нахождение большего из двух чисел»

If x y Then M = x Else M = y

Return

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

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

• определение понятия алгоритмической структуры;

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

• построение блок-схемы;

• запись программы на языке программирования QBasic.

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

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

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

1. Информатика и информационные технологии. Учебник для 10-11 классов/ Н.Д. Угринович. – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2005. – 511 с.: ил. ISBN 5-94774-189 –X

2. Информатика. 7-9 класс. Базовый курс. Теория. / Под ред. Н.В. Макаровой. – СПб.: Питер, 2003. – 368с.: ил. ISBN 5-273-00186-9

3. Энциклопедия для детей. Том 22. Информатика/Глав.ред. Е.А. Хлебалина, вед.науч.ред. А.Г. Леонов. – М.: Аванта+,2003. – 625с.:ил. ISBN 5-94623-040-9 ?ISBN 5-94623-001-8

4. Бейсик и Паскаль в вопросах и задачах.(Рабочая тетрадь 2) Житкова О.А., Кудрявцева Е.К. – М. Интеллект Центр. 2001 80 с.

5. Информатика. 5-6 класс. Начальный курс. / Под ред. Н.В. Макаровой. – СПб.: Питер, 2002. – 160с.: ил. ISBN 5-272-00129-Х

6. Конспекты уроков информатики в 9-11 классах: Практикум по программированию / Авт.-сост. А.А. Чернов – Волгоград: Учитель, 2005. – 236 с. ISBN 5-7057-0548-4

20