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

Задачи для тренировки и лучшего понимания - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Теория плагинов http://www.cyberforum.ru/cpp/thread123914.html
Всем привет. Для одной моей проги, нужно реализовать поддержку плагинов. Плагины предполагаются простенькие, написанные на Си. То, что плагин, это просто .so файл - понятно. То, что прога может дергать из .so файла функции - тоже понятно. 1. Непонятно то, как сам плагин сможет дергать функции из программы? 2. Программа написана на С++, но плагины предполагаю писать на Си, во избежания...
C++ ./massdown: /usr/lib/libstdc++.so.6: version `GLIBCXX_3.4.11' not found (required by ./massdown) всем хай! собираю свою программу на новом железе х86_64 долго не получалось скомпилить. при линковке получал вот такое сообщение: relocation R_X86_64_32 against `a local symbol' я так понял, это из-за того что часть библиотек от которых зависит цель, были собраны как 32-ух битные. но с этим вроде все нормально, пересобрал все либы - скомпилировалось. теперь при запуске получаю такое... http://www.cyberforum.ru/cpp/thread98890.html
Как понять этот константный указатель? C++
В общем, имеется класс Cat. Объект класса - SimpleCat. И имеется функция с константым указателем: const SimpleCat* const FunctionTwo(const SimpleCat* const theCat) Что обозначают все эти const? Насколько я понимаю: 1. Константный указатель. 2. Может ссылаться только на FunctionTwo 3. Ничего не изменяет в объекте. 4. Ничего не делает с объектом theCat.
C++ Перехват и подмена вызываемых функций
Здравствуйте. Нужно подменить вызов таких функций как open(), lstat(), stat(), read(), write(), mkdir(), chdir(), getcwd() для определенного процесса. Интересует мнение других. Как бы вы реализовали эту задачу. Спасибо!

