5

问题：给定一个整数 n，打印从 1 到 n 2的数字，如下所示：

n = 4

结果是：

01 02 03 04
12 13 14 05
11 16 15 06
10 09 08 07

您如何解决它（除了下面链接中提供的解决方案）？

http://www.programmersheaven.com/mb/CandCPP/81986/81986/problem-in-making-ap-c++-program/?S=B20000

我正在寻找另一个方向。到目前为止，我试图弄清楚是否可以获得我必须填写的职位的有序列表。

这就是我正在研究的内容：有没有办法获得“fdisp”以便以这种方式解决问题，而不是在矩阵中“走”？

matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
n = len(matrix)

# final disposition wrote by hand: how to get it for arbitrary n?
fdisp = [(0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3), (3,2),
         (3,1), (3,0), (2,0), (1,0), (1,1), (1,2), (2,2), (2,1)]

for val,i in enumerate(fdisp):
    matrix[i[0]][i[1]] = val + 1

def show_matrix(matrix, n):
    for i,l in enumerate(matrix):
        for j in range(n):
            print "%d\t" % matrix[i][j],
        print

show_matrix(matrix, n)
4

5 回答 5

5

这是一种不同的方法。它依赖于发现您所做的运动在：右、下、左、上、右、...之间循环。此外，您移动的次数是：3 右，3 下，3 左，2 上，2 右, 1 下, 1 左。因此，事不宜迟，我将用 Python 编写代码。

首先，我将使用一些 itertools 和一些 numpy：

from itertools import chain, cycle, imap, izip, repeat
from numpy import array

方向在：右、下、左、上、右、...之间循环：

directions = cycle(array(v) for v in ((0,1),(1,0),(0,-1),(-1,0)))

（我在这里使用 numpy 的数组，所以我可以轻松地将方向添加在一起。元组不能很好地添加。）

接下来，我移动的次数从 n-1 倒数到 1，每个数字重复两次，第一个数字重复 3 次：

countdown = chain((n-1,), *imap(repeat, range(n-1,0,-1), repeat(2)))

所以现在我的方向序列可以通过在倒计时中通过配对数字重复每个连续方向来创建：

dirseq = chain(*imap(repeat, directions, countdown))

为了得到我的索引序列，我可以对这个序列求和，但是（AFAIK）Python 没有提供这样的方法，所以让我们快速将一个放在一起：

def sumseq(seq, start=0):
  v = start
  yield v
  for s in seq:
    v += s
    yield v

现在要生成原始数组，我可以执行以下操作：

a = array(((0,)*n,)*n) # n-by-n array of zeroes
for i, v in enumerate(sumseq(dirseq, array((0,0)))):
  a[v[0], v[1]] = i+1
print a

其中，对于 n = 4，给出：

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

并且，对于 n = 5，给出：

[[ 1  2  3  4  5]
 [16 17 18 19  6]
 [15 24 25 20  7]
 [14 23 22 21  8]
 [13 12 11 10  9]]

这种方法可以推广到矩形网格；我将此作为练习留给读者；）

于 2009-07-24T13:46:31.387 回答
2

尽管您的示例是在 python 中，而这是在 Java 中，但我认为您应该能够遵循以下逻辑：

public class SquareTest {

public static void main(String[] args) {
    SquareTest squareTest = new SquareTest(4);
    System.out.println(squareTest);
}

private int squareSize;
private int[][] numberSquare;
private int currentX;
private int currentY;
private Direction currentDirection;

private enum Direction {
    LEFT_TO_RIGHT, RIGHT_TO_LEFT, TOP_TO_BOTTOM, BOTTOM_TO_TOP;
};

public SquareTest(int squareSize) {
    this.squareSize = squareSize;
    numberSquare = new int[squareSize][squareSize];
    currentY = 0;
    currentX = 0;
    currentDirection = Direction.LEFT_TO_RIGHT;
    constructSquare();
}

private void constructSquare() {
    for (int i = 0; i < squareSize * squareSize; i = i + 1) {
        numberSquare[currentY][currentX] = i + 1;
        if (Direction.LEFT_TO_RIGHT.equals(currentDirection)) {
            travelLeftToRight();
        } else if (Direction.RIGHT_TO_LEFT.equals(currentDirection)) {
            travelRightToLeft();
        } else if (Direction.TOP_TO_BOTTOM.equals(currentDirection)) {
            travelTopToBottom();
        } else {
            travelBottomToTop();
        }
    }
}

private void travelLeftToRight() {
    if (currentX + 1 == squareSize || numberSquare[currentY][currentX + 1] != 0) {
        currentY = currentY + 1;
        currentDirection = Direction.TOP_TO_BOTTOM;
    } else {
        currentX = currentX + 1;
    }
}

private void travelRightToLeft() {
    if (currentX - 1 < 0 || numberSquare[currentY][currentX - 1] != 0) {
        currentY = currentY - 1;
        currentDirection = Direction.BOTTOM_TO_TOP;
    } else {
        currentX = currentX - 1;
    }
}

private void travelTopToBottom() {
    if (currentY + 1 == squareSize || numberSquare[currentY + 1][currentX] != 0) {
        currentX = currentX - 1;
        currentDirection = Direction.RIGHT_TO_LEFT;
    } else {
        currentY = currentY + 1;
    }
}

private void travelBottomToTop() {
    if (currentY - 1 < 0 || numberSquare[currentY - 1][currentX] != 0) {
        currentX = currentX + 1;
        currentDirection = Direction.LEFT_TO_RIGHT;
    } else {
        currentY = currentY - 1;
    }
}

@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < squareSize; i = i + 1) {
        for (int j = 0; j < squareSize; j = j + 1) {
            builder.append(numberSquare[i][j]);
            builder.append(" ");
        }
        builder.append("\n");
    }

    return builder.toString();
}
}
于 2009-07-23T21:04:08.713 回答
2

另一种方法，这次是在 C# 中：

int number = 9;
var position = new { x = -1, y = 0 };
var directions = new [] { 
    new { x = 1, y = 0 },
    new { x = 0, y = 1 },
    new { x = -1, y = 0 },
    new { x = 0, y = -1 }
};

var sequence = (
    from n in Enumerable.Range(1, number)
    from o in Enumerable.Repeat(n, n != number ? 2 : 1)
    select o
).Reverse().ToList();

var result = new int[number,number];

for (int i = 0, current = 1; i < sequence.Count; i++)
{
    var direction = directions[i % directions.Length];      

    for (int j = 0; j < sequence[i]; j++, current++)
    {
        position = new {
            x = position.x + direction.x,
            y = position.y + direction.y
        };

        result[position.y, position.x] = current;
    }
}
于 2009-07-23T21:18:44.177 回答
1

我找到了一个方法。现在我必须对其进行一些改进，尤其是我必须找到一种更清洁的方法来构建“fdisp”。n = 5

dim = n
pos = (0, -1)
fdisp = []
squares = n % 2 == 0 and n / 2 or n / 2 + 1

for _ in range(squares):
    pos = (pos[0], pos[1] + 1)
    fdisp.append(pos)

    fdisp += [(pos[0],pos[1]+i) for i in range(1, dim)]
    pos = fdisp[-1]
    fdisp += [(pos[0]+i,pos[1]) for i in range(1, dim)]
    pos = fdisp[-1]
    fdisp += [(pos[0],pos[1]-i) for i in range(1, dim)]
    pos = fdisp[-1]
    fdisp += [(pos[0]-i,pos[1]) for i in range(1, dim - 1)]
    pos = fdisp[-1]
    dim = dim - 2

matrix = [[0] * n for i in range(n)]

for val,i in enumerate(fdisp):
    matrix[i[0]][i[1]] = val + 1

def show_matrix(matrix, n):
    for i,l in enumerate(matrix):
        for j in range(n):
            print "%d\t" % matrix[i][j],
        print

show_matrix(matrix, n)
于 2009-07-24T10:22:53.583 回答
1

我已经使用 C++ 解决了您的问题。不知道对你有没有帮助。不过贴出来。如果它对你有用，那将是一种乐趣。

这是代码：

    #include<iostream>
    #include<string.h>
    using namespace std;

    bool valid(int n,int r,int c)
    {
        if(r>=1 && r<=n && c>=1 && c<=n)
            return true;
        return false;
    }


    int main()
    {
        pair<int,int>d1,d2,d3,d4,temp;
        d1 = make_pair(0,1);
        d2 = make_pair(1,0);
        d3 = make_pair(0,-1);
        d4 = make_pair(-1,0);
        /**********************direction******************************/

        int n, i, j, counter=1, newR = 1, newC = 0, direction = 4;
        bool changeDir=true;
        /**************************variables*************************/

        cin>>n;
        int arr[n+1][n+1];
        int visited[n+1][n+1];
        /*************************arrays********************************/

        memset(visited,0,sizeof(visited));
        memset(arr,0,sizeof(arr));
        /***************initializing the array**************************/

        while(counter<=n*n)
        {
            if(direction==1 && changeDir)
            {
                temp = make_pair(d2.first,d2.second);
                direction=2;
                changeDir=false;
            }
            else if(direction==2&& changeDir)
            {
                temp = make_pair(d3.first,d3.second);
                direction=3;
                changeDir=false;
            }
            else if(direction==3&& changeDir)
            {
                temp = make_pair(d4.first,d4.second);
                direction=4;
                changeDir=false;
            }
            else if(direction==4&& changeDir)
            {
                temp = make_pair(d1.first,d1.second);
                direction=1;
                changeDir=false;
            }
            while(counter<=(n*n) && !changeDir)
            {
                newR =newR+temp.first;
                newC=newC+temp.second;
                if(valid(n,newR,newC) && !visited[newR][newC])
                {
                    arr[newR][newC]=counter;
                    visited[newR][newC]=1;
                    counter++;
                }
                else
                {
                    newR-=temp.first;
                    newC-=temp.second;
                    changeDir=true;
                    break;
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(arr[i][j]<10)
                    cout<<0;
                cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
        return 0;
    }

这是 N=5 的输出：

01 02 03 04 05 
16 17 18 19 06 
15 24 25 20 07 
14 23 22 21 08 
13 12 11 10 09

谢谢你。

于 2015-02-03T16:23:08.273 回答