Творческий проект по теме:Алгоритмы и основные алгоритмические конструкции
Содержание.
Введение. Обоснование проекта.
Алгоритмы.
Определение и примеры алгоритмов.
Свойства алгоритмов.
Способы описания алгоритмов.
Основные алгоритмические конструкции.
Алгоритмы линейной структуры
Алгоритмическая структура «ветвление».
Алгоритмическая структура "цикл".
Воз можность автоматизации деятельности человека.
Программное обеспечение, используемое для создания проекта.
Текстовый редактор Word.
Программа PowerPoint.
Заключение
Используемая литература.
Введение. Обоснование проекта.
В современном обществе освоение компьютерной техники и компьютерных технологий актуально буквально для всех. Естественно, что овладеть глубокими навыками работы с вычислительной техникой можно, изучив не только устройство компьютера, но и научившись самому разрабатывать алгоритмы и создавать программы. Кроме того, этот вид деятельности позволяет развить человеку алгоритмический стиль мышления, который поможет в любой профессии и в жизни.
Тема «Алгоритмизация и программирование» одна из наиболее сложных в курсе информатики, именно поэтому я решила создать обучающий компьютерный курс по теме «Основные алгоритмические конструкции». В своей работе я постаралась изложить материал на языке, понятном и школьнику, и начинающему пользователю. Этот проект можно предложить учащимся для самостоятельного изучения данной темы, а так же в помощь преподавателям информатики и компьютерной техники при проведении уроков.
Алгоритмы.
2.1. Определение и примеры алгоритмов.
Алгоритм это понятное и точное указание испол нителю совершить последовательность действий, направ ленных на решение поставленной задачи.
Термин имеет интересное историческое происхожде ние. В IX веке великий узбекский математик Аль-Хо-резми разработал правила арифметических действий над десятичными числами. Совокупность этих правил в Ев ропе стали называть "алгорзм". Впоследствии слово трансформировалось до известного вам сейчас вида и, кроме того, расширило свое значение: алгоритмом ста ли называть любую последовательность действий (не только арифметических), которая приводит к решению той или иной задачи. Можно сказать, что понятие выш ло за рамки математики и стало применяться в самых различных областях.
Человек, едва родившись, уже сталкивается с алго ритмами типа "в бутылочку с кефиром влить пастери зованный охлажденный отвар из риса...". Большин ство женщин и некоторые мужчины пользуются по варенной книгой сборником всевозможных описа ний последовательности действий, направленных на получение вкусных блюд. Еще более четкие указания по изготовлению продукции содержит обыкновенный аптечный рецепт в этом случае от точности выпол нения алгоритма может порой зависеть жизнь паци ента. Определенным алгоритмом действий "руковод ствуется" стиральная машина или микроволновая печь. Любому шахматисту известен способ, как поставить мат одинокому королю противника с помощью ладьи и своего короля. Школьный курс математики также предлагает большое разнообразие алгоритмов: умно жение "столбиком" и деление "уголком", приведение к общему знаменателю.
А теперь пример из художественной литературы. Вот как описывает известная писательница Андрэ Нортон в своей книге "Саргассы в космосе" алгоритм движения по гигантскому лабиринту. Главный герой Дейн, тайком наблюдая за главарем галактических гангстеров Ричем, быстро узнает этот алгоритм.
"Он дал Ричу отойти, а затем двинулся сле дом. Рич шагал уверенно, сразу было видно, что он отлично знает дорогу. Еще до того, как вдали в сером сумраке засветился луч фона рика Муры, Дейн уже знал формулу пути к выходу из лабиринта. Два поворота направо, один налево, еще три направо и пропустить один проход. И снова: два поворота направо, один налево и так далее до самого выхода. Рич на глазах у Дейна проделал этот цикл четыре раза подряд..."
Описанные выше алгоритмы обычно принято назы вать "бытовыми". Кроме них, можно выделить еще три крупных разновидности алгоритмов: вычислительные, информационные и управляющие. Первые, как пра вило, работают с простыми видами данных (числа, век торы, матрицы), но зато процесс вычисления может быть длинным и сложным. Информационные алгоритмы, на против, реализуют сравнительно небольшие процедуры обработки (например, поиск элементов, удовлетворяю щих определенному признаку), но для больших объемов информации. Наконец, управляющие алгоритмы непре рывно анализируют информацию, поступающую от тех или иных источников, и выдают результирующие сигна лы, управляющие работой тех или иных устройств. Для этого вида алгоритмов очень существенную роль играет их быстродействие, так как управляющие сигналы всегда должны появляться в нужный момент времени.
Итак, всюду мы встречаем алгоритмы, но удивитель ным образом это изобилие не только не мешает нам, но, наоборот, ведет нас кратчайшими путями к реше нию наших проблем.
2.2. Свойства алгоритмов.
Рассмотрим теперь, какими наиболее важными чер тами обладает алгоритм. Начнем с того, что алгоритм использует исходные данные, перерабатывая которые он получает требуемый результат. Данное положение легко проиллюстрировать в виде следующей наглядной схемы.
Таким образом, каждый алгоритм это правила, описывающие процесс преобразования исходных дан ных в необходимый результат. Заметим, что данное важ ное свойство в некоторых книгах приводят как опреде ление алгоритма.
Для того чтобы произвольное описание последователь ности действий было алгоритмом, оно должно обладать следующими свойствами.
Дискретность.
Процесс решения задачи должен быть разбит на пос ледовательность отдельных шагов, каждый из которых называется командой. Примером команд могут служить пункты инструкции, нажатие на одну из кнопок пульта управления, рисование графического примитива (линии, дуги и т.п.), оператор языка программирования. Наи более существенным здесь является тот факт, что алго ритм есть последовательность четко выделенных пунк тов, такие "прерывные" объекты в науке принято называть дискретными.
Понятность.
Каждая команда алгоритма должна быть понятна тому, кто исполняет алгоритм; в противном случае эта команда и, следовательно, весь алгоритм в целом не могут быть выполнены. Данное требование можно сформулировать более просто и конкретно. Составим полный список команд, которые умеет делать испол нитель алгоритма, и назовем его системой команд ис полнителя (СКИ). Тогда понятными будут являться только те команды, которые попадают в этот список. Именно из такой формулировки становится ясно, по чему компьютер такой "привередливый" при приеме введенных в него команд: даже если неверно написана всего одна буква, команда уже не может быть обнару жена в СКИ.
Приведем теперь несколько примеров. Рядовой школь ник вряд ли сможет найти статистическое среднее, но не потому, что это очень сложно, а просто из-за незна комого термина. Переформулируйте задачу (найти сум му чисел и поделить на их количество), и ученик немед ленно с ней справится. Или еще. Казалось бы, что мо жет быть проще, чем нарисовать на экране точку. Но, пока вы не будете знать команду, которая это делает, получить результат будет невозможно. Обратите внима ние, что совсем не обязательно речь идет об операторе языка программирования. Определенную СКИ, оформ ленную в форме панели инструментов, имеет и графи ческий редактор.
Определенность (или детерминированность)
Команды, образующие алгоритм (или, можно ска зать, входящие в СКИ), должны быть предельно четки ми и однозначными. Их результат не может зависеть от какой-либо дополнительной информации извне алгорит ма. Сколько бы раз вы не запускали программу, для одних и тех же исходных данных всегда будет получаться один и тот же результат.
При наличии ошибок в алгоритме последнее сфор мулированное свойство может иногда нарушаться. На пример, если не было предусмотрено присвоение пе ременной начального значения, то результат в некото рых случаях может зависеть от случайного состояния гой или иной ячейки памяти компьютера. Но это скорее не опровергает, а подтверждает правило: алгоритм должен быть определенным, в противном случае это не алгоритм.
Результативность.
Результат выполнения алгоритма должен быть обяза тельно получен, т.е. правильный алгоритм не может об рываться безрезультатно из-за какого-либо непреодоли мого препятствия в ходе выполнения. Кроме того, лю бой алгоритм должен завершиться за конечное число шагов. Большинство алгоритмов данным требованиям удовлетворяют, но при наличии ошибок возможны на рушения результативности. В качестве первого примера возьмем случай, когда алгоритм по тем или иным при чинам получит в качестве номера символа в строке от рицательное число. При попытке найти такой символ выполнение алгоритма, естественно, завершится аварий ным образом. Теперь пример другой ситуации. Рассмот рим алгоритм деления некоторого числа п "столбиком" на 3. При п 4,2 он благополучно получает результат, а вот для простейшего значения п = 1 процесс деления оказывается бесконечным. Впрочем, достаточно допол нить алгоритм условием на количество требуемых в от вете знаков после запятой, и результативность немед ленно будет восстановлена.
Корректность.
Любой алгоритм создан для, решения той или иной задачи, поэтому нам необходима уверенность, что это решение будет правильным для любых допустимых ис ходных данных. Указанное свойство алгоритма принято называть его корректностью. В связи с обсуждаемым свойством большое значение имеет тщательное тести рование алгоритма перед его использованием. Как пока зывает опыт, грамотная и всесторонняя отладка для слож ных алгоритмов часто требует значительно больших уси лий, чем собственно разработка этих алгоритмов. При этом важно не столько количество проверенных сочета ний входных данных, сколько количество их типов. Например, можно сделать сколько угодно проверок для положительных значений аргумента алгоритма, но это никак не будет гарантировать корректную его работу в случае отрицательной величины аргумента. Кстати гово ря, именно результатом недостаточной тщательности тестирования чаще всего объясняются многочисленные сюрпризы, преподносимые современным программным обеспечением в процессе эксплуатации.
Массовость.
Алгоритм имеет смысл разрабатывать только в том случае, когда он будет применяться многократно для различных наборов исходных данных. Например, если составляется алгоритм обработки текстов, то вряд ли целесообразно ограничивать его возможности только русскими буквами стоит предусмотреть также ла тинский алфавит, цифры, знаки препинания и т.п. Тем более что такое обобщение особых трудностей не вызы вает. Заметим, что массовость алгоритма в отдельных случаях может нарушаться: к числу подобных исключе ний можно отнести алгоритмы пользования некоторы ми простыми автоматами (для них входными данными служит единственный тип монет) или довольно яркий и впечатляющий алгоритм поиска клада» который бессмысленно выполнять повторно.
2.3. Способы описания алгоритмов.
1) Словесное или словесно-формульное описание алгоритма.
Описание алгоритма с помощью формул и слов. Для его понимания рассмотрим пример.
Задача 1. Составить алгоритм начисления зарплаты согласно следующему правилу:
Если стаж работы сотрудника менее 5 лет. То зарплата 130 руб., при стаже работы от 5 до 15 лет – 180 руб.. при стаже свыше 15 лт зарплата повышается с каждым годом на 10 руб.
Сформулируем задачу в математическом виде: вычислить
Где ZP – зарплата; ST – стаж работы.
Словесно-формульное описание алгоритма решения задачи:
1. Ввести ST-перейти в п.2.
2. Если ST < 5, то ZP:=130, перейти в п.4, иначе перейти в п.3.
3. Если ST < =15, то ZP:=180, перейти в п.4, иначе ZP:=180+(ST-15)10, перейти в п.4.
4. Вывести (отпечатать) значение ZP, перейти в п.5.
5. Вычисления прекратить.
2) Графическое описание алгоритма.
Описание с помощью блок – схем алгоритма. Схема алгоритма представляет собой систему связанных геометрических фигур. Каждая фигура обозначает один этап процесса решения задачи и называется блоком. Порядок выполнения этапов указывается стрелками, соединяющими блоки. В схеме блоки стараются размещать сверху вниз, в порядке их выполнения. Для наглядности операции разного вида изображаются в схеме различными геометрическими фигурами.
Операция присваивания изображается прямоугольником, например
13 SHAPE \* MERGEFORMAT 1415
Операция Ввод и Вывод изображаются параллелограммом, например:
13 SHAPE \* MERGEFORMAT 1415
Каждый из трех указанных блоков имеет один вход и один выход.
Операция Условный переход изображается ромбом; блок имеет два выхода – Да и Нет, например:
13 SHAPE \* MERGEFORMAT 1415
Если условие выполняется – выходим из блока по выходу Да, если не выполняется – по выходу Нет.
Начало процесса решения задачи обозначается блоком Начало. Завершение процесса решения задачи обозначается блоком Останов. Последние два блока обозначаются так:
13 SHAPE \* MERGEFORMAT 1415
На рис 1. изображена схема решения задачи 1.
13 SHAPE \* MERGEFORMAT 1415
Рис 1. Схема решения задачи 1.
3) Описание алгоритма на алгоритмическом языке.
Алгоритмический язык – это средство для записи алгоритмов в аналитическом виде, промежуточном между записью алгоритма на естественном (человеческом) языке и записью на языке ЭВМ (языке программирования).
Пример: запись алгоритма решения задачи 1 на алгоритмическом языке:
алг ЗАРПЛАТА (цел ST, вещ ZP)
арг ST
рез ZP
нач
если ST<5
то ZP:=130
иначе
если ST<=15
то ZP:=180
иначе ZP:=180+(ST-15)*10
все
все
кон
Из примера видно, что запись алгоритма на алгоязыке весьма близка к его словесно-формульному описанию. Разница между ними состоит в том, что в алгоязыке используется ограниченный набор терминов, более строгие правила записи оперции и т.д. с целью обеспечения однозначности понимания алгоритма.
4) Программный способ описания алгоритма.
Запись алгоритма на языке программирования требует от человека знания синтаксиса и семантики этого языка. Языков программирования высокого уровня существует очень много. В школьной практике наиболее часто изучают Бейсик и Паскаль.
На языке Бейсик решение нашей задачи будет иметь вид:
10 REM «ЗАРПЛАТА»
20 INPUT «ВВЕДИТЕ СТАЖ РАБОТЫ»
30 IF ST<5 THEN ZP=130: GOTO 50
40 IF ST<=15 THEN ZP=180 ELSE ZP=180+(ST-15)*10
50 PRINT ZP
60 END
Основные алгоритмические конструкции.
Существуют всего три базовые алгорит мические структуры, комбинируя которые можно пост роить любой алгоритм: это следование, ветвление и цикл.
Алгоритмы линейной структуры.
Алгоритмы линейной структуры состоят из последовательности каких-либо действий, иногда такую структуру называют «следование».
Базовая структура "следование" образуется последо вательностью действий, следующих одно за другим:
Простейшие задачи имеют линейный алгоритм ре шения. Это означает, что такой алгоритм не содержит проверок условий и повторений, действия в нем выпол няются последовательно, одно за другим, т.е. при его реализации используется структура "следование"'.
Рассмотрим примеры алгоритмов ли нейной структуры.
Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине vl км/ч, в гору v2 км/ч и под гору -" v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?
Составим алгоритм решения этой задачи (команда присваивания здесь обозначена знаком ":= "):
1. Ввести vl, v2, v3, tl, t2, t3.
2. SI := vl * tl.
3. S2 := v2 * t2.
4. S3 := v3 * t3.
5. S := Sl+ S2 + S3.
6. Вывести значение S.
Конец.
Для проверки работоспособности алгоритма необхо димо задать значения входных переменных, вычислить конечный результат по алгоритму и сравнить с результа том ручного счета. В разработанном алгоритме v1, v2, v3, t1, t2, t3 аргументы, S результат, SI, S2, S3 промежуточные величины.
Пример 2. Дано натуральное трехзначное число п, в записи которого нет нулей. Составить ал горитм, который возвращает значение "истина", если верно утверждение: "чис ло п кратно каждой своей цифре", и "ложь" в противном случае.
1. Ввести число п.
2. А := n mod 10 (разряд единиц).
3. В := n div 100 (разряд сотен).
4. С := n div 10 mod 10 (десятки).
5. L :=(n mod A = 0) and (n mod В = 0) and (n mod С = 0)
6. Вывод L.
7. Конец
На приведенном выше алгоритме div и mod соответ ственно операции деления нацело и получения остатка от целочисленного деления.
Алгоритмическая структура «ветвление».
Ветвления играют в алгоритмах очень большую роль, поскольку предусматривают корректную реакцию на са мые разнообразные ситуации, возникающие в процессе обработки информации. Благодаря этой структуре алго ритм приобретает способность выбирать один из суще ствующих вариантов работы, наиболее подходящий к сло жившейся в данный момент ситуации. В частном случае речь может идти о выполнении или игнорировании при определенных условиях того или иного участка алгоритма.
Значение ветвления в современном программном обес печении трудно переоценить. Достаточно вспомнить стандартные элементы управления, такие, как меню, радио кнопки, флажки проверки или Списки. Именно они дают возможность пользователю чувствовать себя за компью тером свободно и комфортно и выбирать те режимы работы, которые ему нужны. С точки зрения нашего разговора анализ состояния любого из органов управле ния осуществляется в виде ветвления.
Команду ветвления чаще всего называют по первому слову конструкции если. Вся команда обычно записы вается в форме одного из приведенных ниже вариантов:
если логическое выражение
то серия команд 1
иначе серия команд 2
конец ветвления
если логическое выражение
то серия команд
конец ветвления
Первый вариант принято называть полным, а вто рой - неполным.
Прокомментируем входящую в описание терминологию. Под логическим выражением (ЛВ) подразумевается несколько довольно разнообразных конструкций. Чаще все го в качестве ЛВ используется общепринятое условие вида: х = 0, х < у или аналогичное, (допускается даже объединение нескольких таких условий в одно при помощи логических операций и, или, не).
Поэтому во многих книгах в рассматриваемой части конструкции просто пишется термин условие. Но подобные условия не исчерпывают всех воз можностей задания ветвления. Иногда после слова если помешается некоторое высказывание (утверждение), относительно которого можно однозначно сказать, истинно оно или ложно. Вот простейший пример: если небо хмурится, то надо взять с собой зонтик. В языках программи рования оба описываемых случая удается объединить в еди ное целое логическое выражение.
Еще один термин это серия команд. Более просто, хотя и длиннее, можно сказать "последо вательность команд" (между прочим, вспомните о популярных телесериалах, которые принято смотреть подряд серия за серией, названия похожи не случай но). В частном случае серия может состо ять из единственной команды.
Служебные слова если, то, иначе достаточно стан дартны. Что касается конца ветвления, то здесь в раз личных учебниках пишутся разные конструкции, начи ная от короткого все до довольно забавного кесли сокращения от "конец если".
Изображение ветвления в виде блок-схемы выгля дит следующим образом (справа неполный вариант ветвления):
13 SHAPE \* MERGEFORMAT 1415
Глядя на рисунок, легко понять, почему ветвление часто называют развилкой.
Приведем также полную форму ветвления в различных алгоритмических языках.
Бейсик, Паскаль
if <ЛВ> then < серия команд 1>
else < серия команд 2>
Си
if (<ЛВ>) <серия команд 1>;
else <серия команд 2>
Очевидно, что запись отличается лишь незначитель ными второстепенными деталями. Для получения не полного ветвления ветвь else разрешается опускать.
Приведем пример алгоритма с использованием ветв ления.
Задача. Из трех предложенных чисел А, В и С вы брать и вывести максимальное.
Решение:
Идея алгоритма решения задачи несложная. Снача ла сравним между собой А с В И наибольшее значение сохраним во вспомогательную переменную М. Затем, если окажется, что С > М, то заменим значение М; в противном случае никаких действий предпринимать не нужно.
Данная задача интересна тем, что в ней одновремен но используются оба варианта развилки полный и неполный.
Блок-схема решения выглядит следующим образом.
13 SHAPE \* MERGEFORMAT 1415
Здесь на схеме А изображен общий стратегический при решения задачи, а на схеме Б его развернутая реализация. Если не кон кретизировать деталей анализа исходных чисел, то ал горитм на схеме А получается линейным, а вовсе не разветвляющимся, как следует из схемы Б. Практиче ский вывод из этого факта такой: по скольку в чистом виде разветвляющийся алгоритм прак тически никогда не встречается, то лучше говорить не о типе всего алгоритма в целом, а о типе его отдель ных элементов (Частей).
А вот как выглядит решение этой задачи на языке Паскаль:
program maximum_3x (input, output);
var a,b,с,m:real;
begin
readln(a,b,c);
if a > b then m := a else m := b;
if с > m then m := c;
writeln (axlmum=', m: 9: 4)
end.
Для демонстрации важности конструкции ветвления приведем еще несколько примеров. Прежде чем напеча тать текст на бумаге, любой компьютер обязательно про верит, включено ли печатающее устройство и есть ли в нем бумага. Если хотя бы одно из условий не выполнено, то печать не производится, а вместо этого на экран выда ется диагностическое сообщение. Многие теоремы пред ставляют собой прекрасный пример ветвления, напри мер, прочтите внимательно третий признак равенства треугольников: если все стороны одного треугольника соответственно равны сторонам другого треугольника, то такие треугольники равны. Те, кто предпочитает матема тике русский язык, могут вспомнить такое правило: если корень слова начинается со звонкой согласной, то на конце приставки пишется "з", а иначе "с". В химии суще ствует известный алгоритм, как по цвету лакмусовой бу мажки определить свойства среды. Наконец, в учебнике [3] приводится множество забавных примеров с "если-то", заимствованных из книги Григория Остера "Вред ные советы"; например, такой:
Если друг на день рожденья
Пригласил тебя к себе,
То оставь подарок дома
Пригодится самому.
Существует довольно большое количество алгоритмов, в которых приходится выбирать не из двух, а из не скольких вариантов. В таких случаях есть разные воз можности построить алгоритм. Самая простая соста вить комбинацию из нескольких ветвлений. Другой аль тернативный способ состоит в том, чтобы использовать специальную команду, которая называется выбор. Пос ледняя специально придумана для упрощения записи алгоритма в обсуждаемой ситуации.
2.4.3. Алгоритмическая структура "цикл".
Достаточно часто при организации алгоритма реше ния задачи необходимо одну и ту же определенную пос ледовательность команд выполнить несколько раз под ряд. Конечно, самый простой способ записать эти команды несколько раз друг за другом, и необходимое повторение действий будет организовано. Но как быть в тех случаях, когда количество команд, которые исполня ются несколько раз, слишком велико? Или само коли чество повторений команд огромно? Или вообще неиз вестно, а сколько же раз нужно повторить последова тельность команд? Решить все эти проблемы можно, если использовать алгоритмическую структуру цикл.
Командой повторения, -или циклом, называется такая форма организации действий в алгоритме, при которой выполнение одной и той же последовательности команд повторяется до тех пор, пока истинно некоторое логи ческое выражение.
Для организации цикла необходимо выполнять следую щие действия:
перед началом цикла задать начальное значение па раметров (переменных, используемых в логическом выражений, отвечающем за продолжение или за вершение цикла);
внутри цикла изменять переменную (или перемен ные), которая сменит значение логического выра жения, за счет которого продолжается цикл, на про тивоположное (для того чтобы цикл в определен ный момент завершился);
вычислять логическое выражение проверять ус ловие продолжения или окончаний цикла;
выполнять операторы внутри цикла;
управлять циклом, т.е. переходить к его началу, если он не закончен, или выходить из цикла в против ном случае.
Различают циклы с известным числом повторений (цикл с параметром) и итерационные (с пред- и постусловием),
Приведем обозначение каждого из видов циклов на блок-схемах алгоритмов.
13 SHAPE \* MERGEFORMAT 1415
На схемах "Серия" обозначает один или несколько любых операторов (команд); ЛВ есть логическое вы ражение (если его значение истина, переход проис ходит по ветви, обозначенной да, иначе по нет).
На схеме цикла с параметром использованы обозна чения:
ПЦ параметр цикла,
НЗ начальное зна чение параметра цикла,
КЗ конечное значение па раметра цикла,
Ш шаг изменения параметра цик ла.
Серию команд, которые выполняются в цикле, называют телом цикла.
Опишем схематично, как выполняется каждый из циклов.
Цикл с предусловием:
а) вычисляется значение логического выражения;
б) если значение логического выражения истина, переход к следующему пункту, иначе к п. д);
в) выполняется тело цикла;
г) переход к п. а);
д) конец цикла.
Цикл с постусловием:
а) выполняется тело цикла;
б) вычисляется значение логического выражения;
в) если значение логического выражения ложь, переход к п. а), иначе к следующему пункту;
г) конец цикла.
Замечание. Таким образом, цикл с постусловием организо ван, в частности, в алгоритмических языках Паскаль и QBasic. В языке Си переход к повторению вычислений, как и в цикле с предусловием, осуществляется в случае истинности логического выражения.
Цикл с параметром:
а) вычисляются значения выражений, определяющие начальное и конечное значения параметра цикла;
б) параметру цикла присваивается начальное значение;
в) параметр цикла сравнивается с конечным значением;
г) если параметр цикла превосходит (при положи тельном шаге) конечное значение параметра цикла (или, наоборот, меньше конечного значения параметра цикла при отрицательном шаге), переход к п. з), иначе к сле дующему пункту;
д) выполняется тело цикла;
е) параметр цикла автоматически изменяется на зна чение шага;
ж) переход к п. в);
з) конец цикла.
Циклы с предусловием и постусловием в большин стве случаев (за исключением отдельных реализаций алгоритмических языков) являются более универсаль ными по сравнению с циклом с параметром, посколь ку в последнем требуется заранее указать число повто рений, в то время как в первых двух это не требуется. Цикл с параметром в любом случае может быть преоб разован к циклу с пред- или постусловием. Обратное верно не всегда.
Рассмотрим примеры задач, при решении которых необходим цикл.
Пример 1. Подсчитать количество нечетных цифр в записи натурального числа п.
Идея решения. Из заданного числа необходимо выби рать из младшего разряда цифру за цифрой (отбрасывая просмотренную) до тех пор,
пока число не исчерпается, т.е. станет равным нулю. Каждую нечетную цифру учи тывать.
1. Ввести число п.
2. К:= 0 (подготавливаем счетчик)
3. Если n = 0, переход к п. 7.
4. Если n mod 10 Mod 2=1, тоК:=К+1.
5. n:= n div 10.
6. Переход к п. 3.
7. Вывод К.
8. Конец.
Задача решена двумя способами.
Первое решение оформлено с использованием цикла
с предусловием, второе с постусловием
(div и mod обозначают опе рации вычисления
частного и остатка при делении на цело).
Пример 2. Дана последовательность, общий член
которой определяется формулой:
Вычислить при n > 2 сумму тех ее членов,
которые больше за данного числа
·.
При решении задачи находится очередной член
последовательности и, если он больше
·, добавляется
к сумме.
1. Ввести
·.
2. S: = 0.
3. А: = 1/4.
4. n: = 3.
5. Сравнить A с
·. Если А <=
·, переход к п. 10.
6. S := S+ А.
7. A:=(n-1)/(n*n)
8. n:=n+1
9. Переход к п. 5.
10. Вывод S.
11. Конец.
В рассмотренных выше примерах количество повто рений, заранее неизвестно. В первом оно зависит от количества цифр в записи натурального числа, во вто ром от числа
·.
В тех же случаях, когда количество шагов известно из условия задачи, проще и предпочтительней использовать цикл с параметром.
Пример 3. Найти произведение первых k натураль ных чисел, кратных трем.
При составлении алгоритма учтем, что первое, нату ральное число, кратное 3, есть тройка, а все последующие больше предыдущего на 3.
1. Ввод k.
2. Р := 1 (здесь накапливаем произведение).
3. Т := 0 (здесь будут числа, кратные 3).
4. I := 1.
5. Если I > k, переход к п. 10.
6. Т := Т + 3.
7. Р := Р * Т.
8. I := I + 1.
9. Перейти к п. 5.
10. Вывод Р.
11. Конец.
Реализация циклов в языке Паскаль
Для организации цикла с известным числом повторе ний в языке Паскаль используется оператор for.
Структура цикла, организованного с помощью этого оператора, имеет вид:
for i : = a down to b do
begin
тело цикла
end;
for i := a to b do begin
тело цикла
end;
Здесь i параметр, изменяющийся в цикле; а, b выражения, обозначающие начальное, конечное значения параметра цикла. Шаг изменения номера па раметра цикла равен 1, если в заголовке цикла стоит to; и 1 при down to. С другим шагом параметр цикла изменяться не может. Параметр цикла, его начальное и конечное значения должны быть совместимых типов, причем это могут быть только порядковые типы (це лые, символьный, логический, перечисляемый и диапазонный).
Порядок выполнения цикла с шагом 1 следующий: вычисляются значения начального и конечного зна чений параметра цикла; параметр i принимает на чальное значение; если i меньше или равно конеч ному значению, исполняется тело цикла; параметр цикла заменяется .следующим по порядку значени ем, т.е.
i := succ(i) (здесь succ функция, определенная для порядковых типов, возвращает сле дующее по порядку значение); проверяется условие i < b (для отрицательного шага условие i > b) и при его выполнении цикл повторяется. Выход из цик ла осуществляется, если i > b (i < b для шага 1)> и выполняется оператор, следующий за оператором цикла. Если а > b (или а < b для шага 1), то цикл не исполняется ни разу. При отрицательном шаге значение параметра цикла при каждом повто рении автоматически заменяется предыдущим по порядку значением: i : = pred (i).
Если в операторе цикла с параметром начальное или конечное значение параметра заданы переменными или выражениями, то значения этих переменных должны быть определены в программе до оператора цикла. Не следует внутри цикла изменять параметр цикла, его на чальное и конечное значения с помощью операторов присваивания или ввода.
Входить в цикл можно только через его начало, т.е. нельзя входить внутрь цикла с помощью управляющего оператора, так как в этом случае параметр цикла не определен.
Задача 1. Дано натуральное п, действительное х. Вы числить:
S = sin1 х + sin2 x + + sinn x.
Разработаем алгоритм решения задачи:
1) ввести данные количество слагаемых п и число X,
2) присвоить переменной, в которой будем хранить степени sinx, значение 1; S := 0;
3) присвоить параметру цикла значение 1;
4) если значение параметра цикла меньше п, перейти к следующему пункту, иначе к п. 9;
5) вычислить очередную степень sin x;
6) добавить вычисленное значение к сумме;
7) увеличить параметр цикла на 1;
8) перейти к п. 4;
9) вывести на печать сумму S;
10) конец.
program summa;
var s, x, pr : геаl; n, i : integer;
begin
write('введите число слагаемых и х: '); readln(n, x);
pr := 1; {в этой переменной хранятся последовательные степени sin x}
s := 0;
for i : = 1 to n do
begin pr:=pr*sin(x); {очередная степень, sin(x)}
s := s + pr
end;
writeln ('сумма равна ', s :7 :4)
end.
Для организации итерационных циклов используются операторы цикла с предусловием while и циклы с постусловием repeat until.
Эти операторы не задают закон изменения параметра цикла, поэтому необходимо перед циклом задавать начальное значение параметра с помощью оператора присваивания, а внутри цикла изменять текущее значение этого параметра.
Соответствующие структуры циклов:
While b do
begin
тело цикла
end;
repeat
тело цикла
until с;
Здесь b, с логические выражения.
Для оператора цикла с предусловием проверяет значение логического выражения; если оно имеет значение true, то операторы, входящие в цикл, выполняются, в противном случае осуществляется выполнение оператора, следующего за циклом.
Цикл с постусловием выполняется хотя бы один раз. Проверяется логическое выражение; если его значение false, то операторы, входящие в цикл, выполняются, противном случае осуществляется выход из цикла.
2.5 Воз можность автоматизации деятельности человека.
Таковы основные свойства алгоритмов. Если их внимательно проанализировать, то становится очевидно, что исполнитель алгоритма не нуждается в какой-либо фантазии и сообразительности. Более того, для выполнения алгоритма совсем не требуется его понимание, а правильный результат может быть получен путем формального и чисто механического следования держанию алгоритма. В самом деле, используя алгоритм настройки телевизора на существующие в данной местности каналы, который подробно описан в инструкции, любой человек сможет успешно справится с этой задачей, даже если он понятия не имеет об устройстве телевизора. А вот обратный пример: люди, не разбирающиеся в компьютерах, постоянно нуждаются, чтобы кто-то им формулировал алгоритм (вспомните характерный вопрос "А теперь куда нажимать?").
Из возможности формального исполнения алгоритма следует очень важное следствие: поскольку осознавать содержание алгоритма не требуется, его исполнение вполне можно доверить автомату или ЭВМ. Таким образом, составление алгоритма является обязательным этапом автоматизации любого процесса. Как только разработан алгоритм, машина может исполнять его лучше человека быстрее и, что очень важно, не ошибаясь. Напротив, даже самое простое по человеческим меркам действие не может быть выполнено машиной, пока не сформулировать четкий алгоритм такого действия. Например, попробуйте научить машину, как отличить на фотографии кошку от собаки; наверное вы тоже затрудняетесь сформулировать четкий алгоритм такого действия. А между тем пятилетний ребенок совершенно безошибочно справляется с такой задачей! И еще один, чуть более сложный, пример. В данный момент неизвестен алгоритм составления расписания уроков в наиболее общем виде, поэтому опытный завуч часто делает это лучше, чем компьютер. Зато в деле проверки уже готового расписания, напротив, компьютер вне конкуренции, поскольку алгоритм операции достаточно простой.
Программное обеспечение, используемое для создания проекта.
Для создания данного проекта я использовала программы Microsoft Word и Microsoft Power Point.
3.1. Текстовый редактор Microsoft Word
– это специальная компьютерная программа, предназначенная для создания документов, брошюр и учебных пособий. При помощи программы Microsoft Word я вводила информацию в компьютер, а затем редактировала набранный текст. Для печати текста я применяла шрифт Times New Roman 12 размера. Мною также были использованы линейки для задания отступа красной строки и выравнивание текста по ширине. Заголовки я печатала жирным шрифтом. Я воспользовалась возможностями этого текстового редактора для вставки и оформления таблиц и рисунков, расстановки нумерации страниц, форматирования абзацев и шрифтов.
При выполнении рисунков блок-схем алгоритмов я пользовалась панелью рисование.
Для создания надписей к рисункам
и БСА я использовала вставку объектов WordArt.
3.2. Microsoft Рower Рoint
- это компьютерная программа, предназначенная для создания мультимедийных презентаций. Свой обучающий курс я оформила в виде набора компьютерных слайдов.
В меню Формат я выбрала пункт
Оформление слайда, и из
представленного программой
списка выбрала подходящий,
создала фон слайда при помощи
градиентой заливки.
Для выбора нужного шаблона разметки
слайда я использовала пункт меню
Формат-Разметка слайда.
Различные анимационные эффекты
для объектов слайда я добавляла
с помощью пункта меню
Показ слайдов – Настройка анимации.
В выпавшем окне настройка анимации
я настраивала порядок и параметры
анимационных эффектов.
Для наглядности и лучшего восприятия слайд-фильма я использовала вставку различных картинок и рисунков, в том числе и анимированных.
Также весь проект снабжен гиперссылками и управляющими кнопками для более удобного использования программы. Для создания гиперссылок и добавления управляющих кнопок используется пункты меню Вставка – Гиперссылка и Показ слайдов – Управляющие кнопки.
Для наилучшего эффекта восприятия информации я проделала работу по звуковому сопровождению каждого слайда пояснительным текстом.
Яркие слайды, снабженные анимацией и звуками, помогут привлечь внимание учащихся к изучаемой теме, и, соответственно, лучше изучить её. Удобная система навигации позволит любому пользователю самостоятельно освоить структуру обучающего курса, быстро найти слайд с нужной информацией.
Заключение
Я надеюсь, что моя работа поможет школьникам хорошо овладеть этой интересной, но сложной темой. А учителям информатики моя презентация поможет сделать уроки по теме «Алгоритмы» более интересными, наглядными и познавательными.
При работе над проектом я приобрела не только хорошие знания по этой теме, но и очень нужные навыки по работе с программным и аппаратным обеспечением современного персонального компьютера: операционной системой Windows, пакетом прикладных программ Microsoft Office, накопителями на магнитных и лазерных дисках, принером и сканером.
Используемая литература.
Гейн А.Г., Сенокосов А.И., Шолохович В.Ф. Информатика. – Москва: Дрофа, 2002.
Ляхович В.Ф. Информатика: Пособие для учащихся 10-11 кл.- М.: Просвещение, 1998.
Угринович Н.Д. Информатика и информационные технологии. Учебное пособие для 10-11 классов. – М.: Лаборатория Базовых Знаний, АО «Московские учебники», 2001.
Журин А.А. Самый своевременный самоучитель работы на компьютере – М.: ООО «Издательство АСТ»: 2004.
Экзаменационные вопросы и ответы. Информатика. 9 и 11 выпускные классы: Учеб. Пособие/ Авт.-сост.: Г.А.Евсеев, С.В. Симонович – М.: АСТ-ПРЕСС ШКОЛА, 2003.
Алфеева Н.И. Язык программирования Бейсик. Учебное пособие для средних общеобразовательных школ. - Орел – 1995.
Маховых А.А. Сборник задач по информатике. – Мценск – 2000.
13PAGE 15
13PAGE 141815
13 EMBED Equation.3 1415
Y:=ln2X=3B
13 EMBED Equation.3 1415
Искомый результат
Алгоритм
Исходные данные
A := n mod 10
B := n div 100
C := n div 10 mod 10
L := (n mod A = 0) and (n mod B = 0) and (n mod C = 0)
М:=В
М:=С
М:=А
Выбор МАХ
Серия
Серия
Серия
13 EMBED PBrush 1415