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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.88
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
#1

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

24.06.2010, 23:06. Просмотров 3337. Ответов 26
Метки нет (Все метки)

На шахматной доске,размером N*N клеток(2<=N<=8),подсчитать кол-во способов,которыми можно замостить данную доску стандартными доминошками.Если есть какие то идеи,как решить данную задачу,поделитесь пожалуйста.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2010, 23:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подсчитать количество способов замостить шахматную доску доминошками (C++):

Нарисовать шахматную доску - C++
Задание из книги Страуструпа &quot;Принципы и практика использования С++&quot;: &quot;Нарисуйте доску для шахмат 8x8, чередуя белые и красные квадраты&quot;....

Нарисовать шахматную доску - C++
Ввести число N и нарисовать шахматную доску размера NxN, где верхнее левое - белое. Белые поля обозначить O, черные - X. Использовать цикл...

создать шахматную доску - C++
прошу помощи 1 Поле шахматної дошки визначаться парою натуральних чисел,кожне з яких не перевищує 8:перше число – номер вертикалі (при...

Вывод на экран консоли шахматную доску - C++
Дело в том, что алгоритм у меня есть. Но я совсем не могу разобраться в скрипте. for (int i = 1; i &lt;= 10; i++) { for (int...

Обойти шахматную доску ходом коня - C++
Обязательные условия: 1. Рекурсивный алгоритм. 2. Размер доски вводит пользователь. 3. Использовать динамический массив. #include...

Реализовать программу на рекурсию про шахматную доску - C++
Магараджа - шахматная фигура, сочетающая возможности ферзя и коня. Найти число способов расставить на доске с заданной размерностью NxN...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 23:06 #16
Ну мля, невозможно, способов 0, она и выдает 0.

Добавлено через 29 секунд
Его вполне устроит такой ответ, так как он верный.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 23:30  [ТС] #17
ну вот он спросит,почему нет способов,на чём это основано..ведь должен быть логический ответ..хотя можно в принципе назвать алгоритм,по которому он считает способы..объяснить его суть..только для этого надо самой в нём разобраться)
0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 23:35 #18
Цитата Сообщение от Solnechnayanny Посмотреть сообщение
ну вот он спросит,почему нет способов,на чём это основано..ведь должен быть логический ответ
Доминошка покрывает ровно две клетки, куча неперекрывающихся доминошек покрывает четное количество клеток. Доска с нечетной стороной состоит из нечетного количества клеток. Следовательно доминошки не могут покрыть ее без перекрытий.
Это его устроит.
1
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.06.2010, 23:41 #19
Ну вообще-то в задаче сказано полностью замостить доску. При нечетной стороне доски число клеток на ней нечетно, так что одна непременно гуляет. Но чтобы увидеть это воочию, можно использовать такую программу:
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
//На шахматной доске,размером N*N клеток(2<=N<=8),подсчитать кол-во способов,
//которыми можно замостить данную доску стандартными доминошками.
//--------------------------------------------------------------------------
//  Программа демонстрирует и попытки замостить доску с нечетной стороной.
//--------------------------------------------------------------------------
#include <iostream>
#include <cmath>
#include <map>
#include <iomanip>
 
class T_doska
{
    typedef std::map<int, int>           T_horizontal;
    typedef std::map<int, T_horizontal>  T_kletki;
    static const int                     EMPTY_KLETKA  = -1;    
 
    int                                  dim_;
    int                                  count_;    
    double                               vsego_kostey_domino_;    
    double                               variant_max_;
    T_kletki                             kletki_;
public:
    T_doska(int dim) 
        : dim_(dim), 
          count_(0),          
          vsego_kostey_domino_(dim_ * dim_ / 2),
          variant_max_(pow(static_cast<double>(2), vsego_kostey_domino_))
    {}
    //---------------------------------------------------------------------------
    void  count_zamostit_domino()
    {        
        for(unsigned  cur_variant = 0; cur_variant < variant_max_; ++cur_variant)
        {
            if(uspeshno_zamostil(cur_variant))
            {
                ++count_;            
                print_kletki();            
            }
        }
        std::cout << "Всего получили "
                  << count_
                  << " вариантов замощения доски "
                  << dim_
                  << " x "
                  << dim_
                  << " костями домино."
                  << std::endl;
    }
    //---------------------------------------------------------------------------
private:
    //---------------------------------------------------------------------------
    void  print_kletki()
    {
        std::cout << "Вариант № "
                  << count_
                  << std::endl;
        for(int i = 0; i < dim_; ++i)
        {
            for(int j = 0; j < dim_; ++j)
            {
                if(kletki_[i][j] == EMPTY_KLETKA)
                {
                    std::cout << std::setw(4)
                              << "";                                
                }
                else
                {
                    std::cout << std::setw(4)
                              << kletki_[i][j];                
                }
            }
            std::cout << std::endl
                      << std::endl;
        }    
    }
    //---------------------------------------------------------------------------
    bool  uspeshno_zamostil(unsigned  cur_variant)
    {
        unsigned  temp_cur_variant = cur_variant;
        kletki_clear();
        
        for(int cur_cost_domino = 1; cur_cost_domino <= vsego_kostey_domino_;
            ++cur_cost_domino)               
        {
            int variant_bin_dig = temp_cur_variant % 2;
            temp_cur_variant /= 2;
            const int VPRAVO  = 0;
            const int VNIZ    = 1;
            //Ищем первую пустую клетку доски.
            int first_empty_kletka_i;
            int first_empty_kletka_j;
            if(!get_first_empty_kletka(first_empty_kletka_i, first_empty_kletka_j))
            {
                return false;
            }
            kletki_[first_empty_kletka_i][first_empty_kletka_j] = cur_cost_domino;
            switch(variant_bin_dig)
            {
            case VPRAVO:
                {
                    int&  kletka_sprava_ot_pustoy 
                        = kletki_[first_empty_kletka_i][first_empty_kletka_j + 1];
                    if(kletka_sprava_ot_pustoy != EMPTY_KLETKA) return false;
                    kletka_sprava_ot_pustoy = cur_cost_domino;
                    break;               
                }
            case VNIZ:
                {
                    int&  kletka_snizu_ot_pustoy
                        = kletki_[first_empty_kletka_i + 1][first_empty_kletka_j];
                    if(kletka_snizu_ot_pustoy != EMPTY_KLETKA) return false;
                    kletka_snizu_ot_pustoy = cur_cost_domino;
                    break;                
                }
            }//switch(variant_bin_dig)
        }//for(int cur_cost_domino = 1; cur_cost_domino <= vsego_kostey_domino_;
        return true;
    }
    //---------------------------------------------------------------------------
    bool  get_first_empty_kletka
        (
            int&  first_empty_kletka_i,
            int&  first_empty_kletka_j
        )
    {
        for(int i = 0; i < dim_; ++i)
        {
            for(int j = 0; j < dim_; ++j)
            {
                if(kletki_[i][j] == EMPTY_KLETKA)
                {
                    first_empty_kletka_i = i;
                    first_empty_kletka_j = j;
                    return true;                
                }
            }
        }
        return false;
    }
    //---------------------------------------------------------------------------
    void  kletki_clear()
    {
        for(int i = 0; i < dim_; ++i)
        {
            for(int j = 0; j < dim_; ++j)
            {                
                kletki_[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;
}
1
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
26.06.2010, 00:05  [ТС] #20
ну в принципе можно итак ответить и если понадобится показать способы замещения доски при нечётных N.Большое вам спасибо за помощь*)

Добавлено через 8 минут
и последний вопрос,как называется алгоритм,по которому идёт обход и заполнение клеток доминошками?в принципе его суть я более или менее уловила)
0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.06.2010, 00:22 #21
Mr.X, прикольный алгоритм, мне понравился . Я думал, решается строго рекурсией или динамикой по профилю, а тут вон какая штука веселая. Сами придумали его?
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
26.06.2010, 13:38 #22
Цитата Сообщение от Solnechnayanny Посмотреть сообщение
и последний вопрос,как называется алгоритм,по которому идёт обход и заполнение клеток доминошками?в принципе его суть я более или менее уловила)
Если это ко мне вопрос, то этот алгоритм я сам придумал, да он здесь и очевиден. Если мы обходим доску слева направо и сверху вниз, то в очередной клетке мы можем положить кость домино только двумя способами: горизонтально (т.е. вправо), или вертикально (т.е. вниз). Таким образом, если сопоставить одному из этих действий 0, а другому 1, то каждое решение можно представить как двоичное число, длина которого равна необходимому количеству костей домино для заполнения доски. Остается только перебрать все такие двоичные числа и подсчитать те, которые подходят.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
27.06.2010, 23:53  [ТС] #23
ещё раз большое спасибо за помощь)))со сдачей заданий всё прошло удачно))
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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;
}
1
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
27.06.2010, 23:57 #25
Какие же проблемы с распечатыванием у рекурсии? Нашли вариант, распечатали сразу, либо сохранили в число вашим способом. А вот с динамикой действительно проблематично...
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
28.06.2010, 00:03 #26
Цитата Сообщение от Хохол Посмотреть сообщение
Какие же проблемы с распечатыванием у рекурсии? Нашли вариант, распечатали сразу, либо сохранили в число вашим способом. А вот с динамикой действительно проблематично...
А можете привести пример программы с рекурсией?
0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
28.06.2010, 00:04 #27
Решающей эту задачу? Пожалуй, лень.

Добавлено через 13 секунд
Хотя, если хотите, наверно напишу.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.06.2010, 00:04
Привет! Вот еще темы с ответами:

Написать программу, которая выводит на экран шахматную доску - C++
Добрый день, Помогите пожалуйста решить задание на с++, &quot;Написать программу, которая выводит на экран шахматную доску. Количество...

Как можно сформировать массив кнопок, моделирующий шахматную доску? - C++
Как можно сформировать массив кнопок, моделирующий шахматную доску?

Подсчитать количество способов размещения, чтобы между числами k было ровно k других чисел - C++
Условие: Дано следующие множество чисел {1,1,1,2,2,2...9,9,9} (тройки). Подсчитать количество способов размещения всех этих чисел в...

Определить количество плиток, чтобы замостить пол - C++
Для того, чтобы замостить пол прямоугольной комнаты размерами AxB мастера решили приобрести квадратные плитки со стороной C. В магазине...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
28.06.2010, 00:04
Ответ Создать тему
Опции темы

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