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

Цикл не повторяется - C++

Восстановить пароль Регистрация
 
shkrekperviy
1 / 1 / 0
Регистрация: 27.06.2012
Сообщений: 12
11.11.2013, 11:43     Цикл не повторяется #1
Задача: Пройти шахматным конем максимальное количество клеток доски.
Ставлю несколько попыток, но выполняется только одна. Начиная со второй конь двигаться со стартовой позиции не хочет. Что не так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <iomanip>
using namespace std;
 
int accessBoard(int);
int setArrayRand(int []);
 
const int size=8;
int a[size][size]={}; // Матрица с колич. вариантов ходов на следующую клетку
 
int main(){
    int board[size][size]={0};
    int hor[size]={2,1,-1,-2,-2,-1,1,2}; // Возможные ходы по горизонтали
    int ver[size]={-1,-2,-2,-1,1,2,2,1}; // Возможные ходы по вертикали
    int steps=0, maxSteps=0;
    int k; // Номер шага
    accessBoard(2); // Создаем матрицу a
    for(int i=0; i<2; i++){
      k=1; 
      int currentRow=0, currentColumn=0;
      board[currentRow][currentColumn]=k;
      int tempRow=0, tempColumn=0;
      while(k<64){
        int arrayRand[size]={0};  
        int accessability=9; // Макс. количество вариантов может быть 8
        setArrayRand(arrayRand); // Генерирование случайной последовательности
        for(int i=0; i<8; i++){
          int row, column;
          int number;
          number=arrayRand[i];
          row=currentRow+ver[number];
          column=currentColumn+hor[number];
          if((row>=0&&row<=7)&&(column>=0&&column<=7)&&(board[row][column]==0)){
            if(a[row][column]<accessability){
              tempRow=row;
              tempColumn=column;
              accessability=a[tempRow][tempColumn];
            }
          }  
        }
        if(currentRow!=tempRow){
          currentRow=tempRow;
          currentColumn=tempColumn;
          k++;
          board[currentRow][currentColumn]=k;
        }
        else{
          break;
          }
        }
        steps=k; // Количество пройденных клеток в данной попытке
        cout<<"steps["<<i+1<<"] = "<<steps<<endl<<endl;
        if(steps>maxSteps) maxSteps=steps; // Макс. количество во всех попытках
    }
    cout<<"Max steps: "<<maxSteps<<endl;
    system("pause");
    return 0;
}
 
int accessBoard(int digit){
    a[0][0]=digit;
    a[0][1]=a[1][0]=digit+1;
    a[0][2]=a[0][3]=a[1][1]=a[2][0]=digit+2;
    a[1][2]=a[1][3]=a[2][1]=digit+4;
    a[2][2]=a[2][3]=digit+6;
    for(int i=0; i<4; i++){
      a[3][i]=a[2][i];
    }
    for(int i=4, k=1; i<8; i++, k+=2){
      for(int j=0; j<4; j++){
        a[i][j]=a[i-k][j];
      }
    }
    for(int i=0; i<8; i++){
      for(int j=4, l=1; j<8; j++, l+=2){
        a[i][j]=a[i][j-l];
      }
    }
}
 
int setArrayRand(int a[]){
    int combine;
    combine=rand()%8;
    a[0]=combine;
    for(int j=1; j<size; j++){
        int count=0;
        combine=rand()%8;
        for(int m=0; m<j; m++){
        if(combine!=a[m]) count++;
        }     
        if(count==j) a[j]=combine;
        else j--;
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
11.11.2013, 11:54     Цикл не повторяется #2
ты реально надеешься задачу решить рандомно? Не выйдет! гарантирую.
shkrekperviy
1 / 1 / 0
Регистрация: 27.06.2012
Сообщений: 12
11.11.2013, 12:17  [ТС]     Цикл не повторяется #3
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ты реально надеешься задачу решить рандомно? Не выйдет! гарантирую.
А можно пояснить, почему не выйдет? И как мне быть тогда, ведь без случайных последовательностей шаги будут постоянно одни и те же.
Festral
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 22
11.11.2013, 12:20     Цикл не повторяется #4
Цитата Сообщение от shkrekperviy Посмотреть сообщение
А можно пояснить, почему не выйдет? И как мне быть тогда, ведь без случайных последовательностей шаги будут постоянно одни и те же.
шаги необходимо варьировать, но "перебрав все варианты", .. а так это лотерея;
JleLLlka
0 / 0 / 0
Регистрация: 11.11.2013
Сообщений: 3
11.11.2013, 12:22     Цикл не повторяется #5
Самый простой способ решения этой задачи воспользоваться рекурсией...
shkrekperviy
1 / 1 / 0
Регистрация: 27.06.2012
Сообщений: 12
11.11.2013, 12:24  [ТС]     Цикл не повторяется #6
Цитата Сообщение от Festral Посмотреть сообщение
шаги необходимо варьировать, но "перебрав все варианты", .. а так это лотерея;
Почему лотерея. Перед каждым ходом коня создается случайный массив чисел от 0 до 7, который и перебирается. Почему действует на первом цикле for (61-62 шага в среднем), а на второй раз цикл while сбоит?
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
11.11.2013, 12:25     Цикл не повторяется #7
Цитата Сообщение от shkrekperviy Посмотреть сообщение
А можно пояснить, почему не выйдет?
потому что лучше перебирать все пути по порядку, чем надеятсься на случайность. Поверь, случайно ткнуть пальцем на путь коня по шахматной доске крайне маловероятно.
Цитата Сообщение от shkrekperviy Посмотреть сообщение
И как мне быть тогда
задача старая и очень известная. Статей о том, как её решить, дофига и больше https://www.google.com/#q=chess+knight+tour+c%2B%2B
Цитата Сообщение от shkrekperviy Посмотреть сообщение
ведь без случайных последовательностей шаги будут постоянно одни и те же.
без случайных последовательностей надо перебирать возможные пути коня не случайно, а специально по порядку от первого до последнего! И поверь, конь способен пройти не 8 и не "какое-то" максимальное число клеток. А именно все 64 клетки!
shkrekperviy
1 / 1 / 0
Регистрация: 27.06.2012
Сообщений: 12
11.11.2013, 12:39  [ТС]     Цикл не повторяется #8
Меня все же больше интересует не решение задачи, это я погуглю. Мне интересно, почему цикл перестает работать. Почему не перебираются варианты row=currentRow+ver[number] и соответственно tempRow остается равным нулю?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.11.2013, 12:44     Цикл не повторяется
Еще ссылки по теме:

C++ Не повторяется цикл
C++ Повторяется ли слово в строке
Случайность повторяется C++

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
11.11.2013, 12:44     Цикл не повторяется #9
shkrekperviy, Не знаю, что там у тебя не перебирается. Решение неверное. Если что-то зациклилось - поставь брейкпоинт и пройди цикл пошагово, отслеживая условие.
Очевидно, k==64 шага ты никогда не достигнешь.
currentRow==tempRow тоже
Кстати,Ю что это за условие за такое странное???
C++
1
if(currentRow!=tempRow){
Yandex
Объявления
11.11.2013, 12:44     Цикл не повторяется
Ответ Создать тему
Опции темы

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