0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
|
||||||
1 | ||||||
Вывести всевозможные комбинации из n-чисел размером k08.10.2014, 00:00. Показов 19916. Ответов 14
Метки нет (Все метки)
Вводим в программе n и k
n - кол-во цифр (1, 2, 3,...,n) k - длинна выводимой комбинации (если k=3, то должны получать 123, 124, 125..и тд) Цифры в комб. должны идти по возростанию Через итерацию либо рекурсию нужно проделать вывод всех возможных таких комбинаций Понятное дело что код нужно строить через внутренние цыклы, но у меня руки дошли писать кол-во циклов равное k
Буду крайне благодарен за помощь
0
|
08.10.2014, 00:00 | |
Ответы с готовыми решениями:
14
Сформируйте всевозможные комбинации K-значных чисел Из указанных чисел сгенерировать всевозможные комбинации Вывести на экран всевозможные комбинации кроликов и гусей Вывести на экран всевозможные комбинации кроликов и гусей |
Guardian of Asgaard
377 / 319 / 197
Регистрация: 11.11.2013
Сообщений: 1,046
|
|
08.10.2014, 01:57 | 2 |
Не понятно, что точно нужно сделать. Навскидку - длиной k можно обозначить размер массива, указав в нём элементы n.
0
|
1978 / 1082 / 87
Регистрация: 29.11.2013
Сообщений: 3,353
|
|
08.10.2014, 02:11 | 3 |
Хм, интересно как это будет выглядеть на сишеньке. На лиспе у меня ушло 5 минут, 24 строчки (учитывая форматирование и комментарии). Алгоритм следующий (хотя у меня немного другой, но в итоге тот же):
1. формируем сочетания из n по k. 2. из каждого сочетания формируем число 3. отфильтровываем числа, меньшие чем 10^(k - 1) (это возможно если в множестве n есть 0) 4. сортируем по возростанию. Например, есть множество n = {1,2,3} и k = 2, сочетания: {1,2} -> 12 {1,3} -> 13 ... {3,2} -> 32. Добавлено через 1 минуту ну и множество n соответственно должно быть не более 10 (0..9).
0
|
08.10.2014, 06:24 | 4 | |||||
Сообщение было отмечено Emisare как решение
Решение
вот сочетания или "цэшки"
не понял - 12 и 21 - у тебя должны быть разные сочетания или одно и то же? можно так и так делать
1
|
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
|
|
27.10.2014, 16:08 [ТС] | 5 |
все же, хочу понять как можно реализовать данную задачу без рекурсии
именно чистой итерацией
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
|
||||||
27.10.2014, 21:45 | 6 | |||||
Без рекурсии
При этом пользоваться вот этими битовыми трюками не обязательно. Там же по ссылке описан алгоритм, как от одного подмножества размера K перейти к следующему подмножеству. Добавлено через 2 минуты Ну во-первых, понятно, что k <= n. Иначе задача не имеет решения. А во-вторых, что вы предлагаете использовать в качестве цифр для n=20? Для n=100? Для n=1024?
1
|
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
|
|
27.10.2014, 22:07 [ТС] | 7 |
ну, по условию, для n=100 и тд, мы используем все числа от 2 до 100, но так же можно ограничить n в дефайне, что бы не переусердствовать.
думаю, что битовые операции мне стоит переделать за ссылку - спасибо Добавлено через 9 минут и все же меня попросили сделать задачу без дополнительных вызовов функции в мейне
0
|
Boleon
|
27.10.2014, 23:56
#8
|
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
|
|
28.10.2014, 02:49 | 9 |
Никто вам не мешает скопировать текст функции прямо в 'main' и тем самым избавиться от вызова.
0
|
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
|
|
05.11.2014, 23:15 [ТС] | 10 |
Кстати, ваш способ ефективен только для n<10
Для реализации задачи полностью, мне посоветовали взять 2 цикла while Сначало заполним первую последовательность как 5 6 7 8 9 при n=9, k=5 а дальше будем уменьшать по очереди елементы например дальше будет 4 6 7 8 9 3 6 7 8 9 и так до 1 2 3 4 5 Реализовать пока не получается, но способ довольно простой
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
|
|
05.11.2014, 23:30 | 11 |
Мой способ эффективен для любого значения N.
Моя реализация работает только для N, которое не превышает разрядности максимального целочисленного типа на платформе. Все что надо сделать, это договориться, что мы будем использовать для представления "цифр" при N > 10 и подправить код соотв. образом. Если N превышает разрядность максимального целочисленного типа на платформе, то придется обойтись без битовых операций, а реализовывать алгоритм перечисления подмножеств, как описано по ссылке в Википедии. В обоих случаях мы получаем очень эффективные алгоритмы. Добавлено через 2 минуты Ну раз простой, то и реализовать его должно быть несложно, так? Но выглядит перспективно. В принципе, почему бы не идти по возрастанию от 12345, 12346, ..., 12349, 12356, 12357, ..., 56789?
0
|
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
|
|
05.11.2014, 23:34 [ТС] | 12 |
Для меня ваш подход совсем незнаком
В моей ситуации можно пожертвовать эффективностью Главное - работоспособность и адекватный вывод при любом значение n
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
|
||||||
05.11.2014, 23:56 | 13 | |||||
Тут нет никакого жертвования. Ваш алгоритм действительно эффективнее моего. Вот моя реализация вашего алгоритма в восходящей версии
1
|
0 / 0 / 0
Регистрация: 14.05.2014
Сообщений: 29
|
|
06.11.2014, 00:00 [ТС] | 14 |
вариант с циклом for тут более уместен чем while кстати
благодарю за реализацию
0
|
Вездепух
11696 / 6375 / 1724
Регистрация: 18.10.2014
Сообщений: 16,073
|
|
13.11.2014, 22:59 | 15 |
del
0
|
13.11.2014, 22:59 | |
13.11.2014, 22:59 | |
Помогаю со студенческими работами здесь
15
Найти всевозможные комбинации чисел, которые можно получить из одного числа Всевозможные комбинации Составить всевозможные комбинации трех букв Как посчитать всевозможные комбинации строки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |