Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
После того, как сформирован массив D, остается найти пер- вые N максимальных значений и вывести затем соответствую- щие подпоследовательности. Остановимся на ключевых момен- тах обработки. Разумно в массиве констант определить индексы для D, ко- торые определяют первые последовательности заданной длины, что мы и сделаем. Const .13] Of Integer=(0, 0, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, определяет, с какого номера начинаются последовательности длины i . *} Var D: Of A, B, N: Integer; При обработке очередного символа требуется вычислять по- следовательности, а лучше их номера, образуемые предыдущи- ми символами и текущим символом из входной строки. Как это сделать? Пусть в массиве Sold хранятся номера последних об- 6. Избранные олимпиадные задачи по программированию 307 работанных подпоследовательностей, например (0, 1, 1, 5, 5). Обработана следующая часть исходной последовательности — 0101, и мы обрабатываем символ (Значение В равно 4, поэ- тому 5 элементов в массиве Sold). Что это значит (вспомните о массиве Rt)? В Sold хранятся текущие смещения, получаемые из последних символов входной строки, относительно первых констант заданной длины в массиве D. Так, первая единица означает, что последней была обработана последовательность ' 1 ' , находящаяся на первом месте в своей группе последовате- льностей. Вторая единица — первая последовательность дли- ны 2, т. е. (начинаем отсчет в каждой группе с нулевого индекса). Первая пятерка — обрабатывалась последователь- ность длины 3 с пятого места, т. е. '101'. Последняя пятерка — обрабатывалась последовательность длины 4 с пятого места, т. е. '0101'. Еще раз повторим. Подпоследовательности: • длины 1 имеет 1-й номер, начиная с 0 (0+1=1 и соответст- вует последовательности в массиве • длины 2 — 1-й номер (2+1=3 и соответсвует последовате- льности '01' в массиве D); • длины 3 — номер 5 (6+5=11 и соответствует последовате- льности '101' из таблицы); • длины 4 — 5-й номер (14+5=19 и соответсвует последова- тельности '0101' из таблицы). Переходим к вычислению новых номеров при обработке оче- редного символа '0' из входной строки: • длины 1 - 0*2+0, 0-й номер; • длины 2 — 1*2+0, подпоследовательность '10' имеет 2-й номер; • длины 3 - подпоследовательность имеет 2-й номер; • длины 4 — 5*2+0, подпоследовательность '1010' имеет 10-й номер и массив Sold имеет вид: (0, 0, 2, 2, 10). Обрабатываем сле- дующий '0'. • длины 1 - 0*2+0, 0-й номер; • длины 2 - 0*2+0, 0-й номер; • длины 3 - 2*2+0, 4-й номер; • длины 4 — 2*2+0, 4-й номер. Результат Sold — (0, 0, 0, 4, 4). Подпоследовательности и '00' находятся на нулевых местах. Подпоследовательности '100' и '0100' на четвертых местах в своих группах. Проверьте. Откуда берем цифры выше по тексту, выделенные курсивом? 308 Избранные задачи по программированию В таблице приведено изменение значения элементов массива Sold при обработке первых 10 разрядов последовательности, приведенной в условии задачи. № символа 1 2 3 4 5 6 7 8 9 10 0 1 0 1 0 0 1 0 0 1 Sold 0,0, -1, -1, -1 0,1, 1,-1,-1 0, 0, 2, 2, -1 0, 1, 1,5,5 0,0,2, 2, 10 0, 0, 0, 4, 4 0, 1, 1, 1,9 0, 0, 2, 2, 2 0, 0, 0, 4, 4 0, 1, 1, 1,9 Procedure Var: nch: Char; Of Integer; Begin SizeOf(Nw) , 0) ; For i:=l To MaxB Do :=-l : Read (nch) ; While nch<>'2' Do не прочитали последний символ. *} For В Do Begin If Sold[i-1]<>-1 Then Begin Nw[i] :=Sold[i-l] *2 + Ord(nch) -Ord 0 ') ; If Then Inc(D[Rt[i] + единицу к соответствующему элементу массива End Else End; Sold: =Nw; { *3апоминаем вычисленную последовательность номеров.*} следующий символ. *} End; End; Приведем еще одну вспомогательную процедуру. Мы работа- ем с номерами последовательностей, а на заключительном эта- пе требуется сама последовательность. Этот перевод осуществ- ляется с помощью следующей простой процедуры. 6. Избранные задачи по программированию 309 Procedure номеру подпоследовательности вычисляем ее вид. *} Var i , j : Integer; s: String; Begin While (i>0) And (Rt[i]>num) длины. *} - ' ; For j:=0 To Do Begin Mod 2 + Ord('O')) + s; num:= Div 2; End; (' ', s); End; 23. Даны «цепочки» из нулей и единиц одинаковой (боль- шой) длины. Над ними можно выполнять поразрядно операции NOT, AND и OR. Таким образом: Написать программу, которая вводит натуральное число N четыре цепочки a, длины N и определяет: • можно ли последовательным применением перечислен- ных операций получить d из а, Ъ и с; • при удовлетворительном ответе строит нужную последова- тельность операций (достаточно одной последовательно- сти). Пример 1. Для с=010001 и d= 100010 вывод программы может быть следующим: • на первый вопрос — «Да»; • на второй вопрос — AND(NOT(a),OR(b,a)). Пример 2. Для с=010001 и ответ на первый вопрос отрицательный. Указание. Если рассматривать разрядные «срезы» цепочек а, Ъ и с, то различных всего восемь. Это наводит на мысль о том, что логика обработки должна быть независима от длины цепочек, естественно, после их какой-то первоначальной обра- ботки. Поясним это утверждение на примерах. Пусть: а=1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 С=0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 2 «среза» 8 «срезов» 4 «среза» 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 310 Избранные задачи по программированию Из этого факта следует, что цепочки при предварительной обработке необходимо «сжать». Это первое. Кроме того, очевид- но, что если одному значению разрядных срезов (срезы по по- рядку различные) цепочек а, Ъ и с соответствуют различные значения в соответствующих разрядах цепочки d, то на первый вопрос задачи имеется отрицательный ответ — «из одних и тех же данных невозможно получить два различных результата». Так, для третьего примера ответ —«Нет», первому и третьему разрядным срезам соответствуют различные значения в соот- ветствующих разрядах цепочки d. Итак, предположим, что мы умеем сводить наши длинные цепочки Ь, с и d) к цепочкам с длиной не более восьми разрядных срезов и решать первую часть задачи. Что из этого следует? Количество различных це- почек длины не более 8 — 256. Это первое. И второе, какие бы операции над цепочками а, Ъ и с мы ни выполняли, наш резу- льтат — это одна из 256 цепочек. Значит, необходимо органи- зовать перебор вариантов не по различным последовательно- стям операций (NOT, AND и OR), а по результатам этих операций. А это уже только техника перебора и не более. При- ведем часть структур данных, которые, на наш взгляд, соответ- ствуют решаемой задаче. Const Max=256; .3] Of ; Type operation: - нет операции; 1 - NOT; 2 - OR; 3 - AND. *} операндов - индексы элементов в массиве типа А.*} -.Byte; данной операции. *} End; Var Of Action; Счетчики числа записанных элементов в массив А.*} ok -.Boolean; Первые четыре элемента массива А описывают исходные данные задачи после операции сжатия — значения полей opera- tion, ор2 равно нулю, A[l и В качестве примера приведем одну из процедур — вывода результата. Входным параметром является номер (индекс) эле- мента массива А — первая операция, которая имеет результат, равный d. 6. Избранные олимпиадные задачи по программированию 311 Procedure Out (p:Nord)/ Begin With A[p] Do Case operation Of 0: 1 : Begin NOT 2: Begin Write (' (opl) /Write (' OR ')/ Out (op2) /Write (') ') /End/ 3: Begin Write ('(') /Out (opl) /Write (' AND '); Out (op2) /Write (') ') /End/ End/ End/ И основная логика. Begin <сжать исходные - первые 4 элемента массива А и логическая переменная, в которой фиксируется признак отсутствия решения. *} <нет решения> Then <вывод сообщения> Else Begin Repeat <Перебор>/ Until Or ok/ End/ End; 24. Заданы две строки А и В длины N (l можно перевернуть подстроку, составленную из символов с 3-й по 6-ю позиции. Получится стро- ка 11101000. Две строки считаются эквивалент- ными, если одну из них можно получить из дру- гой с помощью описанных преобразований. Написать программу, которая: • определяет эквивалентность заданных строк А и Пример. input.txt 9 001011001 output.txt yes 6 9 3 8 1 5 Задачу предложил для одной из областных олимпиад по информатике Вита- лий Игоревич Беров. 312 Избранные задачи по программированию • если строки эквивалентны, предлагает один из возмож- ных способов преобразования строки А в строку В. Входные данные расположены в файле с именем input.txt. В первой строке файла содержится число N. Следующие две стро- ки содержат слова и В соответственно. Слова записаны без ве- дущих и «хвостовых» пробелов. Выходные данные. Результат работы программы выводится в файл с именем output.txt. Если заданные слова не эквивалент- ны, то выходной файл должен содержать только сообщение по. Если слова эквивалентны, то в первую строку выходного файла нужно вывести сообщение yes, в последующие — последовате- льность преобразований слова А в слово В. Каждое преобразо- вание записывается в отдельной строке в виде пары чисел i, j (разделенных пробелом), означающей, что переворачивается подстрока, составленная из символов с номерами i, j. Указание. Основная идея решения задачи формулируется следующим образом. На множестве всех слов W следует выде- лить подмножество S такое, что для любого слова можно указать эквивалентное ему слово Алфавит и слова у нас заданы, преобразования тоже. Осталось определить мно- жество S, свести каждое слово к представителю из множества S, и если представители совпадают, то слова эквивалентны. Из каких слов состоит S? Слов вида причем как первая группа единиц, так и первая группа нулей, а также следующая единица (слово из одних 0) могут отсутствовать. За- метим, что вывод преобразований, в случае эквивалентности слов, чисто техническая деталь. Она требует дополнительной структуры данных (массива) для запоминания значений i и при каждом перевертывании. Другая схема реше- ния (автор приводит рассуждения одного из восьмиклассников, ре- шавших данную зада- чу). Как обычно, ребе- нок вначале рисует, рисует примеры слов и преобразований над ними. Попытаемся вос- произвести его рисунки. Столбцы с заголовком — это уже выводы из рисунков. № 1 2 3 4 5 6 7 8 9 10 11 11111001 0000001000 10010001100 0100101101 1001001101 1100100101 1111000100 1 5 6 1 4 4 4 5 5 5 5 5 4 0 6 5 5 5 3 3 3 3 3 ? 1 2 3 2 2 2 2 2 2 2 2 6. Избранные задачи по программированию 313 Его вывод заключается в том, что количество нулей после четного числа единиц (4-й столбец) и после нечетного числа единиц (5-й столбец) в слове постоянно — не изменяются в про- цессе преобразования слов (строки таблицы с номерами 4-6 и 7-11). После этого он пишет небольшой фрагмент подсчета этих чисел (сразу после их ввода) chl:=0;ch2:=0; For i:=2 (S) Do If Then If cnt Mod Then Inc(chl) Else Inc(ch2) Else (cnt) ; и выписывает результат — слово после его приведения. Нуле- вая позиция в слове считается при этом четной, например чис- ла 1, 5 (5 нулей после четного числа единиц — нулевого), 4 (4 нуля после нечетного числа единиц) однозначно определяют слово 0000010000. Обоснуем результат рассуждений. Инвариантом преобразо- вания является знакочередующаяся сумма вида: где i — номер единицы, а — номер позиции г единицы. Схема до- казательства. Обозначим через s номер позиции в подстроке, соответствующий центру переворачиваемой подстроки. Пусть х — номер позиции до «переворота», у — номер этой позиции после операции «переворота». Очевидно, что (x+y)/2=s, т. е. или Количество элементов в сумме четно, знаки чередуются и Поэтому после ввода слов следует подсчитать количество 1 в каждом из них и суммы указанного типа. Если они совпадают, то слова и В эк- вивалентны. Например, для строки 0101 сумма равна после переворачивания — 1010, сумма — Они совпадают, строки эквивалентны. Для примера (110100 и 110001) эти суммы равны -3 и - 5 , строки неэквивалентны. Дополним задачу при ограничении Необходимо найти количество слов, эквивалентных заданному слову А. Входные данные расположены в файле с име- нем input.txt. В первой строке файла содержится Пример. input.txt число Следующая строка содержит слово А, записанное без ведущих и «хвостовых» пробе- лов. Выходной файл с именем output.txt должен содержать искомое количество слов. 3500 9 101010011 output.txt 30 314 Избранные олимпиадные задачи по программированию Задача на умение использовать динамические схемы подсче- та, плюс — «длинная» арифметика. Рассмотрим первую часть задачи. Мы подсчитали количество 0 после четного числа 1 в слове и после нечетного. Из вышеизложенного ясно, что пере- мещение 0 из той или другой групп по соответствующим циям (после четного числа единиц или после нечетного) приво- дит к эквивалентным словам. Приведем пример для пояснений. Пусть есть слово 101010010. Количество нулей по- сле всех четных единиц в сумме равно 2, после нечетных — 3. Количество позиций, на которые можно переставлять нули из первой группы, равно 3, из второй — 2. Выделим их — Переставляем «крупные» нули: OlOllOOlO (подчеркнута та подстрока, которая переворачивается, но в данном случае это уже не принципиально). Переставляем «мелкие» нули: 10l0l00l0, lOOOlOllO. Найдем для каждого случая количество эквивалентных слов, эти значения необходимо перемножить, результат — ответ задачи. Для на- шего примера первое значение 6, второе — 4. Ответ — 24. Кста- ти, возвращаясь к предыдущим рассуждениям, подсчитаем ин- варианты, например, для двух последних строк: и Совпадают, строки эквивалентны. Приведем текст процедуры, назовем ее Find, параметрами которой являются числа и — число позиций и число нулей, результат — число эквивалент- ных слов типа Пусть найдено решение для t позиций, т. е. определено число способов размещения для всех количеств нулей от 1 до При позиции решение получается оче- видным способом — в позиции с номером размещаем опре- деленное количество нулей, в позициях с номерами от 1 до t — оставшиеся (они уже подсчитаны). Один из возможных вариан- тов реализации этой схемы приведен ниже, разумеется, это не единственный способ. Function Longlnt; Var Of Longlnt; j Begin FillChar (Q) ,0) ; For j:=0 To 1 Do Q[l,j] :=1; For i:=l To Do Begin Q[2,0] :=1 ; For j:=l To 1 Do ] ; :=Q[2]; 6. Избранные олимпиадные задачи по программированию 315 End; End; 25. Алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел хорошо известен и изучается в кур- се основ информатики. Рассмотрим задачу повышенной слож- ности, идея решения которой основана на алгоритме Евклида. Даны натуральные числа р и q. Разработать программу опреде- ления последовательности натуральных чисел наибольшей дли- ны N, такой, что значение суммы любых р идущих подряд эле- ментов этой последовательности было бы положительно, а любых q — отрицательно*. Разумно предположить, что последовательность имеет неко- торую регулярную структуру, т. е. она не случайна. И эту ре- гулярность следует найти. Можно считать, что значение N>max(p,q). Случай, когда q=lp (одно из чисел делит- ся нацело на другое) отсекается моментально. Действительно, пусть и построена последовательность ..., Из ра- венства _Р_ . V — / i = l i=l следует противоречие. Сделаем два предположения: q>p (иначе просто меняем зна- ки у элементов последовательности); взаимно просты, т. е. Затем результат обобщим. Действия учащегося, ум которого не обременен техникой доказательств, выглядят достаточно просто — он пытается прорисовать последователь- ности. Попытаемся воспроизвести эти действия с помощью сле- дующей таблицы для произвольных значений р и q (на послед- ний столбец таблицы пока не обращаем внимания). № 1 2 3 4 5 6 7 12 8 Р 5 5 5 5 5 Схема Евклида Последовательность ? |