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

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

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

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

22.04.2013, 20:48. Просмотров 2175. Ответов 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
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
22.04.2013, 21:55 #16
Цитата Сообщение от gorus95 Посмотреть сообщение
наткнулся на идею
Идея, конечно, симпатичная, но крайне не эффективная. Вы предлагаете рассматривать все kn комбинаций, выбрасывая из них те, которые не являются сочетаниями, т.е. содержат повторы. Сочетаний-то в самом деле, значительно меньше.
И я толком не понимаю, что вам мешает пройтись по ссылочкам, приведенным в посте #8. Там алгоритмы в несколько строчек.
0
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 152
Завершенные тесты: 1
22.04.2013, 22:03  [ТС] #17
Байт, не совсем понимаю как работать с теми алгоритмами, т.к. с <vector> и <algorithm> работать пока не умею
0
Olivеr
412 / 408 / 13
Регистрация: 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
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 152
Завершенные тесты: 1
22.04.2013, 22:39  [ТС] #19
Olivеr, спасибо
0
Olivеr
412 / 408 / 13
Регистрация: 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
Байт
Эксперт C
16545 / 10815 / 1639
Регистрация: 24.12.2010
Сообщений: 20,864
22.04.2013, 23:21 #21
Достали.
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
#include <stdio.h>
#include <alloc.h>
#include <stdio.h>
int main(int ac, char *av[])
{  int n, k, i, j, *A;
  if (ac<2) { n = 6; k = 4; }
  else {
    n = atoi(av[1]);
    k = n - 2;
  }
  if (ac >= 3) k = atoi(av[2]);
  if (n < k) return 1;
  A = (int *) malloc(k*sizeof(int));
  for(i=0; i<k; i++) A[i] = i;
  while(1) {
    for(i=0; i<k; i++) printf("%d ", A[i]);
    printf("\n");
    if (A[k-1] < n-1) { A[k-1]++; continue; }
    for(i=k-1; i>0; i--) {
      if (A[i] == A[i-1]+1) continue;
      A[i-1]++;
      for(j=i; j<k; j++) A[j] = A[j-1]+1;
      break;
    }
    if (i==0) break;
  }
  return 0;
}
Добавлено через 1 минуту
Вызов программы proga.exe n k
3
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 152
Завершенные тесты: 1
23.04.2013, 00:06  [ТС] #22
Байт, вот то что надо)
0
23.04.2013, 00:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.04.2013, 00:06
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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