7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
1 | |
Комбинаторика на С++22.04.2013, 20:48. Показов 10101. Ответов 21
Метки нет (Все метки)
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит все возможные произведения k чисел с числами от 1 до n, где каждое следующее число больше предыдущего.
Понимаю что объяснение не очень, попробую показать на примере: допустим наше n = 4, тогда у нас есть числа 1, 2, 3, 4. при k = 1 программа должна выдать 1, 2, 3, 4 пусть k = 2, тогда программа должна выдать 12, 13, 14, 23, 24, 34 если например k = 3 тогда 123, 124, 234 если k = n тогда будет одна комбинация из всех чисел n, то есть в нашем случае 1234 помогите сделать программу которая для любого натурального n и k даст такие перестановки (желательно без использования algorithm, vector и т.д.) уже третий час сижу, что-то не получается...
0
|
22.04.2013, 20:48 | |
Ответы с готовыми решениями:
21
Комбинаторика Комбинаторика Комбинаторика Комбинаторика |
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
|
22.04.2013, 20:49 | 2 |
Вам нужны не перестановки, а сочетания из n по k (без повторений)
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 20:55 [ТС] | 3 |
Olivеr, не знал как правильно сказать...
можете помочь?
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
22.04.2013, 20:57 | 4 |
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 21:01 [ТС] | 5 |
Байт, спасибо. но мне нужно без повторений, и чтоб каждая следующая цифра была больше предыдущей.
никак не получается написать
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
22.04.2013, 21:08 | 6 |
gorus95, Извиняюсь, там были перестановки, а у вас - сочетания. Тоже было где-то, сам участвовал ...
Но могу посоветовать такую книжонку - Липский В. "Комбинаторика для программистов". Наверное, сегодня есть что-то и посвежее. Но вообще-то задача классическая. Поищите.
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 21:10 [ТС] | 7 |
Байт, пытаюсь найти, но ничего пока нету, уже немало ищу
если найдете, буду благодарен
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
22.04.2013, 21:16 | 8 |
Это раз
http://e-maxx.ru/algo/generating_combinations Два http://www.prog.org.ru/topic_744_0.html Три http://forum.sources.ru/index.php?showtopic=330364 (кстати, из Липского) Добавлено через 51 секунду http://lmgtfy.com/?q=%D1%81%D0... 0%B8%D1%8F
1
|
179 / 127 / 25
Регистрация: 12.01.2012
Сообщений: 623
|
|
22.04.2013, 21:19 | 9 |
Сейчас времени нет, но я бы рассматривал n как основание сиситемы счисления, далее бы по умолчанию инициализировал массив из k элементов числами от 1 до n(или как можно ближе к этому). Далее бы увеличивал это число в этой системе счисления на 1, при этом при любом переполнении разряда, ставил бы на то место, где переполняется разряд, значение предыдущего(более левого разряда) + 1. Если перполняется самый первый разряд, то выход. Как-то так. Наверное, не самое эффективное решение... И не знаю работает ли
Ну и при переполнии разряда естественно по мере надобности инкрементировать все последующие более правые разряды
2
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 21:28 [ТС] | 10 |
в общем у меня задача вычислить коэффициенты многочлена, если известны его корни, по формуле Виета
но чтоб это сделать для i-того коэффициента нужно сделать сумму таких перестановок корней вот беда(
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 21:40 [ТС] | 12 |
наткнулся на идею что может сделать что-то связанное с матрицей, если например записать для k = 2 матрицу
но если будет k = 5 или 10, там будет проблемно... там получается k-мерная матрица, тоже ни к чему(
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
22.04.2013, 21:45 | 13 | |||||
вообще то будет
123 124 134 234 вот мой код. хреновый, конечно, но для понимания подойдет. принцип как написал Buckstabue
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 21:47 [ТС] | 14 |
можно бы сделать через цикл в цикле, но опять же, если k = 5 или 10 то надо будет столько же циклов в цикле..
Добавлено через 1 минуту Olivеr, сейчас посмотрю а можно как-то сделать без векторов и алгоритмов?
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
|
22.04.2013, 21:48 | 15 |
не смотрите, код неправильно работает, щас попробую исправить
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
22.04.2013, 21:55 | 16 |
Идея, конечно, симпатичная, но крайне не эффективная. Вы предлагаете рассматривать все kn комбинаций, выбрасывая из них те, которые не являются сочетаниями, т.е. содержат повторы. Сочетаний-то в самом деле, значительно меньше.
И я толком не понимаю, что вам мешает пройтись по ссылочкам, приведенным в посте #8. Там алгоритмы в несколько строчек.
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 22:03 [ТС] | 17 |
Байт, не совсем понимаю как работать с теми алгоритмами, т.к. с <vector> и <algorithm> работать пока не умею
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
22.04.2013, 22:35 | 18 | |||||
gorus95, вот рабочий код
0
|
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
|
|
22.04.2013, 22:39 [ТС] | 19 |
Olivеr, спасибо
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
22.04.2013, 22:57 | 20 | |||||
gorus95, вот Вам без алгоритмов:
Кликните здесь для просмотра всего текста
0
|
22.04.2013, 22:57 | |
22.04.2013, 22:57 | |
Помогаю со студенческими работами здесь
20
Комбинаторика комбинаторика комбинаторика) Комбинаторика Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |