Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Адаптация ребенка к детскому садуОчевидно, где-то в подсознании у нас укоренилось: раз ребенку стукнуло три года - значит, ему надо идти в детский сад...полностью>>
'Документ'
Доступ к USSD-меню возможен только с Вашего номера телефона. Для использования USSD-меню не требуется подключение дополнительных услуг и запоминание п...полностью>>
'Документ'
о порядке организации и проведения регионального этапа Всероссийской Олимпиады профессионального мастерства по специальности среднего профессиональног...полностью>>
'Документ'
Для получения официальных результатов ЕГЭ-2016 следует обращаться в свою школу или в муниципальный орган управления образованием, в котором Вы регистр...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

алгоритм Оптимальный путь от Аэровокзала до Домодедово

| Дано: находимся у Аэровокзала

| Надо: оказаться в аэропорту Домодедово

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

| если нет пробки на Ленинградском проспекте

| | в направлении из центра

| | то

| | // ...выполняем предыдущий алгоритм...

| | Проезд от Аэровокзала до Домодедово через МКАД

| | иначе

| | повернуть направо на боковой проезд

| | Ленинградского проспекта в сторону центра;

| | доехать до пересечения с Беговой улицей;

| | повернуть направо на Третье транспортное кольцо;

| | ехать по Третьему транспортному кольцу против

| | часовой стрелки до пересечения с Варшавским шоссе;

| | повернуть направо на Варшавское шоссе

| | в сторону из центра;

| | ехать прямо до развилки с Каширским шоссе;

| | на развилке с Каширским шоссе проехать прямо в сторону

| | Каширского шоссе; // Варшавское уходит направо

| | двигаться, никуда не сворачивая, до

| | аэропорта Домодедово;

| конец если

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

Здесь исполнитель алгоритма сначала должен проверить условие

нет пробки на Ленинградском проспекте

в направлении из центра

Если это условие истинно, то выполняется первый алгоритм "Проезд от Аэровокзала до Домодедово через МКАД"; если ложно - часть алгоритма между строками "иначе" и "конец если". Следует отметить, что

1) здесь выполняется алгоритм "Проезд от Аэровокзала до Домодедово через МКАД", описанный ранее. Возможность использования (вызова) описанных ранее алгоритмов является важной чертой любого алгоритмического языка, позволяющей строить более сложные алгоритмы из имеющихся заготовок;

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

Второй важнейшей конструкцией алгоритмического языка является конструкция "цикл пока". Заголовок цикла состоит из ключевых слов "цикл пока", за которыми следует некоторое условие. Дальше записывается тело цикла, завершаемое строкой "конец цикла". При выполнении цикла исполнитель сначала проверяет условие в заголовке тела цикла. Если условие истинно, то выполняется тело цикла. Затем вновь проверяется условие в заголовке цикла, опять выполняется тело цикла, если условие истинно, и так до бесконечности. Если же условие ложно с самого начала или становится ложным в результате предыдущего выполнения тела цикла, то тело цикла не выполняется и цикл завершается. Таким образом, по выходу из цикла условие, записанное в его заголовке, всегда ложно. Если условие ложно перед началом цикла, то цикл не выполняется ни разу! Программисты иногда называют "цикл пока" циклом с предусловием, поскольку условие продолжения цикла проверяется перед выполнением тела цикла, а не после него. Иногда используют циклы с постусловием (do... while), когда тело цикла всегда выполняется хотя бы один раз, а условие продолжения проверяется после каждой итерации. Всегда предпочтительнее использовать цикл с предусловием, это помогает избежать многих ошибок.

Для иллюстрации конструкции "цикл пока" можно привести следующую модификацию алгоритма проезда.

алгоритм Добраться из Аэровокзала до Домодедово

| Дано: находимся у Аэровокзала

| Надо: оказаться в аэропорту Домодедово

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

|

| цикл пока пробка на Ленинградском проспекте

| | выпить чашку кофе в кафе Аэровокзала

| | ждать полчаса

| конец цикла

|

| Проезд от аэровокзала до Домодедово через МКАД

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

Здесь снова использован определенный ранее алгоритм "Проезд от аэровокзала до Домодедово". Условие продолжения цикла проверяется перед выполнением тела цикла, но не в процессе его выполнения! Так, если пробка рассосалась после чашки кофе, то все равно нужно ждать полчаса.

Теперь можно подвести итоги.

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

если условие

| то

| последовательность действий 1

| иначе

| последовательность действий 2

конец если

Последовательность действий 1 выполняется, когда условие истинно; в противном случае выполняется последовательность действий 2. Ключевое слово "иначе" и последовательность действий 2 могут отсутствовать; в этом случае, когда условие ложно, исполнитель ничего не делает.

Цикл "пока", или цикл с предусловием выглядит следующим образом:

цикл пока условие

| последовательность действий

конец цикла

Сначала проверяется условие в заголовке цикла. Если оно истинно, то выполняется последовательность действий, составляющая тело цикла. Это повторяется неограниченное число раз, пока условие истинно. Цикл заканчивается, когда условие при очередной проверке оказывается ложным. Важно отметить, что условие проверяется перед каждым выполнением тела цикла, но не в процессе его выполнения.

Помимо элементарных действий, в записи алгоритма можно использовать другие алгоритмы. Для вызова другого алгоритма нужно просто указать его название. (В некоторых языках, например, в Фортране, для вызова алгоритма используется ключевое слово CALL.) Также в записи алгоритма могут присутствовать комментарии, которые игнорируются исполнителем алгоритма. Для отделения комментария будут использоваться знаки // (двойная косая черта) в соответствии с синтаксисом языка C++.

Понятие переменной

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

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

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

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

Значение каждого параметра хранится в определенном участке памяти компьютера и может меняться в процессе выполнения алгоритма. Такой участок памяти компьютера называется переменной. Понятие переменной - важнейшее понятие алгоритмического языка. Переменные встроены в конструкцию универсального исполнителя.

Каждой переменной присваивается имя. В рассмотренном примере используются переменные "скорость", "обороты двигателя", "передача", "нагрузка", "температура", "обогащенность смеси", "угол опережения зажигания" и другие. С каждой переменной связан ее тип, т.е. множество значений, которое она может принимать. Например, "передача" принимает целые значения от 1 до 5 (обратная и первая передачи не различаются), тогда как "скорость", а также "обогащенность смеси" принимают вещественные значения (скорость измеряется в м/сек, обогащенность смеси может измеряться либо соотношением кислорода и паров бензина в единице объема, либо в процентах относительно стехиометрической смеси 14/1, соответствующей полному сгоранию паров бензина).

С переменной можно выполнять два действия:

прочитать текущее значение переменной;

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

В алгоритмическом языке чтение значения переменной выполняется в результате использования ее имени в любом выражении. Запись нового значения переменной выполняется с помощью так называемого оператора присваивания. Он выглядит следующим образом:

имя переменной := выражение;

Знак := читается как присвоить значение. Во многих языках вместо него используется просто знак равенства:

имя переменной = выражение;

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

скорость := число импульсов от датчика скорости /

(6 * интервал времени);

Переменная "число импульсов от датчика скорости" в течение каждого интервала времени суммирует число импульсов. В начале каждого интервала она обнуляется. Полученная в результате скорость выражается в м/с. Если нужно получить скорость в км/час, то дополнительно выполняется следующее действие:

скорость := скорость * 3600 / 1000;

Здесь переменная "скорость" входит как в правую, так и в левую части оператора присваивания. В правой части используется старое значение этой переменной, вычисленное в м/сек. Поскольку час содержит 3600 секунд, то при домножении на 3600 получается расстояние в метрах, проходимое за 1 час; после деления на 1000 получается расстояние в километрах. Вычисленное значение затем присваивается переменной "скорость".

Суммируем сказанное выше:

универсальный исполнитель, или компьютер, - это исполнитель, который может управлять другими исполнителями. Запись алгоритма для универсального исполнителя может включать команды, которые он должен передать подчиненным исполнителям, и команды, изменяющие внутреннее состояние самого универсального исполнителя;

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

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

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

имя переменной := выражение;

При его выполнении сначала вычисляется значение выражения справа от знака присваивания :=, затем оно записывается в переменную. Выражение в правой части может включать имя переменной в левой части. В этом случае при вычислении выражения используется старое значение переменной.

Типы переменных

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

Целочисленные переменные

