Предисловие дорогие друзья !
| Вид материала | Документы |
- К. Бальмонт Дорогие друзья, сегодня мы в гостях у замечательного русского поэта Константина, 164.76kb.
- Медникова Надежда Александровна учитель начальных классов моу «Уинская сош» Пермский, 91.48kb.
- И в шутку и всерьез Ведущий Добрый день, дорогие друзья! Вот и пришла весна, вот, 339.91kb.
- Играют 2 команды. Вопросы викторины, 53.15kb.
- Летние каникулы в праге, 322.16kb.
- Мои дорогие литературные друзья, 136.81kb.
- Ведущий: Дорогие, друзья! Разрешите поздравить вас с большим и дорогим для всех праздником, 124.29kb.
- Отчет о конференции 17-18 апреля дорогие друзья!, 182.44kb.
- Дорогие друзья и единомышленники, 134.05kb.
- Сценарий для 7-8 классов «Старая сказка на новый лад», 52.44kb.
ПРЕДИСЛОВИЕ
Д
орогие друзья !Вы начинаете изучение информатики на углубленном уровне. Как известно, компьютер обладает неограниченными возможностями: с ним можно поиграть в какую-нибудь игру, с его помощью можно написать рассказ, его можно превратить в пианино, в альбом для рисования… Действительно, всё это возможно, но при одном условии: компьютер выполнит какое-то задание, если ему будет выдана определённая последовательность инструкций. Составление инструкций для компьютера называется программированием. Создание даже самых простых программ поможет вам лучше понять как работает компьютер и как устроено программное обеспечение.
Программист должен обладать способностью первоклассного математика к абстракции и логическому мышлению, сооружать всё, что угодно из 0 и 1. Он должен сочетать аккуратность бухгалтера с проницательностью разведчика, фантазию автора детективных романов с практичностью экономиста.
Независимо от того, станет ли программирование вашим увлечением или профессиональным занятием, обучаясь составлению программ, используя современные методы алгоритмизации, вы наверняка получите удовольствие от возможности самостоятельно управлять компьютером.
Как и в любом учебнике, вам встретятся новые термины. Для удобства они напечатаны жирным шрифтом. В разделе «Для любознательных» приведены интересные факты и задачи, позволяющие ещё больше углубить свои знания.
В учебнике разобрано большое количество задач. Заучивать их решения наизусть совсем не обязательно, важно понимать их смысл и уметь применять на практике.
Мы считаем, что временами и о серьезных вещах можно говорить в простой, доступной форме. Ведь простота нередко позволяет увидеть неожиданные стороны того, что, казалось бы, уже хорошо знакомо. В общем, надеемся, что читать учебник будет не только полезно, но и приятно. А теперь — в путь! В неизвестную вам пока страну ПРОГРАММИРОВАНИЕ.
ГЛАВА 1 ЭТАПЫ РЕШЕНИЯ ЗАДАЧ С ПОМОЩЬЮ ЭВМ
§1. Алгоритм и его свойства.
Всякий компьютер ценен настолько, насколько ценен человек работающий за ним.
(Н. Винер)
1.1. Понятие алгоритма. люди всегда стремились облегчить свой труд, придумывая различные приспособления, усиливающие физические возможности человека. Но лишь немногие механизмы помогали человеку лучше выполнять умственную работу. Пока основным видом деятельности человека был физический труд, человек с этим мирился. Однако в последнее время всё изменилось. И человек смог создать такой механизм, который позволил резко усилить умственные возможности. Этим механизмом стал компьютер.
Компьютер был создан, прежде всего, для того, чтобы освободить человека от громоздких и утомительных вычислений. Быстродействие компьютера позволило легко решить многие практические задачи, требующие больших объёмов вычислений. Конечно, без методов вычислений, созданных людьми, многие важные задачи так и остались бы нерешенными, даже если бы компьютеры работали в миллионы раз быстрее.
Чтобы компьютер стал настоящим помощником человека, его необходимо научить решать поставленные перед ним задачи. Для этой цели и необходимы люди, умеющие программировать, т.е. создавать программные средства для компьютера.
В основе программирования лежит умение создавать алгоритмы для решения поставленной задачи.
С понятием алгоритма вы познакомились в курсе информатики в предыдущих классах. Поэтому мы в этом параграфе только обобщим и закрепим ваши знания по этой теме.
Термин «алгоритм» произошёл от имени среднеазиатского учёного IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского означает «Мухамед сын Мусы из Хорезма»), который описал десятичную систему счисления и впервые сформулировал правила выполнения арифметических действий над целыми числами и простыми дробями. В латинском переводе эти правила начинались словами «Алгоризми сказал». Постепенно люди забыли, что Алгоризми — это автор правил, и стали сами эти правила называть алгоритмами.
Что же мы понимаем под термином «алгоритм»?
 ïîâñåäíåâíîé æèçíè äîâîëüíî ÷àñòî ïðèõîäèòñÿ âñòðå÷àòüñÿ ñ ðàçëè÷íûìè èíñòðóêöèÿìè, ãäå óêàçûâàåòñÿ ðÿä çàðàíåå ïðåäóñìîòðåííûõ îïåðàöèé, ïðè ïîñëåäîâàòåëüíîì âûïîëíåíèè êîòîðûõ ìîæíî ïðèéòè ê æåëàåìîìó ðåçóëüòàòó.
