Очень интересная программа построения пирамиды - PullRequest
Новая
       5

Очень интересная программа построения пирамиды

2 голосов
/ 24 июня 2011

Я столкнулся с этой очень интересной программой печати чисел в пирамиде.

Если n = 1, выведите следующее: 

1  2
4  3

, если n = 2, выведите следующее:

1  2  3
8  9  4
7  6  5

если n = 3, выведите следующее: 

1   2   3   4
12  13  14  5
11  16  15  6
10   9   8  7

Я могу распечатать все это, используя довольно много циклов и переменных, но это выглядит очень специфично.Вы, возможно, заметили, что все это заполнение пирамиды начинается в одном направлении, пока она не найдет путь заполненным.Как вы могли заметить, 1,2,3,4,5,6,7,8,9,10,11,12 поданы по внешним краям до тех пор, пока не найдет 1, после того, как он войдет во второй ряд после 12 и напечатает 13,14и так далее.Он печатает в спиральном режиме, что-то вроде игры змей, продолжающейся до тех пор, пока змеи не дойдут до самого себя.

Я хотел бы знать, есть ли какие-нибудь алгоритмы, стоящие за этим поколением пирамид или его просто сложной программой генерации пирамид.

Заранее спасибо.Это очень интересная и сложная программа, поэтому я прошу не нуждаться в конвейерном голосовании:)

Ответы [ 3 ]

3 голосов
/ 25 июня 2011

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

public int Determine(int n, int x, int y)
{
  if (y == 0) return x + 1;         // Top
  if (x == n) return n + y + 1;     // Right
  if (y == n) return 3 * n - x + 1; // Bottom
  if (x == 0) return 4 * n - y + 1; // Left
  return 4 * n + Determine(n - 2, x - 1, y - 1);
}

Вы можете вызвать его с помощью двойного цикла for.x и y начинаются с 0: 

for (int y=0; y<=n; y++) 
  for (int x=0; x<=n; x++) 
    result[x,y] = Determine(n,x,y);
1 голос
/ 25 июня 2011

Вот некоторый код на C, реализующий базовый алгоритм, представленный @ C.Zonnerberg. В моем примере для массива 6x6 используется n=6.

Мне пришлось внести несколько изменений, чтобы получить результат так, как я ожидалэто посмотреть.Я поменял местами большинство x's и y's и изменил несколько из n's на n-1 и изменил сравнения в циклах for с <= на < 

int main(){
  int x,y,n;
  int result[6][6];
  n=6;
  for (x=0; x<n; x++){
    for (y=0; y<n; y++) {
      result[x][y] = Determine(n,x,y);
      if(y==0)
        printf("\n[%d,%d] = %2d, ", x,y, result[x][y]);
      else
        printf("[%d,%d] = %2d, ", x,y, result[x][y]);
    }
  }
return 0;
}

int Determine(int n, int x, int y)
{
  if (x == 0) return y + 1;         // Top
  if (y == n-1) return n + x;     // Right
  if (x == n-1) return 3 * (n-1) - y + 1; // Bottom
  if (y == 0) return 4 * (n-1) - x + 1; // Left
  return 4 * (n-1) + Determine(n - 2, x - 1, y- 1);
}

Выход 

[0,0] =  1, [0,1] =  2, [0,2] =  3, [0,3] =  4, [0,4] =  5, [0,5] =  6,
[1,0] = 20, [1,1] = 21, [1,2] = 22, [1,3] = 23, [1,4] = 24, [1,5] =  7,
[2,0] = 19, [2,1] = 32, [2,2] = 33, [2,3] = 34, [2,4] = 25, [2,5] =  8,
[3,0] = 18, [3,1] = 31, [3,2] = 36, [3,3] = 35, [3,4] = 26, [3,5] =  9,
[4,0] = 17, [4,1] = 30, [4,2] = 29, [4,3] = 28, [4,4] = 27, [4,5] = 10,
[5,0] = 16, [5,1] = 15, [5,2] = 14, [5,3] = 13, [5,4] = 12, [5,5] = 11,
0 голосов
/ 24 июня 2011

С массивом из всех нулей вы можете начать с [row, col] = [0,0], заполнить это пространство, затем добавить [0,1] в положение (один справа), пока оно не будетконец или сталкивается с ненулевым значением.

Затем идите вниз (добавьте [1,0]), заполняя пробел, пока не закончится или не попадет в ненулевое значение.

Затем идитевлево (добавить [0, -1]), заполняя пробел до конца или до ненулевого значения.

Затем подниматься (добавить [-1,0]), заполняя пространство доконец или наталкивается на ненулевое значение.

и повтор ...

...