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

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

Восстановить пароль Регистрация
 
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
25.06.2013, 17:26     Генерация сочетаний #1
Всем привет. Давеча решал вот эту задачку на генерацию сочетаний, казалось бы ничего сложного. Сперва решил делать рекурсией.

вот решение

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 теста получили превышение по времени?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.06.2013, 17:26     Генерация сочетаний
Посмотрите здесь:

Программу для поиска сочетаний в С. C++
C++ Число сочетаний
Перебор неповторяющихся сочетаний C++
Число сочетаний из n по k C++
C++ Генерация сочетаний из k элементов по n в лексикографическом порядке
C++ Вычислить число сочетаний из n по m
Программа генерации сочетаний C++
C++ Нахождение числа сочетаний

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 05:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru