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

@ForEveR · Регистрация: 24.06.2010

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

Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо.

Список задач, решение которых присутствует в данной теме:

@Kastaneda · 27.08.2010, 20:44

Сообщение от 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 · 28.08.2010, 05:40

Kastaneda, для решения этой задачи нужно пользоваться методом перебора с возвратом, вот(внимание, по первой ссылке - жестокие спойлеры!)

@fasked · 28.08.2010, 19:12

Не пойму, где накосячил "про коня"

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 · 28.08.2010, 20:12

fasked могу ошибаться, но я думаю ваша ошибка в том, что нет контроля типа "так я уже ходил, ни чего не получилось, больше так ходить не надо)" Например идем вверх вправо, вверх влево, вправо вниз и ОП - дальше хода нет, делаем шаг назад, пробуем ходить дальше и ОПЯТЬ идем вправо вниз (мы же не "знаем", что так ходить нельзя, что первое попалось в if else (в FindPath())туда и идем) и так происходит очень много раз, из-за чего происходит ошибка сигментации памяти (при ходе назад что-то же куда-то пишется) Вот, по-моему так)

@nikkka · 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 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.

@Kastaneda · 05.09.2010, 11:55

Сообщение от nikkka

придумал такую штуку:
конь стоит на клетке 0,0.
перед тем как пойдти на новую клетку, он проверяет:
а) находятся ли её координаты на поле (на пример конь не может пойдти на клетку с координатами 8,9)
б) был ли он на ней.
после хода, координаты новой клетки впихаются в стек. старая помечается "пройденной".
если не один из возможных вариантов не удовлетворяет условий а и б, конь возвращается на предидущею клетку. а клетка с которой он вернулся помечается не пройденной и вытаскивается из стека. продолжаем повторять этот процес пока все клетки не будут пройдены.

nikkka, у меня такой же алгоритм, только без стека (через массив), у faskedа тоже такой же. А вообще я находил в сети решение где-то в 50 сторок на С, но не стал его сюда выкладывать, пробовал сам написать)(причем так, чтоб не повторять найденное решение)) А вот про Правило Варнсдорфа не знал, спасибо. Интересно на чем оно основывается?

@nikkka · 05.09.2010, 12:05

Сообщение от Kastaneda

Интересно на чем оно основывается?

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

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

Сообщение от Kastaneda

у меня такой же алгоритм, только без стека (через массив), у faskedа тоже такой же

я добавил проверку на "пройденность": "я уже пробовал так ходить, и ничего хорошого не вышло".

@Kastaneda · 05.09.2010, 12:07

Сообщение от nikkka

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

)))Да читать то я умею) Мне интересно - почему выбирается клетка, с которой существует наименьшее количество возможных ходов? Это же должно как то логически обосновываться.

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

Не по теме:

Сообщение от nikkka

я добавил проверку на "пройденность": "я уже пробовал так ходить, и ничего хорошого не вышло".

У меня это есть, просто может быть по коду не совсем понятно как это реализованно.

@nikkka · 05.09.2010, 12:24

Сообщение от Kastaneda

Мне интересно - почему выбирается клетка, с которой существует наименьшее количество возможных ходов?

А... Думаю это будет не так уж и просто понять... Над задачкой ведь бились с IX века!...
http://en.wikipedia.org/wiki/Knight's_tour

Evg · 05.09.2010, 13:03

Сообщение от Lavroff

Кто-нибудь может дать задачу для тренировки?

Есть игрушка: http://www.gamereclaim.com/200... equest-01/
Составить программу, которая решает уровень методом перебора
Графическая часть не нужна. Просто в каком-то виде задать уровень и в каком-то виде напечатать результат

@лендер · 05.09.2010, 15:02

Сообщение от 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;
}

Немного поздновато но всеже
откуда бы конь не начинал ити, где бы не стоял, при такой раскладке он может пойти всего на две кнопки.

@Хохол · 05.09.2010, 15:10

Из 4 и 6 на 3 кнопки, из 5 на 0 кнопок.

@nikkka · 05.09.2010, 17:54

Сообщение от лендер

Немного поздновато но всеже
откуда бы конь не начинал ити, где бы не стоял, при такой раскладке он может пойти всего на две кнопки.

ничего не понял

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

Сообщение от лендер

откуда бы конь не начинал ити ... он может пойти всего на две кнопки.

неправда. если он стартует с кнопки 6, то у него 3 варианта следуйшей цифры, а если с 5 то вариантов 0.

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

Сообщение от лендер

Lavroff, есть ещё одна (подскажу, что тема - графы)
На телефонном аппарате имеется десять кнопок, расположенных следующим образом:
[1][2][3]
[4][5][6]
[7][8][9]
... [0] ...
Конь может стартовать с любой кнопки и передвигаться на следующую только Г-образным ходом (т.е. с кнопки 1 он может попасть либо на 6, либо на 8). Сколько различных N-значных номеров можно набрать таким образом?
Всё зависит от конфигурации поля, можно придумать поизощрённее.

а с 0 номер начинать можно?

@Хохол · 05.09.2010, 18:59

nikkka, в подобных задачах если что-то не запрещено, значит можно.

@лендер · 05.09.2010, 20:07

да, затупил я

думал самый умный

@nikkka · 05.09.2010, 20:34

лендер, со всеми бывает

кстате, есть намного более лёгкий способ возведения двойки в степень. с помощю битогого сдвига.
а вот и моё решение:

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;
}

@Хохол · 06.09.2010, 17:44

Вспомнил простенькую задачку, интересно, какие будут решения)
Дана последовательность из N чисел. Вывести эту последовательность в обратном порядке. В программе запрещено использовать массивы.

@ForEveR · 06.09.2010, 17:45 **[ТС]**

Хохол, А векторы?)

@fasked · 06.09.2010, 17:47

Сообщение от Lavroff

А векторы?

стек - линейный список

@Nameless One · 06.09.2010, 17:48

Хохол, а как заданная последовательность представляется в программе?

Новые блоги и статьи Все статьи Все блоги /
По какой причине рабочий алгоритм может называться бредом? Hrethgir 05.08.2026 3 мая мной была сделана публикация на Хабре авторского алгоритма итеративного обхода дерева "эстафета хвоста". Удаление публикации видимо произошло из-за отзывов об алгоритме такого рода Ну, я тебе. . .	Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .
Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .	Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562

	Задачи для тренировки и лучшего понимания 15.07.2010, 05:53. Показов 516074. Ответов 1272 Метки нет (Все метки) Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо. Список задач, решение которых присутствует в данной теме: Виртуальное наследование Единственное число в массиве Работа с указателями Поменять значения переменных местами без использования дополнительной Цикл и префиксная форма инкремента Выделить смайлики из последовательности Игра "Крестики-нолики" Минимальный путь в пространстве Минимальное количество ударов для убийства Змея Горыныча Передвижение шахматной фигуры без жертв Игра "Жизнь" (Conway's Game of Life) Обойти шахматную доску фигурой "конь" без повторений Разработка функции-инкремента Жучок в программе, реализующей вывод на экран Жучок с меткой Жучок в программе, использующей ссылки Зоны видимости Жучок при использовании указателя Конструктор в структуре Жучок при выводе символа в цикле Модификация задачи о Ханойской башне Минимизировать копирование(перемещение) элементов Удаление повторяющихся чисел и сортировка минимальным количеством кода Генерация последовательности из 1 000 000 строчного латинского письма с определёнными условиями Задача о повторениях Задача о сгоревших предохранителях Задача об оптимизации собственного класса String Одновременное использование префиксного и постфиксного инкремента Написание прототипа для функции Задача на нахождение факториала числа Калькулятор для вычисления выражений вводимых пользователем Области видимости Представление арабского представления числа в римское Двоичный формат в десятичный и обратно Узнать день недели по дате Вычислить результат алгоритма в псевдокоде Найти наибольшее из двух заданных чисел без использования циклов Выявить некорректность при использовании указателей Перестановка значений трёх переменных без использования вспомагательных Умножения двух чисел без использования оператора "*" Определить язык (С или С++) Альтернативное обращение к элементу массива Расчёт и проверка контрольного ключа Описать траекторию черепахи Интерпретатор языка HQ9+ Хитрости в наследовании Синтаксис языка Си: приведения указателя к типу многомерного массива Задача на подсчёт количества итераций цикла Плавающее сравнение одних и тех же чисел на "меньше" и "больше или равно" даёт один и тот же результат На корректном тесте компилятор под intel и sparc выдают разные результаты Ферзя в угол! Головоломка Бутылки Шахматная доска Произведение цифр Максимальная подпоследовательность Сообщество роботов Свадьба Телеграфный перевод Апельсины Последняя цифра N! Задача про триграфы Почему компилятор игнорирует операцию инкрементации? 44

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	28.08.2010, 05:40
	Kastaneda, для решения этой задачи нужно пользоваться методом перебора с возвратом, вот(внимание, по первой ссылке - жестокие спойлеры!) 1

@Kastaneda 5232 / 3206 / 362 Регистрация: 12.12.2009 Сообщений: 8,143 Записей в блоге: 2
	28.08.2010, 20:12
	fasked могу ошибаться, но я думаю ваша ошибка в том, что нет контроля типа "так я уже ходил, ни чего не получилось, больше так ходить не надо)" Например идем вверх вправо, вверх влево, вправо вниз и ОП - дальше хода нет, делаем шаг назад, пробуем ходить дальше и ОПЯТЬ идем вправо вниз (мы же не "знаем", что так ходить нельзя, что первое попалось в if else (в FindPath())туда и идем) и так происходит очень много раз, из-за чего происходит ошибка сигментации памяти (при ходе назад что-то же куда-то пишется) Вот, по-моему так) 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	05.09.2010, 15:10
	Из 4 и 6 на 3 кнопки, из 5 на 0 кнопок. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	05.09.2010, 18:59
	nikkka, в подобных задачах если что-то не запрещено, значит можно. 1

@лендер 48 / 48 / 10 Регистрация: 12.01.2010 Сообщений: 183
	05.09.2010, 20:07
	да, затупил я думал самый умный 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	06.09.2010, 17:44
	Вспомнил простенькую задачку, интересно, какие будут решения) Дана последовательность из N чисел. Вывести эту последовательность в обратном порядке. В программе запрещено использовать массивы. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	06.09.2010, 17:45 [ТС]
	Хохол, А векторы?) 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	06.09.2010, 17:48
	Хохол, а как заданная последовательность представляется в программе? 0