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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Конкурс(поиск простых чисел) http://www.cyberforum.ru/cpp-beginners/thread628243.html
Я тут подумал, посмотрел по теме Hello world'a как всем нравится находить изощренные способы.Так вот - задание на засыпку: написать программу, вычисляющую простые числа от 1 до 300000.Программа ДОЛЖНА работать за 6 секунд.Обьем памяти неограничен.За 6 сек должна работать на процессоре примерно таком - 2 ядра по 3.2 ггц каждое! Ну что, кто напишет?))) Кто напишет, тому спасибо поставлю)
C++ Переход на заданную строку вот хочу считать последнюю строку из файла такием раком fstream str("base.txt",ios_base::in|ios_base::out); str.seekp(0, ios::end); char* words; str >> words; str >> words; str >> words; cout << words; http://www.cyberforum.ru/cpp-beginners/thread628241.html
C++ Вывести на экран значение элемента...
Работа с квадратными массивами В задаче рассматривается двумерный массив с одинаковым количеством строк и столбцов; такой массив называют квадратным. Задача: Известен номер столбца, на котором расположен элемент побочной диагонали квадратного массива. Вывести на экран значение этого элемента.
C++ Найти все десятизначные числа с неповторяющимися цифрами, при делении которых на 9 получается симметричное частное
Здравствуйте, друзья. Вот задача: Найти все десятизначные числа с неповторяющимися цифрами, при делении которых на 9 получается симметричное частное. Например: 4938271605 / 9 = 548696845 (таким же свойством обладают числа 2165904378/9=2406556042 или 2934815607/9=326090623 и др.) Вот код: #include <iostream> using namespace std; void main() { double Sc=1000000000, Otv;
C++ Какой заголовочный файл надо для функции ord() ? http://www.cyberforum.ru/cpp-beginners/thread628199.html
Всем привет... Тут такая напасть случилась забыл заголовочный файл(include <???>) для функции ord =)
C++ Имена переменных русскими словами Попробовал объявить переменную русским словом, присвоить значение и напечатать. Всё получилось. А почему в учебниках пишут, что можно только латинскими буквами ? подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
25.07.2012, 13:11     Супер-быстрый перебор
Набросал решение, проверил весьма бегло.
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). Но там довольно большая константа(длинка, все-таки), поэтому в секунду не укладывается. Причем из длинки используется только сложение, для которого сложно придумать более оптимальный алгоритм.
В общем, если вас не устраивает быстродействие - пишите свою длинку, т.к. я сомневаюсь, что эта задача решается быстрее, чем за квадрат.
 
Текущее время: 23:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru