|
|
 |
Условие
Напечатать все последовательности длины n из чисел в диапазоне от 0 до k-1 в лексикографическом порядке.
Входные данные
Два числа - n и k (1<=n<=10, 2<=k<=10, nk<=10000).
Выходные данные
В каждой строке вывести n чисел через пробел - запись соответствующего размещения с повторением.
Пример
|
Входной файл |
Выходной файл |
|
2 2 |
0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
|
Также доступны документы в формате DOC
Решение
Решение задачиРешение, тесты, проверяющая программа
Рассмотрим последовательности из трех чисел, в которых каждый член - целое число в диапазоне от 0 до 2. Как перебрать все такие последовательности?
Для решения этой и подобных задач перебора всех объектов из некоторого множества обычно применяют такой подход: сначала упорядочивают все элементы данного множества, а потом учатся переходить от одного элемента к следующему.
Как упорядочить все такие числовые последовательности? Представим на минуту, что у нас есть не последовательности чисел, а наборы букв ("слова"). Тогда один из естественных способов упорядочить их - воспользоваться алфавитом и расположить их в такой последовательности, в какой они встречаются в словаре (такой порядок называют лексикографическим). Теперь давайте вернемся к числам. Упорядочим их также "по алфавиту": сначала будут идти последовательности, начинающиеся с нуля, затем - с единицы, и в конце - с двойки. Среди всех последовательностей, начинающихся с нуля, в начале будут стоять последовательности, в которых второй член - 0, затем те, у которых второй член - 1, и затем - 2. Вот как в итоге будет выглядеть полный список последовательностей:
000 001 002 010 011 012 020 021 022 100 101 102 110 111
112 120 121 122 200 201 202 210 211 212 220 221 222
Упорядочив все последовательности, можем перейти к следующему этапу решения задачи: научимся по данной последовательности получать следующую. Если последняя цифра данной последовательности - не 2, то для получения следующей последовательности достаточно просто увеличить последнюю цифру на 1: например, 021 → 022. Если же последовательность заканчивается на 2, то нужно заменить последнюю двойку и все стоящие перед ней на 0, а самую правую цифру, отличную от 2, увеличить на 1: например, 022 → 100.
Теперь, пользуясь изложенным, можно составить алгоритм для перебора всех размещений с повторениями (так называют такие последовательности): берем самое первое размещение (000), и строим по нему следующее. Эту процедуру повторяем до тех пор, пока не дойдем до последнего размещения (222).
Заметим, что полученные последовательности можно трактовать как записи чисел в соответствующей системе счисления. Тогда операция перехода к следующей последовательности приобретает смысл прибавления к числу единицы.
Трюк. Возникает справедливый вопрос: когда нужно остановится? Напрашивающийся ответ "Когда дойдем до последовательности 2 2 2" не совсем удовлетворительный: ведь если взять более длинные последовательности, то на проверку всех ее членов на каждом шаге будет уходить слишком много времени.
Можно прибегнуть к такому трюку: добавим к последовательности слева еще одно число. Изначально оно будет нулем, и мы будем проверять только его. Тогда сигналом для остановки будет появление на этой позиции единицы: 0222 → 1000.
Также доступны документы в формате DOC
