Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
Шаг Многоразрядное число разбивается на несколько пар (граней) чисел. Если число содержит четное количество разря- дов, тогда первая грань содержит две цифры, если нечетное, то одну. Так, число 236488 разбивается на три грани, каждая из которых содержит две цифры: 23 64 88, а для числа 15385 пер- вая грань состоит из одной цифры 1. Число граней определяет 22 1. Арифметика многоразрядных целых чисел количество разрядов ответа. В качестве примера возьмем число 574564 и разобьем его на грани: 57 45 64. Таким образом, отве- том является трехразрядное число (обозначим через у). Шаг 2. Рассматривается первая грань 57 и подбирается чис- ло х такое, чтобы х 2 было как можно ближе к 57, но не превос- ходило его. Таким образом, х—7, так как а Первая цифра ответа у равна 7. Шаг 3. Находится разность между первой гранью 57 и 57-49=8. Эта разность приписывается к следующей гра- ни, получается число 845. Шаг 4. Подбирается следующая цифра. Находится новое значение х, такое, чтобы не превосходило 845 и было наиболее близким к 845. Это число 5, так как (14*10+5)*5=725<845, а (14*10+6)*6=876>845. Итак, вторая цифра ответа 5 и y=75. Шаг 5. Повторятся шаг 3. Находим разность: 845-725=120, её «подклеим» к следующей грани — 12064. Шаг 6. Выполняются действия шага 4. Значение х равно 8, так как Итак, Пояснений требует шаг 4, а именно, не понятно, почему ис- пользуется такая формула для подбора очередной цифры отве- та. Пусть Возведём в квадрат числа Полу- чим Значение у подобрано на шаге 2, оно дает вклад в число z. Подбор цифры х обя- зан дать максимальный вклад в число Примечание Если корень не извлекается в результате повторения шагов 3, 4, то после последней цифры заданного числа ставят запятую и образу- ют дальнейшие грани, каждая из которых имеет вид 00. В этом случае процесс извлечения корня прекращается при достижении требуемой точности. 5. Определить, встречаются ли в записи некоторого разрядного числа две подряд идущие цифры, например 9? 6. Определить наибольший общий делитель двух многораз- рядных чисел. 7. Определить наименьшее общее кратное двух многоразряд- ных чисел. 8. Определить, являются ли два многоразрядных числа вза- имно простыми. 9. Найти количество делителей многоразрядного числа. 10. Написать программу проверки того, что число является совершенным, т. е. равным сумме своих делителей, кроме самого себя. 1. Арифметика многоразрядных целых чисел 23 11. Написать программу перевода многоразрядного числа в системы счисления с основаниями 2, 8, 16. 12. Написать программу разложения многоразрядного числа на простые множители. 13. Известно, что целочисленное деление (умножение) на 2 равносильно сдвигу числа на один разряд вправо (влево). Два обычных числа а и b можно сложить с помощью следующего алгоритма: • если а и b четные числа, то • если а и b нечетные числа, то • если а — четное, а b — нечетное, то • если а — нечетное, а b — четное, то Заметим, что при нечетном значении для целочисленного деления Приведенная логика выполнения операции сложения реализуется с помощью следующей рекурсивной функции: Function Sum Integer) : Integer; Begin If x=0 Then Else If y=0 Then Else If (x Mod 2 =0) And (y Mod 2=0) Then Div 2, у Div Else If (x Mod 2 =1) And (y Mod Then Sum:=Sum(x Div Div 2+1)*2 Else Div Div Написать аналогичную процедуру сложения (не обязательно рекурсивную) двух многоразрядных целых чисел а и b. Деле- ние и умножение на 2 заменить соответствующими операциями сдвига на один разряд. 14. Два числа а и b можно перемножить, используя только сдвиги на один разряд и операцию сложения. Например, Выпишем следующий столбик чисел: 125*37 250*18+125 24 1. Арифметика многоразрядных целых чисел 500*9+125 1000*4+500+125 2000*2+500+125 4000*1+500+125. И результат: 125*37=125+500+4000=4625 (в каких случаях изменяемое число b входит в сумму?). Он основан на следую- щих тождествах: • если а четное число, то • если а нечетное число, то Эта логика реализуется с помощью следующей рекурсивной функции: Function ; предполагается, что результат не выходит за пределы Integer.*} Begin If х=0 Then Else If x Mod 2=0 Then (x Div Else Div 2,y) *2+y; End; Написать аналогичную процедуру умножения (не обязатель- но рекурсивную) двух многоразрядных целых чисел а и b. Де- ление и умножение на 2 заменить соответствующими операци- ями сдвига на один разряд. 15. Напишите программу сложения двух знаковых разрядных чисел [2]. Указание. Необходимо заменить отрицательное число numb на его дополнение до числа 10*, то есть на число Алгоритм получения дополнительного кода отри- цательного числа известен [2, 23]. Находят обратный код деся- тичного числа путем замены каждой цифры i на 9-i. Прибавле- ние единицы к обратному коду дает дополнительный код. После замены отрицательных слагаемых на их дополнитель- ный код работает логика сложения многоразрядных чисел, рас- смотренная в 1.1. 2. Комбинаторные алгоритмы Одна из главных целей изучения темы, помимо традицион- ных, заключается в том, чтобы учащиеся осознали суть «отно- шения порядка» на некотором множестве объектов. На множе- стве объектов типа Word, Integer, Char, Boolean отношение порядка воспринимается как нечто очевидное. Объяснить, что на типе Real его нет, гораздо сложнее. Однако осознание того факта, что компьютер, в принципе, что-то может делать с ка- ким-то множеством объектов только в том случае (по крайней мере, перебрать их все), если на этом множестве введено ка- кое-то отношение порядка, требует длительной работы. А выра- ботка автоматических навыков «вычленения» отношения по- рядка на множестве данных конкретной задачи — работа многих дней. 2.1. Классические задачи комбинаторики При решении практических задач часто приходится выби- рать из некоторого конечного множества объектов подмножест- во элементов, обладающих теми или иными свойствами, разме- щать элементы множеств в определенном порядке и т. д. Эти задачи принято называть комбинаторными задачами. Многие из комбинаторных задач решаются с помощью двух основных правил — суммы и произведения. Если удается раз- бить множество объектов на классы и каждый объект входит в один и только один класс, то общее число объектов равно сум- ме числа объектов во всех классах (правило сложения). Прави- ло умножения чуть сложнее. Даны два произвольных конеч- ных множества объектов А и В. Количество объектов в А равно N, в В — М. Составляются упорядоченные пары где (а принадлежит А) и Количество таких пар (объектов) равно N*M. Правило обобщается и на большее количество множеств объектов. Перестановки (обозначение — число перестановок). Классической задачей комбинаторики является задача о числе перестановок — сколькими способами можно переставить N различных предметов, расположенных на N различных местах. 26 2. Комбинаторные алгоритмы Объяснение примеров 1. Сколькими способами можно переставить три монеты 1,2,5 рублей, расположенных соответственно на трех местах с но- мерами 1, 2, 3? Ответ: 6. 2. Сколькими способами можно пересадить четырех гостей А, Б, В, Г, сидящих соответственно на четырех местах 1, 2, 3, 4? Ответ: 24. 3. Сколькими способами можно переставить буквы в слове эс- киз? Ответ: 120. 4. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга? От- вет: 40320. N различных предметов, расположенных на N различных местах, можно переставить N! способами Отвлекаясь от природы объектов, можно считать их для простоты натуральными числами от 1 до N. При этой трактов- ке понятие перестановки можно дать следующим образом. Пе- рестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Места также нумеруются от 1 до N. Тогда перестановку можно записать таблицей с двумя строками, из которых каждая содержит все числа от 1 до N. Например, Перестановку называют тождественной. Под суперпо- зицией перестановок и G понимают перестановку FG, опреде- ляемую следующим образом: Так, если F сов- падает с приведенной выше перестановкой, а то По переста- новке F однозначно определяется перестановка F -1 , такая, что Так, для нашего примера Каж- дую перестановку можно представить графически в виде ориен- тированного графа с множеством вершин от 1 до N. Для пере- становки соответствующий ориентирован- 2. Комбинаторные алгоритмы 27 ный граф изображен на рисунке. Графическая иллюстрация об- легчает введение понятия цикла перестановки. Видим, что пере- становка представима двумя циклами: 3], [2, 5, 4, 6]. Пару i ,f>, i f i >f j .. Число инверсий (I) определяет знак перестановки (-1) I Для нашего примера число инверсий равно 6, а знак переста- новки положительный. Произвольную перестановку, являю- щуюся циклом длины 2, обычно называют транспозицией. Размещения (обозначение — ). Задача формулируется следующим образом: сколькими способами можно выбрать и разместить по М различным местам М из N различных предме- тов? Объяснение примеров 1. Сколькими способами можно выбрать и разместить на двух местах 1, 2 две из трех монет 2, 5 рублей? Ответ: 6. 2. Сколькими способами можно выбрать и разместить на двух местах 1, 2 двух из четырех гостей А, Б, В, Г? Ответ: 12. 3. Сколько трехбуквенных словосочетаний можно составить из букв слова эскиз? Ответ: 60. 4. В чемпионате но футболу принимают участие 17 команд и разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами они могут быть распределены? Ответ: 4080. 5. Партия состоит из 25 человек. Требуется выбрать председа- теля партии, его заместителя, секретаря и казначея. Сколь- кими способами можно это сделать, если каждый член пар- тии может занимать лишь один пост. Ответ: 303600. Число размещений вычисляется по формуле Сочетания (выборки) — обозначение Другой классиче- ской задачей комбинаторики является задача о числе выборок: сколькими способами можно выбрать М из N различных пред- метов? Объяснение примеров 1. Сколькими способами можно выбрать две из трех монет 1,2, 5 рублей? Ответ: 3. 2. Сколькими способами можно выбрать двух из четырех гос- тей А, Б, В, Г? Ответ: 6. 28 2. Комбинаторные алгоритмы 3. Сколькими способами можно выбрать три из пяти букв сло- ва Ответ: 10. 4. В чемпионате по футболу России принимают участие 17 команд и разыгрываются золотые, серебряные и бронзовые медали. Нас не интересует порядок, в котором располагаются команды-победительницы, ибо все они выходят на Европей- ские турниры. Сколько различных способов представления нашего государства на Европейских турнирах? Ответ: 680. 5. Партия состоит из 25 человек. Требуется выбрать председа- теля партии и его заместителя, ибо они представляют пар- тию в президиуме межпартийных форумов. Сколькими спо- собами можно это сделать, если каждый член партии может занимать лишь один пост? Ответ: 300. 6. Сколькими способами можно поставить на шахматной доске 8 ладей (условие о том, что ладьи не могут бить друг друга, снимается)? Ответ: 4328284968. 7. Сколько различных прямоугольников можно вырезать из клеток доски размером N*M (стороны прямоугольников проходят по границам клеток)? Пояснение. Горизонтальные стороны могут занимать любое из положений. Число способов их выбора — , аналогично для вертикальных сторон. Ответ: Сочетание можно определить и как подмножество из М раз- личных натуральных чисел, принадлежащих множеству чисел из интервала от 1 до N. Число сочетаний вычисляется по фор- муле Полезные формулы: (правило симметрии) (правило Паскаля) . Эта формула является следствием известного соотношения под названием бином Ньютона: При х=у=1 бином Ньютона дает при- веденную формулу. Размещения с повторениями (обозначение — ). Даны предметы, относящиеся к N различным типам. Из них состав- 2. Комбинаторные алгоритмы 29 всевозможные расстановки длины k. При этом в расста- новки могут входить и предметы одного типа. Две расстановки считаются различными, если они отличаются или типом входя- щих в них предметов, или порядком этих предметов. Объяснение примеров 1. Найти общее количество шестизначных чисел. Ответ: 9*10*10*10*10*10=900000. 2. Найти число буквосочетаний длины 4, составленных из 33 букв русского алфавита, и таких, что любые две соседние буквы этих буквосочетаний различны. Ответ: 33*32*32*32=1081344. 3. Ячейка памяти компьютера состоит из 16 бит (k). В каждом бите, как известно, можно записать 1 или 0 (N). Сколько различных комбинаций 1 и 0 может быть записано в ячей- ке? Ответ: Общая для подсчета числа размещений с повторе- ниями — Перестановки с повторениями. Выше рассмотрены переста- новки из различных предметов. В том случае, когда некоторые переставляемые предметы одинаковы, часть перестановок сов- падает друг с другом. Перестановок становится меньше. Задача формулируется следующим образом. Имеются предметы k раз- личных типов. Сколько перестановок можно сделать из предметов первого типа, — второго, ..., — k-гo типа Объяснение примеров 1. Сколько различных буквосочетаний можно получить из букв слова папа? Ответ: 6 (папа, паап, ппаа, апап, аапп, аппа). 2. Сколько различных буквосочетаний можно получить из букв слова Ответ: 180. 3. Сколькими способами можно расположить в ряд 2 одинако- вых яблока и 3 одинаковые груши? Ответ: 10. 4. Сколько различных сообщений можно закодировать, меняя порядок 6 флажков: 2 красных, 3 синих и 1 зеленый? Ответ: 60. 5. Для выполнения работы необходимо в некотором порядке выполнить дважды каждое из трех действий (а, Ъ, с). Напри- мер: ааbbсс, Сколько существует различных спосо- бов выполнения работы? Ответ: 90. 30 2. Комбинаторные алгоритмы Общая формула для подсчета перестановок с повторениями имеет вид: где N = — общее число элементов. Она следует из Сочетания с повторениями. Имеются предметы N различ- ных типов. Сколько существует расстановок длины k, если не различать порядок предметов в расстановке (различные расста- новки должны отличаться хотя бы одним предметом)? Схема рассуждений. Пусть N=4. и k=7. Закодируем расста- новку с помощью последовательности из нулей и единиц. Запи- шем столько единиц, сколько предметов первого типа, затем нуль, а затем столько единиц, сколько предметов второго типа, и т. д. (нуль, единицы, соответствующие предметам третьего типа, нуль и единицы для предметов четвертого типа). Суммар- ное количество единиц в последовательности равно 7, количе- ство нулей — N-1 или 3, т. е. длина равна 10. Количество та- ких последовательностей определяется количеством способов записи 3 нулей на 10 мест, или Общая формула для подсчета числа сочетаний с повторения- ми имеет вид Объяснение примеров 1. Четверо ребят собрали в лесу 30 белых грибов. Сколькими способами они могут разделить их между собой? Ответ: 2. Сколькими способами можно выбрать 3 рыбины из трех оди- наковых щук и трех одинаковых окуней? Ответ: 4 (N=2, 3. Сколькими способами можно выбрать 13 из 52 игральных карт, различая их только по масти? Ответ: 560 4. Сколько всего существует результатов опыта, заключающе- гося в подбрасывании 2 одинаковых игральных костей (если кости различные, то 36)? Ответ: 21 (N=6, k=2). 5. Сколько существует целочисленных решений уравнения Ответ: 120 пример решения — 1101101101). Разбиения. Требуется подсчитать число разбиений конечно- го множества предметов S, где |S|=N (количество предметов), на k различных подмножеств попарно не пересе- кающихся, 2. Комбинаторные алгоритмы 31 Схема рассуждений. можно сформировать способами, способами, ... способами. Таким об- разом, число разбиений равно или Объяснение примеров 1. Сколькими способами можно разбить три монеты 1,2,5 руб- лей на три группы по одной монете? Ответ: 6. 2. Сколькими способами можно разбить четырех гостей А, Б, В, Г на две группы? Ответ: 6. 3. Сколькими способами можно разбить пять букв слова эскиз три группы так, чтобы в первой группе одна буква, а во второй и третьей по 2? Ответ: 4. Сколькими способами можно расселить 8 студентов по трем комнатам: одноместной, трехместной и четырехместной? Ответ: б. Сколькими способами можно раскрасить в красный, зеле- ный и синий цвет по 2 из 6 различных предметов? Ответ: Число Стирлинга второго рода определяется как чис- ло разбиений N-элементного множества на k подмножеств. Так, . Считается, что Если , то При В общем случае справедлива формула для 2.2 Генерация комбинаторных объектов 2.2.1. Перестановки Первая задача. Научимся вычислять число перестановок для заданного значения N. Известно, что число перестановок равно факториалу числа Рекурсивное опре- деление: 1 2 3 4 5 6 1 2 6 24 120 720 32 2. Комбинаторные алгоритмы 7 8 9 10 11 12 13 30 5040 число типа Integer) 40320 362880 3628800 39916800 число типа Longlnt) 6227020800 265252859812191058636308480000000 Функция имеет ограниченную область применения. Function Fac Var r,i: LongLnt; Begin For i:=l к Do r:=r*i; End; Функция работоспособна при N, меньшем или равном 12. Для больших значений N требуется использовать «длинную» арифметику: умножение «длинного» числа на короткое; вывод «длинного» числа (глава 1). |