Алгоритмы и структуры данных (CDIO)

Оглавление 
 

1 

Министерство образования и науки Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
 
 
 
Р. Ю. Царёв 
А. В. Прокопенко 
 
 
АЛГОРИТМЫ  
И  СТРУКТУРЫ  ДАННЫХ  (CDIO) 
 
 
Рекомендовано УМО РАЕ по классическому университетскому 
и техническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по направлениям подготовки: 09.03.04 «Программная инженерия», 09.03.03 
«Прикладная информатика», 38.03.02  «Менеджмент», 38.03.05  
«Бизнес-информатика» (рег. № 516 от 03.06.2015 г.) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2016 

Алгоритмы и структуры данных (CDIO) 

2 

УДК 004.422.63(07) 
ББК 32.973я73 
        Ц181 
 
 
 
 
 
Р е ц е н з е н т ы: 
А. Н. Антамошкин, доктор технических наук, профессор Красноярского государственного аграрного университета; 
А. А. Ступина, доктор технических наук, профессор Красноярского 
государственного аграрного университета 
 
 
 
 
 
 
 
 
 
 
 
Царёв, Р. Ю. 
Ц181  
Алгоритмы и структуры данных (CDIO) : учебник / Р. Ю. Царёв, А. В. Прокопенко. – Красноярск : Сиб. федер. ун-т, 2016. – 204 с.  
ISBN 978-5-7638-3388-1 
 
Рассмотрены структуры данных и алгоритмы, которые являются основой 
современной методологии разработки программ. Приведено детальное описание 
и анализ основных алгоритмов обработки данных: сортировка данных, поиск 
образа в строке, алгоритмы обработки графов.  
Предназначен для бакалавров направлений 09.03.04 «Программная инженерия», 09.03.03 «Прикладная информатика», 38.03.02 «Менеджмент», 38.03.05 
«Бизнес-информатика» и преподавателей дисциплины «Алгоритмы и структуры 
данных». 
 
 
Электронный вариант издания см.: 
http://catalog.sfu-kras.ru 
УДК 004.422.63(07) 
ББК 32.973я73 
 
ISBN 978-5-7638-3388-1                                                            © Сибирский федеральный  
                                                                                                          университет, 2016 

Оглавление 
 

3 

 
ОГЛАВЛЕНИЕ 
 
ВВЕДЕНИЕ .......................................................................................................... 6 
 
1. ОБЩИЕ  СВЕДЕНИЯ  ОБ  АЛГОРИТМАХ ................................................ 9 
1.1. Свойства алгоритмов ............................................................................. 11 
1.2. Примеры алгоритмов ............................................................................. 12 
1.3. Типы и структуры данных .................................................................... 14 
1.4. Абстрактные типы данных ................................................................... 16 
1.5. Время выполнения программ ............................................................... 18 
1.6. Вычисление времени выполнения программ ..................................... 24 
 
2. ПОИСК  ОБРАЗА  В  СТРОКЕ .................................................................... 34 
2.1. Прямой поиск строки ............................................................................ 34 
2.2. Алгоритм Кнута, Морриса и Пратта .................................................... 36 
2.3. Алгоритм Бойера и Мура ...................................................................... 39 
 
3. СОРТИРОВКА  МАССИВОВ ..................................................................... 44 
3.1. Сортировка с помощью прямого включения ...................................... 45 
3.2. Сортировка с помощью прямого выбора ............................................ 47 
3.3. Сортировка с помощью прямого обмена ............................................ 49 
3.3.1. Пузырьковая сортировка ............................................................ 49 
3.3.2. Шейкерная сортировка ............................................................... 50 
3.4. Сортировка Шелла ................................................................................. 52 
3.5. Сравнение различных алгоритмов сортировки .................................. 54 
 
4. СОРТИРОВКА  ПОСЛЕДОВАТЕЛЬНОСТЕЙ ......................................... 57 
4.1. Простое слияние .................................................................................... 57 
4.2. Естественное слияние ........................................................................... 61 
4.3. Многопутевая сортировка .................................................................... 64 
4.4. Многофазная сортировка ...................................................................... 75 
 
5. СТРУКТУРЫ  ДАННЫХ ............................................................................. 95 
5.1. Массивы .................................................................................................. 95 
5.2. Списки .................................................................................................... 96 
5.2.1. Стек .............................................................................................. 97 
5.2.2. Очередь ........................................................................................ 98 
5.2.3. Дек ................................................................................................ 99 

Алгоритмы и структуры данных (CDIO) 

4 

5.3. Деревья ................................................................................................... 99 
5.3.1. Двоичное дерево ....................................................................... 101 
5.3.2. Двоичное дерево поиска .......................................................... 103 
5.3.3. Куча ............................................................................................ 104 
5.3.4. АВЛ-дерево ............................................................................... 105 
 
6. ОРИЕНТИРОВАННЫЕ  ГРАФЫ .............................................................. 110 
6.1. Основные определения ....................................................................... 110 
6.2. Представления ориентированных графов ......................................... 112 
6.3. Задача нахождения кратчайшего пути .............................................. 114 
6.4. Нахождение кратчайших путей между парами вершин .................. 119 
6.5. Обход ориентированных графов ........................................................ 125 
6.6. Ориентированные ациклические графы ............................................ 129 
6.7. Сильная связность ............................................................................... 133 
 
7. НЕОРИЕНТИРОВАННЫЕ  ГРАФЫ ........................................................ 136 
7.1. Основные определения ........................................................................ 136 
7.2. Остовные деревья минимальной стоимости ..................................... 139 
7.3. Обход неориентированных графов .................................................... 146 
7.4. Точки сочленения и двусвязные компоненты .................................. 150 
7.5. Паросочетания графов ......................................................................... 153 
7.6. Максимальный поток в сети ............................................................... 157 
 
8. СОВРЕМЕННЫЕ  АЛГОРИТМЫ  ОБРАБОТКИ  ДАННЫХ ............... 163 
8.1. Алгоритмы и простые числа .............................................................. 163 
8.2. Генетические алгоритмы .................................................................... 168 
8.3. Муравьиные алгоритмы...................................................................... 173 
8.3.1. Биологические принципы поведения  
          муравьиной колонии ................................................................ 174 
8.3.2. Идея муравьиного алгоритма .................................................. 174 
8.3.3. Формализация задачи коммивояжера  
          в терминах муравьиного подхода ........................................... 175 
8.3.4. Области применения и возможные модификации ................ 178 
 
9. ПАРАЛЛЕЛЬНЫЕ  АЛГОРИТМЫ ........................................................... 180 
9.1. Введение в параллелизм ..................................................................... 180 
9.1.1. Категории компьютерных систем ........................................... 181 
9.1.2. Параллельные архитектуры ..................................................... 182 
9.1.3. Принципы анализа параллельных алгоритмов ...................... 184 
9.2. Модель PRAM ...................................................................................... 184 
 

Оглавление 
 

5 

9.3. Простые параллельные операции ...................................................... 186 
9.3.1. Распределение данных в модели CREW PRAM ..................... 186 
9.3.2. Распределение данных в модели EREW PRAM ..................... 187 
9.3.3. Поиск максимального элемента списка ................................. 188 
9.4. Параллельный поиск ........................................................................... 190 
9.5. Параллельная сортировка ................................................................... 191 
9.5.1. Сортировка на линейных сетях ............................................... 191 
9.5.2. Четно-нечетная сортировка перестановками ......................... 195 
9.5.3. Другие параллельные сортировки .......................................... 196 
9.6. Параллельные алгоритмы на графах ................................................. 196 
9.6.1. Параллельный алгоритм поиска кратчайшего пути ............. 196 
9.6.2. Параллельный алгоритм поиска  
          минимального остовного дерева ............................................. 198 
 
ЗАКЛЮЧЕНИЕ ............................................................................................... 201 
 
БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................... 203 

Алгоритмы и структуры данных (CDIO) 

6 

 
ВВЕДЕНИЕ 
 
CDIO (от англ. conceive, design, implement, operate – планировать, 
проектировать, производить, применять) представляет собой новую философию обучения студентов инжинирингу. Основной идеей данной инициативы является предоставление студентам инженерных специальностей        
такого образования, которое подчеркивает инженерные основы, изложенные 
в контексте жизненного цикла реальных систем, процессов и продуктов. 
Данный международный проект направлен на устранение противоречий между теорией и практикой в инженерном образовании. Новый подход 
предполагает усиление практической направленности обучения, а также 
введение системы проблемного и проектного обучения.  
CDIO подразумевает проектно-ориентированное обучение, построенное 
на определенных стандартах. В стандартах CDIO определены специальные 
требования к программам CDIO, которые могут выступать руководством 
для реформирования и оценки образовательных программ в области техники и технологий, создавать условия для их непрерывного улучшения            
и интеграции в мировое образовательное пространство. 
Решение любой вычислительной задачи предполагает выполнение 
определенной последовательности шагов. При этом один и тот же результат может быть получен различными способами. Один из способов может 
быть более эффективным, другой менее эффективным, но более легким           
в реализации. Алгоритм, будучи той самой последовательностью шагов, 
можно оценить так, как это будет показано дальше. Имея набор алгоритмов, предназначенных для решения какой-либо проблемы, программист            
в состоянии выбирать удовлетворяющий его нуждам. 
В настоящем учебнике приведены различные алгоритмы решения 
довольно широкого класса задач. Данные алгоритмы не привязаны к какому-либо языку программирования, хотя предполагается, что программная  
реализация будет выполняться на языке программирования высокого 
уровня. Теоретическая часть наглядно иллюстрируется примерами на языках Pascal, Си и псевдоязыке, сочетающем высказывания на естественном 
языке с одним из указанных выше языков программирования. 
Приведенные в данном учебнике алгоритмы представляют собой 
«классику» в области обработки данных. Существенный вклад в развитие 
современной теории алгоритмов и алгоритмизации решения практических 
задач внесли такие ученые, как Н. Вирт [2], Д. Кнут [4], Дж. Макконнелл [6],  
к трудам которых можно обратиться для более глубокого исследования 

Введение 
 

7 

проблемы построения и анализа алгоритмов. Большое количество информации об алгоритмах можно также найти в сети Интернет, как на англоязычных, так и на русскоязычных сайтах. 
Учебник освещает структуры данных и алгоритмы решения наиболее 
распространенных задач, покрывая практически всю область программирования. Здесь приведены как фундаментальные алгоритмы, так и современные методы обработки данных. Учебник состоит из девяти глав, посвященных алгоритмам решения различных классов задач.  
В первой главе приводятся основные сведения об алгоритмах, их  
свойства. Отражена разница между такими понятиями, как «структура  
данных», «тип данных» и «абстрактный тип данных». Показано, как может 
измеряться временная сложность алгоритма, которая в дальнейших главах 
служит основным критерием оценки скорости выполнения алгоритма. 
Следующая глава касается поиска образа в строке. Наглядным примером этой задачи может служить поиск слова в тексте в редакторе Word.  
Вообще задача поиска является одной из фундаментальных задач теоретического программирования. В этой главе приведен алгоритм прямого поиска, а также два алгоритма, позволяющих произвести более эффективный 
поиск.  
Сортировка или упорядочивание ряда объектов по возрастанию или 
убыванию является одной из основных задач обработки данных. Выбор алгоритма и даже класса алгоритмов, используя который возможно произвести 
сортировку, зависит от структуры данных. В связи с этим выделяют два 
типа сортировки: внутреннюю и внешнюю.  
Третья глава учебника посвящена алгоритмам внутренней сортировки, при которой все данные помещаются в оперативную память, где можно 
получить доступ к данным в любом порядке. Работа алгоритмов данного 
класса показана на примере упорядочивания элементов массива. 
Внешняя сортировка применяется в том случае, когда объем упорядочиваемых данных настолько большой, что невозможно поместить все 
данные в оперативную память. Здесь задействуется механизм обмена 
большими блоками данных между внешними запоминающими устройствами и оперативной памятью. Тот факт, что физически непрерывные данные необходимо для удобства перемещения организовывать в блочную 
структуру вынуждает использовать специальные алгоритмы внешней сортировки. Алгоритмам внешней сортировки посвящена четвертая глава,           
в которой предполагается, что все данные хранятся в файлах. 
Невозможно говорить о практической или даже формальной реализации алгоритмов безотносительно структур и типов данных. Пятая глава 
посвящена различным структурам данных, которые позволяют хранить          
и обрабатывать данные, исходя из особенностей решаемой задачи. В дан

