Формат входных данных:
В первой строке входного файла записано целое число: N – количество имеющихся элементов. В следующих N строках записаны названия элементов. (0<N<=100)
Формат выходных данных:
Выходной файл должен содержать перечень всех возможных вариантов смешивания по одному варианту в строке. Вариант смешивания задается перечнем номеров исходных элементов, записанных через пробел. Варианты могут быть выведены в произвольном порядке.
Пример:
INPUT.TXT OUTPUT.TXT
3
сера
пепел
растертый зуб вампира 1
2
3
1 2
1 3
2 3
1 2 3
Рекомендации к решению. Еще одна классическая задача комбинаторики. Если отвлечься от Гарри Поттера и его друзей, то задача читается так: «Необходимо сгенерировать все подмножества данного N-элементного множества». Один из наиболее популярных методов ее решения заключается в использовании двоичных чисел. Заведем массив А[1..N]. Будем обозначать А[к]=1, если вещество с номером к входит в состав смеси и А[к]=0, если не входит. Таким образом, все возможные сочетания веществ задаются последовательностями длиной N, состоящими из нулей и единиц, т.е. двоичными числами от 0 до 2N-1. Здесь 0 обозначает «пустую» смесь, в которую не входит ни одно вещество.
В первой строке входного файла записано целое число: N – количество имеющихся элементов. В следующих N строках записаны названия элементов. (0<N<=100)
Формат выходных данных:
Выходной файл должен содержать перечень всех возможных вариантов смешивания по одному варианту в строке. Вариант смешивания задается перечнем номеров исходных элементов, записанных через пробел. Варианты могут быть выведены в произвольном порядке.
Пример:
INPUT.TXT OUTPUT.TXT
3
сера
пепел
растертый зуб вампира 1
2
3
1 2
1 3
2 3
1 2 3
Рекомендации к решению. Еще одна классическая задача комбинаторики. Если отвлечься от Гарри Поттера и его друзей, то задача читается так: «Необходимо сгенерировать все подмножества данного N-элементного множества». Один из наиболее популярных методов ее решения заключается в использовании двоичных чисел. Заведем массив А[1..N]. Будем обозначать А[к]=1, если вещество с номером к входит в состав смеси и А[к]=0, если не входит. Таким образом, все возможные сочетания веществ задаются последовательностями длиной N, состоящими из нулей и единиц, т.е. двоичными числами от 0 до 2N-1. Здесь 0 обозначает «пустую» смесь, в которую не входит ни одно вещество.
Последнее изменение: Суббота, 15 Август 2020, 02:35