Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
1

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

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

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

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

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

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

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

Вывести найденное количество чисел.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.07.2012, 21:11
Ответы с готовыми решениями:

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

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

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

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

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

Добавлено через 1 час 28 минут
Так каков алгоритм вычислений?
0
Эксперт С++
1659 / 1031 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
25.07.2012, 00:17 4
Для начала предлагаю разработать критерий, проверяющий, существуют ли вообще такие числа для заданных N и M. Сама такая проверка уже даст некое начальное понимание сути проблемы, отталкиваясь от которого, можно продолжать решение далее.
0
Higher
1944 / 1210 / 120
Регистрация: 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
56 / 28 / 18
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
25.07.2012, 13:35  [ТС] 6
Спасибо... но не могли бы объяснить свой код? Я плохо пока понимаю С++, и сам алгоритм решения.

Добавлено через 4 минуты
Цитата Сообщение от diagon Посмотреть сообщение
В общем, если вас не устраивает быстродействие - пишите свою длинку, т.к. я сомневаюсь, что эта задача решается быстрее, чем за квадрат.
Да... Гораздо быстрее!
0
Higher
1944 / 1210 / 120
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.07.2012, 13:48

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

Быстрый перебор объектов в коллекции
Добрый вечер. Пишу онлайн-игрушку, и столкнулся с такой проблемой : передаю объекты класса от...

Анпивот таблицы - быстрый перебор строк
Люди, здравствуйте. Есть таблица (типа таблица - диапазон, оформленный под таблицу). И он...

Самый быстрый перебор пар чисел
Задача: Есть число N. Найти все пары чисел от 1 до N, которые в сумме дают M. Можно так: for...


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

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

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