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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.88
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
24.06.2010, 23:06     Подсчитать количество способов замостить шахматную доску доминошками #1
На шахматной доске,размером N*N клеток(2<=N<=8),подсчитать кол-во способов,которыми можно замостить данную доску стандартными доминошками.Если есть какие то идеи,как решить данную задачу,поделитесь пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.06.2010, 00:22     Подсчитать количество способов замостить шахматную доску доминошками #21
Mr.X, прикольный алгоритм, мне понравился . Я думал, решается строго рекурсией или динамикой по профилю, а тут вон какая штука веселая. Сами придумали его?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
26.06.2010, 13:38     Подсчитать количество способов замостить шахматную доску доминошками #22
Цитата Сообщение от Solnechnayanny Посмотреть сообщение
и последний вопрос,как называется алгоритм,по которому идёт обход и заполнение клеток доминошками?в принципе его суть я более или менее уловила)
Если это ко мне вопрос, то этот алгоритм я сам придумал, да он здесь и очевиден. Если мы обходим доску слева направо и сверху вниз, то в очередной клетке мы можем положить кость домино только двумя способами: горизонтально (т.е. вправо), или вертикально (т.е. вниз). Таким образом, если сопоставить одному из этих действий 0, а другому 1, то каждое решение можно представить как двоичное число, длина которого равна необходимому количеству костей домино для заполнения доски. Остается только перебрать все такие двоичные числа и подсчитать те, которые подходят.
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
27.06.2010, 23:53  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #23
ещё раз большое спасибо за помощь)))со сдачей заданий всё прошло удачно))
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
27.06.2010, 23:53     Подсчитать количество способов замостить шахматную доску доминошками #24
Убедился, что доску 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;
}
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
27.06.2010, 23:57     Подсчитать количество способов замостить шахматную доску доминошками #25
Какие же проблемы с распечатыванием у рекурсии? Нашли вариант, распечатали сразу, либо сохранили в число вашим способом. А вот с динамикой действительно проблематично...
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
28.06.2010, 00:03     Подсчитать количество способов замостить шахматную доску доминошками #26
Цитата Сообщение от Хохол Посмотреть сообщение
Какие же проблемы с распечатыванием у рекурсии? Нашли вариант, распечатали сразу, либо сохранили в число вашим способом. А вот с динамикой действительно проблематично...
А можете привести пример программы с рекурсией?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2010, 00:04     Подсчитать количество способов замостить шахматную доску доминошками
Еще ссылки по теме:

C++ Подсчитать количество способов размещения, чтобы между числами k было ровно k других чисел
C++ Реализовать программу на рекурсию про шахматную доску
Написать программу, которая выводит на экран шахматную доску C++

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

Или воспользуйтесь поиском по форуму:
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
28.06.2010, 00:04     Подсчитать количество способов замостить шахматную доску доминошками #27
Решающей эту задачу? Пожалуй, лень.

Добавлено через 13 секунд
Хотя, если хотите, наверно напишу.
Yandex
Объявления
28.06.2010, 00:04     Подсчитать количество способов замостить шахматную доску доминошками
Ответ Создать тему
Опции темы

Текущее время: 15:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru