Реферат: Представление о программе


РАЗДЕЛ 2 Программное обеспечение информационных технологий


ТЕМА 12

Алгоритмы




ТЕМА 13

Представление о программе. Классификация программ




ТЕМА 14

Системная среда Windows




ТЕМА 15

Общая характеристика прикладной среды









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

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

В этом разделе вы узнаете о назначении и возможностях трех классов программного обеспечения: системного, прикладного и инструментария программирования. В качестве примера систем­ной среды рассматривается операционная система Windows. При изучении прикладных сред будет использован объектный подход. Вы познакомитесь с общими и отличительными характеристика­ми прикладных сред общего назначения: графическим редакто­ром, текстовым и табличным процессорами, системой управле­ния базой данных. Для понимания технологии работы с инстру­ментарием программирования вы должны научиться составлять алгоритм решения поставленной задачи, чему и будет посвяще­на одна из тем. Непосредственно же программная среда, в каче­стве которой выбрана среда ЛОГО, будет изучаться в практикуме.

Сведения о программном обеспечении в этом разделе изла­гаются с теоретических позиций. Поэтому изучение всех тем дол­жно идти параллельно с практическим освоением технологии разработки алгоритмов и технологии работы в системной среде, в прикладных средах общего назначения, в среде программирова­ния на основе учебного пособия «Информатика и ИКТ. Практи­кум. 8-9 класс».

Тема 12 Алгоритмы


Изучив эту тему, вы узнаете:

назначение алгоритма и его основные свойства;

формы представления алгоритма;

типовые алгоритмические конструкции и виды алгоритмов;

разновидности циклических алгоритмов и их особенности;

назначение вспомогательных алгоритмов;

основные стадии создания алгоритма.


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

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



Например, с утра вас призывает радио «На зарядку стано­вись!» Вам предлагается выполнить одно из упражнений в сле­дующей последовательности:

Потянитесь, лежа в постели.

Сядьте на кровати, поставив ноги на пол.

Нагнитесь вперед, пытаясь достать ру­ками пальцы ног.

Выгните спину дугой.

Сосчитайте до 10.

Вернитесь в исходное положение.

Рассмотрим еще пример. Вы решили зайти к другу, а у негов подъезде установлен домофон. Вы выполняете действия, следуя инструкции, вывешенной на входной двери:

Наберите номер квартиры.

Нажмите кнопку «Вызов».

Услышав прерывистый сигнал, ждите ответа.

Услышав ответ, говорите.

Услышав звуковой сигнал — входите.



В первом примере вашими действиями управляет спортивный инструктор по ра­дио. Во втором случае вы сами в соответ­ствии с инструкцией управляете техниче­ским устройством (домофоном), с помощью которого осуществляется голосовая связь и дистанционное открытие двери. В обо­их случаях вы совершаете заданную по­следовательность действий для достиже­ния определенной цели. А если вместо вас будет кто-то другой, сможет ли он выпол­нить то, что делали вы? Конечно сможет, ведь эти инструкции адресованы любому человеку.

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



Подробное описание действий, необходимых для получения ожидаемого результата, получило название алгоритма. С этим понятием вы сталкиваетесь постоянно.

В кулинарных книгах собраны рецепты приготовления разных блюд.

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

В журналах мод есть выкройки и описания, руководствуясь ко­торыми можно сшить одежду.

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

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

Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (825 г.) ученый из города Хорезма Абдулла




