Реферат по информатике Алгоритмические структуры

МОУ Нижнеингашская средняя общеобразовательная школа №2

Реферат

по информатике на тему:

Выполнила: Нерушкина Е. В.

Проверила: Алексеева О.В.

п. Нижний Ингаш

2006 г.

1.

Введение

3

2.

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

4

3.

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

6

4.

Классификация понятия «Алгоритм»

6

5.

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

7

6.

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

8

7.

Линейная алгоритмическая структура

9

8.

Алгоритмическая структура «Ветвление»

• Полная развилка

• Неполная развилка

10

11

12

9.

Алгоритмическая структура «Цикл»

• Циклический алгоритм с предусловием

1. Цикл «Пока . . .»

2. Цикл «Для . . .»

• Циклический алгоритм с постусловием

14

14

14

16

17

10.

Вспомогательный алгоритм

18

11.

Заключение

21

12.

Список используемой литературы

22

13.

Приложение

23

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

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

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

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

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

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

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

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

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

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

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

Известно, что в раннем средневековье слово 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 в. компьютер сделался неотделимым атрибутом нашей жизни, общеупотребительной становится и компьютерная лексика. Слово «алгоритм» в наши дни известно каждому. Оно настолько уверенно шагнуло в разговорную речь, что сейчас мы нередко встречаем на страницах газет, слышим в выступлениях политиков. Слово живет, обогащается всё новыми значениями и смысловыми значениями, так что, скорее всего, в словарях будущего его уже никогда не придется снабжать пометкой устаревшее.

Алгоритм -

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Задача:

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

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

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

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

Найти:

F

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

• Программа:

Cls

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

Input m, a

F=m*a

Print F

End

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

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

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

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

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

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

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

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

Сложное условие - это последовательность простых условий, объединенных между собой знаками логических операций. Например, 5>3 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 «Вычисление значения составной функции

Input 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 x<>y

If x>y 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 x>y 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

Приложение 1

Понятие

Содержание

Объём

Алгоритм

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

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

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

I. По порядку выполнения действий:

1.1. Линейный;

1.2. Нелинейный.

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

1. Алгоритм, в котором команды выполняются однократно одна за другой.

2. Описание действий, которые выполняются однократно в заданном порядке.

3.Алгоритм, в котором команды выполняются одна за другой.

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

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

По наличию условия:

1. Алгоритм с условием;

2. Алгоритм без условия (Вспомогательный алгоритм).

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

1. Нелинейный алгоритм, в состав которого входит команда проверки условия.

По количеству проверок:

1. Разветвляющийся;

2. Циклический.

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

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

По наличию действия при ложном значении условия:

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

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

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

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

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

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

Циклический алгоритм

1. Описание действий, которые должны повторяться указанное число раз, или пока не выполнено заданное условие.

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

I. По расположению команды проверки условия:

1.1. Циклический алгоритм с предусловием;

1.2. Циклический алгоритм с постусловием.

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

1. Циклический алгоритм, в котором условие проверяется до выполнения команд - тела цикла.

I. По виду команды:

1.1. Цикл «пока»;

1.2. Цикл «для» ( с параметром).

Цикл «пока»

1. Циклический алгоритм с предусловием, в состав которого входит команда пока <условие>, делай <тело цикла>.

Цикл «для» ( с параметром)

1. Циклический алгоритм с предусловием, в состав которого входит команда «для каждого значения…выполнить», что требует того, что действия должны повторятся заданное число раз.

Циклический алгоритм с постусловием

1. Циклический алгоритм, в котором условие проверяется после выполнения команд - тела цикла.

Вспомогательный алгоритм (Подпрограмма, процедура)

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

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

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

Данный сборник понятий составлен

Алексеевой О. В.

Приложение 2

Есть люди, для которых соблюдение точного, сложного и многогранного режима - своего рода хобби. Такие всегда знают, что им надлежит делать в следующий момент, у них всё расписано. Другие поступают так по необходимости, из-за большого числа разнообразных нагрузок. Честь и хвала! Но для подавляющего большинства такое четкое расписание нереально: их жизнь слишком зависит от непредвидимых внешних обстоятельств. Поэтому главнейший принцип составления расписания: чем меньше предусмотрено в нем пунктов. Тем лучше. Забредший приятель, телефонный звонок или захватывающая телепередача легко разрушает наши намерения. Вы сердитесь на себя и на людей, но завтра сами своей неотложной нуждой разобьёте планы вашего друга. Лучше совсем отказаться от режима, чем постоянно переживать по поводу его нарушения. При составлении режима необходимо, прежде всего, считаться с реальностью внешнего мира. Но не забудем еще и реальность внутреннего мира. Люди различаются не только своим сознательным отношением к режиму, но и, если можно так выразиться, способностями к нему. Некоторым людям режим дня даётся почти без усилий, даже при необходимых условиях, он будто сам собой вытекает из их натуры. Я называю таких людей «ритмиками». Не берусь утверждать, что главное в возникновении этого типа: рано и прочно выработанная привычка или прирождённая психофизиологическая скоординорованность.

Другой полюс - дизритмики. Здесь всё наоборот: режим поддерживать трудно, и не потому, что нет желания: как раз стремление огромно, именно из-за трудности! Но мозг и организм этих людей, никак не вписываются ни в какие режимные рамки: их внутренние ритмы слишком сложны, изменчивы, мало предсказуемы, плохо управляемы. Два дня у дизритмика нет аппетита, на третий появляется волчий голод, три ночи почти нет потребности во сне, затем два дня сплошной сон…

Это два крайних полюса. Обычный человек находится где-то между тем и другим.

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

Если вы в течение ряда лет честно выдерживали режимы и перепробовали несколько вариантов с достаточной длительностью, но всё равно ничего не получалось, то вы, скорее всего, дизритмик. Это значит, что вам нет смысла стремиться к жестокому режиму, а целесообразнее по возможности следовать тому прихотливому расписанию жизни и работы, которые диктует ваш организм. Делайте режим возможно более гибким (я сознаю свою слабость этого совета для множества людей, зависящих от расписания работы общественных учреждений, транспорта, предприятий и т.д.). Не требуйте от себя высокой продуктивности те часы и дни, когда организм её не даст, подлавливайте хорошее время и полноценно выкладываётесь. Спите и ешьте, когда хочется и можется. Возможно, изучив себя, вам удастся и в неправильных колебаниях вашего состояния уловить кое-какие закономерности. Кроме того, всё меняется: со временем, быть может, изменятся и ритмы вашего организма; возможно, они упростятся и скоординируются. Во всяком случае, не считайте себя менее здоровым и полноценным, чем люди, легко поддерживающие режим.