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

Супер-быстрый перебор - C++

Восстановить пароль Регистрация
 
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
24.07.2012, 21:11     Супер-быстрый перебор #1
Используя минимальное количество библиотек(Вместо iostream - stdio.h) сделать рекурсивный перебор:

Найти количество N-значных натуральных чисел, сумма цифр у каждого из которых равняется M. N и M заданные натуральные числа.

Технические условия
Входные данные.

В строке файла записаны значения N и M. (1<=N<=100, 1<=M<=900).

Выходные данные.

Вывести найденное количество чисел.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.07.2012, 21:11     Супер-быстрый перебор
Посмотрите здесь:

C++ Быстрый Вопрос
C++ Супер простой вопрос
C++ быстрый xor
Супер Программа C++
Быстрый поиск C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
24.07.2012, 21:14     Супер-быстрый перебор #2
Тут комбинаторика(или динамика), перебор не пройдет.
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
24.07.2012, 23:40  [ТС]     Супер-быстрый перебор #3
ДП? Нужна работа с массивами?

Добавлено через 1 час 28 минут
Так каков алгоритм вычислений?
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
25.07.2012, 00:17     Супер-быстрый перебор #4
Для начала предлагаю разработать критерий, проверяющий, существуют ли вообще такие числа для заданных N и M. Сама такая проверка уже даст некое начальное понимание сути проблемы, отталкиваясь от которого, можно продолжать решение далее.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 13:11     Супер-быстрый перебор #5
Набросал решение, проверил весьма бегло.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <string>
#include <iomanip>
#include <cstdlib>
 
class BigInteger
{   
public:
 
    BigInteger();   
    BigInteger( const std::string& );
    BigInteger( long long );
    
    BigInteger& operator = ( const BigInteger& );
    BigInteger& operator += ( const BigInteger& );
    
    friend BigInteger operator + ( const BigInteger&, const BigInteger& );
    
    friend std::istream& operator >> ( std::istream&, BigInteger& );
    friend std::ostream& operator << ( std::ostream&, const BigInteger& );
 
private:
 
    std::vector<int> value;
    static const int base = 1e9;
    static const int count_of_digits = 9;
};
 
 
typedef BigInteger bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
 
int main()
{
    int n, m;
    std::cin >> n >> m;
 
    if ( m > n * 9 )
    {
        std::cout << 0 << std::endl;
        return 0;
    }
    
    matrix_t dinamic(n + 1, std::vector< bigInt > (n * 9 + 1) );
    
    /* dinamic[i][j] - количество i-значных чисел с суммой цифр, равной j */
    
    /* количество однозначных чисел с суммой цифр i (0 <= i <= 9) равно 1 */
    for (int i = 0; i <= 9 ; ++i)
        dinamic[1][i] = 1; 
        
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= i * 9 ; ++j)
        {
            for ( int k = 0 ; k <= std::min( j - 1, 9 ) ; ++k)
            {
                dinamic[i][j] += dinamic[i - 1][j - k];
            }
        }
    }
    
    std::cout << dinamic[n][m] << std::endl;
}
 
BigInteger::BigInteger( const std::string& str )
{
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
}
 
BigInteger::BigInteger()
{
    value.push_back(0);
}
 
BigInteger::BigInteger( long long x )
{
    std::ostringstream ost;
    ost << x;
    std::string str = ost.str();
    
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
    
}
 
BigInteger& BigInteger::operator += ( const BigInteger& b )
{
    for ( int temp = 0, i = 0; i < (int) std::max( this->value.size(), b.value.size() ) || temp != 0 ; ++i)
    {
        if ( i == (int) value.size() )
            value.push_back( 0 );
        
        value[i] += temp + ( i < (int) b.value.size() ? b.value[i] : 0 );
        temp = value[i] >= base;
        
        if ( temp != 0 )
            value[i] -= base;
    }
    
    return *this;
}
 
BigInteger operator + ( const BigInteger& a, const BigInteger& b )
{
    BigInteger c = a;
    c += b;
    return c;
}
 
std::istream& operator >> ( std::istream& stream, BigInteger& big )
{
    std::string str;
    std::cin >> str;
    big = BigInteger(str);
    
    return stream;  
}
 
std::ostream& operator << ( std::ostream& stream, const BigInteger& big )
{
    if ( big.value.empty() )
        stream << 0;
    else
        stream << big.value.back();
        
    for (int i = (int) big.value.size() - 2; i >= 0; --i)
    {
        stream << std::setfill('0') << std::setw(BigInteger::count_of_digits) << big.value[i];
    }
    
    return stream;
}
 
