Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.98/56: Рейтинг темы: голосов - 56, средняя оценка - 4.98
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
1

Комбинаторика на С++

22.04.2013, 20:48. Показов 10101. Ответов 21
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Нужно составить программу, или скорее функцию, которая для заданного натурального числа 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.04.2013, 20:48
Ответы с готовыми решениями:

Комбинаторика
Привет. Есть 4 елемента А,Б,В,Г. Как можно узнать сколько способов расположить эть элементы есть,...

Комбинаторика
В общем, изучаю комбинаторику в данный момент.Тема "Перестановки". Задание следующее: Hапечатать...

Комбинаторика
Очень прошу помочь в решении задач по комбинаторике. :gcray: Совсем не могу понять эти теории...

Комбинаторика
Лототрон содержит 500 шаров с номерами. Из него выбирают шар, номер которого записывают. Шар...

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
Диссидент
Эксперт C
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
Диссидент
Эксперт C
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
Диссидент
Эксперт C
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
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
22.04.2013, 21:29 11
Цитата Сообщение от Buckstabue Посмотреть сообщение
на то место, где переполняется разряд
Вот как это место определить? Но идея здравая. Надо подумать... И не будет ли там слишком много повторов... Сейчас с ходу не соображу...
0
7 / 7 / 1
Регистрация: 22.12.2012
Сообщений: 173
22.04.2013, 21:40  [ТС] 12
наткнулся на идею что может сделать что-то связанное с матрицей, если например записать для k = 2 матрицу

11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 43
тогда те числа которые нам нужны будут в правом верхнем треугольнике матрицы, над главной диагональю
но если будет k = 5 или 10, там будет проблемно... там получается k-мерная матрица, тоже ни к чему(
0
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
22.04.2013, 21:45 13
Цитата Сообщение от gorus95 Посмотреть сообщение
если например k = 3 тогда 123, 124, 234
вообще то будет
123
124
134
234

вот мой код. хреновый, конечно, но для понимания подойдет. принцип как написал Buckstabue
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool increase(vector<int> &vec, const int n)
{
    for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); it++)
        if (*it + 1 <= n && find(vec.begin(), vec.end(), *it + 1)==vec.end()  ) {
            ++*it;
            return true;
        }
    return false;
}
 
void print(const vector<int> &vec)
{
    for (size_t i = 0; i != vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
    // сочетания из n по k без повторений
    int n = 5;
    int k = 3;
    vector<int> vec(k);
    for (size_t i = 0; i != n; i++)
        vec[i] = i + 1;
    print(vec);
 
    while (increase(vec, n) )
        print(vec);
 
    return 0;
}
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
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
22.04.2013, 21:55 16
Цитата Сообщение от gorus95 Посмотреть сообщение
наткнулся на идею
Идея, конечно, симпатичная, но крайне не эффективная. Вы предлагаете рассматривать все 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, вот рабочий код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool increase(vector<int> &vec, const int n)
{
    for (int i = vec.size() - 1; i >= 0; i--)
        if ( vec[i] + 1 <= n && find(vec.begin() + i + 1, vec.end(), vec[i] + 1) == vec.end() ) {
                ++vec[i];
 
            for (int j = i + 1; j < vec.size(); j++)
                vec[j] = vec[j - 1] + 1;
            return true;
        }
    return false;
}
 
void print(const vector<int> &vec)
{
    for (size_t i = 0; i != vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
    // сочетания из n по k без повторений
    int n = 6;
    int k = 4;
    vector<int> vec(k);
    for (size_t i = 0; i != n; i++)
        vec[i] = i + 1;
 
 
    print(vec);
 
    while (increase(vec, n) )
        print(vec);
 
    return 0;
}
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, вот Вам без алгоритмов:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
 
using namespace std;
 
bool increase(vector<int> &vec, const int n)
{
    for (int i = vec.size() - 1; i >= 0; i--)
        if ( vec[i] + 1 <= n ) {
            if ( i != vec.size() - 1 && vec[i + 1] == vec[i] + 1 )
                continue;
            ++vec[i];
 
            for (int j = i + 1; j < vec.size(); j++)
                vec[j] = vec[j - 1] + 1;
            return true;
        }
    return false;
}
 
void print(const vector<int> &vec)
{
    for (size_t i = 0; i != vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
    // сочетания из n по k без повторений
    int n = 10;
    int k = 8;
    vector<int> vec(k);
    for (size_t i = 0; i != k; i++)
        vec[i] = i + 1;
 
    print(vec);
 
    while (increase(vec, n) )
        print(vec);
 
    return 0;
}
0
22.04.2013, 22:57
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.04.2013, 22:57
Помогаю со студенческими работами здесь

Комбинаторика
Здравствуйте! Помогите, пожалуйста, разобраться. Не могу правильно решить одну из задач. Вот та,...

комбинаторика
1.шары 1,2,3...15 разместить в ряд так, что шары с парным намером лежат на непарных местах 2.10...

комбинаторика)
помогите разобраться с задачами: 1) в коробке 8 одинак. изделий, причем половина из них окрашены....

Комбинаторика
Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru