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

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

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

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

24.06.2010, 23:06. Просмотров 3336. Ответов 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
24.06.2010, 23:51 #2
Это очень нехилая задача. Кто это вам ее задал?
0
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;
1
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;
}
2
time2die
51 / 51 / 3
Регистрация: 25.05.2010
Сообщений: 182
25.06.2010, 08:34 #5
странное ощущение подсказывает мне, что для вычисления количества способов достаточно использовать стандартную формулу на размещение без повторения
0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 09:19 #6
time2die, нэа. Это действительно динамика по профилю. Можно конешно написать какую-нить простую рекурсию, но наверно оч долго работать будет.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 09:57  [ТС] #7
Спасибо большое)))а то не знаю,как бы справлялась)))

Добавлено через 10 минут
Правда есть одна проблема..у меня при компиляции g++ -Wall ошибка выдаётся...а ещё при запуске ответ не выдаётся(((не подскажите,что делать?
0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 10:00 #8
AemClock, че-то у меня эта программа на любой тест 1 выводит.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 10:05  [ТС] #9
и у меня так же...
0
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);
}
1
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 13:36 #11
Лучше.
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 13:38  [ТС] #12
теперь работает,спасибо)
0
Mr.X
Эксперт С++
3049 / 1694 / 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;
}
2
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
25.06.2010, 17:52 #14
Эй-эй, Mr.X, она ж теперь весь день печатать будет!
0
Solnechnayanny
1 / 1 / 0
Регистрация: 20.06.2010
Сообщений: 43
25.06.2010, 22:56  [ТС] #15
извините,за возможно глупый вопрос,но как преподавателю внятно объяснить,почему программа работает только при чётном N?я понимаю, что допустим поле 3*3 замостить так,чтобы доминошки не покрывали друг друга не возможно,т.к. остаются две пустые клетки..но его врядли устроит такой ответ
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2010, 22:56
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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