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

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

Войти
Регистрация
Восстановить пароль
 
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
#1

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

24.07.2012, 21:11. Просмотров 1084. Ответов 6
Метки нет (Все метки)

Используя минимальное количество библиотек(Вместо 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++
Доброго всем вечера, можете подсказать как с этим разобраться? Неободимо перебрать все числа от 1 до 12345678 и проверить что в каждом из...

Быстрый перебор всех комбинаций 32 байтов - C++
Здравствуйте, как можно очень быстро перебрать все комбинации 32 байтов, с записью результата в string для сравнения строк ? то-есть...

Супер Программа - C++
Вводятся числа a и b. Найти сумму таких чисел в диапазоне , которые при возведении в квадрат дают число с последней цифрой 6.С...

Супер простой вопрос - C++
есть например printf(&quot;%f &quot;,sum); как ограничить количество знаков после запятой в float? забыл и ни где найти не...

Супер длинные вычисления(число в строковой записи) - C++
Подскажите как реализовать супер длинные вычисления(число в строковой записи) на С++ . Уже несколько дней написать не могу.

Быстрый почтальон - C++
Привет всем. Eсли сможете напишите код программы &quot;Быстрый почтальон&quot; на я.п. С\С++ Почтальону необходимо разнести несколько писем...

Быстрый поиск - C++
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в исходном наборе чисел. Написал такой поиск, но работает...

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

Добавлено через 1 час 28 минут
Так каков алгоритм вычислений?
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,930
Завершенные тесты: 1
25.07.2012, 00:17     Супер-быстрый перебор #4
Для начала предлагаю разработать критерий, проверяющий, существуют ли вообще такие числа для заданных N и M. Сама такая проверка уже даст некое начальное понимание сути проблемы, отталкиваясь от которого, можно продолжать решение далее.
diagon
Higher
1927 / 1193 / 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
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++
Как програмно сделать так что бы при нажатии сочетания клавиш F12+Home запускалась программа из windpws C:\program Files\test.exe

Быстрый аллокатор - C++
Собственно, необходим аллокатор для быстрого выделения памяти под мелкие объекты, совместимый со стандартными контейнерами (std::list и...

быстрый xor - C++
Нужно про-xor-ить биты в числе. Можно ли это сделать быстрее, чем u_char r = 0; for (i = 0; i &lt; sizeof (u_char); ++i) r ^= (n &gt;&gt;...

Быстрый Вопрос - C++
У меня один короткий вопрос. Как найти все цифры числа ? Т.е. 12345 число. 1 2 3 4 5 цифры.

Быстрый сплит - C++
Помогите пожалуйста найти самый быстрый способ преобразования строки в массив подстрок по некоторому символу (в частности, по пробелу) Я...


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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1927 / 1193 / 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     Супер-быстрый перебор
Ответ Создать тему
Опции темы

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