2

我一直在考虑这个问题，我只是想不出一种方法来填充一个向外螺旋的矩阵，这样我就可以做到以下几点：

转动这个：1 2 3 4 5 ... n

至

21 22 23 24 25 26
20 07 08 09 10 27
19 06 01 02 11 28
18 05 04 03 12 29
17 16 15 14 13 30
           ...n

我的问题是算法本身，但如果你可以用 C++ 来代替伪代码，那就更好了。

这是我为测试而编写的一些代码，但我真的不知道如何才能做到这一点。

#include <stdio.h>
#include <string>

using namespace std;

int main() {
  //int n = 5;
  int spiral[5][6];

  for (int i = 0; i < 5; i++)
    for (int u = 0; u < 6; u++)
      spiral[i][u] = 0;

  spiral[2][2] = 1;
  string direction = "right";
  for (int i = 2; i < 5; i++) {
    for (int u = 2; u < 6; u++) {
      if (direction == "right") {
        spiral[i][u + 1] = spiral[i][u] + 1;
        direction = "down";
      }
    }
  }

  for (int i = 0; i < 5; i++) {
    for (int u = 0; u < 6; u++) {
      printf("%02d ", spiral[i][u]);
    }
    printf("\n");
  }

  return 0;
}

谢谢！

4

5 回答 5

4

您可以观察到在左下角的位置有类似的正方形，其最小值然后向上、向右、向下和向左移动。

您可以使用它来创建这样的函数：

template <typename Array>
void spiral_square(Array& a, int x, int y, int side, int& value)
{
  int mx = x+side-1, my=y+side-1;
  for (int i = 1; i <= side-1; ++i) a[my-i][x] = value++;
  for (int i = 1; i <= side-1; ++i) a[y][x+i] = value++;
  for (int i = 1; i <= side-1; ++i) a[y+i][mx] = value++;
  for (int i = 1; i <= side-1; ++i) a[my][mx-i] = value++;
}

在行动中看到它：http: //ideone.com/9iL1F

于 2012-03-29T21:53:14.987 回答
2

从最后一个数字开始，从一个角落向内走。向一个方向移动，当你撞到墙时，向左转 90 度。

于 2012-03-29T21:48:37.250 回答
2

我认为 ipc 的解决方案是基于你总是想填写整个矩阵的假设。如果你想做n = 28（即有一些不完整的行或列）怎么办？

对于一个通用的n解决方案，我发现从起点开始并向外增加了解旅行模式是最容易的。注意你去：

1 右 1 下 2 左 2 上 3 右 3 下 4 左 4 上 等等

所以基本上，模式是你向右、向下、向左、向上移动数个步骤，每两个方向变化就会增加一次。

不幸的是，我有一段时间没有用 C++ 编程了，所以我用 Ruby 做了。

def output_spiral(n)
  #For formatting, determine the length of the largest number
  max_number_length = n.to_s.length

  #Determine matrix size
  max_x = Math.sqrt(n).floor
  max_y = Math.sqrt(n).floor
  if max_x * max_y < n
    max_x += 1
    if max_x * max_y < n
      max_y += 1
    end
  end

  #The a matrix of the required size.
  #Note that for simplicity in printing spiral is an array of row arrays.
  spiral = Array.new
  row = Array.new(max_x){ |i| '  ' }
  max_y.times{ spiral << row.clone }

  #Determine the starting point index (ie where to insert 1)
  x = ((max_x-1)/2).floor
  y = ((max_y-1)/2).floor

  #Input the start point value, formatted to the right size
  spiral[y][x] = "%0#{max_number_length}d" % 1

  #Setup counters required to iterate through the spiral
  steps_in_direction = 1        #This defines how many steps to take in a direction
  steps_count = 0               #This defines how many steps have been taken in the direction
  direction = 'right'           #This defines the direction currently travelling
  steps_in_direction_count = 0  #This define how many times we have used the same steps_in_direction value

  #Iterate through all the numbers up to n
  2.upto(n) do |i|
    #Change index based on the direction we are travelling
    case direction
      when 'right' then x += 1
      when 'down' then y += 1
      when 'left' then x -= 1
      when 'up' then y -= 1
    end

    #Input the value, formatted to the right size
    spiral[y][x] = "%0#{max_number_length}d" % i

    #Increment counters
    steps_count += 1
    if steps_count == steps_in_direction
      steps_count = 0
      steps_in_direction_count += 1

      if steps_in_direction_count == 2
        steps_in_direction += 1
        steps_in_direction_count = 0
      end

      case direction
        when 'right' then direction = 'down'
        when 'down' then direction = 'left'
        when 'left' then direction = 'up'
        when 'up' then direction = 'right'
      end
    end

  end

  #Output spiral
  spiral.each do |x|
    puts x.join(' ')
  end
end

output_spiral(95)

请参阅http://ideone.com/d1N2c，它执行 n=95 的螺旋。

于 2012-03-30T17:24:40.060 回答
0

我将假设这是针对项目 euler #28 的（前几天我刚刚解决了这个问题）。秘诀不在于创建矩阵，而在于实现模式。实现模式，您可以在不创建矩阵的情况下计算出两条对角线。

1, 3, 5, 7, 9, 13, 17, 21, 25, ... , n

跳过什么？

至于重新创建螺旋矩阵，我认为最好的方法是在弄清楚模式后向后工作。从 n 开始，一直到 1。在矩阵中放置 'n' 比 1 容易得多。

编辑：

确定对角线后创建矩阵并不难（问题 28）。我将这些值放入矩阵中，然后根据我之前填充到矩阵中的主对角线值“遍历”矩阵填充所有其他值。但是，我浪费了少量时间来确定两条主要对角线。我更喜欢 IPC 的解决方案。但是，就像另一种方法一样，这是在我确定了两条主对角线之后计算矩阵的代码。让 n 表示网格的大小，例如 5。

int[,] t = new int[n, n];
int sizeOf = n - 1;

//Note that nums is the array of the two diagonals, which are already in sorted order based on my solution to problem 28.

//fill in diagonals
for (int diagNum = numsCount, i = sizeOf, j = 0; ; i--, j++)
{
    if (diagNum < 3)
    {
        t[i, j] = 1;
        break;
    }

    t[i, i] = nums[diagNum--];
    t[i, j] = nums[diagNum--];

    t[j, j] = nums[diagNum--];
    t[j, i] = nums[diagNum--];
}

//finish filling in matrix
for (int i = sizeOf, c = 0; i > 1; i--, c++)
{
    for (int j = i - 1; j > sizeOf - i; j--)
        t[i, j] = t[i, i] - i + j;

    for (int j = c + 1; j < sizeOf - c; j++)
        t[c, j] = t[c, c] - j + c;

    for (int j = c + 1; j < i; j++)
        t[j, i] = t[c, i] - j + c;

    for (int j = i - 1; j > c; j--)
        t[j, c] = t[i, c] - i + j;
}
于 2012-03-29T21:50:36.643 回答
0 
#include<stdio.h>

main()
{

long int i,j,k,a,b,c,d,sum1=0,sum2=0,sum3=0,sum4=0;

       for(i=1;i<=500;i++)
      {
        a=(2*i+1)*(2*i+1);
        sum1=sum1+a;
        b=a-2*i;
        sum2=sum2+b;
      c=b-2*i;
      sum3=sum3+c;
      d=c-2*i;
      sum4=sum4+d;
      }`

    printf("%ld",sum1+sum2+sum3+sum4+1);``
}
于 2015-12-07T15:47:28.573 回答