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

Путешествие коня - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
21.10.2011, 13:11     Путешествие коня #1
Приветствую всех. Немного запутался с задачей, правильно ли сделал.
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
int main()
{
    setlocale( LC_ALL, "RUS" );
 
    const size_t size = 8;
 
    const int hor[ size ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    const int ver[ size ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
    int count = 0;
 
    for ( size_t i = 0; i < size; i++ )
    {
        for ( size_t j = 0; j < size; j++ )
        {
            int board[ size ][ size ] = { 0 };
            int accessibility[ size ][ size ] =
            {
                { 2, 3, 4, 4, 4, 4, 3, 2 },
                { 3, 4, 6, 6, 6, 6, 4, 3 },
                { 4, 6, 8, 8, 8, 8, 6, 4 },
                { 4, 6, 8, 8, 8, 8, 6, 4 },
                { 4, 6, 8, 8, 8, 8, 6, 4 },
                { 4, 6, 8, 8, 8, 8, 6, 4 },
                { 3, 4, 6, 6, 6, 6, 4, 3 },
                { 2, 3, 4, 4, 4, 4, 3, 2 }
            };
 
            bool flag = false;
            int minX, minY;
            int curRow = i, curCol = j;
            int n = 1;
 
            while ( !flag )
            {
                board[ curRow ][ curCol ] = n;
 
                for ( size_t i = 0; i < size; i++ )
                {
                    if ( curRow + hor[ i ] >= 0 && curRow + hor[ i ] < size && curCol + ver[ i ] < size && curCol + ver[ i ] >= 0 && board[ curRow + hor[ i ] ][ curCol + ver[ i ] ] == 0 )
                    {
                        minX = curRow + hor[ i ];
                        minY = curCol + ver[ i ];
                        n++;
                        break;
                    }
                    else if ( i == size - 1 )
                    {
                        flag = true;
 
                        if ( n == 64 )
                            count++;
                    }
                }
                
                for ( size_t i = 0; i < size; i++ )
                {
                    if ( curRow + hor[ i ] >= 0 && curRow + hor[ i ] < size && curCol + ver[ i ] < size && curCol + ver[ i ] >= 0 && board[ curRow + hor[ i ] ][ curCol + ver[ i ] ] == 0 )
                    {
                        accessibility[ curRow + hor[ i ] ][ curCol + ver[ i ] ]--;
                        if ( accessibility[ curRow + hor[ i ] ][ curCol + ver[ i ] ] < accessibility[ minX ][ minY ] )
                        {
                            minX = curRow + hor[ i ];
                            minY = curCol + ver[ i ];
                        }
                    }
                }
                
                curRow = minX;
                curCol = minY;
            }
        }
    }
 
    std::cout << "Полных путешествий: " << count << std::endl;
 
    std::cout << '\a' << std::endl;
    system( "pause" );
    return 0;
}
Полных путешествий 63 из 64 возможных, не полное одно всего, которое начинается с board[ 2 ][ 3 ].
Так и должно быть, правильно ли я вообще понял задание, и выполнил его?

Та часть задания на которой остановился.
(Путешествие коня) ...
с) После попытки написать и запустить программу путешествия коня вы, вероятно, получили более глубокие представления о задаче. Вы будете использовать их для создания эвристики (или стратегии) передвижения коня. Эвристика не гарантирует успеха, но при тщательной разработке обычно существенно повышает шансы на успех. Вы можете заметить, что клетки на краях доски более трудны для обхода, чем клетки в центре доски. Наиболее трудны для обхода или даже недоступны четыре угловые клетки. Интуиция может подсказать вам, что в первую очередь нужно попытаться обойти конем наиболее трудные клетки и оставить «на потом» те, доступ к которым проще, чтобы, когда доска окажется к концу путешествия заполненной сделанными ходами, было больше шансов на успех.
Мы можем разработать «эвристику доступности» путем классификации каждой клетки в соответствии с ее доступностью (в терминах хода конем, конечно) и перемещать коня на наиболее недоступную клетку. Мы пометим двумерный массив accessibility числами, указывающими, со скольких клеток доступна каждая клетка. На пустой доске каждая центральная клетка оценивается как 8, а каждая угловая клетка как 2, остальные клетки имеют числа доступности 3, 4 или 6 в соответствии с таблицей:
2, 3, 4, 4, 4, 4, 3, 2
3, 4, 6, 6, 6, 6, 4, 3
4, 6, 8, 8, 8, 8, 6, 4
4, 6, 8, 8, 8, 8, 6, 4
4, 6, 8, 8, 8, 8, 6, 4
4, 6, 8, 8, 8, 8, 6, 4
3, 4, 6, 6, 6, 6, 4, 3
2, 3, 4, 4, 4, 4, 3, 2
Теперь напишите вариант программы «Путешествие коня», используя эвристику доступности. В любом случае конь должен ходить на клетку с наименьшим числом доступности. В случае равенства чисел доступности для разных клеток конь может ходить на любую из них. Таким образом, путешествие можно начать в любом из четырех углов. [Замечание. По мере перемещения коня по доске ваша программа должна уменьшать числа доступности по мере того, как больше клеток оказываются занятыми. Таким образом, в каждый данный момент путешествия число доступности каждой имеющейся в распоряжении клетки будет делаться равным количеству клеток, из которых можно пойти на данную клетку.] Выполните эту версию вашей программы. Смогли ли вы совершить полное путешествие? Теперь модифицируйте программу для выполнения 64 путешествий, каждое из которых начинается со своей клетки шахматной доски. Сколько полных путешествий удалось сделать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2011, 13:11     Путешествие коня
Посмотрите здесь:

C++ "Путешествие коня"
Путешествие коня. Упрощеннаяя версия. C++
Путешесвтие коня. C++
C++ Путешествие коня. Почему конь не хочет пробежать все возможные варианты?
Головоломка о путешествии коня C++
C++ Похождения коня
Кратчайший путь коня с++ C++
C++ Задача - Путешествие коня

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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