ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеПримеры и задачи для самостоятельной работы > Примеры и задачи к теме "Задачи на перечисление"
Примеры и задачи к теме "Задачи на перечисление"
Упражнения
 
1. На основании построенной в методических рекомендациях модели для решения задачи 1, разработайте алгоритм решения задачи и реализуйте его на каком-либо языке программирования. 
 
2. Аналогично тому, как в методических указаниях описано перечисление всех двоичных чисел, можно получать и все N — разрядные числа в любой системе счисления (по основанию D). Модифицируйте алгоритм для решения такой задачи и реализуйте его в программе.
 
3. Разработайте алгоритм решения задачи 2. (о переливаниях) с использованием предложенной в методических указаниях модели данных и реализуйте его в виде программы. 
 
Задачи
 
1. Пусть в задаче 1. из методических указаний гири из разновеса можно устанавливать на обе чаши весов. Необходимо найти наборы гирь из разновеса, которые при установке на правую (где находится груз) и на левую (пустую) чаши весов приводили бы весы в состояние равновесия.
 
Указание. В данном случае гири из разновеса разбиваются на три кучки: первая — для правой чаши весов, вторая — не выбранные, третью для левой чаши весов. Получим троичную систему счисления с цифрами 0, 1, 2. Заметим, что здесь может быть применена так называемая троичная уравновешенная система счисления с цифрами -1, 0, 1, к которой легко перейти от обычной отняв от каждой из цифр 1. Однако, можно сразу получать числа в уравновешенной системе счисления (измените алгоритм). Условие равновесия весов останется в прежнем виде:  , здесь при установке гири в правую чашу весов (Ci=-1), ее вес будет отниматься от суммы весов на левой чаше, если гиря не выбрана (Ci=0), ее вес не учитывается. 
 
2. Напишите программу, которая бы выдавала на печать все возможные разбиения множества из N элементов на K непересекающихся подмножеств. 
 
3. Эта задача является несколько усложненным вариантом задачи о переливаниях (задача 2 из методических указаний). В безалкогольном баре работает вороватый бармен, имеющий остатки совести. Для получения «левого» дохода он разбавляет сок. Однако совесть ему не позволяет разбавлять сок более чем на одну четверть. В баре имеются краны с соком и водой, раковина и две емкости (A и B миллилитров соответственно). Написать программу, которая позволяет найти последовательность переливаний для того чтобы отмерять в одной из емкостей С миллилитров сока разбавленного не более чем на четверть, если это возможно, менее чем за 10 операций. При этом сок в раковину выливать нельзя, разбавленный сок выливать обратно в емкость для хранения тоже нельзя. Если последовательность найти не удалось, то выдавайте сообщение: «Лучше обсчитай!»
 
4. В математическом ночном клубе проводится лотерея входных билетов. Билет считается выигрышным, если сумма цифр его N — разрядного номера является простым числом. Простое число такое, которое делится без остатка только на 1 и на само себя. Найти номера всех выигрышных билетов. 
 
5. Последовательность из N чисел от 0 до N-1 является перестановкой этих чисел, если каждое число встречается в ней только один раз. Написать программу, генерирующую все возможные перестановки N чисел. При проверке программы вводите N не более 5, а для N=2 и 3, выпишите возможные перестановки вручную и сравните с результатами работы программы.
 
Указание. Можно получать все N — разрядные числа в системе счисления по основанию N и выбирать из них только те, в которых все элементы различные. Этот метод не оптимальный, но достаточно простой. Для проверки, что все цифры различные, можно последовательность отсортировать по возрастанию, тогда одинаковые числа будут стоять рядом и их можно легко обнаружить. 
 
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске