Оптимизация программы - C++ - Ответ 4754088

@Sh0cK · Регистрация: 28.10.2012

Author24 — интернет-сервис помощи студентам

C++

#include<std_lib_facilities.h>
#include<conio.h>
 
void moveHorse(int &, int [][8], int [], int[], int &, int &, int &);//переставляет коня
int where_to_go(int [][8], int [][8], int [], int [], int &, int &);//определяет кудя лучше бежать конем
void zero_massive(int [][8]);//обнуляет массив после попытки с клетки board[n][m] пройти доску
void deckrement(int [][8], int &, int &, int [], int []);//коректирует Эвристику доступности после того как конь побывал на клетке с которой на даную можно походить
int one_more_stroke(int &, int &, int [][8], int &, int &, int [], int[]);//думает на шшаг вперед выбирая куда шагать анализируя следующий шаг
 
int main()
{
    setlocale(LC_CTYPE,"Russian");
    const int arraySize=8;
    int board[arraySize][arraySize]={0};
    int accessibility[arraySize][arraySize]={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};//Эвристика
    int vertical[arraySize]={-1,-2,-2,-1,1,2,2,1};//ходы
    int horizontal[arraySize]={2,1,-1,-2,-2,-1,1,2};//ходы
    int moveNumber;//№хода
    int currentRow,currentColumn;//координаты
    for(int x=0; x<arraySize; x++)
    {
        for(int y=0; y<arraySize; y++)
        {
            currentRow=x;
            currentColumn=y;
            int counter=0;
            zero_massive(board);
            board[currentRow][currentColumn]=1;
            for(int y=0; y<arraySize*arraySize; y++)
            {
                moveNumber=where_to_go(accessibility, board, vertical, horizontal, currentColumn, currentRow);
                if(moveNumber==10)
                {
                    cout << counter << " ";
                    break;
                }
                moveHorse(moveNumber, board, vertical, horizontal, currentColumn, currentRow, counter);
                deckrement(accessibility, currentRow, currentColumn, vertical, horizontal);
            }
        }
    }
    _getch();
    return 0;
}
void moveHorse(int &moveNumber, int board[][8], int vertical[], int horizontal[], int &currentColumn, int &currentRow, int &counter)
{
    currentColumn+=horizontal[moveNumber];
    currentRow+=vertical[moveNumber];
    board[currentRow][currentColumn]=1;
    counter++;
}
int where_to_go(int accessibility [][8], int board[][8], int vertical[], int horizontal[], int &currentColumn, int &currentRow)
{
    int possible_way_to_move=10;
    int smallest=10;
    for(int y=0; y<8; y++)
    {
        currentRow+=vertical[y];
        currentColumn+=horizontal[y];
        if(currentRow >= 0 && currentColumn < 8 && currentRow < 8 && currentColumn>=0 && board[currentRow][currentColumn]==0)
        {
            if(smallest > accessibility[currentRow][currentColumn])
            {
                smallest=accessibility[currentRow][currentColumn];
                possible_way_to_move=y;
            }
            else if(smallest==accessibility[currentRow][currentColumn])
            {
                possible_way_to_move=one_more_stroke(possible_way_to_move, y, accessibility, currentRow, currentColumn, vertical, horizontal);
            }
        }
        currentRow-=vertical[y];
        currentColumn-=horizontal[y];
    }
    return possible_way_to_move;
}
void zero_massive(int board[][8])
{
    for(int h=0; h<8; h++)
        for(int j=0; j<8; j++)
            board[h][j]=0;
}
void deckrement(int accessability[][8], int &currentRow, int &currentColumn, int vertical[], int horizontal[])
{
    for( int l=0; l<8; l++)
        if(currentRow+vertical[l] < 8 && currentRow+vertical[l] >= 0 && currentColumn+horizontal[l] < 8 && currentColumn+horizontal[l] >= 0)
            accessability[currentRow+vertical[l]][currentColumn+horizontal[l]]--;
}
int one_more_stroke(int &possible_way_to_move, int &y, int accessibility[][8], int &currentRow, int &currentColumn, int vertical[], int horizontal[])
{
    int mini=10, maxi=10;
    for( int i=0; i<8; i++)
        if(mini > accessibility[currentRow+vertical[possible_way_to_move]+vertical[i]][currentColumn+vertical[possible_way_to_move]+horizontal[i]])
            mini = accessibility[currentRow+vertical[possible_way_to_move]+vertical[i]][currentColumn+vertical[possible_way_to_move]+horizontal[i]];
    for( int i=0; i<8; i++)
        if(maxi > accessibility[currentRow+vertical[y]+vertical[i]][currentColumn+vertical[y]+horizontal[i]])
            maxi = accessibility[currentRow+vertical[y]+vertical[i]][currentColumn+vertical[y]+horizontal[i]];
    return(mini>maxi) ?y :possible_way_to_move;
}

Вот сообственно код... После его написания я понял что серьёзно болен так как нормальный человек такое не наваяет) Программа вышла прямо скажем "грязная" и я хотел бы спросить способы её оптимизации...
Вот сообственно как звучит задача:

Не по теме:

(Путешествие коня) Одной из наиболее интересных шахматных головоломок
является задача о путешествии коня, впервые предложенная математиком
Эйлером. Вопрос заключается в следующем: может ли шахматная фигура,
называемая конем, обойти все 64 клетки шахматной доски, побывав на каждой из них
только один раз? Рассмотрим эту интересную задачу более подробно.
Конь ходит «буквой Г» (на две клетки в каком-либо направлении и затем на одну
клетку в перпендикулярном ему). Таким образом, из клетки в середине пустой
доски конь может сделать восемь разных ходов (пронумерованных от 0 до 7), как
показано на рис. 7.34.
Рис. 7.34. Восемь возможных ходов коня
a) Нарисуйте на листе бумаги шахматную доску 8 на 8 и попытайтесь выполнить
путешествие коня вручную. Пометьте цифрой 1 первую клетку, куда вы ходите
конем, цифрой 2 вторую, цифрой 3 третью и т.д. Перед началом путешествия
определите, на сколько ходов вперед вы будете думать, памятуя о том, что полное
путешествие состоит из 64 ходов. Как далеко вы уйдете? Что препятствует
вашим планам?
b) Теперь разработайте программу передвижения коня по шахматной доске.
Доску представим двумерным массивом board 8 на 8. Каждой клетке дадим
нулевое начальное значение. Опишем каждый из восьми возможных ходов в
терминах их горизонтальной и вертикальной компонент. Например, ход типа 0,
как показано на рис. 7.25, содержит перемещение на две клетки
горизонтально направо и на одну клетку вертикально вверх. Ход 2 состоит из
перемещения на одну клетку горизонтально налево и на две клетки вертикально вверх.
Горизонтальные перемещения налево и вертикальные перемещения вверх
будем отмечать отрицательными числами. Восемь ходов, которые могли бы быть
описаны двумя одномерными массивами, horizontal и vertical, выглядят
следующим образом:
horizontal[ 0 ] = 2
horizontal[ 1 ] = 1
horizontal[ 2 ] = -1
horizontal[ 3 ] = -2
horizontal[ 4 ] = -2
horizontal[ 5 ] = -1
horizontal[ 6 ] = 1
horizontal[ 7 ] = 2

vertical[ 0 ] =-1
vertical[ 1 ]= -2
vertical[ 2 ]= -2
vertical[ 3 ]= -1
vertical[ 4 ]= 1
vertical[ 5 ]= 2
vertical[ 6 ]= 2
vertical[ 7 ]= 1
Пусть переменные currentRow и currentColumn указывают строку и столбец
текущей позиции коня. Чтобы сделать ход типа moveNumber, где
moveNumber — число от 0 до 7, ваша программа использует операторы
currentRow += vertical[ moveNumber ];
currentColumn += horizontal[ moveNumber ];
Введите счетчик, который изменяется от 1 до 64. Записывайте последний
номер каждой клетки, на которую передвинулся конь. Помните, что для
контроля каждого возможного хода конем нужно видеть, был ли уже конь на этой
клетке. И, конечно, проверяйте каждый возможный ход, чтобы быть
уверенным в том, что конь не вышел за пределы доски. Теперь напишите программу
передвижения коня по доске. Запустите программу. Сколько ходов сделал
конь?
с) После попытки написать и запустить программу путешествия коня вы,
вероятно, получили более глубокие представления о задаче. Вы будете
использовать их для создания эвристики (или стратегии) передвижения коня.
Эвристика не гарантирует успеха, но при тщательной разработке обычно существенно
повышает шансы на успех. Вы можете заметить, что клетки на краях доски
более трудны для обхода, чем клетки в центре доски. Наиболее трудны для
обхода или даже недоступны четыре угловые клетки.
Интуиция может подсказать вам, что в первую очередь нужно попытаться
обойти конем наиболее трудные клетки и оставить «на потом» те, доступ к
которым проще, чтобы, когда доска окажется к концу путешествия заполненной
сделанными ходами, было больше шансов на успех.
Мы можем разработать «эвристику доступности» путем классификации
каждой клетки в соответствии с ее доступностью (в терминах хода конем,
конечно) и перемещать коня на наиболее недоступную клетку. Мы пометим
двумерный массив 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
путешествий, каждое из которых начинается со своей клетки шахматной доски.
Сколько полных путешествий удалось сделать?
d) Напишите версию программы «Путешествие коня», которая при встрече
с двумя или более альтернативными клетками с равными числами
доступности решала бы, какую клетку выбрать, просматривая вперед достижимость
клеток из числа альтернативных. Ваша программа должна ходить на клетку,
для которой следующий ход достигал бы клетки с наименьшим числом
доступности.

Вернуться к обсуждению:
Оптимизация программы C++

Следующий ответ

Другие темы раздела
C++ Динамическое распределение памяти https://www.cyberforum.ru/ cpp-beginners/ thread908925.html Прошу помощи! Даны действительные числа a1...an2 . Получить действительную квадратную матрицу порядка n<8, элементами которой являются числа , расположенные в ней по схеме. Матрица размещается в памяти динамически с помощью операции new, значение n вводится по запросу с клавиатуры. В конце работы программы освободить выделенную память. Вывести полученную матрицу Застрял тут: #include...	C++ программа с массивами, с меню Есть структура Аэропорт: название компании, дата создания, название страны, кол-во маршрутов. сделать программу в которой объявляется массив структур со следующей менюшкой: 1)чтение с клавиатуры элементов массива структур 2)вывод элементов массива на экран 3)сортировка по возрастанию кол-во направлений 4) вывод элементов с названием странны X 5) добавить новый элемент на позицию К 6)...
C++ valarray, наследование Файл использующий объекты: 123.cpp #include <iostream> #include "dma.h" #include <cstdlib> int main(void) { using std::cin; https://www.cyberforum.ru/ cpp-beginners/ thread908906.html	C++ Немогу найти в чем ошибка! #include <vcl> #include <iostream> #include <conio> #include <math> #include <iomanip> using namespace std; class info { int nv,money; https://www.cyberforum.ru/ cpp-beginners/ thread908878.html
C++ Вывксти все целые числа из диапазона от А до В, кратные трем Вывести на экран: все целые числа из диапазона от А до В, кратные трем (А<_В)	C++ Дан номер телевизионного канала (от 1 до 5).Вывести на экран наиболее популярные программы заданного канала. https://www.cyberforum.ru/ cpp-beginners/ thread908867.html Дан номер телевизионного канала (от 1 до 5).Вывести на экран наиболее популярные программы заданного канала.
C++ как рисовать графику в С++ или С Помогите пожалуйста,кто нибудь по пунктам и подробно,начиная с того,какой С или С++ нужно установить,что бы с графикой работать и пошагово как создавать там проект)))для консольного программирования знаю и у меня установлен Microsoft Visual C++ 6.0 https://www.cyberforum.ru/ cpp-beginners/ thread908846.html	C++ stl sort vector не сортирует ?! class Playlist { private: std::vector<Song> s_container; public: Playlist() { s_container=std::vector<Song>(); } double getPlaylistLengthInMinutes()const;
C++ Вычисление площади треугольника по координатам x,y https://www.cyberforum.ru/ cpp-beginners/ thread908813.html Привет, задали написать программу вычислить площади треугольника по координатам..данные координат берутся из файла и конечный результат записывается в файл.. А с файлами у меня очень туго..(	C++ Перегрузка функций https://www.cyberforum.ru/ cpp-beginners/ thread908769.html Необходимо сделать перегрузку #include <iostream> #include <cstdlib> #include <clocale> #include <algorithm> using namespace std; int InitArr(int , int); void PrintArr(int , int); bool DeleteValues(int &, int, int &);
C++ Вычислить координаты и значения экстремумов гамма-функции на отрезке (-2;2) вычислить координаты и значения экстремумов гамма-функции на отрезке (-2;2) (вообще без разницы на каком языке)	C++ Функция в функции :-) Привет! Задался дурацким вопросом :) Можно ли создать функцию внутри функции, чтоб её вызывать там всё время? Например: void Main() { void Child(){std::cout << "DIE YOU SON OF A ...." << std::endl;} .... //а где то в коде просто её вызывать типо Child(); Child(); :-) } https://www.cyberforum.ru/ cpp-beginners/ thread908756.html

	21.06.2013, 19:24