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

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

Войти
Регистрация
Восстановить пароль
 
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
#1

Генерация сочетаний - C++

25.06.2013, 17:26. Просмотров 1229. Ответов 0
Метки нет (Все метки)

Всем привет. Давеча решал вот эту задачку на генерацию сочетаний, казалось бы ничего сложного. Сперва решил делать рекурсией.

вот решение

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
#include <iostream>
 
using namespace std;
 
int k,n;
 
int s[100];
 
void seq_gen(int, int);
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    cin >> n >> k;
    
    seq_gen(0, 0);
    
    return 0;
}
 
void seq_gen(int lvl, int vmax)
{       
    if(lvl >= k)
    {
        for(int i = 0; i < k; ++i)
            cout << s[i] << " ";
        cout << endl;
    } else
    {   
        for(int j = vmax + 1; j <= n; ++j)
        {
            s[lvl] = j;
            seq_gen(lvl + 1, j);
        }
    }
}
получил time limit на 3х тестах. Я подумал что долго работает возможно из-за рекурсии, поэтому решил генерить сочетания последовательно. Соответственно получилось вот такое решение:

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
45
46
47
#include <iostream>
 
using namespace std;
 
int k,n;
 
int s[100];
 
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    cin >> n >> k;
    
    for(int i = 0; i < k; ++i)
        s[i] = i + 1;
        
    if(k > n) return 0;
    
    do
    {
        for(int i = 0; i < k; ++i)
            cout << s[i] << " ";
        cout << endl;
        
        
        if(++s[k - 1] <= n) continue;
        if(k == 1) break;
        
        int ind = -1;
        for(int i = k - 2; i >= 0; --i) 
            if(s[i] <= n - k + i)
            {
                ind = i;
                break;
            }
        
        if(ind == -1) break;
        
        ++s[ind];
        for(int i = ind + 1; i < k; ++i)
            s[i] = s[i - 1] + 1;
    } while(1);
    
    return 0;
}
и оно зашло, но у меня возник вопрос. Разве у алгоритмов не одинаковая асимптотическая сложность, я же ведь в лоб генерирую каждую перестановку, так почему 3 теста получили превышение по времени?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.06.2013, 17:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Генерация сочетаний (C++):

Генерация сочетаний из k элементов по n в лексикографическом порядке - C++
Помогите пожалуйста понять в чем ошибка #include&lt;iostream&gt; using namespace std; #define n 6 #define k 4 int x ; int...

Число сочетаний - C++
Уважаемые юзеры форума,помогите По данным натуральным n и k вычислите C^n_k = \frac{n!}{k! (n - k)!}

Число сочетаний из n по k - C++
Машинно ориентированное программирование.вычислить число сочетаний из н по к

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

Вычислить число сочетаний из n по m - C++
Задание &quot;Вычислить число сочетаний из n по m&quot; Вот формула: C_{n}^{m}=\frac{n!}{m!(n-m)!} Что тут не так ??? #include &lt;iostream&gt; ...

Нахождение числа сочетаний - C++
Прошу помочь: Подсчитать число сочетаний из чисел 1,2…,N£7 по M£N, сумма элементов которых не превосходит заданного числа S.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2013, 17:26
Привет! Вот еще темы с ответами:

Перебор неповторяющихся сочетаний - C++
Здравствуйте. Существует ли какая-нибудь функция на c++, которая перебирает все возможные перестановки без повторений элементов? например...

Вычислить число сочетаний из n по k - C++
Вычислить число сочетаний из n по k (k &lt;= n) по формуле

Вычислить число сочетаний из n по k - C++
Помогите решить это надо сделать простым для новичка но функцией и пожалуйста можете написать что делает элемент кода . Спасибо

Вычисление числа сочетаний из N по M - C++
Напишите программу для вычисления числа сочетаний из N по M. Число сочетаний определяется по формуле N!/(M!*(N-M)!, где N - количество...


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

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

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