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

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

Войти
Регистрация
Восстановить пароль
 
Sh0cK
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 58
Завершенные тесты: 1
#1

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

21.06.2013, 19:24. Просмотров 667. Ответов 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) Напишите версию программы «Путешествие коня», которая при встрече
с двумя или более альтернативными клетками с равными числами
доступности решала бы, какую клетку выбрать, просматривая вперед достижимость
клеток из числа альтернативных. Ваша программа должна ходить на клетку,
для которой следующий ход достигал бы клетки с наименьшим числом
доступности.

0
Миниатюры
Оптимизация программы  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 19:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оптимизация программы (C++):

Оптимизация программы - C++
Нужно, чтобы программа случайным образом придумывала число от 1 до 32767 и печатала его цифры через 2 пробела. (Например, 4236 печатает 4 ...

Оптимизация программы - C++
Как ещё можно оптимизировать нижеприведенный код? По условию задачи он выполняется дооолго. Собственно вот задача: В секретной...

Оптимизация программы - C++
Условие : Даны две действительные квадратные матрицы порядка n. Получить новую матрицу прибавлением к элементам каждого столбца первой...

Оптимизация программы - C++
Здравствуйте,задали задачку :Напишите программу, которая будет выполнять последовательность запросов вида ADD num, PRESENT num и COUNT (без...

Оптимизация программы на С++ - C++
Помогите оптимизировать программу на С++, я не представляю, что в ней можно изменить. Хотя бы намек на функцию, в которой нужна...

Оптимизация программы - C++
Помогите оптимизировать программу, не могу сам. #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main() ...

1
Sh0cK
0 / 0 / 0
Регистрация: 28.10.2012
Сообщений: 58
Завершенные тесты: 1
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;
}
Тема закрыта. Сам смог)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.06.2013, 01:25
Привет! Вот еще темы с ответами:

Оптимизация программы - C++
Ув. обыватели, Вчера написал &quot;Калькулятор&quot;, но так как я ещё зеленый в программировании на С++, прошу вас показать как и где можно...

Оптимизация кода программы - C++
Задача В качестве самостоятельного задания исследуйте предельные значения N! (1*2*3*..*n) для двух указанных типов (long int и unsigned...

Оптимизация программы по памяти - C++
Здравствуйте, дорогие коллеги! Прошу вашей помощи. Кто чем поможет. Есть минимальная программа рекомендательной системы( код ниже...

Оптимизация простой программы - C++
Суть задачи такова: программа должна вычислить сумму цифр которые делятся на a или b и цифры должны быть меньше n. Максимальное число n =...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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