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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 2744, средняя оценка - 4.89
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7954 / 4716 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
15.07.2010, 05:53     Задачи для тренировки и лучшего понимания #1
Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо.

Список задач, решение которых присутствует в данной теме:
Лучшие ответы (59)
Сообщение: #857841 Сообщение: #857861 Сообщение: #858352 Сообщение: #859371 Сообщение: #860160 Сообщение: #860255 Сообщение: #860259 Сообщение: #860317 Сообщение: #860368 Сообщение: #860466 Сообщение: #860508 Сообщение: #860720 Сообщение: #861091 Сообщение: #862174 Сообщение: #862617 Сообщение: #867259 Сообщение: #870298 Сообщение: #872053 Сообщение: #876456 Сообщение: #880114 Сообщение: #882889 Сообщение: #884418 Сообщение: #886414 Сообщение: #886989 Сообщение: #887733 Сообщение: #888464 Сообщение: #888487 Сообщение: #888941 Сообщение: #888947 Сообщение: #889040 Сообщение: #889450 Сообщение: #889587 Сообщение: #891772 Сообщение: #891790 Сообщение: #891862 Сообщение: #897758 Сообщение: #897782 Сообщение: #906325 Сообщение: #907991 Сообщение: #943672 Сообщение: #943700 Сообщение: #967735 Сообщение: #1053777 Сообщение: #1054209 Сообщение: #1083853 Сообщение: #1083928 Сообщение: #1131058 Сообщение: #1131359 Сообщение: #1273743 Сообщение: #1275465 Сообщение: #1276743 Сообщение: #1279215 Сообщение: #1282583 Сообщение: #1309088 Сообщение: #1315633 Сообщение: #1366395 Сообщение: #1550164 Сообщение: #1603678 Сообщение: #1604364
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.07.2010, 05:53     Задачи для тренировки и лучшего понимания
Посмотрите здесь:

C++ Какой компилятор выбрать для лучшего изучения С++ по книге Берна Страуструпа?п
C++ Элементарные программы, для лучшего понимания языка...
Нужны задачи для тренировки C++
C++ Киньте задачки для тренировки
C++ Нужны простые задачи для тренировки
Нужны задачи для тренировки C++
На соревнованиях по фигурному катанию оценки заносятся в компьютер. Составить программу для вывода на экран лучшего результата после каждого выступлен C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4248 / 2780 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
27.08.2010, 20:44     Задачи для тренировки и лучшего понимания #741
Цитата Сообщение от nikkka Посмотреть сообщение
А вот очень старая, "класическая" задача о коне.
конь стоит в левом нижнем углу шахматной доски. ходит как обыно, Г-образно. надо обойти все клетки. НА ОДНУ КЛЕТКУ НЕЛЬЗЯ СТАНОВИТСЯ БОЛЕЕ ОДНОГО РАЗА. найдти количество ходов.
можно вывести на экран передвижения коня в "шахматной" записи, но это не обязательно.
Долго я над ней думал!!! Вот написал код, там есть вывод максимального просчитанного хода (это временно), так вот программа очень быстро считает до 60го (посути до 59го) хода, потом долго думает, очень долго), я так и не дождался когда она закончит, поэтому пишу сюда - может кто-нибудь что-нибудь подскажет)
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
#include <iostream>
using namespace std;
class board {
protected:    
    int desk[8][8];
    int x,y;//текущие координаты
    board();//    
 };
//########## CLASS HORSE ########################### 
class Horse : private board{
    int course[63]; //направление хода
    int counts;  // Счетчик ходов 
public:
    Horse();  
    void go();
    int *courseP;
    bool step(int i,int j);//возможен ли ход
};      
//################################################ 
 
//############# BOARD #######################      
board::board():x(1),y(1){
    memset(desk,0,sizeof(desk)); 
    desk[0][0]=1;}
//############ END BOARD ####################
 
//############ HORSE ########################         
Horse::Horse(){
        memset(course,0,sizeof(course));
        counts=1;
        courseP=course;
        } 
 
bool Horse::step(int i,int j){
        return ((i>=1)&&(i<=8)&&(j>=1)&&(j<=8)&&(desk[i-1][j-1]==0));}
                
void Horse::go(){
        int max=0; //Это просто для отладки, чтоб понимать, что происходит)
        while(counts<=64){       
            if(counts>max){
            max=counts;
            cout<<endl<<"MAXCOUNT = "<<max<<endl;}
        switch (*courseP){ //направление хода   
            case 0:if(step(x+2,y-1)){//вверх влево
                    x+=2;y-=1; // текущие координаты
                    desk[x-1][y-1]=++counts;//записать ход
                    ++courseP;
                    break;}
                    else ++*courseP;
                            
            case 1: if(step(x+2,y+1)){//вверх вправо
                    x+=2;y+=1;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else ++*courseP;
                            
            case 2: if(step(x+1,y+2)){//вправо вверх
                    x+=1,y+=2;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else ++*courseP;
                            
            case 3: if(step(x-1,y+2)){//вправо вниз
                    x-=1;y+=2;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else ++*courseP;
                                    
            case 4: if(step(x-2,y+1)){//вниз вправо
                    x-=2;y+=1;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else ++*courseP;
                                    
            case 5: if(step(x-2,y-1)){//вниз влево
                    x-=2;y-=1;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else ++*courseP;
                            
            case 6: if(step(x-1,y-2)){//влево вниз
                    x-=1;y-=2;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else ++*courseP;
                             
            case 7: if(step(x+1,y-2)){//влево вверх
                    x+=1;y-=2;
                    desk[x-1][y-1]=++counts;
                    ++courseP;
                    break;}
                    else {*courseP=0;//если нет хода
                    --courseP;  
                    desk[x-1][y-1]=0;
                    counts--;
                    switch (*courseP){
                            case 0:x-=2;y+=1;break;//предыдущие координаты
                            case 1:x-=2;y-=1;break;
                            case 2:x-=1,y-=2;break;
                            case 3:x+=1;y-=2;break;
                            case 4:x+=2;y-=1;break;
                            case 5:x+=2;y+=1;break;
                            case 6:x+=1;y+=2;break;
                            case 7:x-=1;y+=2;break;}
                    ++*courseP; 
            //Это просто для отладки, посмотреть что выводит////////        
              for(int i=7;i>=0;i--){
              for(int j=0;j<8;j++)
              if(desk[i][j]/10==0)
              cout<<"[ "<<desk[i][j]<<"] ";
              else cout<<"["<<desk[i][j]<<"] ";
              cout<<endl<<endl;}
              cout<<endl<<endl<<endl<<endl;
           /////////////////////////////////////////////////////////    
          }             
                           
                        }
               
          }}
int main(){
    Horse ob;
    ob.go();
    system("pause");
    return 0;
}
Так же есть готовые ф-ции по формированию и вывода строки ходов (А1 С2 и т.д.), но я убрал это из кода, т.к. в данном случае это не принципиально.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5759 / 3408 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
28.08.2010, 05:40     Задачи для тренировки и лучшего понимания #742
Kastaneda, для решения этой задачи нужно пользоваться методом перебора с возвратом, вот(внимание, по первой ссылке - жестокие спойлеры!)
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
28.08.2010, 19:12     Задачи для тренировки и лучшего понимания #743
Не пойму, где накосячил "про коня"

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct
{
   int x, y;
}  pos_t;
 
#define NROW 8
#define NCOL 8
 
 
/* Возможность шага на клетку */
#define UPLEFT \
   ((pos.x - 2 >= 0 && pos.y - 1 >= 0 && board[pos.x-2][pos.y-1] == 0) ? 1 : 0)
 
#define LEFTUP \
   ((pos.x - 1 >= 0 && pos.y - 2 >= 0 && board[pos.x-1][pos.y-2] == 0) ? 1 : 0)
   
#define DOWNLEFT \
   ((pos.x + 2 < NROW && pos.y - 1 >= 0 && board[pos.x+2][pos.y-1] == 0) ? 1 : 0)
   
#define LEFTDOWN \
   ((pos.x + 1 < NROW && pos.y - 2 >= 0 && board[pos.x+1][pos.y-2] == 0) ? 1 : 0)
     
#define UPRIGHT \
   ((pos.x - 2 >= 0 && pos.y + 1 < NCOL && board[pos.x-2][pos.y+1] == 0) ? 1 : 0)
   
#define RIGHTUP \
   ((pos.x - 1 >= 0 && pos.y + 2 < NCOL && board[pos.x-1][pos.y+2] == 0) ? 1 : 0)
   
#define DOWNRIGHT \
   ((pos.x + 2 < NROW && pos.y + 1 < NCOL && board[pos.x+2][pos.y+1] == 0) ? 1 : 0)
   
#define RIGHTDOWN \
   ((pos.x + 1 < NROW && pos.y + 2 < NCOL && board[pos.x+1][pos.y+2] == 0) ? 1 : 0)
   
pos_t pos;                 /* текущая позиция фигуры */
pos_t path[NROW*NCOL];     /* стек для записи ходов */
 
int board[NROW][NCOL];     /* доска */
int nstep;                 /* номер хода */
 
void FindPath();
void Step(int x, int y);   /* сделать ход на "x" клеток вниз и "y" клеток вправо, отрицательные значения соответственно вверх и влево */
void BackStep();           /* шаг назад */
int End();                 /* проверка на завершение, если все клетки пройдены 1, если нет 0 */
   
int main()
{
   int i, j;
 
   pos.x = NROW - 1;
   pos.y = 0;
   
   nstep = 1;
   
   FindPath();
   
   for(i = 0; i < NROW; ++i) {
      for(j = 0; j < NCOL; ++j)
         printf("%02d ", board[i][j]);
      printf("\n");
   }
   
   for(i = 0; i < NROW * NCOL; ++i)
      printf("%d) %d %d || ", i, path[i].x, path[i].y);
}
 
void FindPath()
{
   if(End())
      return;
      
   if     (UPLEFT)    { Step(-2,-1); }
   else if(LEFTUP)    { Step(-1,-2); }
   else if(DOWNLEFT)  { Step( 2,-1); }
   else if(LEFTDOWN)  { Step( 1,-2); }
   else if(UPRIGHT)   { Step(-2, 1); }
   else if(RIGHTUP)   { Step(-1, 2); }
   else if(DOWNRIGHT) { Step( 2, 1); }
   else if(RIGHTDOWN) { Step( 1, 2); }
   
   else {
      BackStep();
   }
   
   FindPath();
}
int End()
{
   int i, j;
   
   for(i = 0; i < NROW; ++i)
      for(j = 0; j < NCOL; ++j)
         if(board[i][j] == 0)
            return 0;
            
   return 1;
}
 
void Step(int x, int y)
{
   board[pos.x][pos.y] = nstep;
   path[nstep] = pos;
   
   pos.x += x;
   pos.y += y;
   
   ++nstep;
}
 
void BackStep()
{
   board[pos.x][pos.y] = 0;
   pos = path[nstep - 1];
   
   --nstep;
}
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4248 / 2780 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
28.08.2010, 20:12     Задачи для тренировки и лучшего понимания #744
fasked могу ошибаться, но я думаю ваша ошибка в том, что нет контроля типа "так я уже ходил, ни чего не получилось, больше так ходить не надо)" Например идем вверх вправо, вверх влево, вправо вниз и ОП - дальше хода нет, делаем шаг назад, пробуем ходить дальше и ОПЯТЬ идем вправо вниз (мы же не "знаем", что так ходить нельзя, что первое попалось в if else (в FindPath())туда и идем) и так происходит очень много раз, из-за чего происходит ошибка сигментации памяти (при ходе назад что-то же куда-то пишется) Вот, по-моему так)
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 10:22     Задачи для тренировки и лучшего понимания #745
Я 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 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4248 / 2780 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
05.09.2010, 11:55     Задачи для тренировки и лучшего понимания #746
Цитата Сообщение от nikkka Посмотреть сообщение
придумал такую штуку:
конь стоит на клетке 0,0.
перед тем как пойдти на новую клетку, он проверяет:
а) находятся ли её координаты на поле (на пример конь не может пойдти на клетку с координатами 8,9)
б) был ли он на ней.
после хода, координаты новой клетки впихаются в стек. старая помечается "пройденной".
если не один из возможных вариантов не удовлетворяет условий а и б, конь возвращается на предидущею клетку. а клетка с которой он вернулся помечается не пройденной и вытаскивается из стека. продолжаем повторять этот процес пока все клетки не будут пройдены.
nikkka, у меня такой же алгоритм, только без стека (через массив), у faskedа тоже такой же. А вообще я находил в сети решение где-то в 50 сторок на С, но не стал его сюда выкладывать, пробовал сам написать)(причем так, чтоб не повторять найденное решение)) А вот про Правило Варнсдорфа не знал, спасибо. Интересно на чем оно основывается?
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 12:05     Задачи для тренировки и лучшего понимания #747
Цитата Сообщение от Kastaneda Посмотреть сообщение
Интересно на чем оно основывается?
правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

Добавлено через 2 минуты
Цитата Сообщение от Kastaneda Посмотреть сообщение
у меня такой же алгоритм, только без стека (через массив), у faskedа тоже такой же
я добавил проверку на "пройденность": "я уже пробовал так ходить, и ничего хорошого не вышло".
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4248 / 2780 / 219
Регистрация: 12.12.2009
Сообщений: 7,109
Записей в блоге: 1
Завершенные тесты: 1
05.09.2010, 12:07     Задачи для тренировки и лучшего понимания #748
Цитата Сообщение от nikkka Посмотреть сообщение
правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.
)))Да читать то я умею) Мне интересно - почему выбирается клетка, с которой существует наименьшее количество возможных ходов? Это же должно как то логически обосновываться.

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от nikkka Посмотреть сообщение
я добавил проверку на "пройденность": "я уже пробовал так ходить, и ничего хорошого не вышло".
У меня это есть, просто может быть по коду не совсем понятно как это реализованно.

nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 12:24     Задачи для тренировки и лучшего понимания #749
Цитата Сообщение от Kastaneda Посмотреть сообщение
Мне интересно - почему выбирается клетка, с которой существует наименьшее количество возможных ходов?
А... Думаю это будет не так уж и просто понять... Над задачкой ведь бились с IX века!...
http://en.wikipedia.org/wiki/Knight's_tour
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16935 / 5340 / 328
Регистрация: 30.03.2009
Сообщений: 14,353
Записей в блоге: 26
05.09.2010, 13:03     Задачи для тренировки и лучшего понимания #750
Цитата Сообщение от Lavroff Посмотреть сообщение
Кто-нибудь может дать задачу для тренировки?
Есть игрушка: http://www.gamereclaim.com/2008/10/h...nk-request-01/
Составить программу, которая решает уровень методом перебора
Графическая часть не нужна. Просто в каком-то виде задать уровень и в каком-то виде напечатать результат
лендер
46 / 46 / 2
Регистрация: 12.01.2010
Сообщений: 183
05.09.2010, 15:02     Задачи для тренировки и лучшего понимания #751
Цитата Сообщение от k1ry4 Посмотреть сообщение
Lavroff, есть ещё одна (подскажу, что тема - графы)
На телефонном аппарате имеется десять кнопок, расположенных следующим образом:
[1][2][3]
[4][5][6]
[7][8][9]
... [0] ...
Конь может стартовать с любой кнопки и передвигаться на следующую только Г-образным ходом (т.е. с кнопки 1 он может попасть либо на 6, либо на 8). Сколько различных N-значных номеров можно набрать таким образом?

Всё зависит от конфигурации поля, можно придумать поизощрённее.

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
int main(void){
int nomerov = 1, N = 5;
    
    while(N--)
     nomerov *= 2;
 
cout << nomerov;
return 0;
}
Немного поздновато но всеже
откуда бы конь не начинал ити, где бы не стоял, при такой раскладке он может пойти всего на две кнопки.
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
05.09.2010, 15:10     Задачи для тренировки и лучшего понимания #752
Из 4 и 6 на 3 кнопки, из 5 на 0 кнопок.
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 17:54     Задачи для тренировки и лучшего понимания #753
Цитата Сообщение от лендер Посмотреть сообщение
Немного поздновато но всеже
откуда бы конь не начинал ити, где бы не стоял, при такой раскладке он может пойти всего на две кнопки.
ничего не понял

Добавлено через 10 минут
Цитата Сообщение от лендер Посмотреть сообщение
откуда бы конь не начинал ити ... он может пойти всего на две кнопки.
неправда. если он стартует с кнопки 6, то у него 3 варианта следуйшей цифры, а если с 5 то вариантов 0.

Добавлено через 7 минут
Цитата Сообщение от лендер Посмотреть сообщение
Lavroff, есть ещё одна (подскажу, что тема - графы)
На телефонном аппарате имеется десять кнопок, расположенных следующим образом:
[1][2][3]
[4][5][6]
[7][8][9]
... [0] ...
Конь может стартовать с любой кнопки и передвигаться на следующую только Г-образным ходом (т.е. с кнопки 1 он может попасть либо на 6, либо на 8). Сколько различных N-значных номеров можно набрать таким образом?
Всё зависит от конфигурации поля, можно придумать поизощрённее.
а с 0 номер начинать можно?
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
05.09.2010, 18:59     Задачи для тренировки и лучшего понимания #754
nikkka, в подобных задачах если что-то не запрещено, значит можно.
лендер
46 / 46 / 2
Регистрация: 12.01.2010
Сообщений: 183
05.09.2010, 20:07     Задачи для тренировки и лучшего понимания #755
да, затупил я
думал самый умный
nikkka
Мат в 32 хода
 Аватар для nikkka
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 20:34     Задачи для тренировки и лучшего понимания #756
лендер, со всеми бывает
кстате, есть намного более лёгкий способ возведения двойки в степень. с помощю битогого сдвига.
а вот и моё решение:
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
#include <iostream>
using namespace std;
int main()
{
    int nn;
    cin>>nn;
    const int n=nn;
    int a[n][10];
    for(int l=0;l<n;l++)
        for(int k=0;k<10;k++)
            if(l==0)
                a[l][k]=1;
            else
                a[l][k]=0;
    for(int i=1;i<n;i++)
    {
        a[i][0]+=a[i-1][4]+a[i-1][6];
        a[i][1]+=a[i-1][8]+a[i-1][6];
        a[i][2]+=a[i-1][9]+a[i-1][7];
        a[i][3]+=a[i-1][4]+a[i-1][8];
        a[i][4]+=a[i-1][9]+a[i-1][3]+a[i-1][0];
        a[i][5]=0;
        a[i][6]+=a[i-1][7]+a[i-1][0]+a[i-1][0];
        a[i][7]+=a[i-1][2]+a[i-1][6];
        a[i][8]+=a[i-1][1]+a[i-1][3];
        a[i][9]+=a[i-1][4]+a[i-1][2];
    }
    int sum=0;
    for(int j=0;j<10;j++)
        if(n==1 || j!=5)
            sum+=a[n-1][j];
    cout<<sum;
    return 0;
}
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
06.09.2010, 17:44     Задачи для тренировки и лучшего понимания #757
Вспомнил простенькую задачку, интересно, какие будут решения)
Дана последовательность из N чисел. Вывести эту последовательность в обратном порядке. В программе запрещено использовать массивы.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7954 / 4716 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
06.09.2010, 17:45  [ТС]     Задачи для тренировки и лучшего понимания #758
Хохол, А векторы?)
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.09.2010, 17:47     Задачи для тренировки и лучшего понимания #759
Цитата Сообщение от Lavroff Посмотреть сообщение
А векторы?
стек - линейный список
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.09.2010, 17:48     Задачи для тренировки и лучшего понимания
Еще ссылки по теме:

C++ Какая база требуется для понимания C++?
C++ Нужен пример рекурсивной функции для понимания ее назначения и практической пользы
C++ Builder Прошу примеров для понимания INDY
Книги для тренировки/развития котелка и просто убийства времени C++
Дайте задания для тренировки C++

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

Или воспользуйтесь поиском по форуму:
Nameless One
Эксперт С++
 Аватар для Nameless One
5759 / 3408 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
06.09.2010, 17:48     Задачи для тренировки и лучшего понимания #760
Хохол, а как заданная последовательность представляется в программе?
Yandex
Объявления
06.09.2010, 17:48     Задачи для тренировки и лучшего понимания
Закрытая тема Создать тему
Опции темы

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