Алгоритмы и структуры данных (CDIO) 

8 

ной главе рассматриваются как простые, так и «интегрированные» структуры данных, которые состоят из простых: массивы, списки, деревья, графы.  
В шестой главе показаны ориентированные графы. Решается такая 
важная задача, как поиск кратчайшего пути между двумя вершинами. 
Умение решать данную задачу помогает в планировании кратчайшего 
маршрута, например, при передвижении на транспортном средстве или передаче сообщений по компьютерной сети. Также в этой главе показано, как 
можно перебрать все вершины графа методом обхода в глубину, что может 
потребоваться при поиске одной вершины во всем множестве вершин графа. 
В седьмой главе приведены основные определения, связанные с неориентированными графами. Помимо обхода в глубину рассматривается 
обход в ширину, который, впрочем, также применим и к ориентированным 
графам. Другой немаловажной задачей, алгоритмы решения которой представлены в данной главе, является построение минимального остовного дерева графа. Одно из применений минимальных остовных деревьев – организация локальной компьютерной сети с минимальными затратами            
на объединение всех компьютеров в единую сеть. Здесь же рассматривается 
связность графа и задача о паросочетании. 
Восьмая глава содержит краткое изложение некоторых идей, на основе которых разрабатываются современные алгоритмы. Примечательно, 
что данные алгоритмы используются не только для решения практических 
задач, но также активно применяются в научных исследованиях. Генетические алгоритмы  можно встретить в диссертационных работах по различным направлениям. Здесь же представлены общие сведения о новом перспективном подходе к решению задач оптимизации на основе муравьиных 
алгоритмов. Особый интерес представляет тот факт, что в их основе лежит 
моделирование поведения колонии муравьев. 
Девятая глава позволяет взглянуть на алгоритмы, описанные в предыдущих главах, с иной точки зрения. В данной главе предполагается параллельная обработка данных, которая довольно редко освещается в литературе на русском языке. Данную главу можно также рассматривать как 
введение в параллельное программирование. Здесь приводится обзор            
общих понятий, связанных со структурой параллельных компьютерных 
систем, и сами параллельные алгоритмы решения некоторых из практических задач. 
В учебнике предложен широкий спектр алгоритмов, предназначенных 
для решения основных задач современной теории алгоритмов. Особенностью рассмотренных алгоритмов является возможность их применения для 
решения реальных задач. Рассмотренные алгоритмы могут быть применены в большом числе предметных областей и практических ситуаций. 

1. Общие сведения об алгоритмах 
 

9 

 
1. ОБЩИЕ  СВЕДЕНИЯ  ОБ  АЛГОРИТМАХ 
 
 
В основе любой компьютерной программы всегда лежит некоторый 
алгоритм, программа является изложением алгоритма на некотором языке, 
понятном вычислительной машине. 
Первым дошедшим до нас алгоритмом в его интуитивном понимании как конечной последовательности элементарных действий, решающих 
поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел.  
Отметим, что в течение длительного времени, вплоть до начала XX века, 
само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм  
Евклида». Для описания последовательности пошагового решения других 
математических задач чаще использовался термин «метод».  
Во всех сферах своей деятельности, в частности в сфере обработки 
информации, человек сталкивается с различными способами или методиками решения разнообразных задач. Они определяют порядок выполнения 
действий для получения желаемого результата. Можно трактовать это как 
первоначальное, или интуитивное, определение алгоритма. Таким образом, 
можно нестрого определить алгоритм как однозначно трактуемую процедуру решения задачи. Дополнительные требования о выполнении алгоритма 
за конечное время для любых входных данных приводят к следующему 
неформальному определению алгоритма. 
Алгоритм – это заданное на некотором языке конечное предписание, 
задающее конечную последовательность выполнимых и точно определенных элементарных операций для решения задачи, общее для класса возможных исходных данных. 
Пусть Dz – область (множество) исходных данных задачи Z, a R –  
множество возможных результатов, тогда можно говорить, что алгоритм 
осуществляет отображение Dz → R. Поскольку такое отображение может 
быть не полным, то вводятся следующие понятия: 
Алгоритм называется частичным алгоритмом, если результат может 
быть получен только для некоторых d ∈ Dz и полным алгоритмом, если 
алгоритм получает правильный результат для всех d ∈ Dz. 
Несмотря на усилия ученых, сегодня отсутствует одно исчерпывающе строгое определение понятия «алгоритм». Из разнообразных вариантов 
словесного определения алгоритма наиболее удачные, по мнению автора, 
принадлежат российским ученым А. Н. Колмогорову и А. А. Маркову. 

Алгоритмы и структуры данных (CDIO) 

10 

Определение по Колмогорову: алгоритм – это всякая система         
вычислений, выполняемых по строго определенным правилам, которая 
после какого-либо числа шагов заведомо приводит к решению поставленной задачи. 
Определение по Маркову: алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных 
данных к искомому результату. 
Отметим, что различные определения алгоритма в явной или неявной форме постулируют следующий ряд общих требований: 
● алгоритм должен содержать конечное количество элементарно  
выполнимых предписаний, т. е. удовлетворять требованию конечности           
записи; 
● алгоритм должен выполнять конечное количество шагов при решении задачи, т. е. удовлетворять требованию конечности действий; 
● алгоритм должен быть единым для всех допустимых исходных 
данных, т. е. удовлетворять требованию универсальности; 
● алгоритм должен приводить к правильному по отношению               
к поставленной задаче решению, т. е. удовлетворять требованию правильности. 
Неудобства словесных определений связаны с проблемой однозначной 
трактовки терминов. В таких определениях должен быть, хотя бы неявно, 
указан исполнитель действий или предписаний. Алгоритм вычисления 
производной для полинома фиксированной степени вполне ясен тем, кто 
знаком с основами математического анализа, но для прочих он может оказаться совершенно непонятным. Это рассуждение заставляет указать также 
вычислительные возможности исполнителя, а именно уточнить, какие операции для него являются «элементарными». Другие трудности связаны           
с тем, что алгоритм заведомо существует, но его очень трудно описать              
в некоторой заранее заданной форме. Классический пример такой ситуации – алгоритм завязывания шнурков на ботинках «в бантик». Вы сможете 
дать только словесное описание этого алгоритма без использования иллюстраций? 
В связи с этим формально строгие определения понятия алгоритма 
связаны с введением специальных математических конструкций – формальных алгоритмических систем или моделей вычислений, каковыми         
являются машина Поста, машина Тьюринга, рекурсивно-вычислимые 
функции Черча, и постулированием тезиса об эквивалентности такого 
формализма и понятия «алгоритм». Несмотря на принципиально разные 
модели вычислений, использующиеся для определения термина «алгоритм», интересным результатом является формулировка гипотез об эквивалентности этих формальных определений в смысле их равномощности. 

