ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеМетоды и приемы программирования > Задачи на перечисление вариантов
Задачи на перечисление вариантов
            В олимпиадах по информатике достаточно часто встречаются задачи в которых надо перечислить все возможные решения, либо выбрать из всех возможных комбинаций удовлетворяющие условиям задачи.
            В таких задачах для построения исследуемой модели может использоваться N-разрядное число, в системе счисления по некоторому основанию K. Задача часто сводится к тому, чтобы перебрать все такие числа и выбрать из них удовлетворяющие условию задачи.
Этот метод позволяет решать многие задачи «в лоб». В школьных и муниципальных турах олимпиад по информатике такой подход позволяет добиться высокого результата, однако в следующих турах может не дать успеха, потому что начинает оцениваться скорость работы программы.
 
Задача 1.
            Даны чашечные весы и разновес, состоящий из N гирь. Вес каждой гири Mi, i=1,2,..,N. На правой чаше весов установлен груз весом P. Найти такой набор гирь, если он существует, который, при установке на левую чашу весов, уравновешивал бы весы.
 
Решение:
            Набор гирь разновеса представляется как конечное множество элементов. Задача состоит в том, чтобы найти такое подмножество этого множества, которое удовлетворяло бы условию задачи.
            Для моделирования подмножества будем использовать следующую структуру данных. Пусть числовой массив C из N элементов содержит 0 и 1. Если Сi=1, то элемент принадлежит подмножеству, если Сi=0, то не принадлежит. Перебрав все возможные состояния массива C, получим все возможные разбиения множества разновесов на подмножества. Отметим, что если все элементы массива C нули, то это состояние будет соответствовать пустому множеству, а если все равны 1, то подмножество совпадает с исходным множеством.
            Рассмотрим примеры для N=4, пусть значения элементов массива перечисляются справа налево:
 
            С=0,0,0,0 — пустое множество,
            C=1,1,1,1 — исходное множество,
            C=1,0,1,1 -  подмножество, включающее 1,2 и 4 элементы.
 
            Поскольку в записи состояний массива используются только нули и единицы и запись идет справа налево, то можно провести аналогию между нашей моделью подмножества и N-разрядным целым числом в системе счисления по основанию 2. Таким образом, для получения всех возможных подмножеств множества состоящего из N элементов необходимо перечислить все N  — разрядные двоичные числа от 0 до 2N-1.
            Для каждого полученного разбиения выполним проверку условия задачи. Оно может быть записано следующим образом M1*C1+ M2*C2+ M3*C3+…+ MN*CN=P или .
            Рассмотрим алгоритм получения (перечисления) всех N — разрядных двоичных чисел. Пусть вначале число равно 0, то есть во всех его разрядах стоят 0. Прибавляя к числу 1, получим следующее значение числа, последнее число будет иметь во всех разрядах 1. Однако, удобнее для реализации рассматривать не N, а  N+1 разрядное число. Тогда появление в N+1 разряде 1 будет сигналом того, что все числа уже были получены. В этом случае нам нет необходимости постоянно следить за тем, что возникла ситуация соответствующая 1 во всех разрядах.
            Рассмотрим на примере прибавление 1 к какому-либо двоичному числу.
 
            1100110011
           +
                              1
           ----------------
           1100110100
 
            Видно, что все подряд идущие справа 1 обращаются при прибавлении 1 в 0, а первый отличный от 1 разряд справа увеличивается на 1. Тогда можно предложить алгоритм получения следующего двоичного числа прибавлением 1.
 
            i:=1;
            Пока Ci=1
             нц
            Сi:=0;
            i:=i+1;
            кц
            Ci:= Ci +1
 
            Здесь мы действовали из предположения, что число является N+1 разрядным и при первоначальной инициализации все цифры были обнулены.
 
Аналогично можно получать все N — разрядные числа в любой системе счисления (по основанию D). Необходимо модифицировать алгоритм для решения такой задачи.
 
В этих задачах решения построены на использовании в модели N  — разрядного целого числа в системе счисления по какому-либо основанию (2, 3, К) в качестве структуры данных выбран одномерный числовой массив. Однако такая модель и структура данных может использоваться для решения совершенно других по содержанию задач.
 
Задача 2.
 
Даны две емкости A и B литров соответственно. Имеется водопроводный кран и раковина (для выливания воды не на пол, а чтобы сухо было). Можно переливать воду из одной емкости в другую и наоборот, наполнять и опустошать каждую емкость. Необходимо найти такую последовательность, если она есть, названных действий, не превышающую N операций, в результате выполнения которой в одной из емкостей было бы отмерено ровно C литров.
 
Решение:
Составим список возможных действий и пронумеруем их:
0.      Налить в первую емкость A литров воды
1.      Налить во вторую емкость В литров воды
2.      Вылить воду из первой емкости в раковину
3.      Вылить воду из второй емкости в раковину
4.      Перелить воду из первой емкости во вторую
5.      Перелить воду из второй емкости в первую
 
Итого получили 6 действий, то есть 6 команд некоторого алгоритмического языка, специально разработанного для описания переливаний воды в двух емкостях. Заметьте, что с помощью этого языка можно описать и переливание воды из пустого в порожнее. Причем, мы можем не писать сами действия, а только ставить их номера. Например, последовательность — (2, 3, 4) — один из вариантов описания переливания из пустого в порожнее.  Здесь первые две команды опустошают емкости, а третья переливает воду из пустой первой емкости в пустую вторую.
Таким образом, мы получили способ записи искомых алгоритмов. То есть моделью алгоритма будет являться K — разрядное целое число, в системе счисления по основанию 6. А структура данных — тот же самый одномерный числовой массив.
Алгоритм получения всех целых чисел, представляемых как массив их цифр мы уже знаем, остается дополнить нашу задачу интерпретатором полученных алгоритмов переливаний. Если при интерпретации на каком-либо этапе в какой-либо емкости будет ровно C литров воды, то мы нашли нужный на алгоритм.
Пусть V1 и V2 — фактический объем воды в первом и втором сосудах соответственно. Посмотрим, как они изменяются при выполнении команд языка переливаний.
 
0.      V1=A
1.      V2=B
2.      V1=0
3.      V2=0
4.      если V1+V2<=B, то V2=V2+V1, V1=0, иначе V1=V1-V2+B, V2=B
5.      если V1+V2<=A, то V1=V1+V2, V2=0, иначе V2=V2-V1+A, V1=A
 
Первые 4 действия тривиальны, а оставшиеся требуют небольшого «объемного» воображения.
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
промокод связной