Самый популярный сборник таких инструкций — книга кулинарных рецептов, в которых дана подробная технология приготовления тех или иных блюд.
Пример 1. Рецепт приготовления какао на молоке.
Взять какао — 8 грамм, сахара — 25 грамм, молока — 150 грамм.
Порошок какао засыпать в кастрюлю,
добавить сахар,
тщательно перемешать,
влить немного горячей воды или молока
и растереть ложкой до образования однородной массы.
После этого тонкой струёй, непрерывно помешивая, влить молоко
и довести до кипения.
В стакан с налитым какао можно положить взбитые сливки.
Пример 2. Приготовление Гоголь-моголя.
Отделить желтки от белков (2 шт.).
Желтки положить в фарфоровую посуду.
Добавить сахар (25 г).
Ввести апельсиновую или лимонную цедру, натёртую на мелкой тёрке (0,02 г).
Хорошо растереть.
Влить апельсиновый ликёр или ром, или вино розовый мускат (10 г).
Взбить до консистенции густой сметаны.
С инструкциями вы сталкиваетесь и в учебнике математики.
Пример 3. правило сложения дробей с разными знаменателями.
Найти наименьший общий знаменатель.
Разделить наименьший общий знаменатель на знаменатели данных дробей, т.е. найти дополнительные множители для каждой дроби.
Умножить числитель каждой дроби на дополнительный множитель этой дроби.
Найти сумму полученных произведений и записать её в числитель результата.
Наименьший общий знаменатель записать в знаменатель результата.
На первый взгляд между этими примерами нет ничего общего. Одно дело — готовить какао, другое — складывать дроби. Однако если присмотреться внимательно, можно заметить существенное сходство между ними. Прежде всего, это строгий порядок выполнения действий. Затем, каждая инструкция состоит из чёткого описания действий производимых над имеющимися данными, выполняя которые, мы достигаем результата.
Àëãîðèòìîì áóäåì íàçûâàòü ïîñëåäîâàòåëüíîñòü ÷åòêèõ îäíîçíà÷íûõ óêàçàíèé, êîòîðûå, áóäó÷è ïðèìåíåíû ê èìåþùèìñÿ äàííûì, îáåñïå÷èâàþò ïîëó÷åíèå òðåáóåìîãî ðåçóëüòàòà. Êàæäîå òàêîå óêàçàíèå íàçûâàåòñÿ êîìàíäîé.
Äàííûìè íàçûâàþò âñå âåëè÷èíû, ó÷àñòâóþùèå â ðåøåíèè çàäà÷è. Äàííûå, èçâåñòíûå ïåðåä âûïîëíåíèåì àëãîðèòìà, ÿâëÿþòñÿ íà÷àëüíûìè, èñõîäíûìè äàííûìè или аргументами. Данные, полученные в рåçóëüòàòе ðåøåíèÿ çàäà÷è - ýòî êîíå÷íûå, âûõîäíûå (итоговые) äàííûå. Данные, которые нужны лишь на некотором промежутке выполнения алгоритма – это промежуточные данные.
Приведенное выше определение алгоритма не является определением в математическом смысле, а лишь отражает понятие алгоритма на «интуитивном уровне», так как используемые в определении слова не являются математическими терминами.
1.2. Свойства алгоритма. Отметим некоторые общие особенности, присущие всем алгоритмам.
Дискретность — это разбиение алгоритма на ряд отдельных законченных действий — шагов.
Точность — это указание, в какой последовательности должны выполняться команды-шаги.
Понятность — это однозначное понимание и исполнение каждого шага алгоритма его исполнителем.
Результативность — обязательное получение результата за конечное число шагов (отсутствие решения задачи — тоже результат).
Массовость — применимость алгоритма к решению целого класса однотипных задач.
Учитывая перечисленные свойства алгоритма можно дать и такое его определение: под алгоритмом понимают точное и понятное предписание, определяющее, какие действия и в каком порядке необходимо выполнить для решения любой задачи из данного класса однотипных задач.
Необходимо определить, что такое класс задач. Согласно установленным правилам, каждый класс задач характеризуется исходными данными. Что это значит? Попытаемся объяснить это понятие на следующем примере. «Сложить два числа» — это класс задач, а не задача, так как можно предложить различные числа: 5 и 5, 7 и 9, 255 и 634 и т.д. Для каждой пары конкретных чисел мы получим конкретную задачу.
В свою очередь, «сложить числа» тоже является классом задач, но более широким, чем предыдущий. Здесь количество исходных данных иное. Надо указать, сколько чисел сложить 2, 5, 10 или больше, и предложить конкретные числа.
Массовость алгоритма как раз и предполагает его правильную работу при меняющихся в заданных пределах значениях исходных данных.
1.3. Èñïîëíèòåëè. Ñèñòåìà êîìàíä èñïîëíèòåëÿ. Íà ïîèñêè àëãîðèòìà ðåøåíèÿ íåêîòîðûõ çàäà÷ ó÷åíûå çàòðà÷èâàþò ìíîãèå ãîäû. Íî êîãäà îí íàéäåí, ðåøåíèå çàäà÷è ïî ãîòîâîìó àëãîðèòìó óæå íå òðåáóåò êàêèõ-ëèáî ðàññóæäåíèé è ñâîäèòñÿ òîëüêî ê ñòðîãîìó âûïîëíåíèþ êîìàíä àëãîðèòìà.
Êàæäûé àëãîðèòì ñòðîèòñÿ â ðàñ÷åòå íà íåêîòîðîãî èñïîëíèòåëÿ. из курса информатики вы уже знаете, что иñïîëíèòåëåì íàçûâàют ÷åëîâåêà, æèâîå ñóùåñòâî èëè àâòîìàòè÷åñêîå óñòðîéñòâî, êîòîðîå ñïîñîáíî ê âîñïðèÿòèþ è èñïîëíåíèþ êîìàíä.
Роботы-манипуляторы и станки с числовым программным управлением, живая клетка и даже животные в цирке исполняют различные алгоритмы, в том числе и те, которые человек выполнить не в силах.
Ясно, что, как бы ни были разнообразны возможности исполнителя, они всегда ограничены. Поэтому, прежде чем составлять алгоритм решения задачи, нужно узнать, какие действия предполагаемый исполнитель может выполнить.
Ïåðå÷åíü êîìàíä, êîòîðûå понимает è ìîæåò выполнить èñïîëíèòåëü, íàçûâàþò ñèñòåìîé êîìàíä èñïîëíèòåëÿ.
 àëãîðèòì äîëæíû âêëþ÷àòüñÿ òîëüêî òå êîìàíäû, êîòîðûå âõîäÿò â ñèñòåìó êîìàíä èñïîëíèòåëÿ.
Исполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции алгоритма в указанной последовательности.
В этом случае исполнение алгоритма можно поручить не только человеку, но и машине. Конечно, это должна быть машина, специально созданная для выполнения отдельных команд алгоритма и выполняющая их в последовательности, указанной в алгоритме.
Êîìïüþòåðû ïîçâîëÿþò èñïîëüçîâàòü ìîäåëè ðåàëüíûõ èñïîëíèòåëåé. Òàêèõ èñïîëíèòåëåé íàçûâàþò êîìïüþòåðíûìè èñïîëíèòåëÿìè. С некоторыми из них вы уже познакомились на уроках информатики. Это — Робот и Чертёжник.
Êîìïüþòåðíûé èñïîëíèòåëü — ýòî âèðòóàëüíûé îáúåêò, êîòîðûé ñïîñîáåí äåéñòâîâàòü â âèðòóàëüíîé ñðåäå. Îí è åãî äåéñòâèÿ îòîáðàæàþòñÿ íà ýêðàíå äèñïëåÿ.
1.4. Ôîðìû ïðåäñòàâëåíèÿ àëãîðèòìîâ. Àëãîðèòì задаётся в той форме, которая наиболее удобна и понятна людям, работающим с ним. Наиболее распространённые способы задания: ñëîâåñíый, òàáëè÷íый, ãðàôè÷åñêèй (ñ ïîìîùüþ áëîê-ñõåì).
Словесная форма описания алгоритма ñëóæèò äëÿ ïðåäñòàâëåíèÿ àëãîðèòìà ñ ïîìîùüþ ñëîâ è ïðåäëîæåíèé åñòåñòâåííîãî ÿçûêà.
Табличная форма описания алгоритма ñëóæèò äëÿ ïðåäñòàâëåíèÿ àëãîðèòìà â ôîðìå òàáëèö è ðàñ÷åòíûõ ôîðìóë.
Графическая форма описания алгоритма, èëè áëîê-ñõåìà, - ýòî ñïîñîá ïðåäñòàâëåíèÿ àëãîðèòìà ñ ïîìîùüþ ãåîìåòðè÷åñêèõ ôèãóð, íàçûâàåìûõ áëîêàìè, и соединительных линий.
1.5. Áëîê-ñõåìû àëãîðèòìîâ. Ïîñëåäîâàòåëüíîñòü áëîêîâ è ñîåäèíèòåëüíûõ ëèíèé îáðàçóþò áëîê-ñõåìó. Îïèñàíèå àëãîðèòìîâ ñ ïîìîùüþ áëîê-ñõåì — íàèáîëåå íàãëÿäíûé è ðàñïðîñòðàíåííûé ñïîñîá çàäàíèÿ àëãîðèòìîâ. Элементы áëîê-ñõåìû обычно ðàñïîëàãàþò ñâåðõó âíèç. Ëèíèè ñîåäèíåíèÿ áëîêîâ ïîêàçûâàþò íàïðàâëåíèå ïðîöåññà îáðàáîòêè â ñõåìå. Êàæäîå òàêîå íàïðàâëåíèå íàçûâàåòñÿ âåòâüþ.
Îñíîâíûå áëîêè:
Условное обозначение Пояснение
Б
лок показывает начало или конец алгоритма. 
Блок для ввода или вывода данных. Внутри блока указываются переменные (через запятую), которые получают значения или переменные, значения которых надо вывести
Б
лок действия (функционльный блок). 
У
словный блок (логический). Имеет один вход и два выхода и этим позволяет изменять последовательность выполнения шагов в зависимости от истинности или ложности некоторого условия.
Блок вариаций. Повторение действий заданное количество раз. Внутри блока указывается счётчик числа повторений, его начальное и конечное значение и, в общем случае, шаг увеличения счётчика.Блок слияния. Имеет одну или несколько входящих стрелок и одну выходящую
Вопросы и задания.
- Что такое алгоритм?
- Какими свойствами обладает алгоритм?
- Кого или что называют исполнителем алгоритма?
- что называют системой команд исполнителя?
- Назовите формы представления алгоритмов.
§2. типы алгоритмов.
2.1. Понятие о типах алгоритмов. В алгоритме команды записаны одна за другой в определённом порядке. Исполняются же они не всегда в том же порядке. В зависимости от того, каков порядок исполнения команд, различают следующие типы алгоритмов: линейный, разветвляющийся, циклический (или иначе алгоритм с повторением).
2.2. Линейные алгоритмы. алгоритмы, приведённые в примерах 1-3, имеют линейную структуру. В них все команды выполняются в строгом порядке, каждая по одному разу. Алгоритм, все команды которого выполняют одну за другой в порядке их записи, называют линейным.
При изображении линейного алгоритма с помощью блок-схемы блоки следуют один за другим, выстраиваясь в одну ветвь обработки. Разберём процесс построения алгоритма на примерах.
Пример 1. составить блок-схему алгоритма сложения двух чисел a и b.
Р
ешение. Сумма вычисляется по формуле S=a+b. Исходными данными в данной задаче являются числа a и b, результат работы алгоритма — сумма S. схема алгоритма будет содержать только блоки действий. Она изображена на рисунке 1.
Пример 2. составить блок-схему алгоритма нахождения суммы двух обыкновенных дробей
где b и d отличны от нуля.Решение. Для упрощения алгоритма вычислим сумму дробей по формуле
Исходными данными в нашей задаче являются числа a, b, c, d, результат работы алгоритма — сумма S. Поскольку b и d предполагаются отличными от нуля, то схема алгоритма, изображенная на рисунке 2, будет содержать только блоки действий. 2.3. Разветвляющиеся алгоритмы. В ходе решения задач возникают ситуации, которые следует учитывать. В зависимости от ситуации может измениться ход решения задачи. Например, в задаче примера 5 мы предположили, что b и d отличны от нуля. а если исполнитель неосторожно введёт 0? Необходимо остановить выполнение алгоритма, ведь делить на 0 нельзя.
Возникающая ситуация оценивается при помощи условий. Условие понимается как вопрос, на который можно получить один из двух ответов — условие выполняется (говорят, что оно истинно) или условие не выполняется (говорят, что оно ложно).
Алгоритм, содержащий хотя бы одно условие, после проверки которого выполнение алгоритма продолжается по двум совершенно различным наборам команд, называется разветвляющимся.
Схема такого алгоритма содержит несколько (по крайней мере, две) ветвей обработки.
Пример 6. Найти наибольшее из двух различных чисел.
Решение. Исходными данными в задаче являются числа А и В. Результатом – число МАХ. Сравнивая числа А и В присвоим МАХ значение переменной А, если А>В, в противном случае (если В>А) – значение переменной В. Блок-схема алгоритма решения этой задачи приведена на рисунке 3. Например, если А=15, а В=12, то условие истинно и переменной МАХ присвоится значение переменной А, т.е. 15. если же А=25, а В=42, то условие ложно и переменной МАХ присвоится значение переменной В, т.е. 42. В обоих случаях после присваивания на экране появится большее значение. В первом случае —15, во втором-42
2.4. Циклические алгоритмы. Часто перед нами стоят задачи, при решении которых одни и те же действия нужно выполнить несколько раз подряд. Например, красить дощечки забора, пока есть не закрашенные; бегать вокруг стадиона, пока не пробежишь 3 километра; копать на даче картошку, пока вся она не будет выкопана. Для описания алгоритмов решения таких задач используется способ организации команд, который называется циклом. Циклом (или повтором) называется такая форма организации действий, при которой одна и та же последовательность команд выполняется несколько раз (или ни разу) до тех пор, пока выполняется некоторое условие.
Циклическим алгоритмом называется алгоритм, содержащий один или несколько циклов.
Пример 7. Найти сумму первых n натуральных чисел. Значение n задаётся.
Решение. Чтобы найти сумму всех натуральных чисел от 1 до N, необходимо последовательно складывать эти числа. В переменной S будем накапливать значение суммы натуральных чисел. Первоначальное значение переменной S — 0. Переменная I (она называется параметром цикла) будет принимать значения всех натуральных чисел от 1 до N.
Блок-схема алгоритма решения этой задачи приведена на рисунке 4.
Вопросы и задания.
- Перечислите типы алгоритмов.
- Приведите примеры линейных, разветвляющихся и циклических алгоритмов.
Составить алгоритм решения задач 3-10 и изобразить их графически.
- Перераспределить значения переменных x и y так, чтобы в x оказалось большее из этих значений, а в y - меньшее.
- Вычислить значение Z, равное максимальному из чисел Х и Y, если Х<0, и минимальному из чисел Х и Y, если Х≥0 .
- Переменной k присвоить номер четверти плоскости, в которой находится точка с координатами x и y (x * y > 0).
- Известно, что из четырех чисел a1, a2, a3 и a4 одно отлично от трех других, равных между собой. Присвоить номер этого числа переменной n.
- Значения переменных a, b, c поменять местами так, чтобы оказалось
a ≥ b ≥ c.
- Если сумма трех попарно различных действительных чисел x, y и z меньше единицы, то наименьшее из x и y заменить полусуммой этих трех чисел; в противном случае заменить наибольшее число на их произведение.
- Даны действительные числа x, y, z. Выяснить, существует ли треугольник с длинами сторон x, y, z. Учесть условие: третья сторона не должна превышать сумму двух других, иначе треугольник не существует. Если треугольник существует, то выяснить какой он (равносторонний, равнобедренный, разносторонний).
§3. Этапы решения задачи с помощью ЭВМ.
Компьютеры были созданы с одной стороны для вычислений, а с другой стороны компьютеры используются для решения практических задач, с математикой непосредственно не связанных. Например, знакомый вам текстовый редактор служит для создания и редактирования текстовых документов. Графический редактор — для создания графических объектов.
Решение любой задачи с использованием компьютера требует предварительной работы и производится в несколько этапов. Часть этих этапов выполняется только человеком, а другая часть — человеком и компьютером.
Основные этапы решения задачи с помощью ЭВМ следующие:
1) Ïîñòàíîâêà çàäà÷è, âêëþ÷àþùàÿ ïîñòðîåíèå ìàòåìàòè÷åñêîé ìîäåëè è âûäåëåíèå àðãóìåíòîâ è ðåçóëüòàòîâ.
Пусть вам надо решить какую-нибудь задачу, и вы хотите воспользоваться услугами компьютера. С чего начать? Прежде всего, нужно разобраться, что дано, что требуется получить, как связаны исходные данные и результаты. Иначе говоря, задача должна быть чётко сформулирована. Обычно из формулировки школьной задачи можно однозначно извлечь, что дано, что требуется получить, и как связаны исходные данные с результатами (хотя и не всегда просто это сделать). Однако жизнь постоянно заставляет решать задачи посложнее, чем в школьных учебниках.
Про задачи, в которых неясно, что дано или что надо получить, либо нечётко определены связи между исходными данными и результатами, говорят, что они плохо поставлены. Их решение надо начинать с чёткой постановки.
Нелёгкое это дело правильно поставить задачу: не переупростить и не переусложнить, не упустить важных исходных данных и не включить лишних, соразмерить желаемое с возможным. Например, следующая задача.
Составить расписание уроков в школе, удовлетворяющее и учителей и школьников. Каковы исходные данные для этой задачи? Это зависит, конечно, от того, какое расписание считать хорошим. Можно задаться целью обеспечить лишь то, чтобы два разных урока не проходили в одно и то же время в одном классе. Тогда исходных данных будет немного: список учебных предметов да количество классов на каждой параллели. При этом, правда, может случиться, что одному классу придётся изучать только математику, другому — только географию. И это не самые страшные накладки, которые могут при этом получиться. попробуйте сами чётко сформулировать задачу составления расписания. Кстати, компьютерной программы составления расписания, которая бы удовлетворяла всех участников учебного процесса, до сих пор не существует. Вот вам информация к размышлению! Дерзните.
Постановка задачи — это очень важная часть её решения. В процессе выделения исходных данных, результатов и определения связей между ними, путем отбрасывания несущественных деталей, не влияющих на результат, создается модель задачи. Искусство составления моделей как раз и заключается в том, чтобы, не переусложнив модель, учесть в ней всё существенное и отбросить второстепенное. например, все мы привыкли видеть в качестве модели Земли глобус.
Составить хорошую модель задачи — дело непростое. Даже если решать задачу предстоит вам. А если модель надо будет объяснить компьютеру? В этом случае нужно позаботиться о том, чтобы исходные данные и результаты были числами, а связи между ними — математическими соотношениями. Выполнив такой «перевод» задачи на язык математики, вы получите математическую модель.
Создание математической модели завершает первый этап решения задачи с помощью компьютера. Это, пожалуй, самый важный этап решения задачи. От того насколько хорошо и правильно сформулирована задача; насколько точно учитывает модель главные и значимые особенности решаемой задачи в огромной степени зависит, какой результат мы получим.
2) Ïîñòðîåíèå àëãîðèòìà. После постановки задачи начинается поиск метода её решения. Для решения задачи строится алгоритм. При построении алгоритма можно выделить следующие этапы:
Разработка. Как уже говорилось, основная сложность при решении задач заключается в построении алгоритма решения. Построение алгоритма решения задачи можно подчинить вполне определённым правилам, облегчающим само построение и понимание алгоритма. Искусство составления алгоритмов заключается в умении конструировать сложный алгоритм из более простых алгоритмов и структур. Этот метод последовательного построения алгоритмов называют методом пошаговой детализации. Более подробно мы расcкажем о нём позднее. Применяя принцип пошаговой детализации алгоритма, можно конструировать алгоритм на основе небольшого числа конкретных правил.
Обоснование. При создании алгоритма необходимо следить за тем, чтобы он был корректным, т.е. давал результат при всех допустимых значениях входных данных. А также следить за тем, чтобы в алгоритме отсутствовали недопустимые операции. Например, при вычислении значения дроби, необходимо следить за тем, чтобы знаменатель не обращался в нуль; при извлечении квадратного корня из выражения необходимо следить за тем, чтобы подкоренное выражение всегда оставалось не меньше нуля и т.д.
Представление. Мы уже упоминали об основных формах представления алгоритма. При решении конкретной задачи необходимо выбирать тот способ, который позволяет наиболее точно и наглядно передать суть алгоритма.
Если алгоритм предназначен для человека, то в качестве команд можно использовать привычные для человека предложения, фразы. Однако словесная форма удобна для записи небольших алгоритмов. Если же алгоритм содержит десятки команд, то в такой форме довольно трудно проследить всевозможные разветвления. В таком случае удобнее использовать блок-схемы.
Анализ. Анализ построения алгоритма — обязательная часть алгоритмизации. Анализ включает в себя доказательство правильности алгоритма, определение степени сложности алгоритма, тестирование на различных наборах входных данных.
3) Çàïèñü àëãîðèòìà íà ÿçûêå ïðîãðàììèðîâàíèÿ. Задача сформулирована, построена математическая модель, выбран метод решения и разработан алгоритм, что дальше?
Чтобы компьютер смог решить поставленную перед ним задачу, алгоритм должен быть записан на понятном машине языке. Таким языком является язык машинных кодов. Программа, написанная на языке машинных кодов, представляет собой совокупность команд, записанных в двоичном коде. И первые программы приходилось писать на нём. Это было утомительно и неудобно. особенно сложным был ввод программы в машину. Малейшая неточность приводила к непредсказуемым результатам. Для того чтобы облегчить труд программиста, и были созданы специальные языки программирования. Алгоритм, записанный на языке программирования, называется программой.
На языке программирования программа записывается не в виде загадочных последовательностей чисел, а в удобном текстовом виде. Программу, написанную на языке программирования, называют исходным текстом.
язык программирования - средство для написания компьютерных программ, имеющее алфавит, правила синтаксиса и семантики.
Алфавит языка — это набор символов, из которых формируются слова и предложения в программе.
Синтаксис — это система правил, определяющих структуру конструкций языка.
Семантика — это соответствие между конструкциями языка и их значениями.
Исходный текст программы, записанный с помощью языка программирования, не может выполниться компьютером, т.к. не является последовательностью машинных команд. Этот текст необходимо перевести на язык команд процессора, транслировать. Этим и занимаются специальные программы-трансляторы: компиляторы и интерпретаторы. Трансляторы осуществляют перевод текста программы с языка программирования на язык машинных команд. Разница между ними в следующем: компиляторы сначала переводят программу на язык машинных команд, а потом выполняют целиком, а интерпретаторы обрабатывают и выполняют программу пооператорно, шаг за шагом.
В процессе трансляции программы выявляются синтаксические ошибки. Так называются ошибки, допущенные программистом при написании слов языка, а также ошибки в операторах, несоблюдение правил написания программы. После того как ошибки исправлены, можно запускать программу на выполнение.
4) Ðåàëèçàöèÿ àëãîðèòìà ñ ïîìîùüþ ÝÂÌ. Чтобы разобраться, как реализуется алгоритм с помощью ЭВМ, смоделируем сначала наши действия при решении простой задачи обычным способом, без использования компьютера. Найдём сумму двух чисел.
Прежде всего, нам необходимо знать, чему равны первое и второе слагаемые. Эти значения мы получаем или из текста примера (информация поступает через глаза), или же кто-то продиктует нам нужные числа (информация поступает через уши).
Где мы будем хранить значения слагаемых? Либо на бумаге, либо в своей памяти. затем, получив указание «сложить», мы произведём нужное действие и получим ответ. А где будет храниться ответ? Либо в нашей памяти, либо на бумаге.
Машина выполняет те же самые шаги:
1) получает значение слагаемых (делаем вывод, поскольку машина — это техническое устройство, то необходим блок, с помощью которого можно ввести в машину значения чисел; в современных ЭВМ основным устройством для ввода данных обычно используется клавиатура);
2) хранит значения слагаемых до следующего указания (возникает необходимость блока для хранения чисел — внутренняя память);
3) выполняет необходимое действие над заданными слагаемыми и опять хранит, но уже сумму (необходим блок, умеющий считать);
4) сообщает ответ человеку, значит, необходим блок или устройство, на котором возможно показать ответ (чаще всего это экран дисплея).
На этом наши действия закончились, но
5) человек сам себе хозяин: захотел — сложил, захотел — умножил, и он сам знает какую операцию когда выполнить. Машина тоже должна соблюдать определённую последовательность действий и не перепутать! Для этого тоже нужно устройство, управляющее работой машины. Процессор — это и есть тот самый блок, который умеет считать и управлять работой вычислительной машины.
5) Àíàëèç ïîëó÷åííûõ ðåçóëüòàòîâ. Компьютер произведёт необходимые вычисления и выдаст какие-то результаты. Но ответить на вопрос: правильно ли написана программа и получили ли мы по нашей программе тот ответ, который требуется, сразу нельзя.
Проведя вычисления на компьютере, необходимо проанализировать результаты. Ведь какой бы совершенной не была созданная математическая модель, она всегда основана на некотором упрощении, что может привести к искажению результатов. Только сопоставив результаты расчётов с экспериментальными данными и другой информацией, можно убедиться, что модель соответствует реальной задаче. При этом может возникнуть необходимость уточнить как программу, так и математическую модель. Кроме того, при решении задачи могут быть получены результаты, которые противоречат смыслу задачи. Например, пусть математическая модель, описывающая количество изделий, выпускаемых предприятием за день, представляет собой квадратное уравнение. Если один из корней уравнения отрицателен, то такой результат противоречит смыслу и должен быть отброшен. процесс уточнения программы и математической модели называют отладкой программы. Иногда отладку выделяют в отдельный этап решения задачи.
Вопросы и задания.
- Что значит поставить задачу?
- Что такое модель задачи?
- Что такое компьютерная программа?
- Из чего состоят компьютерные программы?
- Что такое программирование; язык программирования; исходный текст?
- Что такое трансляция исходного текста? Что называют компилятором?
- Объясните, почему следующие задачи плохо поставлены. Составьте модели этих задач:
- Вини Пух и Пятачок построили ловушку для слонопотама. Удастся ли его поймать?
- Вини Пух и Пятачок пошли в гости к Кролику. Сколько бутербродов с мёдом можно съесть Вини Пуху, чтобы не застрять в двери?
- Малыш и Карлсон решили по-братски разделить два сладких орешка — большой и маленький. Как это сделать?
- Аббат Фариа решил бежать из замка Иф. Сколько времени ему понадобится, чтобы осуществить свой замысел?