问题是什么样的算法可以找到用大小N*M填充矩阵的可能性
包括从1到N*M的所有数字,从左到右,从上到下排序
例如:
对于N=2,M=3
金额是4
1 2 3个
四五六
1 3 5个
2 4 6个
1 2 5个
3 4 6个
1 2 4个
3 5 6个
我试着找出一些模式但没有成功,这是家庭作业,
我真正意识到的是,在所有情况下,N*M的最大值必须在[N][M]中,最小值必须在[0][0]中,非常感谢您的帮助

最佳答案

你忘了:

1 3 4
2 5 6

C中的代码:
    static int N = 5;
    static int M = 5;
    static int[,] Number;
    static int[] NumbersInRow;


    static int Put(int n)
    {
        if (n > N * M)
        {
            // If output of each solution is desired
            //for (int y = 0; y < N; y++)
            //{
            //    for (int x = 0; x < M; x++)
            //        Console.Write(Number[y, x] + "\t");

            //    Console.WriteLine();
            //}
            //Console.WriteLine();
            return 1;
        }

        int sum = 0;

        int numbersInLastRow = int.MaxValue;
        int currentRow = 0;
        while (currentRow < N)
        {
            int numbersInCurrentRow = NumbersInRow[currentRow];
            if (numbersInCurrentRow < numbersInLastRow && numbersInCurrentRow < M)
            {
                Number[currentRow, NumbersInRow[currentRow]] = n;
                NumbersInRow[currentRow]++;
                sum += Put(n + 1);
                NumbersInRow[currentRow]--;
                Number[currentRow, NumbersInRow[currentRow]] = 0;
            }
            numbersInLastRow = NumbersInRow[currentRow];
            currentRow++;
        }

        return sum;
    }

    static void Main(string[] args)
    {
        Number = new int[N, M];
        NumbersInRow = new int[N];
        Console.WriteLine(Put(1));
        Console.ReadLine();
    }

说明:
把数字按顺序放在黑板上,从1开始。当一个数字有多个正确的位置时,递归地拆分并计算所有的解。
我们如何知道一个数字的正确位置,而不尝试每一个可能的位置/使用回溯?如果“-1th”行中有无限个数字,则可以将数字放在其前一行中有更多数字的任何非整行的第一个空位置就这样这样我们就不会做出错误的举动。
注意,这是对称的-就像你总是可以把下一个数字放在第一行如果它不是满的,你也可以把它放在第一列。
解决方案的数量增长极为迅速:
2x2 - 2
3x3 - 42
4x4 - 24024
5x5 - 701149020

10-08 04:06