Форум программистов, компьютерный форум 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),подсчитать кол-во способов,которыми можно замостить данную доску стандартными доминошками.Если есть какие то идеи,как решить данную задачу,поделитесь пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2010, 23:06     Подсчитать количество способов замостить шахматную доску доминошками
Посмотрите здесь:

создать шахматную доску C++
C++ Обойти шахматную доску ходом коня
C++ Как можно сформировать массив кнопок, моделирующий шахматную доску?
Нарисовать шахматную доску C++
C++ Найти количество способов
C++ Подсчитать количество способов размещения, чтобы между числами k было ровно k других чисел
Вычислить количество способов группировки K предметов из N при больших N C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
24.06.2010, 23:51     Подсчитать количество способов замостить шахматную доску доминошками #2
Это очень нехилая задача. Кто это вам ее задал?
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 02:08  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #3
Преподаватель по комбинаторным алгоритмам,вернее даже его ученик со старших курсов..как он сказал это лёгкая задача с олимпиады..но с моими знаниями в алгоритмах и языках с/с++ мне не справиться((

Добавлено через 2 часа 6 минут
вся информация,которую я нашла по этому вопросу,состоит в этой процедуре на паскале..но как от неё отталкиваться для дальнейшего решения я не знаю((Ниже приведен код рекурсивной процедуры, которая заполняет строку d[p], то есть находит все профили, которые можно получить из p.Алгоритм вычисления D и A работает за
O(22n) (вычисление D) + O(22nm) (вычисление A) = O(22nm).
Pascal
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
 
procedure go(n, profile, len : integer);
begin
    // n - из условия задачи
    // profile - текущий профиль
    // len - длина profile
            
    if (len = n) then begin 
        // как только profile получился длины n, выходим
        d[p][profile] := 1;
        exit;
    end;
    if (bit(p, len) = 0) then begin 
        // текущая ячейка в p (с номером len + 1) не занята
        go(p, profile + (1 shl len), len + 1);
        // положили горизонтальную доминошку
                
        if (len < n - 1) then
            if (bit(p, len + 1) = 0) then begin 
                // не занята еще и следующая ячейка
                go(p, profile, len + 2);
                // положили вертикальную доминошку
            end;
    end else begin
        go(p, profile, len + 1);
        // текущая ячейка занята, ничего положить не можем
    end;
end;
 
procedure determine_D;
var p : integer;
begin
  for p := 0 to (1 shl n) - 1 do
    go(p, 0, 0); // запускать надо именно с такими параметрами
end;
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
25.06.2010, 03:04     Подсчитать количество способов замостить шахматную доску доминошками #4
Как-то писал эту задачу, только она давалась как задача на динамику по профилю, а не комбинаторику, хотя есть наверно и комбинаторное решение, но его с ходу не заметно

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
#include <iostream>
 
using namespace std;
 
long long  d[3000][3000],n,m,j,p1,p2,f[1000][1000];
 
void go(int p1,int p2,int len)
{
  if (len == n)
  {
    d[p1][p2] = 1;
    return ;
  }
  if (p1 & (1 << len) == 0)
  {
    go(p1, p2 | (1 << len), len + 1);
    if (len < n-1 && p1 & (1 << (len+1)) == 0)
    go(p1,p2,len+2);
  }
  else
    go(p1,p2,len+1);
}
int main()
{
  cin >> n >> m;
  for (int p = 0; p < (1 << n); p++)
  go(p, 0, 0);
  f[1][0] = 1 ;
  for (j=1;j<=(m+1);j++)
  {
    for (p2=0;p2<(1<<n);p2++)
    {
      long long sum = 0 ;
      for (p1=0;p1<(1 << n);p1++)
      {
        sum += f[j-1][p1]*d[p1][p2];
      }
      if (j == 1 && p2 == 0) continue ;
      f[j][p2] = sum ;
    }
  }
  cout << f[m+1][0];
  return 0;
}
time2die
51 / 51 / 3
Регистрация: 25.05.2010
Сообщений: 182
25.06.2010, 08:34     Подсчитать количество способов замостить шахматную доску доминошками #5
странное ощущение подсказывает мне, что для вычисления количества способов достаточно использовать стандартную формулу на размещение без повторения
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 09:19     Подсчитать количество способов замостить шахматную доску доминошками #6
time2die, нэа. Это действительно динамика по профилю. Можно конешно написать какую-нить простую рекурсию, но наверно оч долго работать будет.
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 09:57  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #7
Спасибо большое)))а то не знаю,как бы справлялась)))

