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

Подсчитать количество способов замостить шахматную доску доминошками - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ с файлом http://www.cyberforum.ru/cpp-beginners/thread149240.html
Есть задание Написать программу, которая считывает текст из файла и выводит на экран только цитаты. Вот прога: #include <fstream> #include <iostream> using namespace std; int main () { ifstream ifin ("inputtext.txt",ios::in);
C++ С++задачка помогите пожалуйста...от этого зависит мой экзамен...или подскажите с чего начать....Код на С++ В школе продолжительность каждого урока 45 минут, а перемены между уроками – всего 5 минут. Первый урок начинается ровно в 8 часов утра. Напишите программу, отвечающую на вопрос «во сколько в этой школе заканчивается K-ый урок?» Входные данные. Вводится одно натуральное число K, не превышающее 15.... http://www.cyberforum.ru/cpp-beginners/thread149239.html
стек и очередь C++
ребят поделитесь плиз программами реализующими на си стек и очередь (хотябы ввод вывод данных)
C++ C++ нарисовать елочку с символов
Задача E. Елочка «Нарисуйте» с помощью символов лес. При этом не пользуйтесь командами перемещения курсора по экрану. Ваша программа должна последовательно выводить символы строк (или строки целиком). Лес — это одна или несколько елочек. Каждая елочка характеризуется количеством треугольников в ней и размером самого маленького треугольника. Елочка состоит из треугольников, у которых вершины...
C++ создать класс alpha http://www.cyberforum.ru/cpp-beginners/thread149230.html
Доброго времени суток. помогите написать класс. Создать класс Alpha таким образом чтоб при создании первого объекта и удалении последнего объекта этого типа на экран выдавались ответы сообщения применить статические компоненты класса. для VS 2008
C++ Составить прогу для подсчета непарных элементов двумерной матрицы Динамический массив В розмера m×n из целых чисел. Составить прогу для подсчета непарных(??????) элементов двумерной матрицы В, используя функцию обработки массива. подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2801 / 1577 / 247
Регистрация: 03.05.2010
Сообщений: 3,663
27.06.2010, 23:53     Подсчитать количество способов замостить шахматную доску доминошками
Убедился, что доску 8 х 8 можно подсчитать за приемлемое время оптимизированным полным перебором. На моем компьютере нижеследующая программа подсчитывает это за 25 секунд.
Для этого пришлось отказаться от контейнеров STL. После того, как я заменил двумерный std::map на двумерный массив, время подсчета уменьшилась с 64 до 8 минут. После того, как заменил std::vector на одномерный массив, время подсчета уменьшилось с 8 минут до 25 секунд. А ведь кое-кто кое-где нам рассказывает, что STL быстро работает.
Ну и несомненное преимущество данной программы перед алгоритмами рекурсии и динамики по профилю – возможность распечатать вариант с любым номером.
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
//На шахматной доске,размером N*N клеток(2<=N<=8),подсчитать кол-во способов,
//которыми можно замостить данную доску стандартными доминошками.
#include <iostream>
#include <iomanip>
#include <ctime>
 
class T_doska
{    
    static const int  MASSIV_DIM    = 12;
    static const int  EMPTY_KLETKA  = MASSIV_DIM * MASSIV_DIM;    
 
