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

алгоритм обхода поля кубиком - C++

Восстановить пароль Регистрация
 
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
11.12.2009, 17:26     алгоритм обхода поля кубиком #1
народ - никому не попадалась задачка такого вида:
есть поле n*n - начало в координате 0*0(верхний левый угол). есть кубик с 1 красной грань (цвет остальных не важен).
нужно написать процедуру обхода поля кубиком так чтобы он пришел в клетку с координатой 0*n (верхний правый угол) так чтобы красная грань ни разу не оказалась внизу.

мне понятно что тут надо решать через рекурсию

поле представляем как:
1_1_1_1_1_1_1_1_1_1_1_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_0_0_0_0_0_0_0_0_0_0_1
1_1_1_1_1_1_1_1_1_1_1_1

подскажите кто нибудь хотя бы идею на псевдокоде
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
serann
Сообщений: n/a
21.11.2010, 21:22     алгоритм обхода поля кубиком #2
Народ, вопрос все еще актуален. если не код, то хотя бы алгоритм.
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
22.11.2010, 01:22  [ТС]     алгоритм обхода поля кубиком #3
serann, случаем не с ИБКС?=))) Не П.В. Семьянов сию задачку дал?=)
serann
Сообщений: n/a
06.12.2010, 19:24     алгоритм обхода поля кубиком #4
Да, действительно. Вся техническая работа уже выполнена, функции-подзадачи построены, но возникли банальные сложности с алгоритмом перебора с возвратом. Или зацикливается, или обходит не все поле. Опыт предшественников не помешал бы. :]
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
06.12.2010, 19:30  [ТС]     алгоритм обхода поля кубиком #5
Значит так=) я эт задачу решал на 2 курсе в рамках оптимизации, так что там шла речь немного о другом (т.е. не перебор - я рпосто придумал алгоритм пошагового обхода) - может вам пригодиться... выкладываю 2 реализации - на С и С++:

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
#include "stdafx.h"
#include <list>
#include <time.h>
#include <conio.h>
 
#define MATRIX_SIZE     500
 
//  тип: координаты одного квадратика в поле (для 1 шага обхода)
class TMatrixElementIndex
{
public:
  size_t m_row, m_col;
 
  TMatrixElementIndex() : m_row(0), m_col(0) {}
  TMatrixElementIndex(size_t row, size_t col) : m_row(row), m_col(col) {}
};
 
//  тип: список координат обхода поля
typedef std::list<TMatrixElementIndex> TTraverseCoordinatesList;
 
//  функция для циклического обхода 2 столбцов под номерами iFirstCol и iFirstCol + 1
//  подразумевается, что на входе: кубик вверху столбца iFirstCol, красной шапкой кверху
void TraverseTwoColumns(size_t iFirstCol, TTraverseCoordinatesList &TraverseCoordinates)
{
  int i;
 
  //  пройтись по второму столбцу сверху вниз (кубик на боку, красной шапкой вправо)
  for (i = 0; i < MATRIX_SIZE; i++)
  {
    TraverseCoordinates.push_back(TMatrixElementIndex(i, iFirstCol + 1));
    My_Delay(TraverseCoordinates);
  }
 
  //  поворочаться внизу
  TraverseCoordinates.push_back(TMatrixElementIndex(MATRIX_SIZE - 1, iFirstCol));
  TraverseCoordinates.push_back(TMatrixElementIndex(MATRIX_SIZE - 2, iFirstCol));
  TraverseCoordinates.push_back(TMatrixElementIndex(MATRIX_SIZE - 2, iFirstCol + 1));
  TraverseCoordinates.push_back(TMatrixElementIndex(MATRIX_SIZE - 1, iFirstCol + 1));
 
  //  подняться по первому столбцу вверх (красной шапкой влево)
  for (i = MATRIX_SIZE - 1; i >= 0; i--)
  {
    TraverseCoordinates.push_back(TMatrixElementIndex(i, iFirstCol));
    My_Delay(TraverseCoordinates);
  }
 
  //  двинуться вправо: встать красной шапкой кверху
  TraverseCoordinates.push_back(TMatrixElementIndex(MATRIX_SIZE - 1, iFirstCol));
}
 
 
void main()
{ 
  clock_t tStart = clock();
 
  TTraverseCoordinatesList Coordinates;
 
  //  стартуем с левого верхнего угла, красной шапкой вверх
  Coordinates.push_back(TMatrixElementIndex(0, 0));
 
  //  пройтись по всем столбцам
  for (size_t i = 0; i < MATRIX_SIZE - 1; i++)
    TraverseTwoColumns(i, Coordinates);
 
  //  доворочаться к финишу, чтобы красной шапкой вверх
  Coordinates.push_back(TMatrixElementIndex(1, MATRIX_SIZE - 2));
  Coordinates.push_back(TMatrixElementIndex(1, MATRIX_SIZE - 1));
  Coordinates.push_back(TMatrixElementIndex(0, MATRIX_SIZE - 1));
 
  clock_t tFinish = clock();
 
  //  выводим
//  printf("Cube route (row, column):\n");
//   for (TTraverseCoordinatesList::const_iterator i = Coordinates.begin();
//        i != Coordinates.end();
//        i++)
//      printf("(%i, %i)\t->\t", i->m_row, i->m_col);
//   printf("exit\n\n");
 
  printf("Time interval: %f\n", (double)(((double)tFinish - (double)tStart) / (double)CLOCKS_PER_SEC));
  _getch();
}
и сишный код:

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
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <time.h>
 
#define MATRIX_SIZE 10000
#define RECORD_SIZE ((2*MATRIX_SIZE + 5)*(MATRIX_SIZE - 1)+1)
//---------------------------------------------
int DoLoop( int iStartPoint_Col);//сделаем петлю
//---------------------------------------------
//запись координат обхода
int iCoordinatesRecord [RECORD_SIZE][2];// [Ln][Col]
 int iCoordLn;
//---------------------------------------------
int main()
{
    int iCoordCol = 0;
    int i;
    float start,end;
 
    start = clock();
 
    iCoordLn = 0;
    //стартовая точка
    iCoordinatesRecord [iCoordLn][0] = 0;// :x
    iCoordinatesRecord [iCoordLn][1] = 0;// :y
    iCoordLn++;
 
    for( i = 0; i <  MATRIX_SIZE - 1; i++)
    {
        DoLoop(iCoordCol);
        iCoordCol++;
 
    }
    end = clock();
    
    //контрольный вывод координат
    printf("start: \n");
    for( i = 0; i <  RECORD_SIZE; i++)
    {
        printf("(%i, %i)  ", iCoordinatesRecord [i][1],iCoordinatesRecord [i][0] );
 
    }
    printf("end");
 
    printf("(%i, %i) \n ", iCoordinatesRecord [RECORD_SIZE-1][1],iCoordinatesRecord [RECORD_SIZE-1][0] );
    printf("\n\n Time = %f", (end-start)/CLK_TCK);
    _getch();
    return 0;
}
//---------------------------------------------
//функция обхода - делаем "петлю"
int DoLoop( int iStartPoint_Col)
{
    int iLn,iCol;
        int i;
 
    iLn = 0;
    iCol = iStartPoint_Col;
    //поворачиваем кр плоскость направо
    iCol++;
 
    //спускаемся по столбцу - красная плоскость справа
    for(i = 0; i < MATRIX_SIZE; i++ )
        {
            iCoordinatesRecord [iCoordLn][0] = iLn;
            iCoordinatesRecord [iCoordLn][1] = iCol;
            iLn++;
            iCoordLn++;
        }
        iLn--;
    
    
    //вертимся внизу - мини петля
    //кр плоскость вверх
    iCoordinatesRecord [iCoordLn][0] = iLn;
        iCoordinatesRecord [iCoordLn][1] = iCol - 1;
    iCoordLn++;
 
    //кр плоскость вперед
    iCoordinatesRecord [iCoordLn][0] = iLn - 1;
    iCoordinatesRecord [iCoordLn][1] = iCol - 1;
    iCoordLn++;
 
    //кр плоскость вперед
    iCoordinatesRecord [iCoordLn][0] = iLn - 1;
    iCoordinatesRecord [iCoordLn][1] = iCol;
    iCoordLn++;
 
    //кр плоскость вверх
    iCoordinatesRecord [iCoordLn][0] = iLn;
    iCoordinatesRecord [iCoordLn][1] = iCol;
    iCoordLn++;
 
    //поднимаемся по столбцу - красная плоскость слева
        
    
     
        for(i = MATRIX_SIZE - 1; i >= 0; i--)
        {
            iCoordinatesRecord [iCoordLn][0] = iLn;
            iCoordinatesRecord [iCoordLn][1] = iCol-1;
            iLn--;
            iCoordLn++;
        }
        iLn++;
        
    
    //кр плоскость вверх
    iCoordinatesRecord [iCoordLn][0] = iLn;
    iCoordinatesRecord [iCoordLn][1] = iCol;
    iCoordLn++;
    
        return 0;
}
Yandex
Объявления
06.12.2010, 19:30     алгоритм обхода поля кубиком
Ответ Создать тему
Опции темы

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