Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Сонный металюга
46 / 46 / 13
Регистрация: 10.05.2009
Сообщений: 295
1

Алгоритм обхода поля кубиком

11.12.2009, 17:26. Показов 950. Ответов 4
Метки нет (Все метки)

народ - никому не попадалась задачка такого вида:
есть поле 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

подскажите кто нибудь хотя бы идею на псевдокоде
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.12.2009, 17:26
Ответы с готовыми решениями:

Составить алгоритм обхода игрового поля
Вобщем, такая тема: Дан двумерный массив чисел 12х12, который содержит числа от 0 до 5. 0 -...

Алгоритм обхода лабиринта
Помогите реализовать алгоритм обхода лабиринта, на примере матрицы nxn, где 1 (единицы) это...

Необходимо написать программу обхода конем всего шахматного поля
Доброго времени суток! Необходимо написать программу обхода конем всего шахматного поля. Конь...

Жадный алгоритм для определения последовательности обхода городов.
Здравствуйте! Изучаю разные транспортные алгоритмы и возник следующий вопрос. На основе данных,...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
4
serann
21.11.2010, 21:22 2
Народ, вопрос все еще актуален. если не код, то хотя бы алгоритм.
Сонный металюга
46 / 46 / 13
Регистрация: 10.05.2009
Сообщений: 295
22.11.2010, 01:22  [ТС] 3
serann, случаем не с ИБКС?=))) Не П.В. Семьянов сию задачку дал?=)
0
serann
06.12.2010, 19:24 4
Да, действительно. Вся техническая работа уже выполнена, функции-подзадачи построены, но возникли банальные сложности с алгоритмом перебора с возвратом. Или зацикливается, или обходит не все поле. Опыт предшественников не помешал бы. :]
Сонный металюга
46 / 46 / 13
Регистрация: 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;
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.12.2010, 19:30

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

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

Консольная игра с кубиком
Решил написать консольную игру: игрок и компьютер кидают кубик и счет выводится на экран. Дело в...

Алгоритм обхода диагонали параллельной главной диагонали матрицы
Как обработать каждый элемент матрицы, находящийся на диагонали параллельной главной диагонали?...

Алгоритм обхода в игре "точки"
пишу игру &quot;точки&quot; на с++ в VS form, по клику заполняю два вектора с точками, vector&lt;MyPoint&gt; One; ...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.