PАЗНОЕ. Задача 1. Пусть программа на языке BASIC состоит из последовательностей операторов. Каждая последовательность состоит из ненулевого числа операторов. Операторы отделяются друг от друга символом двоеточие (:), который для других целей в программе не используется. После- довательность может располагаться на нескольких строках, при этом разбивка оператора на 2 строки не допускается; если последователь- ность продолжается на следующей строке, в конце текущей строки стоит двоеточие. Последовательности операторов в тексте программы имеют уникальные номера. Таким образом, структура последователь- ности операторов следующая: - каждая новая последовательность начинается с новой строки; - в начале последовательности, до ее номера, состоящего не более чем из 8-ми десятичных цифр, могут присутствовать пробелы; - после номера последовательности также могут присутствовать пробелы; - оператор всегда начинается не с цифры; - оператор нельзя разрывать на несколько строк, если оператор не последний, за ним (возможно через пробелы) следует двоеточие. Переходы в программе осуществляются посредством операторов goto или gosub (эти ключевые слова могут быть записаны как с использованием заглавных, так и прописных букв, например GoSUb). Вид операторов goto номер последовательности gosub номер последовательности (между ключевыми словами и номером последовательности могут присутствовать пробелы). Написать программу, которая читает из файла имя файла (имя файла вводится с клавиатуры), текст BASIC программы и перенумеро- вывает последовательности операторов так, чтобы - в выходном файле порядок последовательностей совпадал с порядком последовательностей исходного файла, отсортированного по возрастанию номеров последовательностей; - первая последовательность выходного файла имела номер f, а каждая следующая последовательность имела номер на d больше, чем предыдущая (f и d - натуральные числа, вводимые с клавиатуры). Текст программы состоит не более чем из 100 строк, длина строки не превышает 80 символов. Преобразованную BASIC-программу выводить в файл имя_файла.OUT. Входные данные корректны. Задача 2. Пусть грамматика языка описывается следующим образом : <выражение>::=<операнд> <операнд> | <операнд> ::=+|-|* <операнд>::=<переменная> | <целое без знака> <переменная>::= A | B | C | D | ... | Z <целое без знака>::= 1 | 2 | 3 | 4 | ... | 9 | 0 <оператор>::= | | <присвоить> <присвоить>::=<переменная>:=<выражение> ::= IF <условие> THEN <оператор> ELSE <оператор> ::= WHILE <условие> DO BEGIN <оператор> END <условие>=<выражение> > <выражение> <программа P>=<оператор> | <программа P><оператор> Значок | обозначает 'или'. Задается текст программы P. Каждый оператор программы Р начи- нается с новой строки. Оператор может быть записан в нескольких строках. Ввод программы осуществляется из файла. Имя файла вво- дится с клавиатуры. В программе все переменные и ключевые слова за- писываются заглавными буквами латинского алфавита. Текст вводимой программы Р синтаксически правильный. Написать программу, оптимизирующую введенный текст программы Р по следующим правилам : 1. Если в операторе IF условие всегда истинно (ложно) (например 2>1 (1>2)), то в текст преобразованной программы включается только оператор, стоящий за THEN ( за ELSE, если он есть). 2. Если в операторе WHILE условие всегда ложно, то WHILE- опе- ратор из текста программы исключается. 3. Если в операторах IF, WHILE в <условие> или в операторе присваивания в правой части стоит выражение, численное зна- чение операндов которого известно, то это значение вычисля- ется и записывается вместо <выражения> в условие или вместо правой части оператора присваивания соответственно. 4. Если в двух операторах присваивания (обозначим их А и В) в программе Р в левой части оператора стоит одна переменная, и эта переменная не используется ни в правой части операторов присваивания, ни в условиях IF- или WHILE-операторов, встре- чающихся в тексте программы между операторами А и В, то в программе Р остается только оператор В. 5. Если внутри тела цикла оператора WHILE стоит оператор присваивания, и переменная из левой части этого оператора не встречается в <условии>, то этот оператор выносится из цикла и ставится перед ним. 6. Если в ветках THEN и ELSE оператора IF стоит один и тот же оператор присваивания (переменные в левых частях этих двух операторов совпадают, а значения правых частей одинаковы, например, IF A>B THEN L:=A+B ELSE L:=B+A), то этот оператор присваивания записывается вместо IF-операто- ра. Вывод программы оптимизатора направляется в файл с именем код.OUT. Задача 3. 'PROLAN/M' (В.В.Прохоров, Свердловск) Представим, что электронный концерн NePhiggah выпустил новый микропроцессор с компактной системой команд. Операционный блок этого микропроцессора "признает" данные только одного типа - текстовые строки - и "умеет" исполнять единственную операцию - контекстную замену (поиск в строке заданной подстроки и замену ее на другую заданную). Микропроцессор соединяется с двумя уст- ройствами памяти: одним - для запоминания программы (набора подстановок для контекстных замен) и другим, R ("почти неограни- ченной емкости") - для размещения (в виде текстовой строки) исход- ных данных, результатов промежуточных преобразований и "ответа". Для программирования микропроцессора используется язык, кото- рый будем условно называть 'PROLAN/M'. Предваряя его формальное описание, приведем пример программы: (aa,b) (ba,a) (bc,a) (c,start) (d,) (b,finish) (,) . Если эту программу исполнить для строки abcabcd , то результатом будет строка finish (при этом в процессе работы программы в R последовательно будут находиться значения abcabcd aaabcd babcd abcd aad bd b finish). Ну а формально синтаксис программы на 'PROLAN/M' таков ("::=" означает "есть по определению", а "|" - "или"): <'PROLAN/M'-program> ::= (,) ::= | ::= (,) ::=

::= | ::= | ::= ::= Исполнение же микропроцессором <'PROLAN/M'-program> для за- данной в R исходной строки проводится так. Среди в <'PROLAN/M'-program> отыскивается первая, для которой ее является некоторой подстрокой строки R. В случае успеха поиска соответствующая подстрока R (при неединствен- ности - самая левая) заменяется на той же . После чего процедура повторяется с самого начала, но уже для изменившейся R. Процесс повторяется так до тех пор, по- ка не случится, что ни одна <'PROLAN/M'-program> не является подстрокой текущей R. Тогда процесс исполнения программы завершается; сложившаяся к этому моменту строка R и есть результат исполнения этой программы для выбранной исходной строки. ______________________________________________________________________ Требуется: 1. Написать программу на PROLAN/M (ее текст должен храниться в файле 'SUM.PRM'), которая для исходной строки вида +=? , где , - записи натуральных десятичных чисел, вырабатывала бы в качестве результата строку вида += , где результирующая строка содержала бы арифметически верное выражение. Например, для исходной строки 1990+123=? Ваша программа должна выдать 1990+123=2113 . 2. Раэработать программу для отладки программ на PROLAN/M, которая бы (a) запрашивала имя текстового файла, в котором хранится программа на PROLAN/M; (b) запрашивала исходную для преобразования строку R; (c) производила бы преобразование исходной строки в соответствии с программой из указанного файла; (d) выдавала реэультат на экран дисплея; (e) желатательна воэможность эапуска программы на PROLAN/M с трассировкой исполнения. Качество Вашей программы п.1 будет оцениваться жюри с одной стороны по количеству в ее , с другой - по скорости выполнения ею тестов жюри. Так что Вы можете предложить два варианта программы, каждый из которых хорош по своему критерию. Тестирование программы п.2 будет проводиться в специально разработанной жюри для проверки PROLAN/M-системе программирования. Качество Вашей программы п.2 будет оцениваться в зависимости от прохождения теста жюри и того, все ли подпункты п.2 будут реализованы. Задача 4. На шашечной доске размера n x n ее верхний правый угол имеет номер (1,1). В позиции (i,j) стоит фишка, которая может двигаться по правилу,показанному на рисунке (допустимые ходы обозначены х, шашка - О). Фишка не может дважды ставиться на одно и то же поле. Играют двое, по очереди двигая фишку. Выигрывает поставивший фиш- ку в позицию (1,1). Для введённых i,j определить, может ли выиграть первый игрок при наилучших ходах второго. Написать программу, где первый игрок- компьютер. n 1 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ │ │ │ │ │ │ │ │ │ 1 ├───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │ │ │ │ │ │ │ │ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │ │ x │ x │ x │ │ │ │ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │ │ │ O │ x │ │ │ │ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │ │ │ │ x │ │ │ │ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │ │ │ │ │ │ │ │ │ n └───┴───┴───┴───┴───┴───┴───┴───┴───┘ Задача 5. Прямоугольник, стороны которого выражены целыми числами M и N, разделен на квадраты размером 1x1. Составить программу, которая находит число квадратов, пересекаемых диагональю прямоугольника. Если дан прямоугольник 4x8, то диагональ пересекает 8 квадра- тов. Если же дан прямоугольник 3x11, то в этом случае диагональ пересекает 13 квадратов. Задача 6. Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a_1, либо a_2, либо ... a_S бананов (а_1 =1. Бумажная полоса разбита на N кле- ток (K <= N <= 40).Играют двое, по очереди выбирая и зачеркивая K пустых смежных клетки.Выигрывает сделавший последний ход. 1 2 N ┌────┬────┬────┬────┬ ────┬────┐ │ │ │ │ │ . . . │ │ └────┴────┴────┴────┴ ────┴────┘ 1)Ввести N и определить, имеет ли игрок 1 выигрышную страте- гию ( т.е. может ли игрок 1 выиграть при наилучших после- дующих ходах игрока 2). Сообщение вида 'У игрока 1 (не) существует выигрышная стратегия'. 2)Для N определить,имеет ли игрок 1,сделав заданный первый ход,выигрышную стратегию. 3)Провести игру для N и первого хода игрока 1. За второго игрока играет программа.Ходы первого вводятся с клавиату- ры. Цель второго игрока -победа. Ход задается индекcoм ячейки L (1<=L<=N-K+1).При этом вычеркиваются клетки с ин- дексами от L до L+K-1.После каждого хода выводится текущая позиция в виде 1 2 3 ... N * * Сверху печатается номер позиции.Зачеркнутые клетки помечаются символом '*'. В конце игры выдать сообщение 'Победа игрока 1(2)'. При вводе N и K выдать подсказывающие сообщения 'N>'и 'K>', при вводе хода - 'Ход игрока 1>'.Предусмотреть контроль корректности входных данных. Задача 8. Пусть слово - это последовательность от 1 до 8 символов, не включающая пробелов. Вводится n слов A1,...,An.Можно ли их переупорядочить так, чтобы получилась "цепочка", т.е. для каждого слова Aj его первая буква должна совпадать с последней буквой предыдущего слова, а последняя буква в Aj - с первой буквой последующего слова; соот- ветственно последняя буква последнего слова должна совпадать с первой буквой первого слова. В цепочку входят все n слов без пов- торений. Дать ответ в виде "Можно"\"Нельзя". Если такое упорядочение возможно, то вывести какую-нибудь це- почку слов. Слова при выводе разделяются пробелами. Задача 9. На линейке из m клеток в разных концах стоят две фишки,кото- рые ходят по очереди. Каждая из фишек может ходить влево или впра- во не более чем на К клеток (m<=80;К<=m-2). При этом нельзя пере- шагивать через фишку и нельзя оставаться на месте. Фишка проигры- вает, если она не может сделать ход. Написать программу, реализую- щую выигрышную стратегию для одной из фишек. При этом разрешается передача хода в самом начале игры. Предусмотреть контроль входных данных. Задача 10. Составить программу, которая по введенному N выдает последова- тельность длины N, состоящую из цифр 0 и 1 такую, что ни один фраг- мент этой подпоследовательности не повторяется подряд трижды. Задача 11. Ввести три числа а,b,с. 1). Представить a в виде суммы минимального числа целых сла- гаемых x[i], каждое из которых лежит на отрезке [b,c]. 2). Можно ли представить число а таким образом, чтобы k а = х[1] * x[2] * ... * x[k] = П x[i], i>=1, i=1 где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Пре- дусмотреть вариант, когда такого представления не существует. Задача 12. Даны три слова X,Y,Z. Определить, существует ли слово V та- кое, что X,Y,Z являются повторениями слова V. Если V существует, то напечатать его. Слова имеют длину не более 1000 символов. Сим- вол "пробел" является разделителем слов. Задача 13. Даны два положительных целых числа А,В. Напечатать слово "ДА" или "НЕТ" в соответствии с тем, можно ли получить десятичную за- пись числа А путем вычеркивания одной или более цифр числа В. Задача 14. Пусть А - последовательность букв. После вычеркивания одной буквы из А (в одной позиции )получили последовательность В. После вычеркивания другой буквы из А (в одной позиции) получили последо- вательность С. Можно ли по последовательностям B и С 1) Определить вычеркнутые буквы. 2) Определить последовательность A. Примечание: В и C могут быть получены вычеркиванием одной и той же буквы. Задача 15. Имеется N книг и два читателя, А и В, желающих прочитать эти книги. Заданы неотрицательные целые числа A[I] и B[I] такие, что читателю А (или В) потребуется A[I] (соответственно,B[I]) часов для прочтения книги I, 1 <=I <=N. Процесс чтения начинается в мо- мент времени 0. В любой момент времени каждый читатель не может читать более одной книги и каждую книгу не могут читать оба чита- теля. Для каждого читателя порядок чтения книг не имеет значения и может быть произвольным. В процессе чтения любой книги любым чита- телем допускаются прерывания. Это означает, что этот процесс может быть прерван в любой целочисленный момент времени и возобновлен позднее с прерванного места. В промежутке между прерыванием и последующим возобновлением процесса чтения книги читатель может читать любую не до конца прочитанную книгу. Задано целое число К, 2<=K <=N, и книги пронумерованы таким образом, что ни один читатель не имеет права начать читать книгу J, 2<= J <= K, прежде чем книга J-1 не будет прочитана обоими чи- тателями. Требуется: 1. Вычислить наименьший момент времени Т, раньше которого все книги не могут быть прочитаны всеми читателями. Вывести вычисленное значение Т. 2. Построить расписание чтения книг каждым читателем, при ко- тором не нарушается ни одно из перечисленных выше условий и процесс чтения всех книг завершается в момент времени Т. Расписание для каждого читателя вывести в виде < РАСПИСАНИЕ ДЛЯ ЧИТАТЕЛЯ А (или В) > <Номер книги> <Начало > <Конец> ....... ...... ..... ....... ...... ..... В таблицах указанного вида необходимо указать все времен- ные интервалы, в течение которых читатель А (или В) читает книгу и номер этой книги. 3. Постарайтесь сократить число прерываний для каждого чита- теля. Задача 16. В программистском фольклоре есть предание, что при приеме в одну из ведущих компьютерных фирм претенденту предлагалась решить следующую задачу: Дана последовательность двузначных чисел 24, 81, 63, 26, 41, ... Продолжить ее. Найти правило формирования последующих членов. Задача 17. Продолжить следующую последовательность 110 , 20 , 12 , 11 , 10 , ... Задача 18. Янис и Петрис играют в следующую игру. Петрис загадывает де- картовы координаты двух различных точек A(Ax,Ay) и B(Bx,By). Из- вестно, что среди чисел Ax, Ay, Bx, By нет двух одинаковых. Янис может задавать вопросы только следующего вида: "Какое расстояние от точки P(Px,Py) до точки A (до точки B)?", где Px и Py - числа. В ответ Петрис называет число, которое является длиной отрезка PA (или, соответственно, PB). Определить, какое наименьшее количество вопросов должен задать Янис, чтобы он смог назвать координаты ка- кой-либо точки, находящейся на серединном перпендикуляре отрезка AB, независимо от того, какие точки загадал Петрис. Описать, как найти эту точку. Ответ обосновать. Задача 19. Известно, что среди 13 монет есть одна отличающаяся по весу (тяжелее одна или легче - неизвестно). За 3 взвешивания на чашеч- ных весах найти эту монету. Задача 20. "Быки и коровы" Пользователь загадывает число из 4 цифр, каждая из которых от 1 до 6, причем все цифры различны. Разработать алгоритм, который угадывает число по следующим правилам: выводится число и пользова- тель сообщает, сколько в нем "быков" и "коров", т.е. сколько цифр стоят на своих местах и сколько цифр содержатся в обоих числах, но совпадают лишь по значению. Например, пусть загадано число 1264, спрошено 1256. В этом случае 2 быка (1,2) и одна корова (6). Модификация: Правила игры те же, но загадывается 6-значное число с цифрами от 1 до 9, причем среди цифр допускаются одинако- вые. Примечание: Спрошенное число должно удовлетворять правилам для загадываемого; компьютеру на ход дается 1 минута . Задача 21. Составить тесты для проверки правильности работы программы определения площади треугольника по его сторонам a, b, c. Задача 22 (Прохоров В.В.). Учитель попросил Диму написать программу вида Ввод (x,y) Пока < условия выполнения итерации > НЦ < тело цикла > КЦ Вывод (x,y) т.е. такие < условия выполнения итерации > (не содержащие никаких переменных кроме x и y) и < тело цикла >, чтобы этот фрагмент для произвольных введенных в операторе ввода чисел x=x0 и y=y0 выдавал бы оператором вывода числа x=x0+y0 и y=x0-y0. Помогите Диме. Задача 23. Игровой автомат состоит из нескольких изогнутых трубок, по форме похожих на перевернутую вверх ногами букву "Y" . Сверху у трубы находится входное отверстие, а два выходных отверстия -- снизу. Труба может находиться в одном из двух возможных состояний: Вход Вход │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ / \ \ / / \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ левый выход правый выход левый выход правый выход Состояние 1: Состояние 0: закрыт левый выход закрыт правый выход │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ / \ \ / / \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ Рис.3 Рис.4 Шарики кладутся вовнутрь один за другим через входное от- верстие. В состоянии 1 (Рис. 3), шарик покидает трубу через незаб- локированный правый выход, при этом Состояние 1 автоматически из- меняется на Состояние 0 ( Рис.4, правый вход заблокирован, левый -- нет ). В состоянии 0 все происходит наоборот. A B C │ │ │ │ │ │ │ │ │ │ │ │ │ │ G1 │ │ G2 │ │ G3 / / \ / / \ / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ / \ / \ \ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ G4 │ │ G5 │ │ \ \ / \ \ / / \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ / \ / \ / │ │ │ │ │ │ │ │ │ │ │ │ │ │ G6 │ │ G7 │ │ G8 / / \ / / \ / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ / / \ \ Пусть игральный автомат состоит из 8 "Y"-образных трубок, их взаимное расположение показано на Рис.5. Вы можете забрасывать ша- рики через Вход A, Вход B, или Вход C. Пусть, например, первый ша- рик опускается через Вход A. Он покидает трубу G1 через левый вы- ход, изменяя ее состояние с 0 на 1, поступает в G6 и покидает ав- томат через левый выход G6 ( изменяя состояние G6 c 0 на 1). Эту процедуру мы запишем следующим образом: A Затем мы забросим шарик через Вход A (он находится в Состоя- нии 1). Шаpик покидает G1 чеpез пpавый выход, изменяя состояние 1 в состояние 0, попадает в G4, покидает G4 чеpез пpавый выход, из- меняя состояние 1 в состояние 0, попадает в G7, покидает автомат чеpез левый выход ( изменяя G7 из состояния 0 в состояние 1 ).Все вышеизложенные действия мы запишем в виде: AA Если мы опустим третий шарик через Вход B, четвертый -- через Вход C, то все действия запишутся следующим образом: AABC Необходимо: 1. Ввести с клавиатуры последовательность из 8 двоичных цифр (бит), показывающих соответственно начальное состояние G1-G8: бит 7 6 5 4 3 2 1 0 Вход G8 G7 G6 G5 G4 G3 G2 G1 Например, последовательность 11001010 означает, что G8, G7, G4 и G2 находятся в Состоянии 1 ( левый вход заблокирован ), тогда как G6, G5, G3 и G1 находятся в Состоянии 0 (правый вход заблоки- рован). 2. Ввести с клавиатуры вторую последовательность из 8 бит, показывающих конечные состояния G'1-G'8. 3. Напечатать последовательность ходов A, B, или C, указываю- щую, каким образом можно получить конечную позицию, забрасывая ша- рики через Входы A, B и C. Задача 24. Определить, является ли периодической последовательностью строка символов A1 A2 ... AN, т.е. имеет ли она вид d d ... d, где d -- некоторая подпоследовательность символов. Задача 25. Если мы из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то получен- ный результат назовем правильным скобочным выражением [скобочное выражение "(()(()))" - правильное, а "()(" и "())(" - нет]. Найти число правильных скобочных выражений, содержащих N отк- рывающихся и N закрывающихся скобок. N вводится с клавиатуры. N - неотрицательное целое число. Задача 26. Одним из стандартных методов кодирования информации когда-то был следующий: текст (длины l) записывался по строкам слева напра- во сверху вниз в прямоугольнике размера m*n (m*n>=l), добиваясь, по необходимоси, пробелами; после этого текст из прямоугольника выписывался по столбцам и получалось шифрованное сообщение. Например: Исходный текст "It is a nice weather today" m=5 n=6 1 2 3 4 5 6 1 I t _ i s _ 2 a _ n i c e 3 _ w e a t h 4 e r _ t o d 5 a y _ _ _ _ Шифрованный текст:"Ia eat wry ne iiat scto ehd " Дается шифрованный текст длины s состоящий из букв и пробе- лов, и известно,что в исходном тексте есть по крайней мере одно из слов набора a ,...,a , k<=10, (под словом в тексте понимается 0 k последовательность символов, не содержащая пробелов, и окруженная пробелами, за исключением случаев, когда слово стоит в начале либо конце текста (тогда ему может не предшествовать (за ним может не следовать) один или несколько пробелов)). Дешифровать текст. Задача 27. Пусть слово - это последовательность от 1 до 8 заглавных букв латинского алфавита. Задается множество слов A={a[1], a[2],..., a[n]}, n<10. Из слов множества A составляется текст - последовательность слов, за- писанных друг за другом без разделителей пробелов. Слова могут встречаться в тексте произвольное число раз. Дешифровка текста - это разбивка текста на слова множества A. В дешифрованном тексте слова разделяются пробелами. Необходимо : 1.Определить, существует ли для заданного множества A такой текст, который дешифруется не единственным образом (сам текст при- водить не надо). Примеры : 1) A = { B , C } Любой текст дешифруется однозначно. 2) A = { B , BC , C } Существует текст, который дешифруется двумя способами Текст ---> Дешифровка BBC ---> B B C BBC ---> B BC 2. Если такой текст существует, то исключить из множества A минимальное число слов так, чтобы после этого любой текст, состав- ленный из слов полученного множества A, дешифровался однозначно. Напечатать эти исключенные слова. Если такой набор не единствен- ный, то напечатать все наборы. 3.Для введенного текста произвести его дешифровку и, если де- шифровка не единственная, вывести все варианты. Примечание: Порядок выполнения пунктов строго фиксирован. Задача 28. На рисунке изображен фрагмент компьютерной сети. Система состоит из двух интерфейсов Международного Союза ORT и двух компьютеров. Каждый интерфейс подключен к отдельному компьюте- ру, один из которых является компьютером-передатчиком, другой - компьютером-приемником. Интерфейсы соединены друг с другом следующим образом: все восемь выходов интерфейса-передатчика соединены с восемью входами интерфейса-приемника, восьмой вы- ход интерфейса-приемника соединен с восьмым входом интер- фейса-передатчика. Реле входов (выходов) интерфейсов нумеру- ются с 0 по 7. Для включения реле-выхода с номером A запишите в порт с адресом 642 байт, в котором бит с номером A равен 1. Для выключения реле-выхода с номером A запишите в порт с ад- ресом 642 байт, в котором бит с номером A равен 0. Для получе- ния информации о состоянии реле-входа с номером A прочитайте байт из порта компьютера с адресом 642 и проанализируйте бит с номером A. Биты нумеруются, начиная с младшего. Задание: Написать программу, которая осуществляет: 1. Ввод с клавиатуры строки символов на компьютере-пере- датчике. Передачу строки через связанные интерфейсы на компь- ютер-приемник. Отображение данной строки на компьютере-прием- нике. 2. Проверку типа компьютера (приемник или передатчик), на котором загружается программа с выдачей сообщения об этом. 3. Проверку правильности соединения интерфейсов согласно рисунку. Примечание: Выдача байта информации D в порт с адресом 642 и считыва- ние байта D из порта с адресом 642 производится следующим об- разом: ┌──────────────────────┬─────────────────┬────────────────┐ │Язык программирования │ Запись в порт │ Чтение из порта│ ├──────────────────────┼─────────────────┼────────────────┤ │ С │ OUTPORTB(642,D) │ D:=INPORT(642) │ │ Pascal │ PORT[642]:=D; │ D:=PORT[642] │ │ Basic │ OUT 642,D │ D=INP(642) │ └──────────────────────┴─────────────────┴────────────────┘ ┌───┐ ┌─────────────────┐ ┌─────────────────┐ ┌───┐ │ К │ │ INPUT OUTPUT │ │ INPUT OUTPUT │ │ К │ │ О │ │ │ │ │ │ О │ │ М │ │ O 0 0 O─┼────────────┼─O 0 0 O │ │ М │ │ П │ │ O 1 1 O─┼────────────┼─O 1 1 O │ │ П │ │ Ь ├───┤ O 2 2 O─┼────────────┼─O 2 2 O ├───┤ Ь │ │ Ю │ │ O 3 3 O─┼────────────┼─O 3 3 O │ │ Ю │ │ Т │ │ O 4 4 O─┼────────────┼─O 4 4 O │ │ Т │ │ Е │ │ O 5 5 O─┼────────────┼─O 5 5 O │ │ Е │ │ Р │ │ O 6 6 O─┼────────────┼─O 6 6 O │ │ Р │ └───┘ │ O 7 7 O─┼────────────┼─O 7 7 O │ └───┘ └─┼───────────────┘ └───────────────┼─┘ └────────────────────────────────────────────┘ Задача 29. Пометить ребра куба числами от 1 до 12 так, чтобы для всех вершин сумма пометок входящих ребер была одинакова. Задача 30. "Дырокол". Бабурин Е.А. Дырокол пробивает на длинной полосе бумаги по два одина- ковых отверстия за одно нажатие его рычага и после несколь- ких нажатий получается следующее состояние бумаги. 0 0 0 00 0 00 00 0 0 Л П Л ПЛ П ЛЛ ПП Л П Буквы "Л" и "П" под лентой обозначают, соответственно, левое и правое отверстия дырокола. По известным координатам отверстий на полосе определить возможную ширину между отверстиями дырокола. Задача 31. КОМПОСТЕР Авторы: АНДРЕЕВА Е.В. МАРЧЕНКО А.П. В билете пассажира оказалось пробито отверстий больше, чем штырей в компостере. Пассажир утверждал, что пользовался только одним компостером, но случайно нажал на него несколько раз. Конт- ролеру требуется определить, могло ли быть получено заданное распо- ложение отверстий одним и тем же компостером, если билет можно пробивать с обеих сторон неограниченное число раз и произвольно перемещать и поворачивать относительно компостера. Пробитые от- верстия не выходят за пределы билета. В билете было пробито N (N<10) отверстий. ТРЕБУЕТСЯ : А. Для компостера с двумя штырями (S=2) составить программу, которая : 1. Определяет, можно ли получить заданным компостером требуемое расположение отверстий в билете. Если это возможно, то изображает вид билета после каждого нажатия компостера. В противном случая, выводит соответствующее сообщение. 2. Определяет количество K различных компостеров каждым из которых можно пробить заданную конфигурацию. 3. При K=0 (см. п.2) находит компостер, с помощью которого можно пробить наибольшее количество из заданных отверстий. 4. Находит минимальное число нажатий, требуемое для пробивки заданной конфигурации отверстий, для каждого компостера из пункта 2. Б. Решить задачу А для компостеров с числом штырей S (S>2). ПРИМЕЧАНИЯ. * Все исходные данные - натуральные числа. * Компостеры, дающие при однократном нажатии совпадающие конфигурации отверстий, считаются одинаковыми. * Относительное расположение отверстий в билете и штырей в компостере вводится либо с клавиатуры, либо из файла с именем COMP.DAT . Структура вводимой информации: {N,x[1],y[1],...,x[N],y[N], S,u[1],v[1],...,u[S],v[S]}, где x[i], y[i] - координаты отверстий в билете, u[i], v[i] - координаты штырей в компостере. * Нажатие компостера (см. п.1) моделировать клавишей "Пробел". * При выводе конфигурации на экран (см. п.п.1,3) изображать координатную сетку. При этом программа должна осуществлять подходящее масштабирование. Задача 32 (Литовская олимпиада 1992 г.) Тендеpные тоpги на товаpной биpже. На бирже есть N продавцов и M покупателей и 1 товар. Каждый продавец определяет для себя и объявляет минимальную цену, по ко- торой он согласен продать товар, а каждый покупатель называет максимальную цену, по которой он еще согласен купить товар. 1) Найти такую единую цену на товар, чтобы сумма сделок купли- продажи была максимальной. 2) Найти такую максимальную единую цену на товар, чтобы общее количество продавцов и покупателей, учавствующих в торгах, было мак- симальным. ВВОД: N <Цены продажи> с1, ..., сN M <Стоимости покупки> p1, ..., pM ВЫВОД: <Цена товара по пункту 1:> цена сумма <Объемы продаж по продавцам> о1, ..., оN <Стоимости покупки> p1, ..., pM <Цена товара по пункту 2:> цена <Количество участников торгов> количество <Номера участников-продавцов:> s1, ..., si <Номера участников-покупателей:> b1, ..., bj Задача 33. M одинаковых дисков, на ободе каждого из которых нанесены по порядку числа от 1 до N, насажены на общую ось. На диски мы смот- рим через "окошко" - такую планку с прямоугольной прорезью, что через прорезь видно только по одному числу с каждого диска. Требу- ется развернуть диски друг относительно друга так, чтобы макси- мальная сумма элементов "окошка" при синхронном вращении дисков, была бы минимальна. РАЗНОЕ. Задача 1. Чисто программистская задача. Задача 2. Другими словами необходимо написать программу, выполняющую те же действия, что и команда RENUM языка ВASIC. Задача 4. Позиция (1,1) проигрышная для игрока, который должен с нее сделать свой очередной ход (фишка уже стоит в позиции (1,1). Все соседние позиции - (1,2), (2,2), (2,1) - выигрышные для делающего текущий ход (они приводят в выигрышную позицию (1,1). Позиции (3,1),(1,3),(3,3) - также проигрышные (любой ход из них приводит в выигрышную позицию, и игрок, делающий следующий ход, выигрывает). Анализируя позиции дальше, получаем предположение, что пози- ции с обеими нечетными координатами являются проигрышными для на- чинающего, все остальные позиции - выигрышные для него. Это действительно так: из проигрышной позиции с обеими нечетными коор- динатами после любого допустимого хода мы попадаем в позицию, где хотя бы одна из координат четная (выигрышную). Из позиции с хотя бы одной четной координатой мы всегда можем опять попасть в пози- цию с обеими нечетными координатами (проигрышную для делающего очередной ход). Так как последняя позиция (1,1) имеет обе нечетные координаты, то человек, начинающий с позиции, где хотя бы одна из координат четная, всегда сможет сделать так, чтобы после любого его хода фишка была в позиции с обеими нечетными координатами, а в конце концов - в позиции (1,1). Итак, если i и j нечетные, то первый игрок при наилучших ходах второго всегда проигрывает, иначе - выигрывает. Задача 5. Если N и M взаимно просты (т.е. если НОД(N,M)=1), то Коли- чество=N+M-1. Если же k=НОД(N,M)<>1, то диагональ большого прямоу- гольника можно представить как объединение k кусочков, каждый из которых является диагональю прямоугольника размера (N/k,M/k), где N/k и M/k взаимно просты. Получаем, что Количество=k*(N/k+M/k-1)=N+M-НОД(M,N). Итак, всегда Количество=N+M-НОД(M,N). Задача 6. Будем обозначать текущую ситуацию в игре парой (S,i), где S - количество бананов, оставшихся в куче, перед текущим ходом i-ой обезьяны (i равно 1 или 2). Для того, чтобы (S,1) была выигрышной для игрока 1, среди возможных ситуаций после его хода (S-a_1,2), ... ,(S-a_k,2) должна быть хоть одна проигрышная для игрока 2 (в эту то ситуацию и надо будет перевести игру); если все ситуации выигрышные для игрока 2, то (S,1) - проигрышная для игрока 1 (как бы он не поступал, он все равно проиграет). Пусть ситуация после хода игрока 1 стала (S',2). Опять же де- лаем все допустимые ходы из этой позиции и смотрим является ли по- лучившаяся ситуация (S",1) выигрышной, проигрышной или такой, ко- торую мы еще не можем оценить. Если выполняется последняя альтер- натива, то из (S",1) мы опять делаем все возможные ходы, анализи- руем, и т.д. Если мы в конце концов определили, для кого является выигрыш- ной текущая позиция, то возвращаемся к предыдущему ходу и пытаемся определить, какая позиция для делающего ход и т. д., пока не вер- немся к ситуации (L,1). const l1=200; s=10; var a: array [0..l1,1..2] of byte; { в ячейке a[L,i] хранится информация, кто выигрывает в ситуации (L,i)} b: array [1..2,0..s] of byte; { массив возможных ходов } { первого и второго игроков } { в b[i,0] хранится число } { возможных ходов игрока i } l,i,j:integer; Function f(ba:Integer;No: Byte): Byte; Var i,p,r: Byte; { рекурсивная функция вычисления (L,i) } Begin { f=i, если в (ba,i) выигрывает i } if Ba<0 { после хода монет <0? } Then f:= 3-No { выигрыш игрока с номером 3-Nо } else if ba=0 { монет = 0? } then begin { выигрыш No} f:=No; a[ba,no]:=no; end Else if a[ba,no]<>0 { в этой ситуации мы уже были } Then F := a[ba,no] { в ней выигрывает a[ba,no] } Else Begin { эту ситуацию мы еще не рассматривали } r := 0; { мы будем делать все возможные ходы } For i := 1 to b[No,0] do if ba-b[no,i]>=0 { если ход возможен } { то делаем его } then r := r or F(Ba-B[No,i],3-No); if r=0 then r:=no; If (No and R)<>0 { есть выигрышный ход? } Then p := No { да, (ba,i)=No } Else p := 3-No; { нет, (ba,i)=3-No } A[Ba,No]:=p; { запоминаем эту информацию } f:=p; End; end; begin for i:=0 to l1 do for j:=1 to 2 do A[i,j] := 0; write('s='); readln(b[1,0]); { b[1,0] = количество ходов первого игрока } for i:=1 to b[1,0] do begin write('a',i,'='); { сами ходы } Readln(b[1,i]); end; write('k='); Readln(b[2,0]); { b[2,0] = количество ходов второго игрока } For j := 1 to b[2,0] do begin write('b',j,'='); Readln(b[2,j]); { ввод ходов } end; repeat { для данных ходов вводятся значения L } write('L='); { число бананов } readln(l); if f(l,1)=1 { вызов рекурсивной функции-проверки } then writeln('1-я выиграла') else writeln('1-я проиграла'); for i:=1 to b[1,0] do { распечатка результатов возможных ходов } if (l-b[1,i])>=0 { из начальной позиции L } then writeln('b=',b[1,i],' winner=',a[l-b[1,i],2]); writeln; until false; end. Задача 7. Идея решения аналогична изложенной в задаче про обезьян. Задача 8. Если n=1, и единственное слово начинается и заканчивается на одну и ту же букву, то цепочка построена. Для того, чтобы можно было переупорядочить слова A1, ..., An из набора A в "цепочку", необходимо, чтобы совокупность букв, на которые заканчиваются слова, совпадала с совокупностью букв, на которые эти слова начинаются (другими словами, чтобы каждой завер- шающей букве слова соответствовала такая же начальная буква како- го-то слова). То, что это не достаточное условие, показывает при- мер: AB, BC, CA, DE, ED. "Цепочку" построить нельзя. Так как цепочка обязана пройти через каждое слово, то все равно, с какого слова набора A начинать. Возьмем слово A1. Удаляем его из множества A: A:=A\A1. Ищем в A какое-нибудь слово Ai, начи- нающееся с последней буквы слова A1 (такое слово всегда существу- ет, так как мы считаем, что необходимое условие, упомянутое выше, выполняется). Удаляем Ai из A: A:=A\Ai, ищем в A какое-нибудь Aj, начинающееся с последней буквы Ai и т.д. Продолжаем до тех пор, пока либо все слова A1, ... ,An не войдут в цепочку (тогда задача решена), либо пока не окажется, что A не пусто, и в нем нет слова, начинающегося на последнюю букву x последнего слова (кстати, из необходимого условия следует, что эта буква x совпадает с первой буквой первого слова). Мы нашли какую-то подцепочку. Пример: A=(AB,BC,CA,BD,DC,CB). Подцепочка1: AB,BC,CA. Цепочка существует: AB,BD,DC,CB,BC,CA. Пусть мы нашли подцепочку 1. Берем опять какое-нибудь слово из A в качестве начального для очередной подцепочки и опять повто- ряем построение следующей подцепочки, и т.д. В конце концов пусть множество A стало пустым, и весь началь- ный набор слов A1, ... ,An распался на k подцепочек. Начнем их склеивать: Пусть в подцепочках i и j соответственно есть слова u и v та- кие, что в u и v совпадают первые буквы. Пусть цепочка i имеет вид i=BuC, а j=EvD (тут B,C,D,E - некоторые последовательности слов). Склеенная из i и j цепочка будет иметь вид EuCBvD. (Проверьте, что такая склейка корректна!) Склеивая все подцепочки, получим искомую цепочку. Если на ка- ком-то шаге окажется, что склейка никаких двух подцепочек невоз- можна, то задача неразрешима. Пример 1. Для приведенного в предыдущем примере набора слов будет 2 подцепочки: AB, BC, CA и BD, DC, CB. У них совпадают первые буквы в словах BC и BD. После склейки получаем AB, BD, DC, CB, BC, CA. Пример 2. A=(ACA, BB). Две подцепочки: ACA и BB. Слов с сов- падающими первыми буквами в них нет, задача неразрешима. Вариант #2 решения задачи. Если при составлении цепочки оказалось, что в наборе A нет слова с первой буквой, совпадающей с последней буквой последнего слова Aj цепочки, то Aj "отщепляем" от нее и пытаемся найти другое подходящее слово. Если это не удается, то "отщепляем" очередное последнее слово цепочки и т.д. Если на каком-то шаге A пусто, то задача решена, иначе если на каком-то шаге цепочка стала пустой, то задача неразрешима. Пусть есть набор слов A=(A1, ... ,An). Каждому слову приписан его уникальный номер, равный индексу. Слова упорядочены по воз- растанию индекса. Цепочка = A1 A=A\A1; инд=1. Пока (A не пусто) и (цепочка не пустая) повторять нц Если в A есть подходящее слово с индексом > инд то приписываем к цепочке это слово, слово удаляем из A инд=1 иначе "отщепляем" от цепочки последнее слово Aj инд=j Aj заносим в A кц Если A пусто, то цепочка найдена иначе задача не имеет решения. Этот метод называется "перебор с возвратом" ("backtracking"). Задача 9. Предположим, что левая фишка (будем называть ее Ф1) можем хо- дить только вправо, а правая фишка Ф2 - только влево, и ход пере- давать нельзя. Решение задачи в первоначальной постановке сводится к решению задачи при налагаемых выше ограничениях. Пусть первый ход делает Ф1. Ф1 выигрывает, если количество клеток между фишками d(Ф1,Ф2) (вначале оно равно m-2) не делится нацело на k+1. Действительно, пусть Ф1 делает такой ход, что d(Ф1,Ф2) кратно k+1. Какой бы ход не сделала Ф2 (например, на L клеток влево), Ф1 следующим ходом смещается на k+1-L клеток впра- во, и, таким образом, после хода Ф1 расстояние d(Ф1,Ф2) снова кратно k+1. А так как 0 также делится на k+1 нацело, то наступит момент, когда d(Ф1,Ф2)=0 и предыдущий ход был ходом Ф1, т.е. Ф2 проиграла. Если (m-2) mod (k+1)=0, то Ф1 при наилучших ходах Ф2 проигрывает. Если разрешить фишкам ходить как влево, так и вправо, то всегда выигрывает та фишка, после хода которой d(Ф1,Ф2) кратно k+1. Задача 10. Последовательность строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 0, т.е. 0 -> 01 -> 0110 -> 01101001 ->... Докажите, что предложенная последовательность удовлетворяет условию задачи. Если не смогли этого сделать, то вот доказательство: Будем нумеровать цифры последовательности, начиная с нуля. Итак, a(0)a(1)=01, a(2)a(3)=10=a(1)a(0). Отметим, что последова- тельность состоит из 'кирпичиков' 01 и 10 (любые a(2k)a(2k+1) есть либо a(0)a(1), либо a(1)a(0)). Любой отрезок четной длины, начина- ющийся с элемента с четным индексом a(2k) имеет поровну нулей и единиц. Предположим, что в M есть три смежных одинаковых отрезка. Если есть такие отрезки, то есть и отрезки минимальной длины. Мож- но считать, что сначала идет начальный отрезок P, затем подряд три смежных одинаковых отрезка S1,S2 и S3 минимальной длины, S1=S2=S3= =S: P S1 S2 S3. Будем обозначать длину отрезка A через IAI. Есть 4 возможных варианта: 1) IPI=2k, ISI=2l. Будем писать 0* вместо 01 и 1* вместо 10. С помощью этих сим- волов последовательность M записывается так же, как и раньше: M=0*1*1*0*1*0*0* ... Значит и P, и S можно записать с помощью символов 0* и 1*; начальный отрезок P будет состоять из k знаков 0* и 1*, а S - из l знаков. Уберем звездочки у цифр - последовательность M от этого не изменится. А из P,S1,S2 и S3 мы получим новые отрезки P', S1',S2' и S3' с длинами вдвое меньшими. Отрезки S1',S2' и S3' остаются одинаковыми, а длина каждого из них станет l. Мы получили противо- речие с утверждением о минимальности длины S. 2) IPI=2k, ISI=2l+1. Отрезок S1 начинается элементом с четным индексом. Длина от- резка S1 S2 четная (она равна 4l+2), и в нем одинаковое число ну- лей и единиц. Длина S1 нечетная, и, без нарушения общности, пред- положим, что нулей в S1 больше, чем единиц, тогда в S2 единиц бу- дет больше чем нулей?! Противоречие с тем, что S1=S2. 3) IPI=2k+1, ISI=2l+1. Отрезок S2 S3 имеет четную длину и начинается элементом с четным индексом. Далее рассуждения аналогичны приведенным в пункте 2. 4) IPI=2k+1, ISI=2l. Последний элемент отрезка P имеет индекс a(2k) (вспомните, что нумерация элементов начинается с нуля). Пара a(2k) a(2k+1) есть либо 01, либо 10, и всегда a(2k)<>a(2k+1). Первые элементы S1,S2 и S3 будут, соответственно, a(2k+1), a(2k+2l+1), a(2k+4l+1). Поэтому из совпадения S1=S2=S3 следует, что a(2k+1)=a(2k+2l+1)=a(2k+4l+1)<>a(2k)=a(2k+2l)=a(2k+4l). Следовательно, так как a(2k)a(2k+1)=a(2k+2l)a(2k+2l+1)=a(2k+4l)a(2k+4l+1), то мы можем считать, что повторяющиеся отрезки S1 S2 S3 начинаются в позиции a(2k), IPI=2k, ISI=2l, а этот случай уже разобран в пункте 1. Задача 11. Рассмотрим сначала случай, когда a, b, c, xi - натуральные. 1) Разбивка на слагаемые. Если ad. Минимальное число слагаемых будет тогда, когда каждое из слагаемых будет как можно больше. Введем функцию ceil(x)=k+1, если kk, то разложения не существует (сла- гаемых, которые надо уменьшить, больше, чем у нас есть, другими словами, a div c = a div d, и a mod c <> 0, a mod d <> 0). Если n<=k, то L, L=p div (d-c), слагаемых уменьшаем на (d-c), одно сла- гаемое - на p mod (d-c), остальные остаются без изменений (равными максимальному). Если a, b, c, xi - целые, то алгоритм практически не изменя- ется. 2) Разбивка на сомножители. Метод решения этой задачи аналогичен использованному при ре- шении задачи о нахождении максимальной по длине возрастающей под- последовательности введенной последовательности (см. задачу 20 главы "Рекуррентные соотношения и динамическое программирование"). Опять будем рассматривать только случай a>d. Обозначим через L упорядоченное по возрастанию множество де- лителей числа A, лежащих на отрезке [c,d], количество делителей не превышает 2*SQRT(A) (если a=f*g, то f<=SQRT(a), g>=SQRT(a), всего разных f - не более SQRT(a), столько же и разных g). Пусть L1 - минимальный элемент из L, a L2- максимальный. В массив S[1..k] за- несем по возрастанию все делители числа a (включая и само число a=S[k]), начиная с минимального элемента из L. Из утверждения выше следует, что k<=2*SQRT(A)+1. Будем искать минимальную по длине последовательность элемен- тов массива S, ведущую из множества L в число a=S[k] такую, что каждый последующий элемент последовательности при делении на пре- дыдущий дает частное, принадлежащее множеству L, и нулевой оста- ток. Заведем массивы B[1..k] и C[1..k]. В B[i] будем заносить ин- декс последующего элемента в подпоследовательности минимальной длины, ведущей из S[i] в S[k] (B[i]=0, если в a из S[i] попасть невозможно), в C[i] будет храниться число элементов в этой мини- мальной последовательности (отметим, что мы рассматриваем только такие последовательности, у которых частное от деления последующе- го члена последовательности на предыдущий принадлежит множеству L, а остаток от деления нулевой). Сначала во все элементы C, кроме последнего, занесем ка- кое-нибудь большое число, например 2*A. Если C[i]=2*A, то будем считать, что последовательности элементов, идущей от S[i] к S[k], пока не обнаружено. После заполнения матриц A и B мы находим минимальную длину цепочки, ведущей из множества L в число a. for i:=1 to k-1 do C[k]:=2*A; { последовательности нет } C[k]:=1; { последовательность из одного элемента A } B[k]:=0; { предыдущего элемента нет } for i:=k-1 downto 1 do for j:=i+1 downto k do if (S[j] div S[i] >=L1) and { частное S[j]/S[i] } (S[j] div S[i] <=L2) and { принадлежит L, и } (S[j] mod S[i] =0) { остаток нулевой } then if C[i]>C[j]+1 { если длина обнаруженной } then begin { сейчас подпоследовательности, } { идущей от S[i] к S[k], меньше, чем } C[i]:=C[j]+1; { ранее найденная, то кор- } B[i]:=j { ректируем длину и индекс } end; { следующего элемента } i:=1; min:=2*A; j:=0; while S[i]<=L2 do begin if C[i]< min then begin min:=C[i]; { корректируем минимум } j:=i; { сохраняем индекс первого элемента } end; i:=i+1 end; if j=0 then writeln('Разложения не существует') else begin writeln('Разложение:'); write(A[j]); for i:=1 to min-1 do begin P:=j; j:=B[j]; write(A[j]/A[p]) { распечатка сомножителя } end end В случае, если a, c, d, xi - целые, в массив S помещаем в по- рядке возрастания модуля все делители числа A, начиная с минималь- ного элемента в L. Далее - аналогично. Задача 12. См. решение задачи о том, является ли введенное слово перио- дическим повторением какого-то другого слова (Задача 24). Задача 13. Решается аналогично задаче 23 (глава "Рекуррентные соотноше- ния и динамическое программирование"). Задача 14. Если последовательности B и C совпадают, то вычеркнутых букв определить нельзя. Если B и C различаются ровно в одной позиции (т.е. в A были вычеркнуты соседние буквы), то определить вычеркнутые буквы можно, а последовательность A - нет (пример: A='ABCDB', B='ACDB', C='ABDB'). Чуть-чуть упростим задачу. Уберем из начала и конца последо- вательностей B и C все совпадающие элементы. Получим последова- тельности B' и C'. Пример B='albce', C='alcde', B'='bc', C'='cd', т.к. первые два и последний символ у B и C совпадают. Если мы смо- жем восстановить слово, из которого получается B' и C', то мы смо- жем восстановить и A. Пусть B'=b1b2b3 ... bk C'=c1c2c3 ... ck. Если b1=c2=b3=c4= ... и (*) c1=b2=c3=b4= ..., то определить последовательность A нельзя, выброшенные буквы - это b1 и c1. Пример: B='abab', C='baba'. В качестве A можно взять как 'babab', так и 'ababa'). Если же (*) не выполняется, то можно найти и A, и вычеркнутые буквы. Мы находим такие элементы в B' и C', что c(i)=b(i+1) и b(i)<>c(i+1) (или c(i)<>b(i+1), а b(i)=c(i+1)), и получаем началь- ную строчку A=b(1) ... b(i)b(i+1)c(i+1)b(i+2) ... b(k) (или A=c(1) ... c(i)c(i+1)b(i+1)c(i+2) ... c(k)). Пример: B'='bc' C'='cd' Слово из которого получается и B' и C' - 'bcd'. Задача 16. Эту же последовательность можно записать и так: 2, 4, 8, 16, 32, 64, 128, ... Очередной член последовательности - 28. Задача 17. Члены последовательности есть запись числа 6 в двоичной, тро- ичной, четверичной, пятеричной, шестеричной, ... системах счисле- ния. Все остальные члены последовательности равны 6. Задача 18. Если мы знаем расстояние R от некоторой точки С до точки А, то точка A будет лежать где-то на окружности O(R,C) радиуса R с центром в точка C. Возьмем на оси абсцисс две точки - V и W. Узнаем 1. Расстояние R1 - от точки V до точки A. 1. Расстояние R2 - от точки W до точки A. 1. Расстояние R3 - от точки V до точки B. 1. Расстояние R4 - от точки W до точки B. Точка A - это одна из двух точек пересечения окружностей O(R1,V) и O(R2,W). Точка B - это одна из двух точек пересечения окружностей O(R3,V) и O(R4,W). Обозначим точки пересечения окруж- ностей соответственно через A1, A2 и B1, B2. Эти точки можно рассматривать как вершины равнобедренное трапеции с основания- ми-отрезками [A1, A2] и [B1, B2]. (Трапеция равнобедренная так как точки A1 и B1 симметричны относительно оси абсцисс точкам A2 и B2 соответственно). Отрезок [A,B], фигурирующиий в задаче, - один из следующих четырех: [A1,B1], [A1,B2], [A2,B1], [A2, B2] - т.е. это либо боковая сторона трапеции, либо ее диагональ. А так как в рав- нобедренной трапеции срединные перпендикуляры к боковым сторонам и срединные перпендикуляры к ее диагоналям пересекаются в одной точ- ке (докажите это!), то для нахождения этой искомой точки достаточ- но четырех вопросов. Задача 19. Определим вначале ситуации, когда можно можно определить фальшивую монету за одно взвешивание. Это возможно сделать, если: есть две неизвестные монеты и одна стандартная (заведомо не фальшивая); есть три неизвестные монеты и известен вес фальшивой монеты (т.е. информация о том, больше или меньше ее вес). Алгоритм: Разобьем 13 монет на 3 части: 4,4 и 5 монет. 1. вес монет в первых частях равны. Тогда это стандартные мо- неты. Будем обозначать их через с а возможные фальшивые монеты че- рез ф. 2-е взвешивание ссс и ффф (остались неопределенными только фф из третьей части). Если веса равны, то фальшивая среди оставшихся двух. Если нет, то среди взвешенных трех, но ее вес известен. 2. Веса монет в первых частях не равны. Тогда монеты из третьей части - стандартные монеты. Определим взвешенные монеты как т (тяжелые) или л (легкие) в зависимости от результатов взве- шивания. 2-е взвешивание ссст и тттл Если веса равны, то фальшивая среди оставшихся трех легких. Если нет, то возможны следующие ситуации. 2.1. ссст легче тттл. Понятно, что фальшивая монета находится среди трех тяжелых монет. 2.2. ссст тяжелее тттл. Понятно, что фальшивая монета нахо- дится среди двух монет: тяжелой монеты слева или легкой справа. Поэтому фальшивую монету можно определить за одно оставшееся взвешивание. Задача 20. { Задача "Быки и коровы" Пользователь загадывает число из 4 цифр, каждая из которых от 1 до 6, причем все цифры различны. Разработать алгоритм, который угадывает число по следующим правилам: выводится число и пользова- тель сообщает, сколько в нем "быков" и "коров", т.е. сколько цифр стоят на своих местах и сколько цифр содержатся в обоих числах, но совпадают лишь по значению. Например, пусть загадано число 1264, спрошено 1256. В этом случае 2 быка (1,2) и одна корова (6) б) Правила игры те же, но загадывается 6-значное число с цифра- ми от 1 до 9, причем среди цифр допускаются одинаковые. Примечание : Спрошенное число должно удовлетворять правилам для загадываемого; компьютеру на ход дается 1 минута . Итак, 1-ое что приходит в голову играть по следующему правилу: называть первое попавшееся число, которое может быть задуманно, т.е. при сопоставлении любого ранее спрошенного числа с новым должно по- лучится такое-же количество 'быков' и 'коров'. Число будем представ- лять в виде массива цифр. } const MaxSgn = 6; { Максимальное значение в числе } Sgn = 4; { Количество цифр в числе } type S = 1..MaxSgn; Numb = array[1..Sgn] of S; function cows(n1,n2:Numb):byte; { Сравнивает два числа и возвращает результат сравнения в виде <количество быков>*10+<количество коров> } var i1,i2 : 1..Sgn; a : byte; begin { Необходимо сравнивать все цифры первого числа со всеми цифрами второго } a:=0; for i1:=1 to Sgn do for i2:=1 to Sgn do if n1[i1]=n2[i2] then if i1=i2 then a:=a+10 { Встретился 'Бык' } else inc(a); cows:=a; end; type Step = Record { Информация об одном вопросе - ответе } n : Numb; { Спрошенное число } answer : byte; { Ответ } end; Game = array[1..32] of step; { Информация о всех вопросах - ответах } var Nstep : byte; { Номер текущего шага } Info : Game; Curnumb : Numb; i,j : integer; b : boolean; BEGIN clrscr; for i:=1 to Sgn do Curnumb[i]:=i; Nstep:=0; while true do { Пока не будут перебраны все числа или не найденно решение } begin { Спросить текущее число } for i:=1 to Sgn do write(Curnumb[i]); write(' ? '); inc(Nstep); Info[Nstep].n:=Curnumb; readln(Info[Nstep].Answer); { Пользователь должен ввести число, первая цифра которого 'Быки', вторая - 'Коровы' } if (Info[Nstep].Answer div 10+Info[Nstep].Answer mod 10)>Sgn then begin writeln('Плохая игра !'); exit; end; { 'Быков' и 'Коров' вместе не может быть больше, чем цифр } if Info[Nstep].Answer=10*Sgn then exit; { Далее идет генерация нового числа } repeat i:=Sgn; { Увеличение числа на 1-цу } while (i>=1) and (Curnumb[i]=MaxSgn) do begin Curnumb[i]:=1; dec(i); end; if i<1 then begin { Все числа перебраны, а ответ не найден } writeln('Вы неправильно отвечали !'); exit; end; inc(Curnumb[i]); b:=true; { Проверка на встречающиеся одинаковые цифры } for i:=1 to Sgn do for j:=i+1 to Sgn do b:=b and (Curnumb[i]<>Curnumb[j]); for i:=1 to Nstep do b:=b and (cows(Curnumb,Info[i].n)=Info[i].Answer); until b; end; { while } END. { program } Итак, наша программа работает следующим образом: мы путем последовательного увеличения на 1 генерируем все возможные 6-значные числа, отбираем среди них те, в которых все цифры различные, и, на- конец, те из них, которые удовлетворяют хранящимся в массиве Info ответам, задается пользователю в качестве вопроса. Возникает ряд ре- зонных вопросов: сколько всего интересующих нас 4-значных цифр и ка- кая их часть не содержит повторений. За сколько шагов может угадать ответ самый быстрый алгоритм и насколько хороша наша стратегия? Давайте попытаемся ответить на них. Итак сколько всего чисел? Пусть k цифр и m позиций. В первой позиции может стоять любая из k цифр, что нам дает k вариантов. Во второй-также любая из k цифр, т.е. k^2. И так далее m раз, т.е. всего k^m вариантов. Обобщим эту идею. Определение: размещение с n повторением из k элементов по m на- зывается m-элементный массив натуральных чисел, каждое из которых не превосходит k. Утверждение: Число размещений с повторениями из k по m равно k^m. Доказательство проводим по индукции: Базис индукции: При m=1 у нас ровно k вариантов. Индуктивный переход: Пусть утверждение верно при m=n-1. Дока- жем, что оно верно при m=n. Зафиксируем число 1. Справа к этому числу припишем k^(n=1) размещений из k по n-1. Аналогично поступим с 1,2,3...k. Получим k^(n-1)*k=k^n вариантов. Таким образом, число 4-значных чисел с цифрами от 1 до 6 равно 6^4=1296. Теперь посмотрим, сколько из них не содержит повторяющихся цифр. Определения: размещением из k элементов по m называется m-эле- ментный массив каждая компонента которого не превосходит k и среди них не встречаются одинаковые. Очевидно, что множество размещений не пусто лишь при m<=k. Число размещений из k по m принято обозначать A. Утверждение A=k*(k-1)*...(k-m+1)=k!/(k-m+1)! Доказательство проводим по индукции: Базис индукции: При m=1 у нас ровно k вариантов. Индуктивный переход: Пусть утверждение верно при m=n-1. Выберем любое из k!/(k-n+1)! размещений из k по n-1. Чисел, которые в нем не участвуют-(k-n+1). Приписывая их поочередно справа к выбранному раз- мещению мы получим (k-n+1) вариантов. Перебирая все размещения: (k!/(k-n+1)!)*(k-n+1)=k!/(k-n)! Таким образом,число 4-значных чисел с цифрами от 1 до 6 без повторений равно A46=6*5*4*3=360, т.е. в 3 раза меньше, чем число вариантов, которые мы перебирали. Итак мы нашли один способ для оп- тимизации нашей программы: генерировать не все числа, а лишь те, ко- торые не содержат повторяющихся цифр. Возьмем это на заметку, а сей- час попробуем оценить максимальное число шагов, за которое отгадыва- ет лучший игрок. Вариантов ответа у нас: Пусть угадано 4 цифры. Среди них могут быть 2,1,0 "быков". Пусть угаданы 3 цифры. Среди них могут быть 3,2,1,0 "быков". И так далее: получаем 3+4+2+1=10 вариантов. Таким образом за каждый вопрос количество допустимых чисел уменьшается, если мы рассматриваем худший случай, не более чем в 10 раз. Число шагов, за которое угадывает лучший игрок, не менее чем [log10 360]+1=3 Ну а теперь попытаемся повысить эффективность работы программы. Как уже было отмечено выше, нам достаточно перебрать не 1096 комби- наций, а всего лишь 360. Это не отразится на быстроте угадывания, т.е. числе шагов, так как не изменим стратегии "первый попавшийся из подходящих", но уменьшит время обдумывания хода. Генерировать числа будем следующим образом: для начала выберем множество цифр,которое в него входит, ну а затем будем переставлять элементы этого множества между собой. Множество цифр удобно, для на- ших целей, представить в виде массива длины 4, элементы которого расположены в порядке возрастания. Будем генерировать эти массивы в лексикографическом порядке, т.е. сначала сравниваются первые циф- ры,если они равны -- вторые, и так далее. То есть: 1 2 3 4 1 2 3 5 1 2 3 6 1 2 4 5 1 2 4 6 1 2 5 6 1 3 4 5 . . . . . . Значит, мы должны увеличить самую правую цифру, какую это возможно, и уменьшить затем те цифры, какие стоят за ней. Заметив, что номер цифры, которую нужно увеличивать, уменьшается на 1, а как только последний элемент массива можно будет увеличить, скачкообразно ста- новится равной длине массива, приходим к следующему алгоритму: {n-число цифр} {A-массив который содержит текущие комбинации} Var p:integer; {номер элемента ,который увеличивается в данный момент } Var i:integer; for i:=1 to n do a[i]:=i;{ Начальное значение } p:=n;{ увеличивается крайняя правая цифра } while p>=1 do begin {Write(A)}-{Последовательность готова}; for i:=k downto p do A[i]:=A[p]+i-p+1; if a[k]=n then dec(p); else p:=k; end; Для генерирования всевозможных перестановок множества служит следую- щая идея: Пусть у нас сформированы всевозможные перестановки длины N-1 .Вставляя оставшийся элемент в каждую перестановку во все воз- можные позиции, мы получим все комбинации длины n. Например, число 1 в перестановку 2 3 можно вставить следующими 3-мя способами: 1 2 3 2 1 3 2 3 1 Следует отметить, что получающиеся перестановки обладают приятным свойством: каждая перестановка получается из предыдущей путем обмена двух соседних элементов. Применяя эту идею рекурсивно, мы получим, например, следующую последовательность перестановок: 1 2 3 2 1 3 2 3 1 3 2 1 3 1 2 1 3 2 Для применения этого алгоритма в рекурсивной форме нам понадобится хранить всевозможные перестановки. Давайте попытаемся привести этот алгоритм к нерекурсивной форме. Для i-го элемента нам необходимо знать: Куда он сейчас движется - вправо или влево. Знать номер возможного из n-i+1 мест в перестановке длины n-i, которое он сейчас занимает. Мы приходим к следующему алгоритму: { B - массив элементов перестановки } { Direc - массив направлений, i-й элемент равен TRUE, если тело i движется вправо } { Posit - массив положения i-го элемента в перестановке n-i элементов } for i:=1 to n do begin B[i]:=i; Posit[i]:=1; Direc[i]:=TRUE; end; Posit[n]:=0; Давайте попытаемся привести этот алгоритм к нерекурсивной фор- ме. Для i-го элемента нам необходимо знать: Куда он сейчас движется-вправо или влево. Номер возможного из n-i+1 мест в перестановке длине n-i, кото- рое он сейчас занимает. Мы проходим к следующему алгоритму: {В-массив элементов перестановки} {Direc-массив направлений. i-й элемент равен true, если число i движений вправо } {Posit- массив положения i-го элемента в перестановке n-i элементов} For i:=1 to n do begin b[i]:=i; posit[i]:=1; direc[i]:=true; end; posit[n]:=0; i:=1; while ib[k+1]; inc(posit[i]) end end; И, наконец, новый вариант программы игры Const MaxSgn=6; Sgn=4; Type s=1..MaxSgn; {цифра} Numb=array[1..Sgn] of s; function cows(n1,n2:Numb):byte; { Сравнивает два числа и возвращает результат сравнения в виде <количество быков>*10+<количество коров> } var i1,i2 : 1..Sgn; a : byte; begin { Необходимо сравнивать все цифры первого числа со всеми цифрами второго } a:=0; for i1:=1 to Sgn do for i2:=1 to Sgn do if n1[i1]=n2[i2] then if i1=i2 then a:=a+10 { Встретился 'Бык' } else inc(a); cows:=a; end; type Step = Record { Информация об одном вопросе - ответе } n : Numb; { Спрошенное число } answer : byte; { Ответ } end; Game = array[1..32] of step; { Информация о всех вопросах - ответах } var NStep:byte; Info:game; Procedure testnumber; {процедура проверяет, удовлетворяет ли входное число ранним ответам, и, если да, то задает его в качестве вопроса. В случае, если число угадано, заканчивает игру} Var i:byte; begin for i:=1 to nstep do if cows(n,info[i].n)<>info[i].answer then Exit; inc(Nstep); info[nstep].n:=n; for i:=1 to sgn do write(n[i]); write(' ? '); readln(info[nstep].answer); if info[nstep].answer=sgn*10 then halt; {игра окончена} end; {test number} Var tset{текущее n-элементное подмножество} ,tn:number; i,j,k,l:byte; direc:array[1..sgn] of boolean; posin:array[1..sgn] of byte; begin {инициализация} nstep:=0; for i:=1 to sgn do tset[i]:=i; i:=sgn; while i>=1 do begin tn:=tset; for j:=1 to sgn do begin posit[i]:=1; direct[i]:=true; end; posit[sgn]:=0; j:=1; testnumber(tn); while j не существует. За- дача алгоритмически не разрешима. Но если мы разрешим использовать в условии обращение к функции F(x,y), которая возвращает всегда логическое значение False, и изменяет аргументы x и y требуемым образом, то тело цикла не будет выполняться, и в этом случае зада- чу можно решить. Задача 23. Метод 1. Во всех узлах (трубках) схемы мы должны получить состояние Gi'. Первоначально установим G1, G2 и G3 в G1', G2' и G3', выбрасывая, по необходимости, шарики через входы A, B и С соответственно. Для того, чтобы G1,G2 и G3 оставались в состоянии G1', G2' и G3' необходимо, чтобы через каждый из входов забрасыва- лось лишь четное число шариков. Если проследить за шариками, заброшенными в игровой автомат, то мы можем заметить, что результат хода, например, ABC аналогичен результату хода BCA, т.е. от порядка заброски шариков ничего не зависит! Рассмотрим узлы,состояние которых может меняться при забрасы- вании шариков через вход A, т.к. при выбранной методике забрасыва- ния только четного числа A * | \ | \ | \ | \ | \ | \ | \ | \ | \ | \ G4 | /* | / \ | / \ | / \ | / \ | / \ | / \ | / \ | / \ | / \ G6 | / \ G7 * * шариков через входы всегда G1=G1', то состояний G6 G4 G7 может быть лишь 2^3=8, от 000 до 111. Если мы будем забрасывать через A пары шариков, то при забросе серии максимум из 8 пар шариков ка- кое-то состояние G6 G4 G7 должно обязательно повториться на протя- жении серии, а далее состояния будут циклически повторяться, и случай с забрасыванием более 8 пар шариков сводится к случаю с ко- личеством пар, не превосходящим 8. Аналогично, для забрасывания шариков через B мы получаем се- рию из не более чем 2^5=32 пар шариков, на протяжении которой бу- дут установлены все возможные состояния G4 G5 G6 G7 G8, а для вхо- да C серия, как и для A, будет иметь длину не более 8 пар. Перебирая все возможные комбинации A2x B2y C2z забрасывания шариков (тут A2x обозначает серию из 2X забрасываний шариков через вход A, 0<= x,y <=8, 0<=z<=32 ) получаем либо комбинацию-решение задачи, либо определяем отсутствие решения. Метод 2. Можно рассматривать эту задачу как задачу на графе. Вершины графа будут обозначать Y-трубки, а дуги - соединения этих трубок. Итак, у нас есть граф с 8 вершинами, каждой из которых мо- жет быть приписана одна из пометок 0 или 1. Всего есть 2^8=256 всевозможных состояний игрального автомата. Каждое состояние можно представить в виде 8-и битного числа. Создадим новый граф П на 256 вершинах следующим образом: 1) Пометим вершины номерами от 0 до 255. Каждая вершина графа П соответствует одному из возможных состояний системы Y-трубок. 2) Для каждого состояния системы i - от 0 до 255 повторять 1. В состоянии i забросить шарик через вход А. Система пе- рейдет в состояние iA. В графе П соединить ориентированной дугой вершины i и iA. Пометить эту дугу символом А. 2. В состоянии i забросить шарик через вход B. Система пе- рейдет в состояние iB. В графе П соединить ориентированной дугой вершины i и iB. Пометить эту дугу символом B. 3. В состоянии i забросить шарик через вход C. Система пе- рейдет в состояние iC. В графе П соединить ориентированной дугой вершины i и iC. Пометить эту дугу символом C. 3) Из вершины графа П, соответствующей начальному состоянию, найти кратчайший путь (по количеству дуг) в вершину, соответствую- щую конечному состоянию. Пометки дуг на этом пути являются поряд- ком заброса через входы шариков. Если пути не существует, то зада- ча решения не имеет. Алгоритм поиска кратчайших путей см. в главе "Задачи на гра- фах". Задача 24. Для решения данной задачи введем так называемую функцию отка- зов F(j), принимающей целочисленные значения [ Ахо А. и др. Пост- роение и анализ вычислительных алгоритмов., М., 1979, с.386]. Функция F задается так: F(j) -- наибольшее число s1 нет, то F(j)=0. (m) Определим функцию F (j) следующим образом: (1) 1) F (j)=F(j) (m) (m-1) 2) F (j)=F(F (j)) для m>1. Будем вычислять функцию F итеративно. По определению F(1)=0. Допустим, что вычислены F(1), F(2), ... , F(j). Пусть F(j)=i. Что- бы вычислить F(j+1) исследуем A и A . Если A = A , то j+1 i+1 j+1 i+1 F(j+1)=F(i)+1 , поскольку A A ... A A = A A ... A A . 1 2 i i+1 j-i+1 j-i+2 j j+1 Если A <> A , то тогда надо найти наибольшее значение i, для j+1 i+1 которого A ... A = A ... A и A = A , 1 i j-i+1 j i+1 j+1 если такое i существует. Если такого i нет, то очевидно, что F(j)=0. Пусть i , i , ... -- наибольшее, второе по величине и т.д. 1 2 значения i, для которых A A ... A = A ... A . 1 2 i j-i+1 j С помощью простой индукции убедимся, что (2) (k) i =F(j), i =F(i )=F (j), ..., i =F(i )=F (j), .... 1 2 1 k k-1 Итак, в случае A <> A находим наименьшее m, для которого либо j+1 i+1 (m) 1) F (j)=u и A = A , и полагаем тогда F(j+1)=u+1, j+1 u+1 либо (m) 2) F (j)=0 и A <> A , и тогда F(j+1) полагаем равным 0. j+1 1 Алгоритм вычисления F следующий: begin F[1]:=0; for j:=2 to n do begin i:=F[j-1]; while ( A[j]<>A[j+1] ) and ( i>0 ) do i:=F[i]; if ( A[j]<>A[i+1] ) and ( i=0 ) then F[j]:=0 else F[j]:=i+1; end; end. Этот алгоритм вычисляет F за O(n) шагов. Чтобы доказать это, покажем, что сложность оператора while при работе программы ( про- порциональная числу уменьшений значения i оператором i:=F[i] ) ли- нейно зависит от N. Единственный способ увеличить i в этом фрагменте программы -- это выполнить оператор F[j]:=i+1 в третьей от конца программы строке. Этот оператор может выполняться не более N-1 раза, следо- вательно, и уменьшение i в операторе while может произойти не бо- лее N раз. Остальная часть алгоритма имеет сложность O(n), и поэ- тому и весь алгоритм имеет сложность O(n). Итак, мы вычислили F(n)=U, это означает, что A A ... A = A ... A (*) 1 2 U N-U+1 N Для того, чтобы последовательность A ... A 1 N была периодической необходимо и достаточно, чтобы длина общей части двух строк в (*) A ... A N-U+1 U была кратна длине периода (в качестве периода последовательности тут выступает строка A ... A ). 1 N-U Действительно, если A ... A = A ... A , то по 1 N-U N-U+1 2(N-U) свойству (*) и A ... A = A ... A и т.д. N-U+1 2(N-U) 2(N-U)+1 3(N-U) Для окончательного решения задачи 1) найдем длину l перекрывающейся части строк в (*) l=U-(N-U+1)+1 =2*U-n; в случае l<=0 последовательность A ... A непериодическая. Стоп. 1 N 2) Если l>0 , то проверим, делится ли нацело l на длину пе- риода (т.е. на N-U) l mod (N-U) = (2U-N) mod (N-U) = - ((N-U)-U) mod (N-U) = =U mod (N-U) = R Если R=0, то последовательность периодическая с периодом A ... A , 1 N-U иначе -- нет. Задача 25. Назовем скобочное выражение элементарным, если оно представи- мо в виде (S), где S - правильное скобочное выражение. Очевидно, что каждое непустое скобочное выражение можно единственным образом представить в виде ES, где E - элементарное скобочное выражение; S - скобочное выражение (возможно, пустое). Обозначим через S(n) число правильных скобочных выражений с 2n скобками. Тогда число элементарных скобочных выражений с 2n скобками есть S(n-1). Таким образом n S(n)=SUM(S(i-1)*S(n-i)). i=1 Замечая, что S(0)=1, - одно пустое скобочное выражение, мы приходим к алгоритму сложности O(n^2). ДРУГОЕ РЕШЕНИЕ этой задачи: Будем изображать знаком / открывающую скобку, а \ - закрываю- щую. Правильное скобочное выражение (ПСВ) при n=1 будет выглядеть так: /\ 0 1 Если мы возьмем картинку / \ / \ / \ 0 1 2 то все ПСВ с n=2 будут такими: / \ / \ и /\ 0 1 2 / \ 0 2 - то есть каждому ПСВ соответствует свой единственный и неповтори- мый путь между вершинами 0 и 2. Аналогично, все ПСВ с n=3 будут описываться путями в графе / \ / \ / \ / \ / \ / \ 0 1 2 3 и т.д. Подсчитаем число ПСВ (число путей) при n=3. C -> 1 В вершину A мы можем попасть единствен- / \ ным способом - из точки 0, равно в B,C и B -> 1 3 <- D точку 1 можно попасть, соответственно, / \ / \ только из точек A, B, A. В E можно A -> 1 2 5 попасть как из 1, так и из B, поэтому / \ / ^ \ / \ пометка E есть сумма пометок этих узлов, 1 1 E 2 5 т.е. 2. В D можно попасть либо из C 0 1 2 3 (пометка 1), либо из E (пометка 2), и, следовательно, пометка D=3 и т.д. Аналогично находим количество ПСВ для любого n. Задача 26. Так как нам известна длина s шифрованного текста, то нам не- обходимо разложить s на всевозможные пары множителей ( например, для s=6 эти пары будут 1*6, 2*3, 3*2, 6*1 ), переписать шифрован- ный текст в таблицу T соответствующего множителям размера по столбцам и посмотреть, есть ли в полученном тексте ( если его чи- тать по строкам ), хоть одно слово из набора. Необходимо проверить все возможные наборы множителей, так как текст может дешифроваться неоднозначно. Также надо предусмотреть обработку случая, когда текст не дешифруется вообще. Если s слишком большое, то матрица размера [1..s, 1..s] может не поместиться в память машины. В этом случае можно промоделиро- вать доступ к тексту длины s как к массиву T[1..n, 1..m], nm=s; при этом обращение к элементу Т[i,j] эквивалентно обращению к эле- мету (i-1)*n+j кодированного текста(представьте себе, что мы весь текст разбили на куски длины m - строки матрицы Т, j-ый элемент i-ой строки массива T будет соответствовать букве (i-1)*n+j коди- рованного текста. Задача 27. Один из возможных алгоритмов решения задачи такой: 1. Предположим, что существует текст, дешифровка которого не- однозначна, следовательно, существует и текст минимальной длины, для которого возможны по меньшей мере две разбивки b[1] b[2]...b[k] = c[1] c[2]...c[m] на слова множества A. Представляя текст в виде отрезка DE, эти разбивки мы можем изобразить следующим образом b[1] b[2] ... b[k] D ├─────┼────────┼──────────────────────────────┼───────┤ E c[1] c[2] c[3] ... c[m] D ├─────────┼────┼─────┼──────────────────────────┼─────┤ E Из того, что текст минимальной длины, следует, что концы слов в разных разбивках не могут лежать на одной вертикали (кроме конца текста), т.к. b[1] <> c[1], то одно из кодовых слов (например b[1]) должно входить в другое в качестве префикса и представляться в виде c[1] = b[1] p[1] , где p[1] - это оставшаяся часть слова (суффикс). Далее, либо p[1] входит в b[2] (b[2] =p[1] p[2]), либо b[2] входит в p[1] (p[1] = b[2] p[1] ) в качестве префикса. Опре- деляем новый суффикс p[2]. Продолжая выделять префиксы и суффиксы, получаем, что на каком-то шаге p[j] совпадет с одним из кодовых слов. Эти рассуждения являются основой следующего алгоритма : На нулевом шаге возьмем все пары (a[i], a[j]), i <> j, таких кодовых слов, что одно из них есть префикс другого, и найдем все суффиксы p[0,k]. На j-ом шаге для всех пар (p[j-1,k], a[i]), где одно из слов является префиксом другого, опять находим все суффиксы, и те из них, которые не появлялись на предыдущих шагах алгоритма, обозна- чим p[j,k]. Эти шаги повторяем либо до тех пор, пока какой-либо суффикс не совпадет с одним из кодовых слов (и тогда существует неоднозначно декодируемый текст), либо пока на очередном шаге не появится ни одного нового суффикса (и тогда для любого текста существует единственная дешифровка). Т.к. количество кодовых слов ограничено, то и суффиксов также конечное число, и на каком-то шаге алгоритм обязательно остано- вится. Этот алгоритм принадлежит в первоначальном варианте A. Сарди- насу и Дж. Паттерсону (см. Кибернетический сборник, вып.3 стр. 93- 102 ). 2. Если существует текст, который, используя A, дешифруется неоднозначно, то начинаем выбрасывать из A слова и их комбинации, пытаясь получить множество A' с максимальным числом слов такое, что все тексты, составленные из слов A' дешифруются однозначно. Сначала из A удаляем i-ое слово , i = 1, 2, ... , n, и делаем проверку по пункту 1. Если удалением одного слова из A мы не полу- чаем искомого множества A', то тогда генерируем все сочетания по n-2 слова из множества A, и для каждого полученного множества де- лаем проверку по пункту 1, и т.д. Воспользуемся следующим алгоритмом генерации сочетаний по i слов из множества A: В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число i). В качестве начальной кон- фигурацией возьмем следующую: B[j]=j, j=1,...,n. Ищем B[j] с максимальным индексом j такое,что B[j]j полагаем B[k]=B[k-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значе- ниями элементов массива B[k], k>j, последний элемент B[i] не пре- восходил бы n). Если такого B[j] не существует, то генерация соче- таний для данного i закончена. Начинаем генерацию с i=n-1 и проводим ее с уменьшением i до тех пор, пока либо i не станет равно 1 (тогда A' состоит из единственного слова), либо пока проверка по пункту 1 не даст од- нозначности декодировки. 3. Этот пункт реализуется следующим рекурсивным алгоритмом по- иска с возвращением (все слова массива A упорядочены по номерам): а) Если строка пустая, то одна из возможных дешифровок найде- на, иначе при разборе текста мы проверяем a[i] (при изменении i от 1 до n) на вхождение в начало дешифруемой в данный момент строки. б) Если какое-то a[i] входит в строку как префикс, то запоми- наем номер i этого слова, затем выделяем слово из строки, а с остатком текста производим операцию разбора по пункту а). Если ни одно из а[i] не входит в качестве префикса в дешифруе- мую сейчас строку, то осуществляем возврат на пункт а), предвари- тельно добавляя в начало строки последнее удаленное оттуда слово, и пытаемся выделить из текста слово с большим номером в A. Если возврат осуществить невозможно (т. к. мы находимся в начале исход- ной строки), то алгоритм заканчивает свою работу. Все возможные дешифровки найдены. Задача 1. Докажите следующую теорему (Марков А. А.): Для однозначности декодировки текста достаточно выполнения од- ного из двух следующих условий: 1) не существует ни одной пары кодовых слов (a[i], a[j]), i<>j, такой, что одно из этих слов есть префикс другого. 2) не существует ни одной пары кодовых слов (a[i], a[j]), i<>j, такой, что одно из них есть суффикс другого. Задача 2. Приведите пример такого множества кодовых слов, что для него не выполняется ни условие 1, ни условие 2 из предыдущего пункта, а декодировка любого текста, составленного при помощи это- их слов - однозначная. Задача 28. Обратите внимание на то, что от посылки сигнала на интерфейс до приема сигнала должно пройти некоторое время. В программе необ- ходимо учесть возникновение этой паузы. Задача 29. Чтобы суммы меток ребер при вершинах были равны, необходимо, чтобы эта сумма равнялась 2*(1+2+...+12)/8, так как каждому ребру смежны 2 вершины (т.е. оно подсчитывается дважды), а количество вер- шин - 8. Но число 2*(1+2+...+12)/8=2*12*13/(2*8) - не целое. Поэтому нумерации не существует. Задача 31. Полное описание решения этой задачи можно найти в журнале "Информатика и образование" N 5-6 за 1992 г. Задача 32. Сформируем массив A из всех цен покупок и продаж. Очевидно, что искомая единая цена для каждого из пунктов есть один из элементов данного массива. 1. Просматриваем элементы массива, и для каждой из текущих цен вычисляем сумму сделок. Находим максимальную из сумм сделок. 2. Просматриваем элементы массива, и для каждой из текущих цен вычисляем общее число участников торгов. Находим максимальное число участников и соответствующую этому числу максимальную цену.