По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
УДК 519.85(023) ББК 22.18 052 Работа выполнена при поддержке Министерства образования Российской Федерации, проект Г00—4.1-60. Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. — 341 с: ил. ISBN 5-94774-010-9 Искусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. Практические рекомендации по тестированию программ являются не- обходимым дополнением курса. Предназначен для школьников, студентов и специалистов, серьез- но изучающих программирование, а также для преподавателей учеб- ных заведений. УДК 519.85(023) ББК 22.18 По вопросам приобретения обращаться в Москве: «БИНОМ. Лаборатория знаний» (095)955-03-98, e-mail: lbz@aha.ru в Санкт-Петербурге: «Диалект» (812)247-93-01, e-mail: dialect@sndlct.ioffe.rssi.ru © Окулов С. М., 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, за что автор благодарит его и желает дальнейших творческих успехов в деле обучения санктпетер- бургских студентов. Многие годы главный редактор газеты «Информатика» Сергей Львович Островский поддерживал ав- тора в его работе, и признательность за это остается неизмен- ной. Об ошибках. Учебники такого плана не могут не содержать ошибок. Для многих алгоритмов можно, естественно, найти другие схемы реализации. Автор с признательностью примет все замечания. Присылайте их, пожалуйста, по адресу okulov@vspu.kirov.ru. Арифметика многоразрядных целых чисел Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позво- ляют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например 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]. |