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など

つまり、基本的にパターンは、2つの方向が変わるたびに増分するいくつかのステップで、右、下、左、上に移動することです。

残念ながら、私はしばらくの間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)

n=95のスパイラルを実行するhttp://ideone.com/d1N2cを参照してください。

于 2012-03-30T17:24:40.060 に答える
0

これはプロジェクトオイラー＃28用だと思います（先日この問題を実行しました）。その秘訣は、マトリックスを作成することではなく、パターンを実現することです。パターンを実現すると、マトリックスを作成せずに2つの対角線を数えることができます。

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

何かスキップしますか？

スパイラルマトリックスを再現する限り、パターンを理解した後、逆方向に作業するのが最善の方法だと思います。nから始めて、1まで下げていきます。マトリックスに1よりも「n」を配置する方がはるかに簡単です。

編集：

対角線を決定した後に行列を作成することはそれほど難しくありません（問題28）。これらの値をマトリックスに配置してから、以前にマトリックスに入力した主対角値に基づいて、他のすべての値を入力するマトリックスを「ウォーク」しました。ただし、2つの主要な対角線を決定するのに少し時間を浪費します。私はIPCのソリューションの方が好きです。ただし、別の方法と同様に、2つの主対角線を決定した後に行列を計算するコードを次に示します。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 に答える