Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться

• Название: По вопросам приобретения обращаться
• Анкор: Окулов.Программирование.в.алгоритмах.pdf
• Дата: 26.04.2017
• Размер: 5.46 Mb.
• Имя файла: Окулов.Программирование.в.алгоритмах.pdf
• Тип: Документы; #5718
• страница: 1 из 26

УДК 519.85(023)
ББК 22.18 052
Работа выполнена при поддержке
Министерства образования Российской Федерации, проект Г00—4.1-60.
Окулов С. М.
Программирование в алгоритмах / С. М. Окулов. —
М.: БИНОМ. Лаборатория знаний, 2002. — 341 с: ил.
ISBN 5-94774-010-9
Искусство программирования представлено в виде учебного курса,
раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению.
Практические рекомендации по тестированию программ являются не- обходимым дополнением курса.
Предназначен для школьников, студентов и специалистов, серьез- но изучающих программирование, а также для преподавателей учеб- ных заведений.
УДК 519.85(023)
ББК 22.18
По вопросам приобретения обращаться
в Москве:
«БИНОМ. Лаборатория знаний» [phone], e-mail: [e-mail]
в Санкт-Петербурге:
«Диалект» [phone], e-mail: [e-mail]
© Окулов С. М., 2002
ISBN 5-94774-010-9 © БИНОМ. Лаборатория знаний, 2002

Содержание
Предисловие 7
1. Арифметика многоразрядных целых чисел 9
1.1. Основные арифметические операции 9 1.2. Задачи 21 2. Комбинаторные алгоритмы 25 2.1. Классические задачи комбинаторики 25 2.2. Генерация комбинаторных объектов 31 2.2.1. Перестановки 31 2.2.2. Размещения 40 2.2.3. Сочетания 46 2.2.4. Разбиение числа на слагаемые 53 2.2.5. Последовательности из нулей и единиц длины N
без двух единиц подряд 58 2.2.6. Подмножества 61 2.2.7. Скобочные последовательности 65 2.3. Задачи 68
3. Перебор и методы его сокращения 79
3.1. Перебор с возвратом (общая схема) 79 3.2. Примеры задач для разбора общей схемы перебора 81 3.3. Динамическое программирование 96 3.4. Примеры задач для разбора идеи метода динамического программирования 98 3.5. Метод ветвей и границ 105 3.6. Метод «решета» 109 3.7. Задачи 113 4. Алгоритмы на графах 141
4.1. Представление графа в памяти компьютера 141 4.2. Поиск в графе 142 4.2.1. Поиск в глубину 142 4.2.2. Поиск в ширину 143 4.3. Деревья 144

Содержание
4.3.1. Основные понятия. Стягивающие деревья 144 4.3.2. Порождение всех каркасов графа 145 4.3.3. Каркас минимального веса. Метод Дж. Краскала . . 148 4.3.4. Каркас минимального веса. Метод Р. Прима 150 4.4. Связность 151 4.4.1. Достижимость 151 4.4.2. Определение связности 153 4.4.3. Двусвязность 154 4.5. Циклы 157 4.5.1. Эйлеровы циклы 157 4.5.2. Гамильтоновы циклы 158 4.5.3. Фундаментальное множество циклов 160 4.6. Кратчайшие пути 161 4.6.2. Алгоритм Дейкстры 163 4.6.3. Пути в бесконтурном графе 164 4.6.4. Кратчайшие пути между всеми парами вершин.
Алгоритм Флойда 166 4.7. Независимые и доминирующие множества 168 4.7.1. Независимые множества 168 4.7.2. Метод генерации всех максимальных независимых множеств графа 169 4.7.3. Доминирующие множества 173 4.7.4. Задача о наименьшем покрытии 174 4.7.5. Метод решения задачи о наименьшем разбиении . . 175 4.8. Раскраски 180 4.8.1. Правильные раскраски 180 4.8.2. Поиск минимальной раскраски вершин графа . . . . 181 4.8.3. Использование задачи о наименьшем покрытии при раскраске вершин графа 185 4.9. Потоки в сетях, паросочетания 186 4.9.1. Постановка задачи 186 4.9.2. Метод построения максимального потока в сети . . . 187 4.9.3. Наибольшее паросочетание в двудольном графе . . . 192 4.10. Методы приближенного решения задачи коммивояжера 195 4.10.1. Метод локальной оптимизации 195 4.10.2. Алгоритм Эйлера 197 4.10.3. Алгоритм Кристофидеса 200 4.11. Задачи 202
5. Алгоритмы вычислительной геометрии 222
5.1. Базовые процедуры 222

Содержание
5.2. Прямая линия и отрезок прямой 227 5.3. Треугольник 232 5.4. Многоугольник 236 5.5. Выпуклая оболочка 241 5.6. Задачи о прямоугольниках 251 5.7. Задачи 259 6. Избранные олимпиадные задачи по программированию 266 7. Заметки о тестировании программ 318 7.1. О программировании 319 7.2. Практические рекомендации 320 7.3. Тестирование программы решения задачи
(на примере) 328
Библиографический указатель 340

Предисловие
Единственной женщине посвящаю.
Курс «Программирование в алгоритмах» является естествен- ным продолжением курса «Основы программирования». Его со- держание достаточно традиционно: структурное программирова- ние, технологии «сверху — вниз» и «снизу — вверх». Освоению обязательной программы курса автор придает огромное значение. Она обязана стать естественной схемой решения за- дач, если хотите — культурой мышления или познания.
Только после этого, по нашему глубокому убеждению, разум- но переходить на объектно-ориентированное программирование,
работу в визуальных средах, на машинно-ориентированное про- граммирование и т. д. Практика подтвердила жизненность дан- ной схемы изучения информатики. Ученики физико-математи- ческого лицея г. Кирова многие годы представляют регион на различных соревнованиях по информатике, включая Междуна- родные олимпиады. Возвращение их без дипломов или меда- лей — редкое исключение. Переходя в разряд студентов, выпу- скники лицея без особых хлопот изучают дисциплины по информатике в любом высшем учебном заведении России, а так- же успешно выступают в командных чемпионатах мира среди студентов по программированию.
Для кого предназначен учебник? Во-первых, для учителей и учащихся школ с углубленным изучением информатики.
Во-вторых, для студентов высших учебных заведений, изучаю- щих программирование и стремящихся достичь профессиона- льного уровня. Особенно он будет полезен тем, кто готовится принять участие в олимпиадах по программированию, включая широко известный чемпионат мира по программированию,
проводимый под эгидой международной организации ACM (As- sociation for Computing Machinery).
О благодарностях, ибо не так часто вслух предоставляется возможность сказать коллегам о том, что ты их безмерно ува- жаешь. Во-первых, это касается моих учеников и учителей од- новременно. Без сотрудничества с ними вряд ли автор смог на- писать что-то подобное. Первая попытка написания книг такого рода была предпринята в 1993 году с Антоном Валерье- вичем Лапуновым. То было совместное вхождение в данную проблематику. Для Антона более легкое, для автора достаточно

8 Предисловие трудное. Затем последовало сотрудничество с Виталием Игоре- вичем Беровым. Наверное, благодаря ему автор нашел ту схему изложения алгоритмов на графах, которую он затем применял в работе даже с восьмиклассниками. Сотрудничество с Викто- ром Александровичем Матюхиным в пору его ученичества было не таким явным, но после того, как он стал студентом МГУ и в настоящее время, оно, на мой взгляд, очень плодотворно. Вли- яние Виктора на развитие олимпиадной информатики в г. Кирове просто огромно. С братьями Пестовыми, Андреем и
Олегом, написаны книги. Более трудолюбивых и отзывчивых учеников автору не приходилось встречать. Сотрудничество с такими ребятами не было бы возможным без высочайшего про- фессионализма Владислава Владимировича Юферева и Галины
Константиновны Корякиной, директора и завуча физико-мате- матического лицея г. Кирова. Особые слова признательности хотелось бы выразить Владимиру Михайловичу Кирюхину, ру- ководителю сборной команды школьников России по информа- тике. В 1994 году он привлек автора к работе в жюри россий- ской олимпиады школьников. За эти годы автор воочию увидел весь тот тяжелейший труд, который стоит за победами россий- ских школьников на Международных олимпиадах. Иосиф Вла- димирович Романовский сделал ряд ценных замечаний по га- зетной версии главы 5, за что автор благодарит его и желает дальнейших творческих успехов в деле обучения санктпетер- бургских студентов. Многие годы главный редактор газеты
«Информатика» Сергей Львович Островский поддерживал ав- тора в его работе, и признательность за это остается неизмен- ной.
Об ошибках. Учебники такого плана не могут не содержать ошибок. Для многих алгоритмов можно, естественно, найти другие схемы реализации. Автор с признательностью примет все замечания. Присылайте их, пожалуйста, по адресу [e-mail].

Арифметика многоразрядных
целых чисел
Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позво- ляют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А
если нам необходимо выполнить арифметические действия над очень большими числами, например
30!= 265252859812191058636308480000000?
В таких случаях мы сами должны позаботиться о представле- нии чисел и о точном выполнении арифметических операций над ними.
1.1. Основные арифметические операции
Числа, для представления которых в стандартных компью- терных типах данных не хватает количества двоичных разря- дов, называются иногда «длинными». В этом случае програм- мисту приходится самостоятельно создавать подпрограммы выполнения арифметических операций. Рассмотрим один из возможных способов их реализации.
Представим в виде:
Номер элемента в массиве А
Значение
0 9
1 0
2 8000 3
3084 4
8636 5
9105 6
8121 7
2859 8
6525 9
2
Возникают вопросы. Что за 9 в А[0], почему число хранится
«ладом наперед»? Ответы очевидны, но подождем с ними. Бу- дет ясно из текста.
Примечание
Мы работаем с положительными числами!
Первая задача. Ввести число из файла. Но прежде описание
Это представление наталкивает на мысль о массиве.

10 1. Арифметика многоразрядных целых чисел
Const
количество цифр — че-
тырехзначных.*}
нашей системы счисления, в эле-
ментах массива храним четырехзначные числа.*}
Type
Of Integer;{* Вычислите мак-
симальное количество десятичных цифр в нашем числе.*}
Прежде чем рассмотреть процедуру ввода, приведем пример.
Пусть в файле записано число 23851674 и основанием (Osn) яв- ляется 1000 (храним по три цифры в элементе массива А). Из- менение значений элементов массива А в процессе ввода (по- символьного — переменная сh) отражено в таблице.
А[0]
3 0
1 1
1 2
2 2
3 3
А[1]
674 0
2 23 238 385 851 516 674
А[2]
851 0
0 0
0 2
23 238 385 851
А[3]
23 0
0 0
0 0
0 0
2 23
-
2 3
8 5
1 6
7 4
Примечание
Конечное состояние
Начальное состояние
1-й шаг
2-й шаг
3-й шаг
4-й шаг
5-й шаг
6-й шаг
7-й шаг
Итак, в А[0] храним количество задействованных (ненуле- вых) элементов массива А — это уже очевидно. И при обработ- ке каждой очередной цифры входного числа старшая цифра элемента массива с номером i становится младшей цифрой чис- ла в элементе i+1, а вводимая цифра будет младшей цифрой числа из А[1].
Примечание (методическое)
Можно ограничиться этим объяснением и разработку процедуры вынести на самостоятельное задание. Можно продолжить объясне- ние. Например, выписать фрагмент текста процедуры переноса старшей цифры из A[i] в младшую
A[i+1], т. е. сдвиг уже введенной части на одну позицию вправо:
For i:=A[0]
1 Do Begin
A[i+1]
+ (LongInt (A[i] ) *10) Div Osn;
A[i] : = (LongInt (A[i] ) *10) Mod Osn;
End;

