Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
5. Из доски 9 × 9 вырезан угловой квадрат. Можно ли уложить эту доску прямоугольниками 1 × 5? 6. В коробке 235 спичек. Два игрока берут их по очереди. За один ход можно взять от 1 до 6 спичек. Выигрывает игрок, взявший последнюю спичку. Кто выигрывает при правиль- ной игре? 62 7. Из доски 8 × 8 вырезан угловой квадрат. Можно ли уложить доску прямоугольниками 1 × 3? 8. Из 30 спичек двое игроков берут по своему усмотрению от 1 до 6 спичек. Выигрывает тот, кто берет последнюю спичку. Разработать алгоритм игры первого игрока. 9. Имеется три кучи камней. Состоянием назовем тройку чисел (x 1 , x 2 , x 3 ), где x i — число камней в i-й куче. Ходом является операция переноса из кучи в кучу числа камней, равного числу камней в той куче, куда осуществляется перенос. Из исходного состояния (11, 7, 6) получить состояние (8, 8, 8). 10. Четырьмя прямыми разбить круг на максимальное количе- ство частей. 11. Двумя прямыми линиями разрезать греческий крест так, чтобы из получившихся частей сложить прямоугольник, од- на сторона которого в два раза больше другой. 12. Имеется 12-литровый запас жидкости и пустые сосуды в 9 и 5 л. Требуется отмерить в точности 6 л. Сколько литров могут быть отмерены такими сосудами из запаса в 12 л? 13. Определить число последовательностей длины n из {0, 1, 2}, в которых отсутствуют две, подряд стоящих единицы. 14. Можно ли покрыть квадрат 10 × 10 фигурами вида 15. Можно ли покрыть квадрат 10 × 10 фигурами вида 63 16. Можно ли покрыть квадрат 8×8 с вырезанной угловой клет- кой фигурами вида 17. Можно ли покрыть фигурами вида шахматную доску 8 × 8, в которой вырезан квадрат: 18. Можно ли уложить шахматную доску с вырезанной угловой клеткой фигурами вида 19. Можно ли совершить переправу четырех пар рыцарь-ору- женосец с помощью двухместной лодки, если оруженосец не может находиться на одном берегу с чужим(и) рыца- рем(ями) в отсутствие своего хозяина? 20. Разработать алгоритм поиска двух наименьших чисел в не- упорядоченной последовательности из n чисел. 21. Из 27 спичек, лежащих на столе, двое играющих поочеред- но берут не менее одной и не более четырех спичек. Выиг- равшим считается тот, у кого по окончании игры окажется четное число спичек. Разработать алгоритм игры первого игрока. 64 22. Два участника игры по очереди называют число от 1 до 10. Называя число, игрок прибавляет его к уже имеющейся сум- ме чисел (называя первое число, игрок прибавляет его к ну- лю). Выигрывает тот из игроков, кто набирает число 100. Разработать алгоритм игры первого игрока. 23. Найти за минимальное число вопросов (возможные ответы: «да», «нет») загаданное 5-значное число, если сумма первых трех цифр равна 17. 24. Найти за минимальное число вопросов (возможные ответы: «да», «нет») загаданное 4-значное число, если сумма второй и четвертой цифры равна 7. 25. Сколькими способами можно разменять 100 р. монетами в 5, 10, 20 и 50 р.? 26. Вычислить рекурсивно число шестизначных чисел, у кото- рых сумма первых четырех цифр равна 26, а сумма послед- них двух равна 14. 27. Вычислить рекурсивно количество разбиений числа 37 пя- тью слагаемыми, первое из которых не превышает 7, второе — 5, а третье и четвертое принимают значения из множества {5, 6, 7, 8}. 28. Вычислить рекурсивно число семизначных чисел, у которых сумма первых четырех чисел равна 21, а сумма последних пяти равна 19. 29. Вычислить рекурсивно количество разбиений числа 27 че- тырьмя слагаемыми, первое из которых не превышает 7, второе — 8, а третье и четвертое принимают значения из множества {3, 5, 7}. 30. Вычислить рекурсивно число пятизначных чисел, у кото- рых сумма первых трех цифр равна 21, а сумма последних равна 12. 65 31. Вычислить рекурсивно число семизначных чисел, у которых сумма первой и третьей цифр равна 12, а сумма остальных пяти равна 19. 32. Вычислить рекурсивно (2n − 2)(2n − 4) × . . . × 2 (n + 1)(n + 3) × . . . × (n + 2n − 1) a n−5 b −(n+3) 33. Вычислить рекурсивно число семизначных чисел, у которых сумма первых четырех цифр равна 17, а сумма последних трех равна 16. 34. Вычислить рекурсивно количество разбиений числа 17 че- тырьмя слагаемыми, первое из которых не превышает 4, вто- рое — 8, а третье и четвертое принимают значения {3, 4, 8}. 35. Вычислить рекурсивно число семизначных чисел, у которых сумма квадратов первых четырех чисел равна 17, а сумма квадратов последних двух равна 16. 36. Вычислить рекурсивно количество разбиений числа 25 че- тырьмя слагаемыми, первое из которых не превышает 8, второе — 3, а третье и четвертое принимают значения из множества {2, 5, 9}. 37. Вычислить рекурсивно число расстановок N ладей на доске N × N таких, что ладьи симметричны относительно обеих диагоналей и не бьют друг друга. 38. Вычислить рекурсивно число двоичных последовательностей из n элементов, в которых отсутствуют две рядом стоящие единицы. 39. Дана решетка N × M : 66 M N A B Вычислить рекурсивно число путей из A в B. Путь — по- следовательность ходов по решетке, ведущих слева направо и снизу вверх. 40. Даны числа a 1 , . . . , a n , стоящие в определенном порядке. Для вычисления произведения a 1 ·. . .·a n при сохранении порядка сомножителей существует множество способов расстановки скобок между сомножителями. Вычислить рекурсивно чис- ло способов расстановки скобок. 41. Вычислить рекурсивно число 8-значных чисел, у которых сумма первых пяти цифр равна 29, а сумма последних трех цифр равна 21. 67 3 . методы анализа алгоритмов 3.1. Классы алгоритмов В предыдущих разделах рассмотрены разные подходы, кото- рые могут быть использованы при построении алгоритмов. Для нахождения решения, для анализа эффективности этого решения можно выдвигать различные предположения, использовать уже известные другие алгоритмы, переформулировать условие зада- чи и т.п. Можно искать некие похожие задачи с уже известным решением и использовать это решение для нахождения алгоритма для требуемой задачи. Однако частных задач, для которых найдены решения, суще- ствует очень много. Еще больше задач нерешенных или решенных с какими-то ограничениями и условиями. Искать похожие задачи среди всего множества задач, оценивать существующие решения по степени их «подходящести» может быть трудной, трудоемкой и не всегда разрешаемой проблемой. Было бы более полезным и про- дуктивным попробовать определить классы задач, объединенных общей проблемой, общими методами и подходами к решению, и затем искать тот класс, к которому можно отнести нашу частную задачу, требующую решения. Конечно, таких классов не должно быть слишком много, но с другой стороны, их и не должно быть слишком мало, чтобы не требовалось для каждой новой задачи определять свой, новый класс, который затем вряд ли будет ис- пользован для решения других задач. В качестве примера задачи, принадлежащей определенному классу, рассмотрим известную задачу об определении фальшивой монеты. Задача 3.1 (задача о фальшивой монете). Имеется n монет, среди которых возможно находится одна фальшивая. Фальшивая монета отличается от остальных по весу, и в нашем распоряжении находятся весы с двумя чашками. Требуется определить фальши- вую монету за минимальное число взвешиваний или установить, что фальшивых монет нет. 68 Решение. Задачу о фальшивой монете решали в подразд. 2.2, но тогда было известно, что фальшивая монета обязательно лег- че. Теперь попробуем решить эту задачу для более общего слу- чая. Любое решение данной задачи (не обязательно оптимальное) можно трактовать как последовательность взвешиваний. Однако ясно, что выбор монет для взвешивания на каком-то шаге зави- сит от того, какие монеты использовались, и результатов взвеши- вания на предыдущих шагах. Будем изображать последователь- ность взвешиваний следующим образом. Перенумеруем монеты и зададим их множеством S = {1, 2, . . . , n}. Множества номеров мо- нет, взвешиваемых на левой и правой чашах весов, можно обозна- чить через S L и S R соответственно. Ясно, что взвешивание имеет смысл, только если мощности множеств S L и S R совпадают, т.е. на каждой чаше весов лежит одинаковое количество монет. Взвеши- вание будем обозначать знаком «:», тогда у каждого взвешивания (S L ) : (S R ) могут быть три возможных исхода. Множество монет S L может быть легче, тяжелее или одинаково по весу с множе- ством S R . Тогда будем обозначать эти исходы взвешивания как «<», «>» или «=», соответственно. Пример взвешиваний для че- тырех монет приведен на рис. 3.1. Овалы обозначают взвешива- ния, квадраты — исходы с указанием номера фальшивой монеты и является ли она более легкой или более тяжелой, чем остальные. Случай отсутствия фальшивой монеты обозначен как «0», пере- черкнутые квадраты соответствуют случаям, которые не могут произойти. Будем оценивать максимальное число взвешиваний, необхо- димое для решения задачи, т.е. худший случай. Как видно из рис. 3.1, решена задача за 3 взвешивания в худшем случае. За- метим, что даже в лучшем случае нам нужно как минимум 2 взвешивания. Можно ли достичь лучшего результата? На рис. 3.1 представлено другое решение задачи о взвешива- нии четырех монет. На первом шаге взвешиваем не пару монет, а все монеты, разбив их на два множества. В результате добились того, что в лучшем случае понадобится всего одно взвешивание, однако в худшем случае число взвешиваний опять равно 3. 69 (1) : (2) (1) : (3) (1) : (4) 0 4 Т 4 Л 3 Т 3 Л (1) : (4) 2 Т 1 Л (1) : (4) 2 Л 1 Т < < < < < = = = > > > > > = = Рис. 3.1. Решение задачи о фальшивой монете Отметим, что в отличие от первого варианта взвешиваний, изображенного на рис. 3.1, во втором варианте не только опре- делили схему взвешивания, но и ввели новое понятие кандидатов в фальшивые монеты. Действительно, рассмотрим результат пер- вого взвешивания, (1, 2) : (3, 4). Пусть (1, 2) < (3, 4) (левая ветвь рисунка). Обозначим множества S L = (1, 2), и S R = (3, 4). Тогда S L < S R . По этому результату нельзя судить, является ли фаль- шивая монета более легкой или более тяжелой, чем все остальные, и в каком множестве она находится. Однако можно предположить (и даже более точно — можно утверждать), что если фальшивая монета принадлежит множеству S L , то фальшивая монета легче остальных, обозначим такое множество с помощью буквы Л. В на- шем случае, если монеты с номерами 1 или 2 фальшивы, то они легче настоящих. Если же фальшивы монеты с номерами 3 или 4, то они тяжелее настоящих, будем обозначать соответствующее множество с помощью буквы Т. На рис. 3.2 легкие и тяжелые кан- дидаты в фальшивые монеты обозначаются с помощью пометок на ребрах дерева. Очевидно, можно ответить на вопрос об оптимальном числе взвешиваний, продолжая перебирать по возможным схемам выбо- ра монет. Так как число монет конечно, то рано или поздно такой перебор может быть завершен. Пока остановимся на полученных двух решениях и попробуем проанализировать, что же они дали 70 (1,2) Л (3,4) Т (1,2) Т (3,4) Л (1,2) : (3,4) (3) : (4) 4 Т 3 Т (1) : (2) 1 Л < < < = = > > > = 0 2 Л (3) : (4) 3 Л 4 Л (1) : (2) 2 Т < < = > > = 1 Т Рис. 3.2. Другое решение задачи о фальшивой монете нам с точки зрения общего подхода к решению задачи. Как известно, любая стратегия взвешивания монет может быть описана с помощью тернарного, или троичного дерева. Другими словами, рассматриваемая задача принадлежит к классу задач, описываемых тернарными деревьями. Подобная классификация задачи дает возможность проводить анализ не каждого конкрет- ного решения, а всех решений в целом, опираясь на известные свойства деревьев. Таким образом, перебор по возможным способам взвешивания фактически является перебором по различным тернарным дере- вьям, которых, конечно, экспоненциально много. С другой сторо- ны, попробуем определить, что вообще возможно достигнуть при решении данной задачи, используя ее принадлежность именно к данному классу. Из рис. 3.1 и 3.2 видно, что, изображая последовательность взвешиваний с помощью дерева, приписываем каждое взвешива- ние вершине дерева, не являющейся листом (изображено с помо- щью овалов), в то время как исходы, в том числе и невозможные, соответствовали листьям дерева (изображено с помощью квадра- тов). Все вершины дерева могут быть упорядочены по уровням, 71 В а < = = > В а И И И < = > В а И И И < = > В а И И И < = > В а И И И < = > В а < = > В а < = > В а < > К В Л У 0 У 1 У l -1 У l …… ……………… ……… … … …… … … … … … …… …… … … Г а = l Рис. 3.3. Т ернарное дерево взвешиваний 72 т.е. по их удаленности от корня дерева. Номер уровня равен чис- лу ребер, которые должны пройти от корня, чтобы попасть в вер- шину данного уровня (рис. 3.3). Если глубина дерева — уровень самого удаленного от корня листа, то эта величина равна числу взвешиваний в худшем случае. Сколько всего возможных исходов в нашей задаче? Каждая из n монет может оказаться фальшивой легкой или фальшивой тяжелой, кроме того, фальшивых монет может не оказаться вовсе. Таким образом, имеем 2n + 1 исходов. Это означает, что в дереве, соответствующем схеме взвешиваний, должно быть не менее, чем 2n + 1 листьев. Троичное дерево глубины l содержит не более, чем 3 l листьев. Отсюда можно оценить минимально возможную глубину дерева 3 l ≥ 2n + 1, и следовательно, l ≥ log 3 (2n + 1). (3.1) Таким образом, при n = 4 минимально возможное число взве- шиваний больше или равно 2. Здесь имеется в виду не минималь- ное число взвешиваний для данной схемы — как на рис. 3.2, а воз- можны случаи, когда решение задачи находится уже после перво- го взвешивания, — оцениваем худший вариант, т.е. максимальное число взвешиваний для данной схемы, другими словами, ищем минимум среди максимальных глубин всех деревьев, имеющих не менее, чем 2n + 1 листьев. Однако можно показать, что не существует способа взвешива- ния, который дал бы равенство в оценке (3.1). Т е о р е м а 3.1 Число взвешиваний в худшем случае для задачи о фальшивой монете оценивается как l > log 3 (2n + 1). Доказательство. Как уже говорили, для n монет возмож- но 2n + 1 исходов. Каждое взвешивание может иметь три воз- можных результата и для каждого результата формируется своя 73 схема дальнейших взвешиваний. При этом схема имеет свое коли- чество возможных исходов, учитывающих результат последнего взвешивания. Пусть при первом взвешивании |S L | = |S R | = k, т.е. используется k монет на одной чаше весов и k монет — на другой, где k ≤ n/2 . Если при этом S L < S R , то монеты из S L объяв- ляем кандидатами в легкие фальшивые монеты, а монеты из S R — кандидатами в тяжелые фальшивые монеты. Таким образом, при этом результате первого взвешивания возможно 2k исходов. Аналогично, при S L > S R возможно 2k других исходов. Следова- тельно, при S L = S R возможны оставшиеся 2n + 1 − 4k исхода. Если в (3.1) выполняется равенство, это значит, что тернарное дерево является полным и все его листья находятся на l-м уровне. Но для этого необходимо, чтобы после каждого взвешивания воз- можные исходы распределялись по трем ветвям равномерно и вы- полнялось равенство 2k = 2n + 1 − 4k, что невозможно, так как 2k является всегда четным числом, а 2n + 1 − 4k всегда нечетно. При доказательстве теоремы 3.1 использовали важную идею: чтобы дерево взвешиваний было оптимальным или, по крайней мере, возможно ближе к оптимальному нужно, чтобы исходы рас- пределялись равномерно по всем результатам каждого взвешива- ния. Итак, получили оценку для худшего числа взвешиваний в за- даче о фальшивой монете, связав эту задачу с классом задач, описываемых тернарными деревьями. Теперь рассмотрим немно- го модифицированную задачу. Задача 3.2 (задача о фальшивой монете при наличии этало- на). Имеется n монет, среди которых возможно находится одна фальшивая, и еще одна монета, про которую точно известно, что она настоящая. Требуется определить фальшивую монету за ми- нимальное число взвешиваний или установить, что фальшивых монет нет. 74 Решение. Данная задача отличается от предыдущей наличи- ем дополнительной эталонной монеты, но оказывается, что эта дополнительная монета позволяет строить оптимальные деревья взвешиваний, для которых в (3.1) выполняется равенство. Обо- значим через n l число, для которого выполняется равенство 3 l = 2n l + 1. (3.2) При рассмотрении предыдущей задачи в теореме 3.1 получи- ли: для выполнения равенства (3.1) нужно, чтобы дерево взвеши- ваний являлось полным. Следовательно, если удастся построить такое оптимальное дерево из l уровней, то оно задаст схему из l взвешиваний для n l монет. Заметим, что справедливо следующее соотношение: n l = 3n l−1 + 1. (3.3) Так как при n 0 = 0 в (3.2) получаем равенство, 3 0 = 2 · 0 + 1, то отсюда с использованием (3.3) можно получить n 1 = 1, n 2 = 4, n 3 = 13 и т.д. Решением (3.2) является последовательность 0, 1, 4, 13, 40, . . .. Таким образом, при выполнении равенства (3.2) множество из n l монет разбивается на три равные части по n l−1 монет и еще остается одна монета. Рассмотрим разные ситуации, которые мо- гут возникать в процессе взвешивания. Схема 1. Пусть в начале взвешивания имеем n i монет, где n i принадлежит последовательности (3.3) для некоторого i. Поло- жим на каждую чашу весов по n i−1 монет, где n i = 3n i−1 + 1, далее добавим на левую чашу весов эталонную монету, а на пра- вую — одну из оставшихся n i−1 + 1 монет. Обозначим взвешивае- мые множества, как и ранее, через S L и S R Теперь пусть в результате взвешивания S L = S R . Так как эта- лонная монета участвовала во взвешивании, очевидно, что фаль- шивая монета, если она есть, находится среди неиспользованных n i−1 монет, и задача сводится к задаче с n i−1 монетами. При этом 75 результате взвешивания у нас остаются возможными 2n i−1 + 1 = 3 i−1 исходов. Теперь, пусть S L < S R . Это означает, что фальши- вая монета находится либо в множестве S L и при этом она легче остальных, либо в множестве S R и тогда она тяжелее остальных. При этом есть n i−1 подозрительных легких монет и n i−1 + 1 по- дозрительных тяжелых и вместе это снова дает 2n i−1 + 1 = 3 i−1 возможных исходов. Наконец, пусть S L > S R . Тогда у нас есть n i−1 кандидатов в тяжелые монеты и n i−1 +1 кандидатов в легкие и всего 2n i−1 +1 = 3 i−1 исходов. Итак, при такой схеме первого взвешивания действи- тельно получаем, что 3 i изначальных исходов равномерно распре- делились по результатам взвешивания. Чтобы определить, можно ли задать схему взвешиваний так, чтобы после каждого взвеши- вания исходы разбивались на равное число частей, рассмотрим результаты взвешивания. Очевидно, при S L = S R приходим к той же задаче, только с меньшей размерностью, и всегда снова можем выполнить взвешивание по схеме 1, но при меньшем значении i. Схема 2. Пусть теперь S L < S R . В этом случае определим стратегию взвешивания следующим образом. Исходными данны- ми является то, что на каком-то шаге i в последовательности взве- шиваний имеем 3 i = 2n i + 1 монет, среди которых n i кандидатов в легкую фальшивую монету и n i + 1 кандидатов в тяжелую, при этом число n i является числом вида (3.3) n i = 3n i−1 + 1. Положим на каждую чашу весов по n i−1 легких кандидатов и n i−1 +1 тяжелых. Так как всего 2n i +1 = 2(3n i−1 +1)+1 = 6n i−1 +3 монет, а взвешиваем 2n i−1 + 2n i−1 + 2 = 4n i−1 + 2 монет, то остается еще 2n i−1 + 1 монет, среди которых n i−1 + 1 легких и n i−1 тяжелых. Так как на обеих чашах весов одинаковое число легких и тяжелых монет, то если весы не уравновешены, это дает n i−1 кандидатов в легкие монеты (с чаши, оказавшей- ся легче) и n i−1 + 1 кандидатов в тяжелые (с чаши, оказавшейся 76 тяжелее). Это приводит нас к исходным данным этой же схемы (схемы 2), но для 3 i−1 = 2n i−1 + 1 монет. Если чаши весов уравно- вешены, то это значит, что надо искать фальшивую монету среди невзвешивавшихся n i−1 + 1 легких и n i−1 тяжелых монет, что со- ответствует схеме 3. Очевидно, во всех результатах взвешивания возможными остается 2n i−1 +1 исходов, т.е. снова множество всех возможных исходов разбивается на три равные части. Схема 3. Пусть теперь S L > S R . В этом случае имеем 3 i = 2n i + 1 монет, среди которых n i + 1 кандидатов в легкую фаль- шивую монету, и n i кандидатов в тяжелую. Все рассуждения ана- логичны схеме 2, с той разницей, что при взвешивании нужно на каждую чашу весов положить n i−1 + 1 легких кандидатов, и n i−1 тяжелых. Если весы не уравновешены, это снова дает нам схе- му 3 для 3 i−1 монет, в противном случае получаем условия для взвешивания, соответствующие схеме 2. Снова во всех случаях множество возможных исходов разбивается на три равные части по 2n i−1 + 1. Таким образом, имеем три раз- 1 2 3 = < > = = < > < > Рис. 3.4. Переходы между схемами взвешиваний в за- даче о фальшивой монете личных состояния, описанных вы- ше и правило взвешивания для каж- дого состояния. В зависимости от результата взвешивания переходим в другое состояние (или остаемся в том же), но для меньшего чис- ла монет. При каждом взвешива- нии число возможных исходов рав- номерно распределяется по резуль- татам взвешивания. Схема перехо- дов между состояниями показана на рис. 3.4. Пример взвешиваний для 27 монет приведен на рис. 3.5. 77 |