Тип целое число является основным для любого алгоритмического языка. Связано это с тем, что содержимое ячейки памяти или регистра процессора можно рассматривать как целое число. Адреса элементов памяти также представляют собой целые числа, с их помощью записываются машинные команды и т.д. Символы представляются в компьютере целыми числами - их кодами в некоторой кодировке. Изображения также задаются массивами целых чисел: для каждой точки цветного изображения хранятся интенсивности ее красной, зеленой и синей составляющей (в большинстве случаев - в диапазоне от 0 до 255). Как говорят математики, целые числа даны свыше, все остальное сконструировал из них человек.

Общепринятый в программировании термин целое число или целочисленная переменная, строго говоря, не вполне корректен. Целых чисел бесконечно много, десятичная или двоичная запись целого числа может быть сколь угодно длинной и не помещаться в области памяти, отведенной под одну переменную. Целая переменная в компьютере может хранить лишь ограниченное множество целых чисел в некотором интервале. В современных компьютерах под целую переменную отводится 4 байта, т.е. 32 двоичных разряда. Она может хранить числа от нуля до 2 в 32-й степени минус 1. Таким образом, максимальное целое число, которое может храниться в целочисленной переменной, равно

232 - 1 = 4294967295

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

a+b = b+a, ab = ba

(a+b) + c = a+(b+c), (ab)c = a(bc)

a(b+c) = ab+ac

Кольцо вычетов по модулю m

Целочисленный тип компьютера в точности соответствует важнейшему понятию математики - понятию кольца вычетов по модулю m. В качестве m выступает число 232 = 4294967296. В математике кольцо Zm определяется следующим образом. Все множество целых чисел Z разбивается на m классов, которые называются классами эквивалентности. Каждый класс содержит числа, попарная разность которых делится на m. Первый класс содержит числа

{...,-2m,-m,0,m,2m, ...}

второй

{..., -2m+1, -m+1, 1, m+1, 2m+1, ...}

последний

{..., -m-1, -1, m-1, 2m-1, 3m-1, ...}

Элементами кольца Zm являются классы эквивалентности. Их ровно m, так что, в отличие от множества целых чисел Z, кольцо Zm содержит конечное число элементов. Операции с классами выполняются следующим образом: надо взять по одному представителю из каждого класса, произвести операцию и определить, в какой класс попадает результат. Этот класс и будет результатом операции. Легко показать, что он не зависит от выбора представителей.

Все числа, принадлежащие одному классу эквивалентности, имеют один и тот же остаток при делении на m. Таким образом, класс эквивалентности однозначно определяется остатком от деления на m. Традиционно остаток выбирается неотрицательным, в диапазоне от 0 до m -1. Остатки используют для обозначения классов, при этом используются квадратные скобки. Так, выражение [5] обозначает класс эквивалентности, состоящий из всех чисел, остатки которых при делении на m равны пяти. Все кольцо Zm состоит из элементов



Похожие документы:

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

    Тесты
    ... ___ 20__г. Психологические тесты специального экзамена для абитуриентов, поступающих на педагогические специальности Назначение психологического комплексного теста ...
  2. Программа вступительного творческого экзамена для абитуриентогв, поступающих на профессионально-образовательные профили

    Программа
    ... ТВОРЧЕСКОГО ЭКЗАМЕНА ДЛЯ АБИТУРИЕНТОГВ, ПОСТУПАЮЩИХ НА ПРОФЕССИОНАЛЬНО-ОБРАЗОВАТЕЛЬНЫЕ ... на вопросы комиссии по выполняемым заданиям. 1.3. Теоретическая и практическая подготовка для ... выявление у абитуриента комплекса общих и специальных способностей, ...
  3. Программа вступительных испытаний по физике для лиц, поступающих на базе среднего (полного) общего образования Абакан 2011

    Программа
    ... по физике для лиц, поступающих на базе среднего ... внимание обращается на понимание абитуриентом сущности физических ... теорий. Поступающий должен проявить осведомленность в вопросах, связанных ... света. Основы специальной ТЕОРИИ ОТНОСИТЕЛЬНОСТИ ...
  4. Вопросы к вступительным испытаниям для поступающих на обучение по программам подготовки научно-педагогических кадров в аспирантуре РИИИ

    Программа
    ... - ответ одного вопроса по билетам. Для поступающих на профиль «Музыкальное искусство ... ответа на выбранный самим абитуриентом вопрос. Поступающие выбирают вопрос из ... Для письменного перевода предлагается оригинальный текст по избранной специальности ...
  5. Учебное пособие для абитуриентов вузов Москва. 2006 удк 373. 167. 1: 3 ббк 60 С48

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

Другие похожие документы..