Создание внешней спирали

Question

Я думал об этом, и я просто не могу придумать, как заполнить матрицу внешней спиралью, чтобы я мог сделать следующее:

Повернуть это: 1 2 34 5 ... n

To

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

Я думаю, что решение 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.

Answer 3

Начните с последнего номера и идите внутрь от угла. Двигайтесь в одном направлении, и когда вы ударите о стену, поверните налево на 90 градусов.

Answer 4

#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);``
}

Answer 5

Я собираюсь предположить, что это для проекта 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;
}