Показать сообщение отдельно
nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 10:22     Задачи для тренировки и лучшего понимания
Я 3тий день бъюсь над задачкой о коне... придумал такую штуку:
конь стоит на клетке 0,0.
перед тем как пойдти на новую клетку, он проверяет:
а) находятся ли её координаты на поле (на пример конь не может пойдти на клетку с координатами 8,9)
б) был ли он на ней.
после хода, координаты новой клетки впихаются в стек. старая помечается "пройденной".
если не один из возможных вариантов не удовлетворяет условий а и б, конь возвращается на предидущею клетку. а клетка с которой он вернулся помечается не пройденной и вытаскивается из стека. продолжаем повторять этот процес пока все клетки не будут пройдены. вот код. но не могу найти ошибку...
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <iostream>
#include <cstdlib>
#include <conio.h>
using namespace std;
const int qoms=100;
short int desk[8][8][9];
class steps
{
    private:
        int cont[2][qoms];
        int l;
    public:
        steps();
        void addstep(int i, int k);
        void gotoback();
        void showthepath();
        int upper(int i);
};
steps::steps()
{
    for(int i=0;i<qoms;i++)
    {
        cont[0][i]=9;
        cont[1][i]=9;
    }
    l=0;
}
void steps::addstep(int i, int k)
{
    for(int j=qoms-1;j>0;j--)
    {
        cont[0][j]=cont[0][j-1];
        cont[1][j]=cont[1][j-1];
    }
    cont[0][0]=i;
    cont[1][0]=k;
    l++;
}
void steps::gotoback()
{
    for(int j=0;j<qoms-1;j++)
    {
        cont[0][j]=cont[0][j+1];
        cont[1][j]=cont[1][j+1];
    }
    for(int i=l;i<qoms;i++)
        cont[0][i]=cont[1][i]=9;
}
void steps::showthepath()
{
    for(int i=0;i<qoms;i++)
        if(cont[0][i]!=9)
            cout<<cont[0][i]<<","<<cont[1][i]<<" ";
}
int steps::upper(int i)
{
    if(i==0) return cont[0][0];
    else return cont[0][1];
}
bool isptogoto(int i, int k)
{
    if(i>=0 && i<8 && k>=0 && k<8)
        return true;
    else
        return false;
}
bool isdone()
{
    bool temp=true;
    for(int i=0;i<8;i++)
        for(int k=0;k<8;k++)
            if(desk[i][k][0]==false)
                temp=false;
    return temp;
}
int main()
{
    steps stps;
    char last;
    char lb;
    short int c=0;
    int qloq[2];
    qloq[0]=qloq[1]=0;
    stps.addstep(qloq[0],qloq[1]);
    int r;
    for(int i=0;i<8;i++)
        for(int l=0;l<8;l++)
            for(int k=0;k<9;k++)
                desk[i][l][k]=false;
    srand(time(NULL));
    while(!isdone())
    {
        if(isptogoto(qloq[0]+2, qloq[1]+1) && desk[qloq[0]][qloq[1]][1]==false && desk[qloq[0]+2][qloq[1]+1][0]==false)
        {
            stps.addstep(qloq[0]+2,qloq[1]+1);
            desk[qloq[0]][qloq[1]][1]=desk[qloq[0]+2][qloq[1]+1][0]=true;
            qloq[0]=qloq[0]+2;
            qloq[1]=qloq[1]+1;
            c++;
        } else if(isptogoto(qloq[0]+1, qloq[1]+2) && desk[qloq[0]][qloq[1]][2]==false && desk[qloq[0]+1][qloq[1]+2][0]==false)
        {
            stps.addstep(qloq[0]+1,qloq[1]+2);
            desk[qloq[0]][qloq[1]][2]=desk[qloq[0]+1][qloq[1]+2][0]=true;
            qloq[0]=qloq[0]+1;
            qloq[1]=qloq[1]+2;
            c++;
        } else if(isptogoto(qloq[0]-2, qloq[1]-1) && desk[qloq[0]][qloq[1]][3]==false && desk[qloq[0]-2][qloq[1]-1][0]==false)
        {
            stps.addstep(qloq[0]-2,qloq[1]-1);
            desk[qloq[0]][qloq[1]][3]=desk[qloq[0]-2][qloq[1]-1][0]=true;
            qloq[0]=qloq[0]-2;
            qloq[1]=qloq[1]-1;
            c++;
        } else if(isptogoto(qloq[0]-1, qloq[1]-2) && desk[qloq[0]][qloq[1]][4]==false && desk[qloq[0]-1][qloq[1]-2][0]==false)
        {
            stps.addstep(qloq[0]-1,qloq[1]-2);
            desk[qloq[0]][qloq[1]][4]=desk[qloq[0]-1][qloq[1]-2][0]=true;
            qloq[0]=qloq[0]-1;
            qloq[1]=qloq[1]-2;
            c++;
        } else if(isptogoto(qloq[0]-2, qloq[1]+1) && desk[qloq[0]][qloq[1]][5]==false && desk[qloq[0]-2][qloq[1]+1][0]==false)
        {
            stps.addstep(qloq[0]-2,qloq[1]+1);
            desk[qloq[0]][qloq[1]][5]=desk[qloq[0]-2][qloq[1]+1][0]=true;
            qloq[0]=qloq[0]-2;
            qloq[1]=qloq[1]+1;
            c++;
        } else if(isptogoto(qloq[0]+1, qloq[1]-2) && desk[qloq[0]][qloq[1]][6]==false && desk[qloq[0]+1][qloq[1]-2][0]==false)
        {
            stps.addstep(qloq[0]+1,qloq[1]-2);
            desk[qloq[0]][qloq[1]][6]=desk[qloq[0]+1][qloq[1]-2][0]=true;
            qloq[0]=qloq[0]+1;
            qloq[1]=qloq[1]-2;
            c++;
        } else if(isptogoto(qloq[0]+2, qloq[1]-1) && desk[qloq[0]][qloq[1]][7]==false && desk[qloq[0]+2][qloq[1]-1][0]==false)
        {
            stps.addstep(qloq[0]+2,qloq[1]-1);
            desk[qloq[0]][qloq[1]][7]=desk[qloq[0]+2][qloq[1]-1][0]=true;
            qloq[0]=qloq[0]+2;
            qloq[1]=qloq[1]-1;
            c++;
        } else if(isptogoto(qloq[0]-1, qloq[1]+2) && desk[qloq[0]][qloq[1]][8]==false && desk[qloq[0]-1][qloq[1]+2][0]==false)
        {
            stps.addstep(qloq[0]-1,qloq[1]+2);
            desk[qloq[0]][qloq[1]][8]=desk[qloq[0]-1][qloq[1]+2][0]=true;
            qloq[0]=qloq[0]-1;
            qloq[1]=qloq[1]+2;
            c++;
        } else
        {
            stps.gotoback();
            if(stps.upper(0)+2==qloq[0] && stps.upper(1)+1==qloq[1]) {desk[stps.upper(0)][stps.upper(1)][1]=true; r=1;}
            else if(stps.upper(0)+1==qloq[0] && stps.upper(1)+2==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][2]=true; r=2;}
            else if(stps.upper(0)-2==qloq[0] && stps.upper(1)-1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][3]=true; r=3;}
            else if(stps.upper(0)-1==qloq[0] && stps.upper(1)-1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][4]=true; r=4;}
            else if(stps.upper(0)-2==qloq[0] && stps.upper(1)+1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][5]=true; r=5;}
            else if(stps.upper(0)+1==qloq[0] && stps.upper(1)-2==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][6]=true; r=6;}
            else if(stps.upper(0)+2==qloq[0] && stps.upper(1)-1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][7]=true; r=7;}
            else if(stps.upper(0)-1==qloq[0] && stps.upper(1)+2==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][8]=true; r=8;}
            for(int t=0;t<9;t++)
                if(t!=r)
                    desk[qloq[0]][qloq[1]][t]=false;
            desk[qloq[0]][qloq[1]][0]=false;
            qloq[0]=stps.upper(0);
            qloq[1]=stps.upper(1);
            desk[qloq[0]][qloq[1]][0]=true;
            c--;
        }
        system("cls");
        for(int x=0;x<8;x++)
        {
            for(int y=0;y<8;y++)
                if(x==qloq[0] && y==qloq[1])
                    cout<<"O";
                else if(desk[x][y][0]==true)
                    cout<<"X ";
                else 
                    cout<<". ";
            cout<<"\n";
        }
        getch();
    }
    stps.showthepath();
    getch();
    return 0;
}
Добавлено через 57 минут
ЛЮДИ!!!! Мы тут мучеемся, а оказывается существует Правило Варнсдорфа.
Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.

Правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

На практике это реализуется, например, следующим образом. Перед каждым ходом коня вычисляется рейтинг ближайших доступных полей - полей, на которых конь еще не был, и на которые он может перейти за один ход. Рейтинг поля определяется числом ближайших доступных с него полей. Чем меньше рейтинг, тем он лучше. Потом делается ход на поле с наименьшим рейтингом (на любое из таковых, если их несколько), и так далее, пока есть куда ходить.

Эвристика всегда работает на досках от 5x5 до 76x76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.
 
Текущее время: 06:32. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru