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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
Toshkarik
1140 / 857 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
#1

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

21.10.2011, 13:11. Просмотров 1147. Ответов 0
Метки нет (Все метки)

Приветствую всех. Немного запутался с задачей, правильно ли сделал.
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++
Выдает необработанное исключение #include &lt;iostream&gt; using std::cout; using std::endl; #include &lt;ctime&gt; using std::time; ...

Путешествие коня. Упрощеннаяя версия. - C++
Здравствуйте! Мне препод задал более упрощенную версию задачи про путешествие коня. Условие задачи такое: написать функцию печатающая...

Путешествие коня. Почему конь не хочет пробежать все возможные варианты? - C++
Всем привет. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; int _tmain(int argc, _TCHAR* argv) { ...

"Путешествие коня" - C++
Доброго времени суток, у меня возникла проблема при решении задачи. Суть такова: задача аналогична головоломке Эйлера (где из...

путешествие камня по галактике - C++
Нужно решить такую задачу Камень движется по вселенной со постоянной скоростью U Допустим он начинает двигаться с этих координат 37°...

Похождения коня - C++
Добрый день! Пишу программу для решения шахматной задачи &quot;Похождения коня,&quot; ( Условие : Требуется обойти конем все 64 клетки шахматной...

Путешесвтие коня. - C++
Я написал программу про ход коня. Мне надо доделать, если ход сделать нельзя (выходит за размер доски) то писал введите другое число и...

Ход коня - C++
Здравствуйте, уважаемые форумчане!!! у меня возникла проблема с задачей про коня!!! Дело в том что первоначальные значения координат...

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б

Головоломка о путешествии коня - C++
Задача - составить такую последовательность ходов, при которой конь может обойти всю шахматную доску, побывав на каждой клетке лишь один...


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

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

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