Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
#1

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

22.04.2013, 20:48. Просмотров 2187. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2013, 20:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Комбинаторика на С++ (C++):

Комбинаторика - C++
Здравствуйте все. В данный момент дпополнительно решил заняться комбинаторикой, столкнулся с задачей, и никак не могу её решить.Суть...

Комбинаторика - C++
От пользователя требуется ввести n. Результат должен быть таким:

Комбинаторика - C++
Помогите написать алгоритм для вычисления количество непустых последовательностей из ряда чисел. Или кинте ссылочку, где почитать. Что я...

Комбинаторика - C++
Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит...

комбинаторика - C++
Здравствуйте! Я решаю задачи по дискретной математике на языке С.В интернете масса примеров задач на тему комбинаторики, но на языке...

Комбинаторика style - C++
Здравствуйте, помогите разобраться с задачей по комбинаторике. Условие: http://codeforces.com/problemset/problem/630/F Решение: ...

21
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
22.04.2013, 20:49 #2
Вам нужны не перестановки, а сочетания из n по k (без повторений)
0
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
22.04.2013, 20:55  [ТС] #3
Olivеr, не знал как правильно сказать...
можете помочь?
0
Байт
Эксперт C
16555 / 10825 / 1640
Регистрация: 24.12.2010
Сообщений: 20,910
22.04.2013, 20:57 #4
Найти все возможные перестановки цифр
0
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
22.04.2013, 21:01  [ТС] #5
Байт, спасибо. но мне нужно без повторений, и чтоб каждая следующая цифра была больше предыдущей.
никак не получается написать
0
Байт
Эксперт C
16555 / 10825 / 1640
Регистрация: 24.12.2010
Сообщений: 20,910
22.04.2013, 21:08 #6
gorus95, Извиняюсь, там были перестановки, а у вас - сочетания. Тоже было где-то, сам участвовал ...
Но могу посоветовать такую книжонку - Липский В. "Комбинаторика для программистов". Наверное, сегодня есть что-то и посвежее.
Но вообще-то задача классическая. Поищите.
0
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
22.04.2013, 21:10  [ТС] #7
Байт, пытаюсь найти, но ничего пока нету, уже немало ищу
если найдете, буду благодарен
0
Байт
Эксперт C
16555 / 10825 / 1640
Регистрация: 24.12.2010
Сообщений: 20,910
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%BE%D1...86%D0%B8%D1%8F
1
Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
22.04.2013, 21:19 #9
Сейчас времени нет, но я бы рассматривал n как основание сиситемы счисления, далее бы по умолчанию инициализировал массив из k элементов числами от 1 до n(или как можно ближе к этому). Далее бы увеличивал это число в этой системе счисления на 1, при этом при любом переполнении разряда, ставил бы на то место, где переполняется разряд, значение предыдущего(более левого разряда) + 1. Если перполняется самый первый разряд, то выход. Как-то так. Наверное, не самое эффективное решение... И не знаю работает ли
Ну и при переполнии разряда естественно по мере надобности инкрементировать все последующие более правые разряды
2
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
22.04.2013, 21:28  [ТС] #10
в общем у меня задача вычислить коэффициенты многочлена, если известны его корни, по формуле Виета
но чтоб это сделать для i-того коэффициента нужно сделать сумму таких перестановок корней
вот беда(
0
Байт
Эксперт C
16555 / 10825 / 1640
Регистрация: 24.12.2010
Сообщений: 20,910
22.04.2013, 21:29 #11
Цитата Сообщение от Buckstabue Посмотреть сообщение
на то место, где переполняется разряд
Вот как это место определить? Но идея здравая. Надо подумать... И не будет ли там слишком много повторов... Сейчас с ходу не соображу...
0
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
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
Olivеr
412 / 408 / 13
Регистрация: 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
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 153
Завершенные тесты: 1
22.04.2013, 21:47  [ТС] #14
можно бы сделать через цикл в цикле, но опять же, если k = 5 или 10 то надо будет столько же циклов в цикле..

Добавлено через 1 минуту
Olivеr, сейчас посмотрю
а можно как-то сделать без векторов и алгоритмов?
0
Olivеr
412 / 408 / 13
Регистрация: 06.10.2011
Сообщений: 832
22.04.2013, 21:48 #15
не смотрите, код неправильно работает, щас попробую исправить
0
22.04.2013, 21:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2013, 21:48
Привет! Вот еще темы с ответами:

Перестановка.(Комбинаторика) - C++
Прошу помощи. Объясните пожалуйста тугодуму этот код. Какой день его пытаюсь понять. Не как не могу в нём разобраться. Вроде знаю как...

Комбинаторика в программировании - C++
есть алфавит длинны Х; длинна слова Y; написать код(лучше на с++) который будет составлять и выводить все возможные варианты слов. ...

Покерная комбинаторика - C++
Добрый день, форумчане. Рад возможности стать членом общества программистов. Я чайник на все 234%. Болею задачей создания покерной...

Комбинаторика. Сочетания - C++
Добрый день! Прошу помочь со следующей задачкой: генерация сочетания по номеру(порядок лексикографический). Толковое объяснение нашел...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru