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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ map http://www.cyberforum.ru/cpp-beginners/thread370055.html
объясните пожалуйсто как это работает, почему тут <string, int, less<string>> так много перемееных #include <map> #include <string> #include <iostream> using namespace std; void main() {...
C++ inline В хедере определён класс со static-методами, в исходнике реализация этих методов. Один из методов определяется с ключевым словом inline. Этот метод (который определён с ключевым словом inline)... http://www.cyberforum.ru/cpp-beginners/thread370053.html
C++ Нужно переписать процедуры с Паскаля на функции в С++
Есть список. И есть процедуры для вывода списка и удаления первого элемента. Не знаю как переписать эти процедуры на С++, потому что не знаю как в С++ передать переменную по значению как в procedure...
C++ Квадратные уравнения
#include <iostream> #include <math.h> using namespace std; int main() { float a,b,c,d,di,x1,x2; cout<<"a=";cin>>a; cout<<"b=";cin>>b; cout<<"c=";cin>>c;
C++ Ошибка в Коде: error C2679 http://www.cyberforum.ru/cpp-beginners/thread370018.html
НЕ давно начал изучать С++. написал программу которая предоставлена в учебники но она у меня что то не компилируется Вот код: #include <iostream> #include <conio.h> #include <locale.h> using...
C++ Дружные функции Завдання 1 1)створити програму, в якій будуть виводитись рядки таблиці, дружня функція виводе рядок 2 і 3. 2)функція дружнього класу рахує суму чисел третього стовпця. Прізвище| Ініціали| ... подробнее

Показать сообщение отдельно
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1

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

21.10.2011, 13:11. Просмотров 1172. Ответов 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 путешествий, каждое из которых начинается со своей клетки шахматной доски. Сколько полных путешествий удалось сделать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru