c - 在大小为 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 为最大值，如果我每次只移动 1 个用户，则以 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;   
}

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