创建向外缓和曲线

Question

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

把这个转过来:12345...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;
}

谢谢!

Answer 1

你可以观察到，在左下角位置有类似的方块，值最低，然后是向上，向右，向下和向左。

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

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

Answer 2

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

Answer 3

我认为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做了螺旋式的处理。