BigInteger& BigInteger::operator = ( const BigInteger& big )
{
    this->value = big.value;
    
    return *this;
}
Решение за O(n^2). Но там довольно большая константа(длинка, все-таки), поэтому в секунду не укладывается. Причем из длинки используется только сложение, для которого сложно придумать более оптимальный алгоритм.
В общем, если вас не устраивает быстродействие - пишите свою длинку, т.к. я сомневаюсь, что эта задача решается быстрее, чем за квадрат.
SeryZone
 Аватар для SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
25.07.2012, 13:35  [ТС]     Супер-быстрый перебор #6
Спасибо... но не могли бы объяснить свой код? Я плохо пока понимаю С++, и сам алгоритм решения.

Добавлено через 4 минуты
Цитата Сообщение от diagon Посмотреть сообщение
В общем, если вас не устраивает быстродействие - пишите свою длинку, т.к. я сомневаюсь, что эта задача решается быстрее, чем за квадрат.
Да... Гораздо быстрее!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2012, 13:48     Супер-быстрый перебор
Еще ссылки по теме:

Быстрый сплит C++
C++ Быстрый перебор всех комбинаций 32 байтов
C++ Быстрый аллокатор

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 13:48     Супер-быстрый перебор #7
Немного оптимизировал алгоритм. Теперь он работает за O(n * m). Но на самом страшном тесте(100 900) все равно работает секунды 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <string>
#include <iomanip>
#include <cstdlib>
 
class BigInteger
{   
public:
 
    BigInteger();   
    BigInteger( const std::string& );
    BigInteger( long long );
    
    BigInteger& operator = ( const BigInteger& );
    BigInteger& operator += ( const BigInteger& );
    
    friend BigInteger operator + ( const BigInteger&, const BigInteger& );
    
    friend std::istream& operator >> ( std::istream&, BigInteger& );
    friend std::ostream& operator << ( std::ostream&, const BigInteger& );
 
private:
 
    std::vector<int> value;
    static const int base = 1e9;
    static const int count_of_digits = 9;
};
 
 
typedef BigInteger bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
 
int main()
{
    int n, m;
    std::cin >> n >> m;
 
    if ( m > n * 9 )
    {
        std::cout << 0 << std::endl;
        return 0;
    }
    
    matrix_t dinamic(n + 1, std::vector< bigInt > (m + 1) );
    
    /* dinamic[i][j] - количество i-значных чисел с суммой цифр, равной j */
    
    /* количество однозначных чисел с суммой цифр i (0 <= i <= 9) равно 1 */
    for (int i = 0; i <= std::min(9, m) ; ++i)
        dinamic[1][i] = 1; 
        
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= m ; ++j)
        {
            for ( int k = 0 ; k <= std::min( j - 1, 9 ) ; ++k)
            {
                dinamic[i][j] += dinamic[i - 1][j - k];
            }
        }
    }
    
    std::cout << dinamic[n][m] << std::endl;
}
 
BigInteger::BigInteger( const std::string& str )
{
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
}
 
BigInteger::BigInteger()
{
    value.push_back(0);
}
 
BigInteger::BigInteger( long long x )
{
    std::ostringstream ost;
    ost << x;
    std::string str = ost.str();
    
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
    
}
 
BigInteger& BigInteger::operator += ( const BigInteger& b )
{
    for ( int temp = 0, i = 0; i < (int) std::max( this->value.size(), b.value.size() ) || temp != 0 ; ++i)
    {
        if ( i == (int) value.size() )
            value.push_back( 0 );
        
        value[i] += temp + ( i < (int) b.value.size() ? b.value[i] : 0 );
        temp = value[i] >= base;
        
        if ( temp != 0 )
            value[i] -= base;
    }
    
    return *this;
}
 
BigInteger operator + ( const BigInteger& a, const BigInteger& b )
{
    BigInteger c = a;
    c += b;
    return c;
}
 
std::istream& operator >> ( std::istream& stream, BigInteger& big )
{
    std::string str;
    std::cin >> str;
    big = BigInteger(str);
    
    return stream;  
}
 
std::ostream& operator << ( std::ostream& stream, const BigInteger& big )
{
    if ( big.value.empty() )
        stream << 0;
    else
        stream << big.value.back();
        
    for (int i = (int) big.value.size() - 2; i >= 0; --i)
    {
        stream << std::setfill('0') << std::setw(BigInteger::count_of_digits) << big.value[i];
    }
    
    return stream;
}
 
BigInteger& BigInteger::operator = ( const BigInteger& big )
{
    this->value = big.value;
    
    return *this;
}
Цитата Сообщение от SeryZone Посмотреть сообщение
сам алгоритм решения
Попробуйте нарисовать матрицу размера n * m, и заполните ее.
Число, стоящее в i-той строке и j-том столбце означает i-значное число, с суммой цифр, равной j.
P.S. кажется, ее можно решить за линию, но это намного сложнее.
Yandex
Объявления
25.07.2012, 13:48     Супер-быстрый перебор
Ответ Создать тему
Опции темы

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