求能计算所有方阵的程序

libinary

对方阵实在是没有研究，这二年把原来的数学底子都丢光了，
写了一个穷举的程序，太慢了，N=3还挺快，N=4就很慢，
重新想了一下，对N的每种取值使得和等于N*(N^2+1)/2的等式是有限的，如N=3有8种：
1  5  9
1  6  8
2  4  9
2  5  8
2  6  7
3  4  8
3  5  7
4  5  6
count: 8
能不能先计算出这些等式再计算方阵，
下面是求等式的程序，数值是用#define定义的，对每个N要重新编译。

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define N 3
   
5. #define N2 9
   
6. #define SUM 15
   
7. #define FALSE 0
   
8. #define TRUE 1
   
9. #define WIDTH 2 /* 每一项输出的宽度 */
   
10. 
    
11. int testsum(void);
    
12. void print_a(void);
    
13. void func(int, int);
    
14. 
    
15. int a[N];
    
16. int count;
    
17. 
    
18. int main(void)
    
19. {
    
20.   func(0, 0);
    
21.   printf("count: %d\n", count);
    
22. 
    
23.   exit(0);
    
24. }
    
25. 
    
26. int
    
27. testsum(void)
    
28. {
    
29.   int i, sum = 0;
    
30. 
    
31.   for(i = 0; i < N; ++i)
    
32.     sum += a[i];
    
33.   if(sum != SUM)
    
34.     return(FALSE);
    
35. 
    
36.   ++count;
    
37.   return(TRUE);
    
38. }
    
39. 
    
40. void
    
41. print_a(void)
    
42. {
    
43.   int i;
    
44. 
    
45.   for(i = 0; i < N; ++i)
    
46.     printf("%*d ", WIDTH, a[i]);
    
47.   printf("\n");
    
48. }
    
49. 
    
50. /* 递归调用，n表示项的位置，pi表示项的取值下限 */
    
51. /* 对a进行穷举，如果用循环实现循环的嵌套层数等于N，就是a的项数，当N改变时
    
52. * 难以实现，所以用递归。第一次调用n=0，对应于a的第一项，调用一次前进一项，
    
53. * 对于N项，有N次递归。函数内用一个循环穷举一项的每种可能取值(我的穷举方阵
    
54. * 就是这么实现的)，对于这个程序，pi是为了使每一项的值都比前一项大，避免重复
    
55. */
    
56. void
    
57. func(int n, int pi)
    
58. {
    
59.   int i;
    
60. 
    
61.   for(i = pi; i < N2; ++i){
    
62.     a[n] = i + 1;
    
63.     if(n == N - 1){
    
64.       if(testsum())
    
65.         print_a();
    
66.     }else
    
67.       func(n + 1, i + 1);
    
68.   }
    
69. }
    

复制代码

下面是一些数据：
SUM: n*(n*n+1)/2
3: 15
4: 34
5: 65
6: 111
7: 175
8: 260
9: 369
10: 505

等式数目：
3: 8
4: 86
5: 1394
6: 32134
7以后我还没算，似乎比较大，能不能用数学方法推出等式的数目？

lordbyorn

过几天我有时间再做。

N=3 时有8个。
N=4时有7040个。
N=5时 ？？？

libinary

改进一下，用命令行参数指定N：

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define FALSE 0
   
5. #define TRUE 1
   
6. #define WIDTH 2 /* 每一项输出的宽度 */
   
7. 
   
8. int testsum(void);
   
9. void print_a(void);
   
10. void func(int, int);
    
11. 
    
12. int N;
    
13. int N2;
    
14. int SUM;
    
15. int *a;
    
16. int count;
    
17. 
    
18. int main(int argc, char *argv[])
    
19. {
    
20.   if(argc == 1){
    
21.     fprintf(stderr, "usage: %s number\n", argv[0]);
    
22.     exit(-1);
    
23.   }
    
24. 
    
25.   N = atoi(argv[1]);
    
26.   N2 = N * N;
    
27.   SUM = N * (N2 + 1) / 2;
    
28.   a = (int *)malloc(N * sizeof(*a));
    
29. 
    
30.   func(0, 0);
    
31.   printf("count: %d\n", count);
    
32. 
    
33.   free(a);
    
34.   exit(0);
    
35. }
    
36. 
    
37. int
    
38. testsum(void)
    
39. {
    
40.   int i, sum = 0;
    
41. 
    
42.   for(i = 0; i < N; ++i)
    
43.     sum += a[i];
    
44.   if(sum != SUM)
    
45.     return(FALSE);
    
46. 
    
47.   ++count;
    
48.   return(TRUE);
    
49. }
    
50. 
    
51. void
    
52. print_a(void)
    
53. {
    
54.   int i;
    
55. 
    
56.   for(i = 0; i < N; ++i)
    
57.     printf("%*d ", WIDTH, a[i]);
    
58.   printf("\n");
    
59. }
    
60. 
    
61. /* 递归调用，n表示a的位置，pi表示num的位置 */
    
62. /* 对a进行穷举，如果用循环实现循环的嵌套层数等于N，就是a的项数，当N改变时
    
63. * 难以实现，所以用递归。第一次调用n=0，对应于a的第一项，调用一次前进一项，
    
64. * 对于N项，有N次递归。函数内用一个循环穷举一项的每种可能取值(我的穷举方阵
    
65. * 就是这么实现的)，对于这个程序，pi是为了使每一项的值都比前一项大，避免重复
    
66. */
    
67. void
    
68. func(int n, int pi)
    
