|
|||||
Олимпиадные задачи по программированию.ПЕРЕБОРНЫЕ ЗАДАЧИ. Задача 1. Построить алгоритм, выдающий без повторений все перестановки N чисел. Задача 2 Сгенерировать все подмножества данного n-элементного множества {0,..., n-1}. Задача 3. Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}. Пример: N=3, k=2, подмножества {1,2}, {1,3}, {2,3}. Задача 4.1. Во время поездки на поезде девочка заменила в названии поезда каждую букву ее номером в русском алфавите и получила запись из единиц и двоек "211221-21221". Определить откуда и куда идет поезд? Задача 4.2. Дана строка S и набор A слов А[1], ..., A[k]. Разбить строку S на слова набора всеми возможными способами. Пример: S=ABBC A[1]=A, A[2]=AB, A[3]=BC, A[4]=BBC, A[5]=H, A[6]=B S = A B BC = A BBC = AB BC Задача 5. Данные N косточек домино по правилам игры выкладываются в прямую цепочку, начиная с косточки, выбранной произвольно,в оба конца до тех пор, пока это возможно. Построить алгоритм, позволяющий определить такой вариант выкладывания заданных косточек, при котором к моменту, когда цепочка не может быть продолжена, "на руках" останется максимальное число очков. Задача 6. a) В написанном выражении ((((1?2)?3)?4)?5)?6 вместо каждого знака ? вставить знак одной из 4 арифметических операций +,-,*,/ так, чтобы результат вычислений равнялся 35 (при делении дробная часть в частном отбрасывается). Найти все решения. б) Вводится строка не более чем из 6 цифр и некоторое целое число R. Расставить знаки арифметических операций ("+", "-", "*", "/"; минус не является унарным, т.е. не может обозначать отрицательность числа; деление есть деление нацело, т.е. 11/3=3) и открывающие и закрывающие круглые скобки так, чтобы получить в результате вычисления получившегося выражения число R. Лишние круглые скобки ошибкой не являются. Например: Строка 505597, R=120: ((5+0)*((5*5)-(9/7)))=120. Задача 7. Построить все слова длины n>0 в алфавите скобок "(" и ")", представляющие правильные скобочные записи. Задача 8. Составить программу, которая печатает все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел (N, K-вводятся, 1<K<N ). Если К=0, то выдать все возможные произведения (суммы). Представления чисел, отличающихся только порядком сомножителей (слагаемых), считаются одинаковыми. |