1. Общие сведения об алгоритмах 
 

11 

1.1. Свойства алгоритмов 
 
В качестве содержательных свойств, характеризующих алгоритм,  
А. А. Марков отмечает следующие: 
1. Определенность. Алгоритм должен быть точным, недвусмысленным и понятным исполнителю. Исполнитель, выполняя алгоритм, должен 
однозначно понимать предписание и знать, что надлежит делать на данном 
шаге вычислительного процесса и каков будет следующий шаг. Определенность не всегда означает детерминированность, т. е. когда на каждом 
шаге вычислительного процесса исполнитель должен исполнить единственное предписываемое действие и результат этого действия определен. 
Хотя в дальнейшем будем предполагать, что алгоритм детерминирован, 
однако не стоит забывать, что могут существовать и недетерминированные 
алгоритмы, особенно при наличии коллектива исполнителей (что характерно для параллельного программирования). При недетерминированности 
на некоторых шагах вычислительного процесса возможен не определяемый алгоритмом выбор из конечного фиксированного набора действий,           
но этот набор должен быть точно определен – определенность есть неотъемлемое свойство алгоритма. 
2. Массовость. Алгоритм предлагает всегда решение некоторой массовой проблемы, его исходные данные варьируются. Существует некоторое (заведомо не пустое и не единичное) множество наборов исходных 
данных, определяемое решаемой проблемой, для которых алгоритм обеспечивает получение искомого результата. 
Не для любой массовой проблемы существует решающий ее алгоритм – в теории алгоритмов для ряда массовых проблем доказана их неразрешимость, т. е. отсутствие алгоритма, получающего искомый результат для 
множества наборов исходных данных, возможного для этой проблемы. 
Близкой для нас неразрешимой массовой проблемой является установление 
эквивалентности двух произвольных программ – доказано, что не существует алгоритма, который для двух произвольных программ устанавливал 
бы, всегда ли они для одинакового набора исходных данных получают 
одинаковый результат. Вместе с тем нас должен утешать тот факт, что 
большинство реальных проблем в их надлежащей постановке вполне          
допускают наличие алгоритма их решения. 
3. Результативность. Обычно алгоритм должен обеспечивать завершение своего выполнения ожидаемым результатом вычислительного процесса в конечное (и хотелось бы, приемлемое) время, разумеется, при надлежащих допустимых исходных данных. Допустимость исходных данных 
следует из существа решаемой проблемы: так, если все исходные данные 
должны быть положительны, то нельзя требовать от алгоритма разумной 

Алгоритмы и структуры данных (CDIO) 

12 

реакции на то, что одно из данных ошибочно оказалось отрицательным. 
Вместе с тем обычно стараются обезопасить алгоритм предварительной 
проверкой исходных данных на допустимость и при их недопустимости 
явно сообщать пользователю об этом.  В пользовательском  программировании все реализуемые алгоритмы носят такой завершающийся характер. 
Однако результатом алгоритма может быть и поддержание некоторого       
постоянного процесса: процесса управления некоторым устройством, процесса контроля его состояния, наконец, процесса  операционной  системы, 
управляющей функционированием компьютера. Результатами таких алгоритмов являются сигналы и сообщения, посылаемые пользователю или 
устройству, и в этом их результативность. Такие алгоритмы, как правило, 
находятся за рамками пользовательского программирования. 
 
 
1.2. Примеры алгоритмов 
 
Классической массовой проблемой, известной с древности, является 
нахождение наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм, решающий эту проблему, может быть следующим. 
Дана пара произвольных чисел, назовем их т и n. Предписание, 
представляющее алгоритм, будем описывать на естественном языке в виде 
последовательности нумеруемых шагов: 
Шаг 1. Возьмем в качестве р значение наименьшего из m и n. 
Шаг 2. Возьмем в качестве t значение 1. 
Шаг 3. Если р = 1, то перейдём к шагу 5, иначе к шагу 4. 
Шаг 4. Задавая в качестве i последовательно все целые значения от 2 
до р (по возрастанию), повторяем Шаг 4.1.  
Шаг 4.1. Если остаток (m / i) = 0 и остаток (n / i) = 0, то возьмем           
в качестве t значение i.  
Шаг 5. Завершаем алгоритм с результатом НОД = t. 
С точки зрения исполнителя-человека это предписание точно и однозначно. Шаги исполняются последовательно, причем шаг 4 является повторением определенного числа раз шага 4.1 каждый раз со следующим 
значением i. Будем считать, что мы знаем, как находить остаток от деления, т. е. определенность здесь присутствует. 
То, что приведенное предписание обладает массовостью, тоже очевидно. Существует множество пар чисел, для которых предписание дает 
результат. Ясно, что вычислительный процесс будет нормально исполняться для любых конечных значений т и п больше нуля. Именно такие 
пары и дают нам допустимые для решаемой проблемы значения исходных 
данных. 

1. Общие сведения об алгоритмах 
 

13 

В данном случае результативность совпадает с завершаемостью.  
Завершаемость вычислительного процесса следует из того, что т и п             
конечны, и, следовательно, число повторений шага 4.1 тоже конечно,            
остальные же шаги выполняются однократно. Число исполненных шагов 
зависит прежде всего от числа повторений шага 4.1, а он будет повторяться 
(min(m, п) – 1) раз. То, что результатом будет действительно наибольший 
общий делитель, очевидно из того, что если одно из значений пары есть 1, 
то полученным НОД будет 1; если ни одно из чисел от 2 до наименьшего 
из пары не является одновременно делителем и п, и т, то полученный 
НОД тоже 1, а если среди этих чисел есть делители и п, и т, то значением t 
после шага 4 будет наибольшее такое число. Именно оно будет последним 
и на шаге 4.1 будет взято в качестве t. Итак, приведенное предписание обладает всеми упомянутыми свойствами алгоритма. 
Заметим, что здесь мы применили подход «в лоб» – перебрали все 
значения, которые в принципе могут быть делителями m и п, и проверили, 
может ли каждое быть общим делителем, а найдя больший, чем ранее найденный, делитель, заменили им ранее найденный. Такие, так называемые 
переборные, алгоритмы (перебираются все потенциально возможные значения решений) мы вынуждены применять, если у нас нет никаких соображений, как сократить число перебираемых значений. Зачастую такие соображения у нас могут быть. Так, для данной проблемы давно известно, 
что 

НОД (m, n) = НОД (остаток (n / m), m), 

где m – наименьшее число пары. Таким образом, нахождение НОД для пары чисел можно свести к нахождению НОД для такой пары, в которой 
прежнее наименьшее становится наибольшим. Перебор уже становится 
перебором пар, определяемых приведенным выше соотношением, что сокращает его по отношению к уже приведенному алгоритму. Алгоритм (так 
называемый алгоритм Евклида) выглядит следующим образом: 
Шаг 1. Пока m не равно 0, выполнять шаги 1.1–1.4, иначе перейти          
к шагу 2. 
Шаг 1.1. Возьмем значение t как остаток (n / m). 
Шаг 1.2. Возьмем n как значение m. 
Шаг 1.3. Возьмем m как значение t. 
Шаг 1.4. Вернемся к шагу 1. 
Шаг 2. Завершаем алгоритм с НОД = n. 
Приведенное предписание действительно является алгоритмом, так 
как оно обладает определенностью (как и предыдущее предписание), массовостью (о допустимых значениях мы поговорим далее) и результативностью 
(повторения шагов 1.1–1.4 создают пары с уменьшающимися неотрица