在一个大小为nxn的矩阵的一个单元格中找到最大用户数

Question

我正在解决这个算法问题，但是我找不到提供的参考答案。欢迎任何帮助或提示来解决这个问题。

问题陈述如下：在一个大小为NxN的区域中，每个单元格在T=0时都包含1，其中1代表一个用户。

Hence, at T= 0 and N = 5 the matrix is as below
1   1   1   1   1
1   1   1   1   1
1   1   1   1   1
1   1   1   1   1
1   1   1   1   1
Each cell is a user.
Now at time T =1,2,3 etc the position of each user changes.

if x(row)+y(col) = even
New x = (x+y)^2%N
New y = (x*y)%N

if x(row)+y(col) = odd
New x = (x+y)%N
New y = |x-y|%N

寻找在T=3时最大的用户数 参考，当N=5且T=3时，每个单元格中的最大用户数应为8。

我尝试解决这个问题，但我总是得到11作为我的最大值，如果我每次移动所有用户，则得到6。 如何解决这个问题或理解它的提示将非常感激。谢谢。 以下是我用于解决此问题的代码 它使用C编程语言编写。提前致谢。

int abs(int y, int x)
    {
     int temp = x - y;
     return temp > 0 ? temp : -temp;
    }

int new_x(int x, int y, int n)
{
 if((x+y)%2)
  return (((x+y)*(x+y))%n);
 else
  return (x+y)%n;
}

int new_y(int x, int y, int n)
{
 if((x+y)%2)
  return (x*y)%n;
 else
  return ((abs(x,y))%n);

}

void print_matrix(int *p, int n, int time)
{
    int i,j;
    int sum = 0;
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            printf("%d\t",*((p+i*n)+j));
            sum += *((p+i*n)+j);
        }
    printf("\n");
    }
    printf("Sum = %d\t at T=%d\n",sum, time);
}


int main(void)
{
    int T = 3;
    int N = 5;
    int test_case,i,j,x,y,item, sum, val;
    int arr_initial[5][5];
    //====================================
    //For Time T=0 all elements are 1
    //====================================
    for(i=0;i<N;i++){
            for(j=0;j<N;j++) {
                arr_initial[i][j] = 1;
            }
        }
        //=====================================
        printf("Initial Matrix at T0 time\n");
        print_matrix((int*)arr_initial, N, 0);
        printf("\n");
        //====================================
        //Now calculate the new position for Time T1,T2 & T3
        //====================================
        for(test_case =1; test_case<=T;test_case++)
        {
            sum = 0;
            for(i=0;i<N;i++)
            {
                for(j=0;j<N;j++)
                {//Get NewX and NewY for movement
                    x = new_x(i,j,N);
                    y = new_y(i,j,N);
                    if(x==i && y==j)
                        {
                        //No movement as initial and new position is same
                        }
                    else{
                        //There is a movement
                        item = arr_initial[i][j];
                        val = item -1;
                            if(val<0) 
                                {
                                //no item to move
                                }
                            else 
                                {
                                arr_initial[x][y] += arr_initial[i][j];
                                arr_initial[i][j] = 0;
                                }
                        }

                    }
                }
            //=======================================================
            printf("\n");
            printf("Matrix at Time T = %d\n",test_case);
            print_matrix((int*)arr_initial, N, test_case);
            printf("\n");
            }
    return 0;   
}

- Niel

---

当 x+y 为奇数时，if((x+y)%2) 为真。 - BLUEPIXY

N和M的限制是什么？问题在于当您更新用户位置时，直接将其更新到同一数组中，因此，在读取和处理之前就可以修改单元格，从而导致错误答案。 - Pham Trung

嗨，感谢指出错误。N的限制为5 <= N <= 100，T的限制为3 <= T <= 100。 - Niel

Answer 1

你的任务说明和代码不一致 - 你说使用 (x*y)^2 但实现了 (x+y)^2。这个解决方案通过在一个单独的数组中构建下一代来实现。

#include <stdio.h>
#include <string.h>
#include <math.h>

#define N 5

int main(void) {
    char matrix[N][N], next[N][N];
    int x, y, t, x2, y2, max;
    memset(matrix, 1, sizeof(matrix));          // initialise matrix
    for(t=0; t<3; t++) {
        memset(next, 0, sizeof(next));          // clear next generation
        for (y=0; y<N; y++)
            for (x=0; x<N; x++) {
                if ((x + y) % 2 == 0) {
                    x2 = ((x + y) * (x + y)) % N;
                    y2 = (x * y) % N;
                } else {
                    x2 = (x + y) % N;
                    y2 = abs(x - y) % N;
                }
                next[y2][x2] += matrix[y][x];
            }
        memcpy(matrix, next, sizeof(matrix));   // copy back
    }

    max = 0;
    for (y=0; y<N; y++) {                       // print matrix
        for (x=0; x<N; x++) {
            if (max < matrix[y][x])
                max = matrix[y][x];
            printf("%-3d", matrix[y][x]);
        }
        printf ("\n");
    }
    printf ("Max is %d\n", max);
    return 0;
}

程序输出：

1  0  0  0  0
0  2  0  0  4
0  0  0  0  0
4  8  0  4  0
0  2  0  0  0
Max is 8

- Weather Vane

Answer 2

1) 你错误地计算了 (x+y) 是否为奇数。如果 (x+y)%2 为真，则 x+y 是奇数。因此：

int new_x(int x, int y, int n)
{
 if((x+y)%2)
  return (((x+y)*(x+y))%n);
 else
  return (x+y)%n;
}

int new_y(int x, int y, int n)
{
 if((x+y)%2)
  return (x*y)%n;
 else
  return ((abs(x,y))%n);

}

应该被改为：

int new_x(int x, int y, int n)
{
 if((x+y)%2)
  return (x+y)%n;
 else
  return (((x+y)*(x+y))%n);
}

int new_y(int x, int y, int n)
{
 if((x+y)%2)
  return ((abs(x,y))%n);
 else
  return (x*y)%n;
}

2) 你改变了数组中尚未处理的字段：

arr_initial[x][y] += arr_initial[i][j];

你需要使用另一个矩阵，初始化为0，来跟踪其中的新值，并在每个步骤结束时将更改复制回原始矩阵。

- Neithrik

---

嗨，谢谢指出错误，我会再试一次。谢谢。 - Niel

Answer 3

问题在于你从数组中读取值，而这个值可能已经被修改了，成为 T+1 的值！因此，你需要另一个数组来跟踪 T 的值。以下是思路：

    for(i = 0; i < N; i ++)
        for (j = 0; j < N; j ++)
            alter_arr[i][j] = current_arr[i][j];

    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {//Get NewX and NewY for movement
            x = new_x(i,j,N);
            y = new_y(i,j,N);

            printf("%d, %d moved to %d, %d\n", i, j, x, y);
            if(x==i && y==j)
            {
                // no movement
            }
            else{
                //There is a movement
                item = current_arr[i][j];
                val = item -1;
                if(val<0) 
                {
                    //no item to move
                }
                else 
                {
                    alter_arr[x][y] += current_arr[i][j];
                    alter_arr[i][j] -= current_arr[i][j];
                }
            }

        }
    }

    int (*tmp)[5] = current_arr;
    current_arr = alter_arr;
    alter_arr = tmp;

    //=======================================================
    printf("\n");
    printf("Matrix at Time T = %d\n",test_case);

并且在你的 new_x 和 new_y 函数中改变 if 语句。

以下是结果，最大值为 8，T = 3：

Initial Matrix at T0 time
1   1   1   1   1   
1   1   1   1   1   
1   1   1   1   1   
1   1   1   1   1   
1   1   1   1   1   
Sum = 25     at T=0


Matrix at Time T = 1
1   2   0   2   0   
2   2   0   4   2   
0   2   0   0   0   
0   2   0   2   0   
2   2   0   0   0   
Sum = 25     at T=1


Matrix at Time T = 2
1   0   0   4   0   
2   4   0   6   2   
0   0   0   0   0   
0   2   0   2   0   
0   2   0   0   0   
Sum = 25     at T=2


Matrix at Time T = 3
1   0   0   4   0   
0   2   0   8   2   
0   0   0   0   0   
0   0   0   4   0   
0   4   0   0   0   
Sum = 25     at T=3

- Pan Long