1. Арифметика многоразрядных целых чисел
11
Пусть мы вводим число 23851674 и первые 6 цифр уже раз- местили «задом наперед» в массиве А. В символьную перемен- ную ch считали очередную цифру многоразрядного числа — это
«7». По нашему алгоритму эта цифра «7» должна быть разме- щена младшей цифрой в А[1]. Выписанный фрагмент програм- мы освобождает место для этой цифры. В таблице отражены ре- зультаты работы этого фрагмента.
i
2 2
1
А[1]
516 516 160
А[2]
238 380 385
А[3]
0 2
2
ch
7
После этого остается только добавить текущую цифру к
Л[1] и изменить значение А[0].
В конечном итоге процедура должна иметь следующий вид:
Procedure
Var
Begin
FillChar
,0) ;
Repeat
Read (ch) ;
Until ch In
не цифр
в начале файла. *}
While ch In
Do Begin
For i:=A[0]
1 Do
старшей цифры в числе из A[i] в младшую
цифру числа из A[i+1]. *}
Div
A[i] := (LongInt (A[i] ) *10) Mod Osn;
End;
A[l]
младшую
цифру к числу
А[1] . *}
If А[А[0] +1]>0 Then
*Изменяем
число задействованных элементов массива А. *}
Read (ch);
End;
End;
Вторая задача. Вывод многоразрядного числа в файл или на экран. Казалось бы, нет проблем — выводи число за числом.
Однако в силу выбранного нами представления числа необходи- мо всегда помнить, что в каждом элементе массива хранится не последовательность цифр числа, а значение числа, записанного

12 1. Арифметика многоразрядных целых чисел этими цифрами. Пусть в элементах массива хранятся четырех- значные числа. И есть число, например, 128400583274. При выводе нам необходимо вывести не 58, а 0058, иначе будет по- теря цифр. Итак, нули также необходимо выводить. Процедура вывода имеет вид:
Procedure
;
Var
i: Integer;
Begin
Div
старшие цифры числа.
For
1 Do Begin
Str(A[i],s) ;
While Length (s)
незначащими нулями. *}
Write (s) ;
End;
WriteLn;
End;
Третья задача. Предварительная работа по описанию спо- соба хранения, вводу и выводу многоразрядных чисел выполне- на. У нас есть все необходимые «кирпичики», например, для написания программы сложения двух положительных чисел.
Исходные числа и результат храним в файлах. Назовем проце- дуру сложения
Тогда программа ввода двух чи- сел и вывода результата их сложения будет иметь следующий вид:
Var
TLong;
Begin
Reset (Input);
ReadLong (A) ;ReadLong (B) ;
Close (Input);
SumLongTwo (A,B,C);
Assign
Rewrite (Output);
Close (Output) ;
End.
Трудно ли объяснить процедуру сложения? Используя про- стой пример — нет.
B=3475912100517461.

1. Арифметика многоразрядных целых чисел
13
i
1 2
3 4
A[i]
9451 1302 0
B[i]
7461 51 9121 3475
С[1]
6912 6912 6912 6912
С[2]
1 1354 1354 1354
С[3]
0 0
7827
С[4]
0 0
1 3476
Результат — С=3476782713546912. Алгоритм имитирует привычное сложение столбиком, начиная с младших разрядов.
И именно для простоты реализации арифметических операций над многоразрядными числами используется машинное пред- ставление «задом наперед». Ниже приведен текст процедуры сложения двух чисел.
Procedure
C:TLong) ;
Var
Begin
FillChar
(C) , 0) ;
If A[0]>B[0] Then
Else
For
к Do Begin
Div
C[i]:=(C[i]+A[i]+B[i]) Mod Osn; {*Есть ли в этих
опера торах
End;
If
Then
Else C[0]:=k+1;
End;
Четвертая задача. Реализация операций сравнения чисел
А<В, А>В, А=<В, А>=В).
Функция А=В имеет вид.
Function
Var
Begin
Eq:=False;
If
Then Begin
i : =1 ;
While
And
Do Inc(i);
Eq:=(i=A[0]+l) ;
End;
End;
Реализация функции А>В также прозрачна.
Function More
TLong): Boolean;
Var
Begin
If A[0]

14 1. Арифметика многоразрядных целых чисел
Else If A[0]>B[0] Then More:=True
Else Begin
i:=A[0];
While (i>0) And (A[i]=B[i])
If i=0 Then
Else If
Then
Else
End;
End;
Остальные функции реализуются через функции и More.
Function
Begin
Or Eq(A,B));
End;
Function More_Eq (A,B: TLong): Boolean;
Begin
Or Eq(A,B);
End;
И наконец, последняя функция А=<В.
Function
Begin
End;
Для самостоятельного решения может быть предложена сле- дующая более сложная задача. Требуется разработать функ- цию, которая выдает 0, если больше В, 1, если меньше В и
2 при равенстве чисел. Но сравнение должно быть выполнено с учетом сдвига. О чем идет речь? Поясним на примере. Пусть А
равно 56784, а B — 634. При сдвиге на 2 позиции влево числа
В функция должна сказать, что В больше А, без сдвига — что А
больше В. Или А равно 567000, а Б — 567 и сдвиг равен 3, то функция должна «сказать», что числа равны. Решение может иметь следующий вид.
Function
А, В: TLong; sdvig: Integer):
Byte;
Var i: Integer;
Begin
If A[0]>(B[0]+sdvig) Then
Else If A[0]< (B[0]+sdvig) Then More:=1
Else Begin

1. Арифметика многоразрядных целых чисел
While (i>sdvig) And (A [i] =B [i-sdvig] ) Do
Dec (i) ;
If i=sdvig Then Begin
чисел с учетом сдвига. *}
For i : = 1
sdvig Do If A[i]>0 Then Exit;
"хвост" числа А
равен нулю.*}
End
Else
End;
End;
Пятая задача. Умножение многоразрядного числа на ко- роткое. Под коротким понимается целое число, не превосходя- щее основание системы счисления. Процедура очень похожа на процедуру сложения двух чисел.
Procedure
A: TLong;Const К:
С: TLong);
Var i:
- значение переменной
С.*}
Begin
FillChar(C,
0);
If K=0 Then Inc(C[0]){*Умножение на ноль.*}
Else Begin
For i:=1 To A[0] Do Begin
C[i+1]:=(LongInt (A[i]
) DivOsn;
Mod Osn;
End;
If C[A[0]+1]>0 Then C[0]:=A[0]+1
Else
длину
End;
End;
В качестве самостоятельной работы можно предложить раз- работку процедуры умножения двух чисел, возможный вари- ант текста которой приведен ниже.
Procedure
А,В: TLong; Var С: TLong);
на "длинное".*}
Var i, j : Word;
dv: Longlnt;
Begin
0) ;
For
To A[0] Do

16 1.
многоразрядных целых чисел
For
B[0] Do Begin
dv:=LongInt (A[i])*B[j]+C[i+j-1];
Div Osn);
Mod Osn;
End;
C[0] :=A[0]+B[0] ;
While (C[0]>1) And (C[C[0]]=0)
End;
Шестая задача. Вычитание двух многоразрядных чисел, с учетом сдвига. Если суть сдвига пока не понятна, то оставьте ее в покое, на самом деле вычитание с учетом сдвига потребуется при реализации операции деления. Выясните логику работы процедуры при нулевом сдвиге.
Введем ограничение: число, из которого вычитают, больше числа, которое вычитается. Работать с длинными отрицатель- ными числами мы не умеем. Процедура была бы похожа на процедуры сложения и умножения, если бы не одно «но» — не перенос единицы в старший разряд, а «заимствование единицы из старшего разряда». Например, в обычной системе счисления мы вычитаем 9 из 11 — идет заимствование 1 из разряда десят- ков, а если из 10000 той же 9 — процесс заимствования неско- лько сложнее.
Procedure Sub (Var A:
TLong;
Integer);
Var i , j :
*Из А вычитаем В с учетом
сдвига sp, результат вычитания в А.*}
Begin
For i : = 1
B[0] Do Begin Dec (A[i+sp], B[i]) ;
{*Реализация сложного заимствования*} {*}
j:=i; {*}
While (A[j+sp]<0) And
Do Begin
Osn); Dec(A[j+sp+1] ); Inc(j) ; {*}
End; {*}
End;
i:A[0];
While (i>1) And (A[i]=0) Do Dec (i) ;
A[0]
(*Корректировка длины результата
операции*)
End;
Если строки, отмеченные заменить на нижеприведенные операторы:
{*Реализация простого заимствования*}

1. Арифметика многоразрядных целых чисел 17
If A[i+sp]<0 Then Begin
(A[i+sp], Osn);
Dec (A[i+sp+1]);End;
то,
понятным причинам, логика не будет работать при всех исходных данных. Можно сознательно сделать ошибку и пред- ложить найти ее — принцип «обучение через ошибку».
Рекомендуется выполнить трассировку работы данной про- цедуры, например, для следующих исходных данных. Число А
равно 100000001000000000000, число В — 2000073859998.
Седьмая задача. Деление двух многоразрядных чисел, т. е.
нахождение целой части частного и остатка. Написать исход- ную (без уточнений) часть логики не составляет труда. Это:
Procedure
Var Res,
Ost: TLong);
Begin
FillChar(Res,
0); Res[0]:=1;
FillChar (Ost,
0) ;
Case More (A, B,0) Of
MakeDel (A,B,Res,Ost); {*A больше В, пока
не знаем, как выполнять операцию, -
"выносим" в процедуру. *}
{ *A меньше В. *}
{*А равно В. *}
End;
End;
А дальше? Дальше начинаются проблемы. Делить столби- ком нас научили в школе. Например:
Что мы делали? На каждом этапе в уме подбирали цифру (1,
3, 5 и т. д.), такую, что произведение этой цифры на делитель дает число меньшее, но наиболее близкое к числу.... Какому?
Это трудно сказать словами, но из примера ясно. Зачем нам это делать в уме? Пусть делает компьютер. Однако упростим при-

18 1. Арифметика многоразрядных целых чисел мер, оставим его для тестирования логики, тем более что и числа длинные. Пусть число будет меньше B*10,
тогда в результате (целая часть деления) будет одна цифра. На- пример, А равно 564, а В — 63 и простая десятичная система счисления. Попробуем подобрать цифру результата, но не мето- дом прямого перебора, а методом деления отрезков пополам.
Пусть Down — нижняя граница интервала изменения подбира- емой цифры, Up — верхняя граница интервала, Ost равен дели- мому.
Down
0 5
7 8
8
Up
10 10 10 10 9
315 441 504 567 504
C
C>Ost
Итак, результат — целая часть частного равна (Up+Down)
Div 2, остаток от деления — разность между значениями Ost и
С. Нижнюю границу (Down) изменяем, если результат (С) мень- ше остатка, верхнюю (Up), если больше. Усложним пример.
Пусть равно 27856, а В — 354. Основанием системы счисле- ния является не 10, а 10000.
Down
0 0
0 0
0 0
0 78 78 78 78 78 78 78 10000 5000 2500 625 312 156 156 117 97 87 82 80 79
С
1770000 885000 442500 221250 55224 41418 34338 30798 29028 28320 27966 27612
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
C>Ost
Целая часть частного равна 78, остаток от деления — 27856
минус 27612, т. е. 244.
Пора приводить процедуру. Используемые «кирпичики»:
функция сравнения чисел (More) с учетом сдвига и умножения многоразрядного числа на короткое (Mul) описаны выше.

1. Арифметика многоразрядных целых чисел 19
Function FindBin (Var Ost:
Const
TLong;
sp: Integer) : LongInt;
Var Down, Up: Word;
C: TLong;
Begin
{*Основание системы счисления.*}
While Up-1>Down Do Begin {*У преподавателя есть
возможность сделать сознательную ошибку. Изменить
условие цикла на
Результат
зацикливание
программы. *}
(B,(Up+Down) Div
С);
Case More (Ost, C, sp) Of
0: Down:=(Down+Up) Div 2;
1: Up:= (Up+Down) Div
2: Begin Up:=(Up+Down) Div 2;
End;
End;
End;
(B, (Up+Down) Div
C) ;
If
=0 Then Sub (Ost, C, sp)
{*Находим остаток от деления.
Else begin
End;
Div
часть частного.*}
End;
Осталось разобраться со сдвигом — значением переменной
sp в нашем изложении. Опять вернемся к обычной системе счисления и попытаемся разделить, например, 635 на 15. Что мы делаем? Вначале делим 63 на 15 и формируем, подбираем в уме, первую цифру результата. Подбирать с помощью компью- тера мы научились. Подобрали — это цифра 4, и это старшая цифра результата. Изменим остаток. Если вначале он был 635,
то сейчас стал 35. Вычитать с учетом сдвига мы умеем. Опять подбираем цифру. Вторую цифру результата. Это цифра 2 и остаток 5. Итак, результат (целая часть) 42, остаток от деления
5. А что изменится, если основанием будет не 10, а 10000? Ло- гика совпадает, только в уме считать несколько труднее, но ведь у нас же есть молоток под компьютер — пусть он вбивает гвозди.
Procedure
А,В:
Res, Ost:
TLong) ;
Var sp: Integer;
Begin
значение остатка. *}

20 1. Арифметика многоразрядных целых чисел
If
Then
B*0sn>A,
в результате одна цифра.*}
Res[0]:=sp+1;
While
Do
очередную цифру
End;
End;
Примечание
В результате работы по данной теме каждый учащийся обязан иметь собственный модуль для работы с многоразрядными числа- ми, который должен содержать следующий (примерный) перечень функций и процедур (описательная часть). Курсивом выделены процедуры и функции, не рассмотренные в данной главе.
F u n c t i o n
А, В: TLong): B o o l e a n ;
F u n c t i o n
A, B: TLong): B o o l e a n ;
F u n c t i o n
A, B: TLong): B o o l e a n ;
F u n c t i o n
A, B: T L o n g ) : B o o l e a n ;
F u n c t i o n
A, B: TLong): B o o l e a n ;
Function LongTurnShort (Const
TLong; Var K:
LongInt): Boolean;
многоразрядного числа в число типа LongInt.*}
Function
TLong; Const K:
Word): Word;
от деления многоразрядного числа на короткое типа Word.*}
Function
(Const A: TLong): Longlnt;
{*Подсчет числа десятичных цифр в многоразрядном
Procedure
A: TLong; К: Word; Var В:
TLong); {*Умножение многоразрядного числа на короткое типа Word.*}
Procedure
A, B: TLong; Var C: TLong);
Procedure
A, B: TLong; Var C:
TLong);
Procedure
A: TLong;
B:
Procedure
(K: LongInt; Var A: TLong);
числа типа LongInt в многоразрядное
Procedure
A: TLong; Const K:
Word; Var B: TLong); {*Целочисленное деление многоразрядного числа на короткое типа Word.*}

1. Арифметика многоразрядных целых чисел
21
Procedure
А, В: TLong; Var С,
ost: TLong);
Procedure
A: TLong; Const p: Word);
{*Сдвиг влево на р длинных цифр.*}
1.2. Задачи
1. Для представления многоразрядных чисел использовался одномерный массив. Каждая цифра числа (или группа цифр)
хранилась в отдельном элементе массива. Рассмотреть пред- ставление многоразрядных чисел в виде двусвязного списка.
Каждая цифра числа — элемент списка. Так, число 25974 име- ет следующее представление. Число хранится «задом наперед».
Такое представление удобно при выполнении арифметических операций, а для вывода у нас есть адрес предшествующего эле- мента. Элемент списка можно описать следующим образом:
Const
системы счисления. *}
elem=Record
End;
Var head, tail :pt;
Разработать программы выполнения основных арифметиче- ских операций при таком способе хранения многоразрядных чисел.
2. Написать программу вычисления при пири
3. Написать программу вычисления при
4. Написать программу извлечения квадратного корня из многоразрядного числа.
Указание. Пусть требуется найти целую часть результата.
Возможна следующая схема решения задачи [9].