Главная страница
Навигация по странице:

  • Разумно в массиве констант определить индексы для D, ко

  • При обработке очередного символа требуется вычислять по- следовательности, а лучше их номера, образуемые предыдущи- ми символами и текущим символом из входной строки. Как это

  • 6. Избранные задачи по программированию 309

  • 6. Избранные олимпиадные задачи по программированию 311

  • 6. Избранные задачи по программированию 313

  • 6. Избранные олимпиадные задачи по программированию 315

  • По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    Дата06.12.2019
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаProgrammirovanie_v_algoritmakh.pdf
    ТипДокументы
    #98984
    страница23 из 26
    1   ...   18   19   20   21   22   23   24   25   26
    После того, как сформирован массив 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 А или В, содержащую четное число единиц, можно перевернуть, т. е. записать в об- ратном порядке. Например, в строке 11010100
    можно перевернуть подстроку, составленную из символов с 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
    Схема Евклида
    Последовательность
    ?
    1   ...   18   19   20   21   22   23   24   25   26


    написать администратору сайта