Главная » Просмотр файлов » Д. Кнут - Искусство программирования том 1

Д. Кнут - Искусство программирования том 1 (1119450), страница 6

Файл №1119450 Д. Кнут - Искусство программирования том 1 (Д. Кнут - Искусство программирования том 1) 6 страницаД. Кнут - Искусство программирования том 1 (1119450) страница 62019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Например, сейчас мы находимся в разделе 1.1; внутри этого раздела алгоритм Евклида называется "Алгоритм Е", но ссылаться на него в последующих разделах мы будем как на алгоритм 1.1Е. Каждый шаг любого алгоритма, например Е1 в вышеприведенном алгоритме, начинается заключенной в квадратные скобки фразой, которая как можно более кратко выражает содержание данного шага. Обычно эта фраза отражается также в сопровождающей алгоритм блок-схеме, такой как на рис.

1, чтобы читатель мог легко представить себе описанный алгоритм. Рис. 1. Блок-схема алгоритма Е. За краткой фразой следует формулировка (выраженная с помощью слов и символов) действия, которое нужно выполнить, .или решения, которое нужно принять. Могут присутствовать также заключенные в круглые скобки комментарии (например, второе предложение шага Е1). Комментарии играют роль пояснений к шагу; с их помощью часто указываются некоторые постоянные характеристики переменных или текущие цели данного этапа. В комментариях не определяются действия, которые являются составной частью алгоритма; они служат только для удобства читателя, чтобы по возможности помочь ему разобраться в алгоритме. Стрелка "+ — ", используемая на шаге ЕЗ, обозначает важнейшую операцию замещения, которую иногда называют присвоепием или иодгллановкой: запись т е- и указывает, что значение переменной т замещается текущим значением переменной и.

В начале работы алгоритма Е т и и — это заданные первоначальные значения, но по окончании его работы эти переменные будут иметь, вообгце говоря, совершенно другие значения. Стрелка используется для того, чтобы отличать операцию замещения от отношения равенства. Мы не будем говорить: "Установим т = и", а, вероятно, спросим: "Действительно ли гп = и?".

Знак "=" обозначает условие, которое можно проверить, а знак ь < — ' — действие, которое можно выполнить. Операция увеличение и на едпннцу обозначается через и < — п+ 1 (и читается так: "и замещается значением и+ 1" или "и принимает значение п+ Г). Вообще говоря, запись "переменная +- формула" означает, что формула будет вычислена на основании текущих значений всех входящих в нее переменных, а полученный результат будет присвоен переменной, стоящей слева от стрелки (таким образом, вычисленный по формуле результат заменит собой предыдущее значение переменной слева).

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

Обратите внимание, что на шаге ЕЗ очень важен порядок действий. Действительно, записи "присвоить т +- и, и ~ — гв и "присвоить и з — г, пз +- и" — это совсем не одно и то же. Из второй записи следует, что предыдущее значение п будет потеряно до того, как его смогут присвоить т. На самом деле эквивалентом второй записи будет "присвоить и з — г, т +- г". Когда нескольким переменным присваивается одно и то же значение, в одном выражении можно использовать несколько стрелок. Так,например, операцию "и <- г, т <- г" мозкно записать как "и +- т < — г". Операцию взаимного обмена значениями двух переменных можно записать так: "Обмен ш с-> и".

Ее можно записать и с помощью новой переменной 1 следующим образом: "Присвоить г +- т, пз з — и, н < — ~". Выполнение алгоритма начинается с шага, имеющего наименыпий номер (обычно зто шаг 1). Затем последовательно выполняются следующие шаги, если нет каких-либо указаний, нарушающих естественный порядок выполнения. На шаге ЕЗ указание "Вернуться к шагу Ерв явным образом определяет порядок вычислений. На шаге Е2 действию предшествует условие "Если г = О" и если г ф О, то оставшаяся часть предложения не применяется и нет указаний на выполнение в этом случае каких-либо действий. Конечно, мы могли бы добавить дополнительное предложение "Если г ф О, то перейти к шагу ЕЗ", но зто совершенно излишне.

Жирная вертикальная черточка "3 ", помещенная в конце шага ЕЗ, обозначает окончание алгоритма и продолжение текста. Итак, мы обсудили практически все соглашения об обозначениях, которые используются в алгоритмах, приведенных в книге. Осталось выяснить только, как обозначать величины с индексами [или "подстрочными" индексами), которые являются элементами упорядоченного массива. Предположим, у нас есть и величин: выев,...,е„.

Для обозначения 1'-го элемента вместо записи в часто используется запись в[у]. Аналогично массив иногда предпочитают обозначать как а[1, у], вместо того чтобы использовать два подстрочных индекса, как в записи си Иногда для обозначения переменных используются имена, состоящие из нескольких букв. обычно прописных.

Например,' ТЕМР может быль именем переменной, использующейся для временного хранения вычисленного значения, а РК1МЕ ГК3 может обозначать К-е простое число, и т. д. До сих пор мы говорили о форме записи алгоритмов, а теперь давайте попробуем вьтолнигль один из них. Хочу сразу заметить, что читателю не следует рассчитывать на то, что алгоритмы можно читать, как роман. Такое чтение приведет к тому, по вам будет трудно понять, что же на самом деле происходит при выполнении алгоритма.

Чтобы проверить алгоритм, в нем нужно разобраться, и лучший способ понять, как он работает, — испытать его. Поэтому я предлагаю вам взять карандаш и бумагу и прорабатывать от начала до конца каждый алгоритм сразу же, как только он встретится в тексте. Обычно к примеру алгоритма прилагается схема, в противном случае читатель легко сможет представить ее. Это самый простой и доступный способ разобраться в алгоритме, в то время как все остальные подходы оказываются неэффективными, Итак, давайте в качестве примера разберем алгоритм Е. Предположим, что т = 119 н и = 544; начнем с шага Е1. (Сейчас можете просто следить за изложением, так как мы разберем алгоритм и подробно все выпишем.) Деление гп на и в этом случае выполняется просто, даже очень просто, так как частное равно нулю, а остаток— 119.

Таким образом, г 4 — 119. Переходим к шагу Е2. Поскольку г ~ О, на этом шаге никакие действия не выполняются. На шаге ЕЗ присваиваем т 4 — 544, и +- 119. Очевидно, что если первоначально гп ( и, то частное на шаге Е1 всегда оказывается равным нулю и в ходе выполнения алгоритма всегда происходит взаимный обмен значений переменных т и и, хотя и таким громоздким способом. Поэтому можно добавить дополнительный шаг. ЕО. [Гарантировать, что т > и .'! Если т ( и, то выполнить взаимный обмен т 4+ и.

В результате алгоритм изменится незначительно (разве что увеличится на один шаг), но зато время его выполнения сократится примерно в половине случаев. Вернемся к шагу Е1, Находим, что — „д = 4 —,д, поэтому г +- 68. В результате 544 66 на шаге Е2 снова не выполняются никакие действия, а на шаге ЕЗ присваиваем т 4- 119, и 4 — 68. В следующих циклах сначала получаем г 4 — 51 и т 4 — 68, и 4 — 51, взамем — г 4- 17 и ш 4 — 51, и 4 — 17. Наконец, в результатеделения 51 на 17 получаем г 4 — О. Таким образом, на шаге Е2 выполнение алгоритма прекращается.

Наибольший общий делитель 119 и 544 равен 17. Вот что такое алгоритм. Современное значение слова "алгоритм" во многом аналогично таким понятиям, как реиепт, процесс, метод, способ, процедура, программа, но все-таки слово 'а!8оНгйш" имеет дополнительный смысловой оттенок. Алгоритм — это не просто набор конечного числа правил, задающих последовательность выполнения операшгй для решения задачи определенного типа. Помимо этого, он имеет пять важных особенностей. 1) Конечность. Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов.

Алгоритм Е удовлетворяет этому условию, потому что после шага Е1 значение т меньше, чем и. Поэтому если г ф О. то в следующем цикле на шаге Е1 значение и уменьи4ается. Убывающая последовательность положительных целых чисел имеет конечное число членов, поэтому шаг Е1 может выполняться только конечное число раз для любого первоначально заданного значения ть Но имейтс в виду, что количество шагов может быть сколь угодно большим; выбор слишком больших значений гп и и приведет к тому, что шаг Е1 будет выполяятьгя более миллиона раз. Процедура, обладающая всеми характеристиками алгоритма, за исключением, возможно, конечности, называется методом вычислений. Евклид (Епс!ьй) предложил не только алгоритм нахождения наибольшего общего делителя, но и аналогичное ему геометрическое построение "наиболыпей общей меры" длин двух отрезков прямой; это уже метод вычислений, выполнение которого не заканчивается, если заданные длины оказываются несоизмеримыми.

2) Определенность, Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. Я надеюсь, что алгоритмьц приведенные в данной книге, удовлетворяют этому критерию. Но дело в 7оь4, что онн описываются обычным языком, и поэтому существует возможность неточного понимания читателем мысли автора. Чтобы преодолеть это затруднение, .для описания алгоритмов были разработаны формально определенные ламии программирования, или маигиппме языки, в котор1дх каждый оператор имеет строго определенное значение.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6384
Авторов
на СтудИзбе
308
Средний доход
с одного платного файла
Обучение Подробнее