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

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

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

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

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

Используя минимальное количество библиотек(Вместо iostream - stdio.h) сделать рекурсивный перебор:

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

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

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

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

Вывести найденное количество чисел.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.07.2012, 21:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Супер-быстрый перебор (C++):

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

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

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

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

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

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

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

Добавлено через 1 час 28 минут
Так каков алгоритм вычислений?
0
Nick Alte
Эксперт С++
1643 / 1015 / 120
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
25.07.2012, 00:17 #4
Для начала предлагаю разработать критерий, проверяющий, существуют ли вообще такие числа для заданных N и M. Сама такая проверка уже даст некое начальное понимание сути проблемы, отталкиваясь от которого, можно продолжать решение далее.
0
diagon
Higher
1932 / 1198 / 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). Но там довольно большая константа(длинка, все-таки), поэтому в секунду не укладывается. Причем из длинки используется только сложение, для которого сложно придумать более оптимальный алгоритм.
В общем, если вас не устраивает быстродействие - пишите свою длинку, т.к. я сомневаюсь, что эта задача решается быстрее, чем за квадрат.
1
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
25.07.2012, 13:35  [ТС] #6
Спасибо... но не могли бы объяснить свой код? Я плохо пока понимаю С++, и сам алгоритм решения.

Добавлено через 4 минуты
Цитата Сообщение от diagon Посмотреть сообщение
В общем, если вас не устраивает быстродействие - пишите свою длинку, т.к. я сомневаюсь, что эта задача решается быстрее, чем за квадрат.
Да... Гораздо быстрее!
0
diagon
Higher
1932 / 1198 / 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. кажется, ее можно решить за линию, но это намного сложнее.
1
25.07.2012, 13:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2012, 13:48
Привет! Вот еще темы с ответами:

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

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

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

Быстрый вызов - C++
Как програмно сделать так что бы при нажатии сочетания клавиш F12+Home запускалась программа из windpws C:\program Files\test.exe


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

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

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