69. {
    
70.   int i;
    
71. 
    
72.   for(i = pi; i < N2; ++i){
    
73.     a[n] = i + 1;
    
74.     if(n == N - 1){
    
75.       if(testsum())
    
76.         print_a();
    
77.     }else
    
78.       func(n + 1, i + 1);
    
79.   }
    
80. }
    

复制代码

lordbyorn

我昨天用了7个小时的时间运行我的程序(N=5)，求出了大概10000个，我估计了一下，这只是全部结果的1/10000个。就是说硬盘都可能放不下。
N=10的时候，我是想也不敢想(全世界的硬盘也只能放下其中的小小一部分)。
我放心了，不用跳楼了。

只能找更加严格的条件了。

hhkk

Kill me?
Can not  work out a better method?

lordbyorn

最初由 hhkk 发表
Kill me?
Can not  work out a better method?

what?
totally don't understand.

can you give me a better method?

我给出的程序已经非常优化了。
用的是穷举的方法。
我的rang() 函数是最重要的，虽然很难理解。
这个函数让我保证只要能够填满方阵，一定是满足条件的。
我不用再写一个函数来检查。

再修改这个程序是不会增加太大的速度的。

libinary

先贴一下我的完全穷举的程序，慢的很，N>=4的情况还是不要试了。

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define N 3
   
5. #define N2 9
   
6. #define SUM 15
   
7. #define FALSE 0
   
8. #define TRUE 1
   
9. #define WIDTH 2
   
10. 
    
11. int testsum(void);
    
12. void print_a(void);
    
13. void func(int);
    
14. 
    
15. int a[N2];
    
16. int num[N2];
    
17. char line[(WIDTH + 1) * N + 1];
    
18. int count;
    
19. 
    
20. int main(void)
    
21. {
    
22.   int i;
    
23. 
    
24.   memset(line, '-', (WIDTH + 1) * N);
    
25.   line[(WIDTH + 1) * N] = '\0';
    
26.   for(i = 0; i < N2; ++i)
    
27.     num[i] = 0;
    
28. 
    
29.   func(0);
    
30.   printf("count: %d\n", count);
    
31. 
    
32.   exit(0);
    
33. }
    
34. 
    
35. int
    
36. testsum(void)
    
37. {
    
38.   int x, y, sum;
    
39. 
    
40. 
    
41.   for(y = 0; y < N; ++y){
    
42.     sum = 0;
    
43.     for(x = 0; x < N; ++x)
    
44.       sum += *(a + y * N + x);
    
45.     if(sum != SUM)
    
46.       return(FALSE);
    
47.   }
    
48.   for(x = 0; x < N; ++x){
    
49.     sum = 0;
    
50.     for(y = 0; y < N; ++y)
    
51.       sum += *(a + y * N + x);
    
52.     if(sum != SUM)
    
53.       return(FALSE);
    
54.   }
    
55.   sum = 0;
    
56.   for(x = 0, y = 0; x < N; ++x, ++y)
    
57.     sum += *(a + y * N + x);
    
58.   if(sum != SUM)
    
59.     return(FALSE);
    
60.   sum = 0;
    
61.   for(x = N - 1, y = 0; y < N; --x, ++y)
    
62.     sum += *(a + y * N + x);
    
63.   if(sum != SUM)
    
64.     return(FALSE);
    
65. 
    
66.   ++count;
    
67.   return(TRUE);
    
68. }
    
69. 
    
70. void
    
71. print_a(void)
    
72. {
    
73.   int x, y, i;
    
74. 
    
75.   for(y = 0; y < N; ++y){
    
76.     for(x = 0; x < N; ++x)
    
77.       printf("%*d ", WIDTH, *(a + y * N + x));
    
78.     printf("\n");
    
79.   }
    
80.   printf("%s\n", line);
    
81. }
    
82. 
    
83. void
    
84. func(int n)
    
85. {
    
86.   int i, sum = 0, val;
    
87. 
    
88.   for(i = 0; i < N2; ++i){
    
89.     if(num[i] == 0){
    
90.       num[i] = 1;
    
91.       *(a + n) = i + 1;
    
92.       if(n == N2 - 1){
    
93.         if(testsum())
    
94.           print_a();
    
95.       }else
    
96.         func(n + 1);
    
97.       num[i] = 0;
    
98.     }
    
99.   }
    
100. }
     

复制代码

time了一下N=3时间是0.261
改进的程序回头再贴。

lordbyorn

libinary 你的程序要比我的好才有用啊。
我的N=4时是30s左右。
N=3时不用什么时间吧。
N=5时，不知道要几年时间。

linuxiae

N必须是奇数吧？

lordbyorn

没有这样的规定
给你看几个：

1. 
   
2. //////////////////////////////////
   
3.     1    2   15   16
   
4.    12   14    3    5
   
5.    13    7   10    4
   
6.     8   11    6    9
   
7. *****************************************
   
8.     1    2   15   16
   
9.    13   14    3    4
   
10.    12    7   10    5
    
11.     8   11    6    9
    
12. *****************************************
    
13.     1    2   16   15
    
14.    13   14    4    3
    
15.    12    7    9    6
    
16.     8   11    5   10
    
17. *****************************************
    
18.     1    3   14   16
    
19.    10   13    4    7
    
20.    15    6   11    2
    
21.     8   12    5    9
    
22. *****************************************
    
23.     1    3   14   16
    
24.    12   13    4    5
    
25.    15    8    9    2
    
26.     6   10    7   11
    
27. *****************************************
    
28.     1    3   14   16
    
29.    15   13    4    2
    
30.    10    6   11    7
    
31.     8   12    5    9
    
32. *****************************************
    

复制代码