(или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал спо­собы выполнения арифметиче­ских действий над многозначны­ми числами. Эти способы и сейчас изучают в школе. Само слово «ал­горитм» возникло в Европе после перевода на латынь книги этого среднеазиатского математика, в ко­торой его имя писалось как «Алгоритми». «Так говорил Алгорит-ми», — начинали европейские ученые, ссылаясь на правила, пред­ложенные Мухаммедом аль-Хорезми.

Научное определение понятия алгоритма дал А. Черч в 1930 го­ду. Позже и другие математики вносили свои уточнения в это определение. В школьном курсе информатики вы будете пользо­ваться следующими определениями.


^ Алгоритм — описание последовательности действий (план), испол­нение которых приводит к решению поставленной задачи за конечное число шагов.

Алгоритмизация — процесс разработки алгоритма (плана дейст­вий) для решения задачи.


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

Теория алгоритмов находит применение в различных сферах деятельности человека. Появление компьютеров внесло свою леп­ту в эту теорию. Алгоритмы, реализованные на компьютере, по­зволили решать сложные задачи в различных областях, напри­мер:

в медицине — автоматическая диагностика и обработка дан­ных компьютерной томографии;

в производстве — управление техни­ческими устройствами, заменяющи­ми человека в сложных или опасных для жизни условиях;

в кинематографии — обработка изо­бражений, моделирование пейзажей и движений, сжатие видео- и аудио­информации;

в Интернете — увеличение скорости поиска и обработки дан­ных поисковыми системами;

в аэрокосмонавтике — управление космическими корабля­ми и спутниками;

в сфере безопасности — распознавание «свой-чужой» и т. д.





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

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

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

Пример 12.1

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

Алгоритм «Разжигание костра при хорошей погоде»

Выберите место для костра в отдалении от деревьев и кустов.

Соберите сухие ветки.

Сложите их недалеко от выбранного для костра места.

На месте костра сложите «шалашиком» тонкие сухие ветки.

Положите под ветки бумагу для растопки.

Подожгите бумагу.

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

Конец алгоритма

В приведенном алгоритме четко указываются как сами дей­ствия, так и порядок их выполнения. Попробуйте поменять мес­тами пункты 1 и 2. Ничего страшного не произойдет, но с хво­ростом в руках искать место для костра или перекладывать хво­рост с одного места на другое неудобно.

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



Пример 12.2

Представьте, что вам нужно сварить кашу на костре в котелке. У вас заранее при­готовлено приспособление для того, что­бы повесить котелок над костром. Снача­ла надо разжечь костер, а затем присту­пить к варке каши. В том же справочнике туриста приводится рецепт варки гречне­вой каши и нормы расхода крупы на одну порцию.

Алгоритм «Приготовление гречневой каши»

Обратитесь к алгоритму «Разжигание костра при хорошей по­годе».

Промойте крупу холодной водой и слейте воду.

Налейте в котелок воды в два раза больше, чем объем крупы.

Установите котелок с водой над костром.

Доведите воду до кипения.

В кипящую воду засыпьте крупу.

Добавьте соли по вкусу.

Дождитесь, когда жидкость на поверхности крупы исчезнет.

Накройте котелок крышкой.

Доведите кашу до готовности на медленном огне (10 минут).

Конец алгоритма

По форме представления этот алгоритм ничем не отличается от предыдущего. Он обладает свойством дискретности, поскольку представляется в виде последовательности заранее определенных действий. Однако каша по этому алгоритму получится не у всех. В пункте 7 этого алгоритма соль добавляется по вкусу. У не­опытного повара этот пункт вызовет сложности. То же самое можно сказать о пункте 10: не каждый знает, как убавить огонь в костре. Кто-то может подумать, что нужно снять котелок и по­дождать, пока дрова прогорят и огонь станет меньше.

Чтобы устранить эту неопределенность, в алгоритм следует внести изменения:

в пункте 7 указать расход соли из расчета на одну порцию;

в пункт 10 добавить уточнение «сдвинув котелок от центра костра к краю».

Теперь этим алгоритмом может воспользоваться любой чело­век, так как он обладает свойством детерминированности (от лат. determinate — определенность, точность). Это свойство ука­зывает, что любое действие в алгоритме должно быть строго и не­двусмысленно определено и описано для каждого случая.

^ ОБРАТИТЕ ВНИМАНИЕ Рассмотренный в примере 12.1 алгоритм «Разжигание костра при хорошей погоде» также обладает свойством детерминированности, так как все действия однозначно определены и отсутствует неопределенность в их выпол­нении.

Пример 12.3

Предположим, в походе вам понадобилось узнать расстояние до ближайшего населенного пункта. Для решения этой задачи не­обходима информация о примерной высоте различных объектов (окна, столба, человека и пр.), а также усредненное значение дли-ны руки взрослого и ребенка. Тогда можно будет воспользовать­ся приведенным в том же справочнике туриста алгоритмом определения расстояния до предмета.



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

Возьмите линейку.

Вытяните руку с линейкой.

Направьте руку на хорошо просматри­ваемый предмет (колокольню, трубу котельной или что-то подобное).

Установите линейку вертикально.

Запомните количество делений линейки, соответствующих изображению предмета.

Умножьте длину руки на примерную высоту предмета.

Разделите получившееся число на измеренное в пункте 5 ко­личество делений. Это и есть примерное расстояние до пред­мета.

Конец алгоритма

Этот алгоритм основан на свойствах подобных треугольников, и при желании вы можете это проверить.

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

А как быть, если нет линейки? Вместо линейки в качестве подручного средства может быть использована спичка, каран­даш, прямая палка или любой другой предмет, на который пред­варительно нанесены деления. Учитывая это, в алгоритме вме­сто слова «линейка» следует поставить обобщающее слово, на­пример «палка с делениями» или «дальномер».

Уточненный алгоритм позволяет решить множество похожих задач — по нему можно измерить расстояние до любого видимо­го предмета при помощи любой палки с делениями.

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

Свойство массовости подразумевает использование перемен­ных в качестве исходных данных алгоритма.

^ ОБРАТИТЕ ВНИМАНИЕ Рассмотренный в примере 12.1 алгоритм «Разжигание костра при хорошей погоде» также обладает свойством массовости, так как в качестве исходных данных здесь используются сухие ветки (любых деревьев) и любой ис­точник огня (спички, зажигалка, лупа и пр.)

Рассмотренный в примере 12.2 рецепт приготовления гречневой каши не может быть использован для приготов­ления каши из другой крупы. Однако по нему может быть приготовлено разное количество порций. В данном случае количество порций — исходные данные для ал­горитма «Приготовление гречневой каши». В рамках этих исходных данных алгоритм обладает свойством массовости.

Пример 12.4



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

В1 — вес рыбы, пойманный первым рыбаком;

В2 — вес рыбы, пойманный вторым рыбаком.

Алгоритм «Кто победил»

Определите В1.

Определите В2.

Если число В1 больше числа В2, то сообщите, что первый ры­бак — победитель.

Если число В1 меньше числа В2, то сообщите, что второй рыбак — победитель.

Конец алгоритма

По этому алгоритму можно определить победителя не только в рыбалке, но и в собирании грибов, ягод и пр.

При всей простоте и очевидности алгоритма не каждый сразу поймет его ошибочность. В этом алгоритме не рассмотрена си­туация равенства чисел В1 и В2, которую следует учесть, доба­вив в алгоритм еще один пункт:

5. Если число В1 равно числу В2, то сообщите: «победила дружба».
В уточненном алгоритме рассмотрены все возможные ситуации и для каждой из них получен результат. В таких случаях гово­рят, что алгоритм обладает свойством результативности.

Конечной целью любого алгоритма является получение резуль­тата, поэтому свойство результативности очень важное. Если результат по каким-либо причинам отсутствует, об этом следует сообщить.

^ ОБРАТИТЕ ВНИМАНИЕ Рассмотренный в примере 12.1 алгоритм «Разжигание костра при хорошей погоде» обладает свойством резуль­тативности, так как изначально он был разработан толь­ко для хороших погодных условий, при которых костер всегда будет разожжен.

Рассмотренный в примере 12.2 алгоритм «Приготовление гречневой каши» обладает свойством результативности, так как ориентирован только на приготовление опреде­ленного сорта каши.

Рассмотренный в примере 12.3 алгоритм «Определение рас стояния» обладает свойством результативности, так как мы всегда можем измерить расстояние.

Из свойства результативности следует свойство конечности алгоритма, которое определяет завершение каждого действия в отдельности и алгоритма в целом за конечное число шагов.

Для иллюстрации этого свойства вспомним рассмотренную ранее инструкцию пользования домофоном. Предположим, вь пришли к другу, а дома никого нет. Действуя строго по инструкции, вы так и будете стоять у дверей, дожидаясь ответа. Это алгоритм не обладает свойством конечности и его следует дора­ботать. Сделайте это самостоятельно.

Обобщим выводы всех рассмотренных примеров.

Алгоритм характеризуется следующими свойствами:

дискретностью;

детерминированностью;

массовостью;

результативностью;

конечностью.




2.3. Формы представления алгоритма

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



Рис. 12.1. Формы представления алгоритма

Приведенные ранее алгоритмы были представлены в виде опи­сания последовательности действий, то есть в словесной форме.

Такой способ представления несложен, но имеет недостатки. Глав­ный недостаток состоит в том, что при таком способе допускается некоторая произвольность изложения, нет четких стандартов описания. Сложные задачи с анализом условий, с повторяющи­мися действиями и возвратами к предыдущим пунктам трудно представляются в словесном и словесно-формульном виде.



Преимуществом графического способа представления являет­ся его наглядность.

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

Можно представить алгоритм в виде схемы или графа — это более строгая, формализованная форма.

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



Рис. 12.2. Алгоритм решения задачи в виде схемы

В виде графа удобно представлять алгоритмы решения ло­гических задач, задач по комбинаторике и пр. На рисунке 12.3 представлен алгоритм «Разбор предложения» в виде графа.

Граф — геометрический объект, состоящий из вершин и со­единяющих вершины линий-дуг. В алгоритме анализа структу­ры предложения вершинами являются члены предложения, дуги показывают связи членов предложения, направления дуг — последовательность анализа (порядок действий алгоритма).



Рис. 12.3. Алгоритм решения задачи в виде графа

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

Наиболее распространенной формой представления алгоритма является блок-схема. Для отображения алгоритма в виде блок-схемы используется стандартный набор графических объектов (блоков), перечень и условные обозначения которых приведены в таблице 12.1. Использование блок-схем, состоящих из типово­го набора блоков, позволяет трактовать алгоритм однозначно.

Таблица 12.1. Стандартные графические объекты блок-схем


^ Название блока

Вид блока

Назначение блока

Начало-Конец




Указание на начало и конец алгоритма

Ввод-Вывод




Организация ввода и вывода данных

Решение (условный, логический блок)




Выбор направления выполне­ния алгоритма в зависимости от выполнения условия

Процесс

(блок действий)




Выполнение действия или группы действий

Ранее определен­ный процесс




Использование вспомогатель­ных алгоритмов

Приведем алгоритм решения задачи, представив его в разных формах.

Пример 12.5

Требуется рассчитать необходимое количество рулонов обоев для оклейки комнаты. Заданы параметры комнаты: длина (а), ши­рина (Ъ) и высота (п). Заданы параметры рулона обоев: длина (I), ширина (d). Считаем, что площадь окон и дверей составляет 15 % от площади стен.



Мы используем для представления алгоритма разные формы: словесно-формульное описание, блок-схему, программу.

Словесно-формульное описание ал­горитма «Оклейка обоями» представ­ляется в виде нумерованной последо­вательности действий, понятных чело­веку.

Алгоритм «Оклейка обоями»

Рассчитать периметр комнаты: р=2*(а+Ъ).

Рассчитать площадь стен с учетом дверей и окон: sl=0,85*p*h.

Рассчитать площадь одного рулона обоев: s2=l*d.

Вычислить количество рулонов: k=div(sl/s2)+l, где div — функция определения целой части числа.

Конец алгоритма

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

Алгоритм «Оклейка обоями» представлен в виде блок-схемы на рисунке 12.4.

Пояснения к блок-схеме:

действия, указанные в блоках 1-4, соответствуют действи­ям, указанным в словесном алгоритме в пп. 1-4;

дополнительно введены блоки для ввода исходных данных в компьютер и вывода результата вычислений;

дополнительно введены блоки начала и конца алгоритма.

Приведем форму представления того же алгоритма «Оклейка обоями» в виде программы на школьном алгоритмическом язы­ке в таблице 12.2.

Таблица 12.2. Алгоритм «Оклейка обоями» в виде программы на школьном алгоритмическом языке

Школьный алгоритмический язык

Пояснения

алг Оклейка обоями

Начало алгоритма

нач вещ a, b, h, 1, d, p,sl,s2, цел k

Описание типов переменных

вывод "Введите длину, ширину, высоту комнаты, длину, ширину обоев"

Вывод подсказки на экран

ввод a, b, h, 1, d

Ввод информации с клавиатуры

p:=2*(a+b)

Вычисление периметра комнаты

sl:=0.85*p*h

Вычисление площади стен

s2:=l*d

Вычисление площади рулона

k:=div(sl,s2)+l

Вычисление количества рулонов

вывод k

KOH

Вывод ответа на экран Конец алгоритма

Все алгоритмы, приведенные в качестве примеров, имели одинаковую структуру: в них действия следовали одно за дру­гим. Это самая простая разновидность алгоритмов. Но существу­ют алгоритмы, в которых последовательность действий может быть нарушена из-за выполнения или невыполнения некоторого условия. Встречаются алгоритмы, в которых некоторая последо­вательность действий повторяется, причем количество повторе­ний тоже определяется условием.

Любой, даже самый сложный алгоритм, можно представить с помощью трех типовых конструкций (структур): последователь­ности, ветвления, цикла. Каждая структура имеет один вход и один выход.

На рисунке 12.5 представлены блок-схемы этих базовых струк­тур, из которых видно, что:

в структуре «последовательность» действия выполняются последовательно, сверху вниз, без возвратов (рис. 12.5, о);

в структуре «ветвление» выполняется либо одна, либо дру­гая группа действий в зависимости от истинности (выполне­ния) или ложности (невыполнения) условия (рис. 12.5, б);

в структуре «цикл» действия повторяются до тех пор, пока выполняется заданное условие (рис. 12.5, в).



Рис. 12.5. Типовые алгоритмические структуры

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

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


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

В основе линейных алгоритмов лежит структура «последователь­ность». Покажем это на примерах.

Пример 12.6

В своей книге «Арифметика» Леонтий Филиппович Магницкий привел следующий способ отгадывания задуманного двузначно­го числа: «Если кто задумает двузначное число, то ты скажи ему, чтобы он увеличил число десятков задуманного числа в 2 раза, к произведению прибавил бы 5 единиц, полученную сумму уве­личил в 5 раз и к новому произведению прибавил сумму 10 еди­ниц и числа единиц задуманного числа, а результат произведен­ных действий сообщил бы тебе. Если ты из указанного тебе ре­зультата вычтешь 35, то узнаешь задуманное число».

Представим предлагаемые Л. Ф. Магницким действия в виде алгоритма в словесной форме. В предлагаемом процессе должны участвовать два человека: загадывающий число и отгадываю­щий его. Поэтому алгоритмов тоже будет два.



Алгоритм для загадывающего число

Задумайте двузначное число.

Умножьте число десятков на 2.

К полученному произведению при­бавьте 5.

Полученную сумму умножьте на 5.

К полученному произведению при­бавьте 10.

К полученной сумме добавьте коли­чество единиц задуманного числа.

Сообщите полученное число отгадывающему.

Конец алгоритма

Алгоритм для отгадывающего число

Отнимите от сообщенного числа 35.

Сообщите результат.

Конец алгоритма

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

Пример 12.7

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

Для исходных данных алгоритма будем использовать следую­щие обозначения:

п — норма расхода продукта на человека в сутки;

k — количество участников похода;

о — количество дней.

Результат работы алгоритма (рассчитанный вес продукта) бу­дет занесен в переменную т (рисунок 12.6).




Рис. 12.6. Алгоритм решения задачи «Вес продукта» в двух формах представления: в виде блок-схемы и в виде программы на школьном алгоритмическом языке

№ блока

Программа

1

алг Масса продукта нач цел d, k, m, n

2

вывод "Введите количество человек, дней, норму расхода на человека"

3

ввод k, d, n

4

m:=n*d*k

5

вывод вес продукта , m

Приведенные ранее в п. 12.3 алгоритмы разведения костра, приготовления каши, измерения расстояния до предмета явля­ются линейными или последовательными.

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


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

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



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

Если закат красный, то жди ветреной погоды.

Нет дыма без огня (если есть дым, то ищи источник возгора­ния).

Кончил дело — гуляй смело (если работа закончена, то мож­но отдыхать).

Если вы нашли в лесу муравейник, то его местоположение относительно дерева указывает на юг.

Здесь условиями, позволяющими делать выводы или влияю­щими на принятие решений, являются слова, расположенные между «если» и «то»:

в первом примере — красный закат;

во втором примере — дым;

в третьем примере — окончание работы;

в четвертом примере — муравейник.

Условие может принимать значение «истина», когда оно вы­полнено, или «ложь», когда оно не выполнено. От значения ус­ловия зависит наше дальнейшее поведение. Например, в предло­жении «Если закат красный, то жди ветреной погоды» условие «закат красный» может быть или истинным, или ложным. Если условие истинно, то следует ждать ветреной погоды, иначе (если условие ложно) ничего о погоде сказать нельзя.

В одних случаях анализ ситуации и сам выбор не вызывают за­труднений, а в других сделать это очень трудно. Приходится про­думывать каждый возможный вариант и последствия принимаемого решения. Шахматист, перед тем как сделать очередной ход, анализирует позицию на несколько ходов вперед. Компьютерные игры также построены на анализе ситуации и выборе действий.

Рассмотрим примеры алгоритмов, содержащих анализ условия.

Пример 12.8

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

Алгоритм проверки можно записать так:

Если гриб съедобный, то положить его в котелок для варки, иначе — выбросить в костер.

В приведенной записи в зависимости от значения условия вы­полняется либо действие, указанное после слова «то» — поло­жить гриб в котелок, либо другое действие, указанное после сло­ва «иначе» — выбросить в костер. На рисунке 12.7 представлен фрагмент блок-схемы алгоритма сортировки грибов для варки супа по признаку съедобный-несъедобный.



Рис. 12.7. Алгоритм проверки грибов, в котором использована полная форма ветвления

Пример 12.9

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

Представим решение этой задачи на школьном алгоритми/ ческом языке. Исходными данными для решения этой задачи являются размеры коробки и длина ленточки. Примем для них следующие обозначения: а, Ъ, с — соответственно длина, шири­на и высота коробки; d — длина ленточки.

алг Подарок

нач вещ a,b,c,d

вывод "Введите размеры коробки"

ввод а,Ь,с

вывод "Введите размеры ленты"

вводе!

если (a+b+2*c)*2 <= d

то

вывод "Ленты хватит" иначе

вывод "Ленты не хватит"

все

кон

В примерах 12.8 и 12.9 при описании алгоритмов в виде блок-схемы и программы на школьном алгоритмическом языке ис­пользовалась конструкция «ветвление».



Различают полную и неполную форму ветвления.

При полной форме ветвления действия выполняются в обоих случаях: и при истинности, и при ложности условия. Вспомните кота из сказки А. С. Пушкина: «идет на­право — песнь заводит, налево — сказку говорит».

В рассмотренных выше примерах использовалась полная фор­ма ветвления, которой соответствует выражение

если <условие>, то <действие 1>, иначе <действие 2>.

Неполной форме ветвления соответствует выражение

если <условие>, то <действия>.

Неполная форма предполагает отсутствие действий в случае невыполнения условия. Например: среднесуточная температура воздуха ниже +8 °С, приступить к протапливанию помещений.

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



Рис. 12.8. Алгоритм тушения костра, в котором используется неполная форма ветвления

Пример 12.10

Известно, что в аэропорту существуют ограничения на бесплат­ный провоз багажа. Если вес багажа превышает норму, то за каждый килограмм сверх нормы необходимо доплачивать. Ис­ходными данными для решения задачи являются: v — вес бага­жа; vn — разрешенная норма провоза багажа; st — стоимость килограмма сверх нормы. Результат будем записывать в пере­менную s — сумму выплат сверх нормы.

Алгоритм «Доплата за багаж» представим на школьном алго­ритмическом языке.

алг Доплата за багаж

нач вещ v, vn, st, s

вывод "введите вес багажа, норму, стоимость кг"

ввод v, vn, st

если v>vn

то s:=(v-vn)*st

вывод "Доплата составляет", s

все

кон



Во всех приведенных алгоритмах анализ условия приводит к выполнению тех или иных действий. Если представить алго/ ритм в виде дороги, ведущей к достижению поставленной цели, то условный блок «если..., то..., иначе...» является развилкой на этой дороге.

На приведенных выше блок-схемах хорошо видны подобные развилки. Они создаются при по­мощи структуры ветвления, имею­щей полную и неполную форму. Подобные алгоритмы называются разветвляющимися.

^ Разветвляющийся алгоритм — алгоритм, содержащий структуру ветвления


12.6. Циклический алгоритм Общее представление

Многие процессы в окружающем мире основаны на многократ­ном повторении одной и той же последовательности действий.



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

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

Циклические алгоритмы могут содержать разные типы цик­лов. Классификация типов циклов представлена на рисунке 12.9 и подробно рассмотрена далее.

^ Циклический алгоритм — алгоритм, содержащий типовую конструкцию «цикл».

Тело цикла — описание действий, повторяющихся в цикле.



Рис. 12.9. Типы циклов


Цикл с известным числом повторений

Цикл с известным числом повторений часто называют «циклом ДЛЯ». Рассмотрим примеры циклических алгоритмов с извест­ным числом повторений.

Пример 12.11

В различных журналах приводятся упражнения, которые необ­ходимо повторять заданное число раз. Рассмотрим пример уп­ражнения для глаз. Особенно это полезно тем, кто долго сидит за компьютером. Подобные алгоритмы чаще всего представля­ются в словесной или графической форме.

Алгоритм «Упражнение для глаз»

Возьмите карандаш.

Установите его в исходное положение у кончика носа.

Повторите 10 раз, следя за движением карандаша:

Переместите карандаш на расстояние вытянутой руки;

Верните карандаш в исходное положение.

Положите карандаш.
Конец алгоритма

В этом примере заранее известно число повторений. Цикл за­кончится, когда действия пунктов а и b повторятся 10 раз. Дей­ствия а и Ь, повторяющиеся в цикле, определяют тело цикла.

Пример 12.12

Требуется подвести итоги контрольной работы.

Исходными данными для этой задачи являются: b — балл те­кущего ученика; п — количество учеников. Расчетные данные: s — сумма баллов; sr — средний балл.

Решение этой задачи представим на школьном алгоритмиче­ском языке в таблице 12.3.

Таблица 12.3. Алгоритм «Итоги» на школьном алгоритмическом языке

Алгоритм

Пояснения

алг Итоги

Заголовок алгоритма

нач цел i, b, s, n, вещ sr

Описание типов переменных

вывод "Введите количество учеников в классе"

Вывод подсказки на экран

ввод п

Ввод с клавиатуры количества учеников

s:=0

Начальному значению суммы присваивается 0

нц для i от 1 до п

Начало цикла (повторение действий) для каждого из п учеников

вывод "Введите оценку", i, "ученика"

Тело цикла

Вывод подсказки

ввод b

Ввод оценки каждого ученика

s:=s+b

Добавление балла к текущей сумме

кц

Конец цикла

sr:=s/n

Расчет среднего балла

вывод средняя оценка=", sr

Вывод среднего балла на экран

кон

Конец алгоритма

Здесь нц, кц — служебные слова, обозначающие соответст­венно начало и конец цикла.

В этом примере повторяются следующие операции:

ввод оценки каждого ученика;
еще рефераты
Еще работы по разное
© РОНЛ.орг 2000-2026 По всем вопросам обращаться на эту почту: admin@ronl.org