Добавлено через 10 минут
Правда есть одна проблема..у меня при компиляции g++ -Wall ошибка выдаётся...а ещё при запуске ответ не выдаётся(((не подскажите,что делать?
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 10:00     Подсчитать количество способов замостить шахматную доску доминошками #8
AemClock, че-то у меня эта программа на любой тест 1 выводит.
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 10:05  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #9
и у меня так же...
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
25.06.2010, 13:25     Подсчитать количество способов замостить шахматную доску доминошками #10
есть такое ) Что-то со скобками напутано, вот так вот лучше

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void go(int p1,int p2,int len)
{
  if (len == n)
  {
    d[p1][p2] = 1;
    return ;
  }
  if ((p1 & (1 << len)) == 0)
  {
    go(p1, p2 | (1 << len), len + 1);
    if (len < n-1 && (p1 & (1 << (len+1))) == 0)
    go(p1,p2,len+2);
  }
  else
    go(p1,p2,len+1);
}
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 13:36     Подсчитать количество способов замостить шахматную доску доминошками #11
Лучше.
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 13:38  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #12
теперь работает,спасибо)
Mr.X
Эксперт С++
 Аватар для Mr.X
3011 / 1667 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.06.2010, 17:47     Подсчитать количество способов замостить шахматную доску доминошками #13
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
//На шахматной доске,размером 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;    
 
    double                               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_(ceil(dim_ * dim_ / 2.0)),
          variant_max_(pow(static_cast<double>(2), vsego_kostey_domino_))
    {}
    //---------------------------------------------------------------------------
    void  count_zamostit_domino()
    {
        for(int 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)
            {
                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;
}
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 17:52     Подсчитать количество способов замостить шахматную доску доминошками #14
Эй-эй, Mr.X, она ж теперь весь день печатать будет!
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 22:56  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #15
извините,за возможно глупый вопрос,но как преподавателю внятно объяснить,почему программа работает только при чётном N?я понимаю, что допустим поле 3*3 замостить так,чтобы доминошки не покрывали друг друга не возможно,т.к. остаются две пустые клетки..но его врядли устроит такой ответ
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 23:06     Подсчитать количество способов замостить шахматную доску доминошками #16
Ну мля, невозможно, способов 0, она и выдает 0.

Добавлено через 29 секунд
Его вполне устроит такой ответ, так как он верный.
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 23:30  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #17
ну вот он спросит,почему нет способов,на чём это основано..ведь должен быть логический ответ..хотя можно в принципе назвать алгоритм,по которому он считает способы..объяснить его суть..только для этого надо самой в нём разобраться)
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 23:35     Подсчитать количество способов замостить шахматную доску доминошками #18
Цитата Сообщение от Solnechnayanny Посмотреть сообщение
ну вот он спросит,почему нет способов,на чём это основано..ведь должен быть логический ответ
Доминошка покрывает ровно две клетки, куча неперекрывающихся доминошек покрывает четное количество клеток. Доска с нечетной стороной состоит из нечетного количества клеток. Следовательно доминошки не могут покрыть ее без перекрытий.
Это его устроит.
Mr.X
Эксперт С++
 Аватар для Mr.X
3011 / 1667 / 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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2010, 00:05     Подсчитать количество способов замостить шахматную доску доминошками
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
26.06.2010, 00:05  [ТС]     Подсчитать количество способов замостить шахматную доску доминошками #20
ну в принципе можно итак ответить и если понадобится показать способы замещения доски при нечётных N.Большое вам спасибо за помощь*)

Добавлено через 8 минут
и последний вопрос,как называется алгоритм,по которому идёт обход и заполнение клеток доминошками?в принципе его суть я более или менее уловила)
Yandex
Объявления
26.06.2010, 00:05     Подсчитать количество способов замостить шахматную доску доминошками
Ответ Создать тему
Опции темы

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