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

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

Восстановить пароль Регистрация
 
Sh0cK
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 58
21.06.2013, 19:24     Оптимизация программы #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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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) Напишите версию программы «Путешествие коня», которая при встрече
с двумя или более альтернативными клетками с равными числами
доступности решала бы, какую клетку выбрать, просматривая вперед достижимость
клеток из числа альтернативных. Ваша программа должна ходить на клетку,
для которой следующий ход достигал бы клетки с наименьшим числом
доступности.

Миниатюры
Оптимизация программы  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 19:24     Оптимизация программы
Посмотрите здесь:

C++ Оптимизация кода программы
C++ Оптимизация программы на С++
Оптимизация простой программы C++
Оптимизация программы C++
Оптимизация программы C++
C++ Оптимизация программы
C++ Оптимизация программы
C++ Оптимизация программы по памяти

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sh0cK
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 58
22.06.2013, 01:25  [ТС]     Оптимизация программы #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
#include<std_lib_facilities.h>
#include<conio.h>
 
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 move;
    int currentRow,currentColumn;
    cin >> currentRow >> currentColumn;
    board[currentRow][currentColumn]=1;
    for(int moves=0; moves < arraySize*arraySize; moves++)
    {
        int min=10;
        for(int moveNumber=0; moveNumber<arraySize; moveNumber++)
        {
            currentRow+=vertical[moveNumber];
            currentColumn+=horizontal[moveNumber];
            if(currentRow < 8 && currentColumn < 8 &&currentRow >= 0 && currentColumn >= 0)
            {
                if(min>accessibility[currentRow][currentColumn] && board[currentRow][currentColumn]==0)
                {
                    min=accessibility[currentRow][currentColumn];
                    move=moveNumber;
                }
                accessibility[currentRow][currentColumn]--;
            }
            currentRow-=vertical[moveNumber];
            currentColumn-=horizontal[moveNumber];
        }
    currentRow+=vertical[move];
    currentColumn+=horizontal[move];
    board[currentRow][currentColumn]=moves+1;
    cout << moves << "\n";
    }
    for(int u=0; u<arraySize; u++)
    {
        for(int o=0; o<arraySize; o++)
            cout << board[u][o] << "\t";
        cout << "\n";
    }
    _getch();
    return 0;
}
Тема закрыта. Сам смог)
Yandex
Объявления
22.06.2013, 01:25     Оптимизация программы
Ответ Создать тему
Опции темы

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