3D 배열의 요소 시퀀스의 최대 수

Question

데이터 구조 할당을 위해 정적으로 할당 된 3D 배열의 각 요소를 무작위로 선택한 다섯 가지 색상 중 하나로 초기화해야했습니다. 배열은이 같은 선언 형 ColorEnum,이었다 :

---

ENUM ColorEnum {RED, ORANGE, YELLOW, GREEN, BLUE};

---

내 작업은 논리적으로 양쪽에 의해 좌우로 시퀀스의 다음 요소를 만지고 시퀀스의 각 요소를 의미 요소 (특정 순서를 구성하는 요소의 인덱스를 찾기 위해 위에서 아래로했다 또는 앞에서 뒤로). 완전한 시퀀스는 RED 요소가 파란색 요소를 터치하고있는 녹색 요소를 터치하고있는 노란색 요소를 터치하고있는 ORANGE 요소를 터치하는 시퀀스입니다. 만지기 위해서는 두 요소의 전체면이 모서리 나 모서리가 아닌 인접해야합니다. 따라서 각 요소는 최대 여섯 개의 다른 요소에 닿을 수 있습니다. 개별 요소는 둘 이상의 순서로 사용될 수 있습니다. 요소의 인덱스를 시퀀스에 저장하기 위해 요소의 행, 열 및 심도 인덱스를 보유하는 정적으로 할당 된 1D 배열의 구조체를 사용했습니다. 각 시퀀스를 저장하기 위해 시퀀스의 요소 색인을 보유하는 배열의 다른 정적으로 할당 된 1D 배열을 사용했습니다. 내 질문에, 가능한 한 작은 메모리를 사용하려면, 배열의 배열을 할당 할 수있는 크기를 알아야합니다. 이 크기를 빨강, 주황색, 녹색, 파랑 색 계열의 최대 수와 같게하고 싶지만이 수를 결정하는 방법을 모르겠습니다. 저에게 수학의 천재가 내게 도움이 되니? 내 임무는 오랫동안 끝났어. 나는 94/100을 가지고 있지만,이 질문은 나를 괴롭 히고있다. 도움에 감사드립니다.

Answer 1

가능한 최대 시퀀스 수는 3D 배열의 크기와 그리드의 채우기에 따라 다릅니다. 조합 각도에서 보았을 때, 저는 그러한 3D 그리드를 가장 효율적으로 채울 수있는 방법을 찾았습니다. 그러나 최대 값을 할당하는 것은 최악의 경우를 전제로하며 벡터로 @Kevin이 주석 처리 한 것보다 나을 것입니다.

나에게 효율적으로 보이는 그리드를 채우는 것은 1 블록의 6 인접 위치에 이전 색상 3 개와 그 다음 색상 3 개를 채우는 것입니다 (노란색 블록에는 3 개의 주황색과 3 개의 녹색 블록이 있음). 이웃). 다음 색상과 이전 색상의 (앞, 왼쪽, 아래) 이웃을 (뒤, 오른, 위) 이웃으로 채운다면 떠오르는 구조로 인해 많은 순서로 한 블록을 사용할 수 있습니다. 색상에 다음/이전 색상이 없으면 이전/다음 색상 만 있습니다.

2D에서

이 같은 (약식 colornames) 왼쪽 아래 R을 사용하여 시퀀스의

BGYOROYGBGYOROYGB 
GBGYOROYGBGYOROYG 
YGBGYOROYGBGYOROY 
OYGBGYOROYGBGYORO 
ROYGBGYOROYGBGYOR 

수있다 2^4, 중간 R의 중 하나를 사용하여 시퀀스의 양 (에있을 것입니다 무한한 필드)는 2^5입니다. 경계를 고려하여이 패턴에 대해 3D 필드의 시퀀스의 정확한 총 nr을 계산할 수 있습니다 (약간의 손실이있을 수 있기 때문에 모서리에서 약간의 손실이 있음)

필링 방법은 한 가지 방법 일뿐입니다 그리드를 채우는 데는 다른 가능성이 있으며 더 좋을 수도 있습니다.