Найти максимальных пользователей в ячейке матрицы размера nxn

Question

Я решал эту проблему с алгоритмом, но я не могу найти ответ ссылки, как предусмотрено. Любая помощь или подсказка в решении этой проблемы приветствуется.

Оператор проблемы выглядит следующим образом: В области размера NxN каждая ячейка содержит 1 в момент времени T = 0, где 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 Reference, для N = 5 и T = 3 Максимальное количество пользователей в ячейке должно быть 8.

Я попытался решить эту проблему, но я всегда заканчиваю с 11 в качестве моего max, если я перемещаю всех пользователей и 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 

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, отслеживать новые значения в нем и копировать изменения в исходную матрицу в конце каждого шага.

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 функции.

Ниже результат, максимальная 8 при Т = 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