    int               doska_dim_;    
    int               solution_count_;    
    int               domino_count_;
    int               nach_kletki_domino_[MASSIV_DIM * MASSIV_DIM / 2];    
    int               kletki_doski_[MASSIV_DIM][MASSIV_DIM];
public:
    T_doska(int dim) 
        : doska_dim_(dim), 
          solution_count_(0),
          domino_count_(0)          
    {        
        kletki_clear();
    }
    //---------------------------------------------------------------------------
    void  count_zamostit_domino()
    {
        clock_t    cstart        = clock();
        const int  PRINT_PERIOD  = 1000000;
        while(uspeshno_zamostil())
        {
            ++solution_count_;
            if(doska_dim_ <= 4)
            {
                print_kletki();
            }
            else
            {
                if(solution_count_ == PRINT_PERIOD)
                {
                    std::cout << "Уже подсчитано вариантов: "
                              << std::endl;
                }
                if(solution_count_ % PRINT_PERIOD == 0)
                {
                    std::cout << solution_count_                              
                              << std::endl;
                }            
            }            
        }
        clock_t  cend = clock();
        double sec = static_cast<double>(cend - cstart) / CLOCKS_PER_SEC;
        std::cout << std::endl
                  << "Время выполнения " 
                  << sec 
                  << " сек."
                  << std::endl;
 
        std::cout << "Всего получили "
                  << solution_count_
                  << " вариантов замощения доски "
                  << doska_dim_
                  << " x "
                  << doska_dim_
                  << " костями домино."
                  << std::endl;
    }
    //---------------------------------------------------------------------------
private:
    //---------------------------------------------------------------------------
    void  print_kletki()
    {
        std::cout << "Вариант № "
                  << solution_count_
                  << std::endl;
        for(int i = 0; i < doska_dim_; ++i)
        {
            for(int j = 0; j < doska_dim_; ++j)
            {
                std::cout << std::setw(4)
                          << kletki_doski_[i][j];
            }
            std::cout << std::endl
                      << std::endl;
        }    
    }
    //---------------------------------------------------------------------------
    inline int get_k(int i, int j)
    {
        return i * doska_dim_ + j + 1;
    }
    //---------------------------------------------------------------------------
    inline int get_i_from_k(int k)
    {
        return (k - 1)/ doska_dim_;
    }
    //---------------------------------------------------------------------------
    inline int get_j_from_k(int k)
    {
        return (k - 1) % doska_dim_;
    }
    //---------------------------------------------------------------------------
    bool  uspeshno_zamostil()
    {        
        int i;
        int j;        
        for(bool go_forward = (solution_count_ == 0); ; )
        {
            for(;go_forward;)
            {
                if(!get_first_empty_kletka(i, j)) return true;
                if(kletki_doski_[i][j + 1] == EMPTY_KLETKA)
                {                        
                    nach_kletki_domino_[domino_count_++] = get_k(i, j);
                    kletki_doski_[i][j + 1] = domino_count_;
                    kletki_doski_[i][j]     = domino_count_;
                }
                else if(kletki_doski_[i + 1][j] == EMPTY_KLETKA)
                {                        
                    nach_kletki_domino_[domino_count_++] = -get_k(i, j);
                    kletki_doski_[i + 1][j] = domino_count_;
                    kletki_doski_[i][j]     = domino_count_;                    
                }
                else
                {
                    go_forward = false;
                    break;
                }
            }//for(;go_forward;)                
            
            for(;!go_forward;)
            { 
                if(domino_count_ == 0) return false;                    
                int k_so_znakom = nach_kletki_domino_[domino_count_ - 1];                    
                nach_kletki_domino_[--domino_count_] = 0;
                int k = abs(k_so_znakom);
                i = get_i_from_k(k);
                j = get_j_from_k(k);
                if(k_so_znakom > 0)
                {
                    if(kletki_doski_[i + 1][j] == EMPTY_KLETKA)
                    { 
                        std::swap(kletki_doski_[i][j + 1], kletki_doski_[i + 1][j]);                            
                        nach_kletki_domino_[domino_count_++] = -k;
                        go_forward = true;
                        break;                        
                    }
                    else
                    {
                        kletki_doski_[i][j]      = EMPTY_KLETKA;
                        kletki_doski_[i][j + 1]  = EMPTY_KLETKA;                        
                    }
                }
                else
                {
                    kletki_doski_[i][j]      = EMPTY_KLETKA;
                    kletki_doski_[i + 1][j]  = EMPTY_KLETKA;
                }
            }//for(;!go_forward;)            
        }//for(;;)
    }
    //---------------------------------------------------------------------------    
    bool  get_first_empty_kletka
        (            
            int& i,         
            int& j
        )
    {
        int i_start = 0;
        int j_start = 0;        
        if(domino_count_ > 0)
        {            
            int k    = abs(nach_kletki_domino_[domino_count_ - 1]);
            i_start  = get_i_from_k(k);
            j_start  = get_j_from_k(k);
        }
        for(i = i_start; i < doska_dim_; ++i)
        {
            for(j = (i == i_start) ? j_start : 0; j < doska_dim_; ++j)
            {
                if(kletki_doski_[i][j] == EMPTY_KLETKA)
                {                   
                    return true;                
                }
            }
        }
        return false;
    }
    //---------------------------------------------------------------------------
    void  kletki_clear()
    {
        for(int i = 0; i < MASSIV_DIM; ++i)
        {
            for(int j = 0; j < MASSIV_DIM; ++j)
            {                
                kletki_doski_[i][j] = 0;
            }
        }    
 
        for(int i = 0; i < doska_dim_; ++i)
        {
            for(int j = 0; j < doska_dim_; ++j)
            {                
                kletki_doski_[i][j] = EMPTY_KLETKA;
            }
        }    
    }
    //---------------------------------------------------------------------------
};
 
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите длину стороны доски: ";
    int doska_dim;
    std::cin >> doska_dim;
    T_doska  doska(doska_dim);
    doska.count_zamostit_domino();
    return 0;
}
 
Текущее время: 12:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru