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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Объясните человеческим языком мне чайнику что такое singleton, статический класс. Зачем они нужны. Что рекомендуете прочитать мне для начала http://www.cyberforum.ru/cpp-beginners/thread911728.html
Объясните человеческим языком мне чайнику что такое singleton, статический класс. Зачем они нужны. Что рекомендуете прочитать мне для начала.
C++ Оператор == char ch = 255; if(ch==255) cout<<"Hello!"; Почему условие выдаёт false? Понятно что ch в данном случае равно -1 из-за переполнения, но если сравнивать побитово то эти выражения равны! Почему так? http://www.cyberforum.ru/cpp-beginners/thread911727.html
Что означает данная строчка кода? C++
#define MASSIZE(x) (sizeof(x)/sizeof(x)) можете пожалуйста объяснить что это значит?
C++ Автораспознавание капчи
Нужно создать прграмму,что бы она могла распознавать такую капчу как в вложении.Все это нужно чтобы создать полностю автоматический автокликер.Автокликер уже создан,и распознает капчу со звездочками(см вложение).Но мне нужно его усовершенствовать что б он распознавал капчу также с примерами см вложение.Помогите ,плиз!
C++ Объясните умственно отсталому как сделать элементарную вещь в списке http://www.cyberforum.ru/cpp-beginners/thread911718.html
Добрый день, спасибо что зашли в эту тему. Сколько я ни пытался лазить по разным сайтам, темам, я никак не могу понять как этим списком пользоваться. Копирую код - всё работает чудесно, но пытаюсь отредактировать под свою задачу - ничего не получается. Объясните мне, пожалуйста: Как при проверке истинности условия в цикле программа может занести в список значение переменной, а потом вывести...
C++ пдскажите какой ответ получится в итоге,а то у меня не запускается! #include"stdafx.h" #include<iostream> using namespace std; int main() { int x,y; x=100; y=560; y=y%x-6; if (y==0) {cout<<y+9;} подробнее

Показать сообщение отдельно
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110

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

25.06.2013, 17:26. Просмотров 1133. Ответов 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 теста получили превышение по времени?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru