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

Китайские шашки. Перебор - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ поиск информации для изучения http://www.cyberforum.ru/cpp-beginners/thread516506.html
Поделитесь ,пожалуйста ,информацией , цитирую : "Библиотечные функции языка программирования С Библиотечные функции обработки символов и строк".
C++ [C] Найти самую длинную строку и поместить ее после самой короткой Найти самую длинную строку и поместить ее после самой короткой. http://www.cyberforum.ru/cpp-beginners/thread516504.html
Найти количество столбцов матрицы, все элементы которых различны. C++
Дана целочисленная матрица размера M × N. Найти количество ее столбцов, все элементы которых различны.
Вывод матрицы в заданном порядке C++
Дана матрица размера M × N. Вывести ее элементы в следующем по- рядке: первая строка слева направо, вторая строка справа налево, третья строка слева направо, четвертая строка справа налево и т. д. Нужно только решение после того как составили матрицу, но если не трудно можно и ее написать
C++ Перегрузка. http://www.cyberforum.ru/cpp-beginners/thread516468.html
Всем привет. Вот, попросили помочь, кому не сложно. Сам код: #ifndef OTREZOK_H #define OTREZOK_H #include <iostream> #include <string> using std::string;
C++ Программирование с использованием строковых данных. Привет ВСЕМ!!! Уважаемые модераторы и форумчане помогите пожалуйста в решении следующей задачки... Составить таблицу слов данного текста, начинающихся с буквы "А", с указанием числа повторений каждого слова. ... буду БЛАГОДАРЕН!!!! =) подробнее

Показать сообщение отдельно
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
11.03.2012, 23:23     Китайские шашки. Перебор
Суть китайских шашек такова: есть поле(см. рисунок) и можно перепрыгивать через фишку, если поле за ней свободно. При этом фишка, через которую перепрыгнули, убирается. Нужно убрать все фишки.
Китайские шашки. Перебор Китайские шашки. Перебор
Сначала я сделал перебор на основе очереди, но он ел слишком много памяти (и это без вывода решений, просто проверка существования)
код
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
#include <iostream>
#include <vector>
#include <queue>
///////////////////////////////////////////////////////////////////////////////
 
using namespace std;
 
///////////////////////////////////////////////////////////////////////////////
 
typedef vector<int  > T_vec;
typedef vector<T_vec> T_mtr;
 
///////////////////////////////////////////////////////////////////////////////
 
enum {EMPTY, POINT, NOTBOARD};
 
///////////////////////////////////////////////////////////////////////////////
 
const int SIZE = 9;
 
///////////////////////////////////////////////////////////////////////////////
 
const int  stepi[] = { 1,-1, 0, 0};
const int  stepj[] = { 0, 0, 1,-1};
 
///////////////////////////////////////////////////////////////////////////////
 
inline bool endOfGame(T_mtr& m)
{
    for(int i = 0; i < m.size(); i++)
        for(int j = 0; j < m[i].size(); j++)
            if(m[i][j] == POINT)
                return false;
    return true;
}
 
///////////////////////////////////////////////////////////////////////////////
 
int main()
{
    T_mtr board(SIZE, T_vec(SIZE, NOTBOARD));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < SIZE; j++)
        {
            board[3+i][j] = POINT;
            board[j][3+i] = POINT;
        }
    board[4][4] = EMPTY;
    
    queue<T_mtr> moves;
    moves.push(board);
    int mv = 0;
    while(!moves.empty())
    {
        T_mtr now = moves.front();
        moves.pop();
        if(endOfGame(now))
        {
            cout << "Find solution!" << endl;
            break;
        }
        //THIS IS BRUTE FORCE!!!!111
        for(int i = 0; i < now.size(); i++)
            for(int j = 0; j < now[i].size(); j++)
                if(now[i][j] == POINT)
                    for(int st = 0; st < sizeof stepi / sizeof *stepi; st++)
                    {
                        int newi  = i +   stepi[st];
                        int newj  = j +   stepj[st];
                        int newdi = i + 2*stepi[st];
                        int newdj = j + 2*stepj[st];
                        if( newdi >= 0 && newdi < SIZE &&
                            newdj >= 0 && newdj < SIZE &&
                            now[newi ][newj ] == POINT &&
                            now[newdi][newdj] == EMPTY)
                        {
                            T_mtr temp = now;
                            temp[i    ][j    ] = EMPTY;
                            temp[newi ][newj ] = EMPTY;
                            temp[newdi][newdj] = POINT;
                            moves.push(temp);
                        }
                    }
    }
    return 0;
}

потом просто заменил очередь на стек (теперь программа потребляет порядка 2 мегабайт)
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
#include <iostream>
#include <vector>
#include <stack>
///////////////////////////////////////////////////////////////////////////////
 
using namespace std;
 
///////////////////////////////////////////////////////////////////////////////
 
typedef vector<int  > T_vec;
typedef vector<T_vec> T_mtr;
 
///////////////////////////////////////////////////////////////////////////////
 
enum {EMPTY, POINT, NOTBOARD};
 
///////////////////////////////////////////////////////////////////////////////
 
const int SIZE = 9;
 
///////////////////////////////////////////////////////////////////////////////
 
const int  stepi[] = { 1,-1, 0, 0};
const int  stepj[] = { 0, 0, 1,-1};
 
///////////////////////////////////////////////////////////////////////////////
 
inline bool endOfGame(T_mtr& m)
{
    for(int i = 0; i < m.size(); i++)
        for(int j = 0; j < m[i].size(); j++)
            if(m[i][j] == POINT)
                return false;
    return true;
}
 
///////////////////////////////////////////////////////////////////////////////
 
int main()
{
    T_mtr board(SIZE, T_vec(SIZE, NOTBOARD));
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < SIZE; j++)
        {
            board[3+i][j] = POINT;
            board[j][3+i] = POINT;
        }
    board[4][4] = EMPTY;
    
    stack<T_mtr> moves;
    moves.push(board);
    int mv = 0;
    while(!moves.empty())
    {
        T_mtr now = moves.top();
        moves.pop();
        if(endOfGame(now))
        {
            cout << "Find solution!" << endl;
            break;
        }
        //THIS IS BRUTE FORCE!!!!111
        for(int i = 0; i < now.size(); i++)
            for(int j = 0; j < now[i].size(); j++)
                if(now[i][j] == POINT)
                    for(int st = 0; st < sizeof stepi / sizeof *stepi; st++)
                    {
                        int newi  = i +   stepi[st];
                        int newj  = j +   stepj[st];
                        int newdi = i + 2*stepi[st];
                        int newdj = j + 2*stepj[st];
                        if( newdi >= 0 && newdi < SIZE &&
                            newdj >= 0 && newdj < SIZE &&
                            now[newi ][newj ] == POINT &&
                            now[newdi][newdj] == EMPTY)
                        {
                            T_mtr temp = now;
                            temp[i    ][j    ] = EMPTY;
                            temp[newi ][newj ] = EMPTY;
                            temp[newdi][newdj] = POINT;
                            mv++;
                            if(mv%1000 == 0)
                                cout << "Valid move: " << mv << endl;
                            moves.push(temp);
                        }
                    }
    }
    return 0;
}
на варианте с очередью я подождал до перебора 2 млн. вариантов, а на модификации со стеком до 200 млн.

И наконец вопрос: как эффективно решить эту задачу?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 05:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru