Форум программистов, компьютерный форум, киберфорум
C++
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
38 из 64 « 34353637 38 39404142 »
 
Рейтинг 4.54/2345: Рейтинг темы: голосов - 2345, средняя оценка - 4.54
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
1

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

15.07.2010, 05:53. Показов 463057. Ответов 1272
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
Ребят. Кто-нибудь может дать задачу для тренировки? Приблизительно по всему курсу С++. Буду благодарен за сложную задачу, но которую способен сделать новичок-любитель. Затраты сил-времени не важно. Главное, чтобы это было интересно и не слишком рутинно. + Если найдется человек который даст задачу просьба помогать с кодом, который я буду себя скидывать. Не переписывать за меня, но указывать на ошибки и желательно объяснять. Заранее спасибо.

Список задач, решение которых присутствует в данной теме:
44
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 15.07.2010, 05:53
Ответы с готовыми решениями:

Элементарные программы, для лучшего понимания языка...
Здравствуйте. Вот сегодня решил что пора изучать с++. Есть пару задач. Начал решать и уже на первой...

Задачи для тренировки и лучшего понимания языка
Предлагаю в этой теме размещать задачи, которые помогут новичкам (и не только) более детально...

Литература для лучшего понимания сути программирования
Привет! Подскажите литературу, которая поможет разобраться в сути самого процесса программирования,...

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

1272
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
27.08.2010, 20:44 741
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от 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 и т.д.), но я убрал это из кода, т.к. в данном случае это не принципиально.
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
28.08.2010, 05:40 742
Kastaneda, для решения этой задачи нужно пользоваться методом перебора с возвратом, вот(внимание, по первой ссылке - жестокие спойлеры!)
1
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 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;
}
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
28.08.2010, 20:12 744
fasked могу ошибаться, но я думаю ваша ошибка в том, что нет контроля типа "так я уже ходил, ни чего не получилось, больше так ходить не надо)" Например идем вверх вправо, вверх влево, вправо вниз и ОП - дальше хода нет, делаем шаг назад, пробуем ходить дальше и ОПЯТЬ идем вправо вниз (мы же не "знаем", что так ходить нельзя, что первое попалось в if else (в FindPath())туда и идем) и так происходит очень много раз, из-за чего происходит ошибка сигментации памяти (при ходе назад что-то же куда-то пишется) Вот, по-моему так)
0
Мат в 32 хода
237 / 172 / 18
Регистрация: 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 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.
1
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
05.09.2010, 11:55 746
Цитата Сообщение от nikkka Посмотреть сообщение
придумал такую штуку:
конь стоит на клетке 0,0.
перед тем как пойдти на новую клетку, он проверяет:
а) находятся ли её координаты на поле (на пример конь не может пойдти на клетку с координатами 8,9)
б) был ли он на ней.
после хода, координаты новой клетки впихаются в стек. старая помечается "пройденной".
если не один из возможных вариантов не удовлетворяет условий а и б, конь возвращается на предидущею клетку. а клетка с которой он вернулся помечается не пройденной и вытаскивается из стека. продолжаем повторять этот процес пока все клетки не будут пройдены.
nikkka, у меня такой же алгоритм, только без стека (через массив), у faskedа тоже такой же. А вообще я находил в сети решение где-то в 50 сторок на С, но не стал его сюда выкладывать, пробовал сам написать)(причем так, чтоб не повторять найденное решение)) А вот про Правило Варнсдорфа не знал, спасибо. Интересно на чем оно основывается?
0
Мат в 32 хода
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 12:05 747
Цитата Сообщение от Kastaneda Посмотреть сообщение
Интересно на чем оно основывается?
правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

Добавлено через 2 минуты
Цитата Сообщение от Kastaneda Посмотреть сообщение
у меня такой же алгоритм, только без стека (через массив), у faskedа тоже такой же
я добавил проверку на "пройденность": "я уже пробовал так ходить, и ничего хорошого не вышло".
0
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
05.09.2010, 12:07 748
Цитата Сообщение от nikkka Посмотреть сообщение
правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.
)))Да читать то я умею) Мне интересно - почему выбирается клетка, с которой существует наименьшее количество возможных ходов? Это же должно как то логически обосновываться.

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

Не по теме:

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

0
Мат в 32 хода
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 12:24 749
Цитата Сообщение от Kastaneda Посмотреть сообщение
Мне интересно - почему выбирается клетка, с которой существует наименьшее количество возможных ходов?
А... Думаю это будет не так уж и просто понять... Над задачкой ведь бились с IX века!...
http://en.wikipedia.org/wiki/Knight's_tour
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
05.09.2010, 13:03 750
Цитата Сообщение от Lavroff Посмотреть сообщение
Кто-нибудь может дать задачу для тренировки?
Есть игрушка: http://www.gamereclaim.com/200... equest-01/
Составить программу, которая решает уровень методом перебора
Графическая часть не нужна. Просто в каком-то виде задать уровень и в каком-то виде напечатать результат
1
48 / 48 / 10
Регистрация: 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;
}
Немного поздновато но всеже
откуда бы конь не начинал ити, где бы не стоял, при такой раскладке он может пойти всего на две кнопки.
0
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
05.09.2010, 15:10 752
Из 4 и 6 на 3 кнопки, из 5 на 0 кнопок.
0
Мат в 32 хода
237 / 172 / 18
Регистрация: 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 номер начинать можно?
0
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
05.09.2010, 18:59 754
nikkka, в подобных задачах если что-то не запрещено, значит можно.
1
48 / 48 / 10
Регистрация: 12.01.2010
Сообщений: 183
05.09.2010, 20:07 755
да, затупил я
думал самый умный
0
Мат в 32 хода
237 / 172 / 18
Регистрация: 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;
}
0
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
06.09.2010, 17:44 757
Вспомнил простенькую задачку, интересно, какие будут решения)
Дана последовательность из N чисел. Вывести эту последовательность в обратном порядке. В программе запрещено использовать массивы.
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
06.09.2010, 17:45  [ТС] 758
Хохол, А векторы?)
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
06.09.2010, 17:47 759
Цитата Сообщение от Lavroff Посмотреть сообщение
А векторы?
стек - линейный список
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
06.09.2010, 17:48 760
Хохол, а как заданная последовательность представляется в программе?
0
06.09.2010, 17:48
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 06.09.2010, 17:48
Помогаю со студенческими работами здесь

Проверить на правильность и закомментировать весь код для лучшего понимания
Всем здравствуйте. Условие задачи - Заданная матрица целых чисел размером (N, N). Найти среднее...

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

Нужны задачи для тренировки
Здравствуйте киньте пожалуйста задания по с++ для человека начинающего изучать Turbo с++

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


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

Или воспользуйтесь поиском по форуму:
760
Закрытая тема Создать тему
38 из 64 « 34353637 38 39404142 »
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru