一道上海交大研究生入学考试试题：物以稀为贵

cjaizss

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. int code_len = 8;//号码长度
   
5. int neib[10][4];//邻接表
   
6. int result[10][1000];//每个存储的如果是0，代表没被设置，否则result[i][j]存储的是以i打头j位号码有多少个
   
7. 
   
8. 
   
9. void create_neib(void)
   
10. {
    
11.         int a[3][3];
    
12.         int i,j;
    
13.         int num,k;
    
14.         for(i=0;i<3;i++)
    
15.                 for(j=0;j<3;j++)
    
16.                         a[i][j]=&a[i][j]-&a[0][0]+1;
    
17.         for(i=0;i<3;i++)
    
18.                 for(j=0;j<3;j++) {
    
19.                         num = a[i][j];
    
20.                         k=0;
    
21.                         if(i-1>=0)
    
22.                                 neib[num][k++] = a[i-1][j];
    
23.                         if(i+1<3)
    
24.                                 neib[num][k++] = a[i+1][j];
    
25.                         if(j-1>=0)
    
26.                                 neib[num][k++] = a[i][j-1];
    
27.                         if(j+1<3)
    
28.                                 neib[num][k++] = a[i][j+1];
    
29.                         if(k<4)
    
30.                                 neib[num][k] = -1;
    
31.                 }
    
32.         neib[0][0] = 8;
    
33.         neib[0][1] = -1;
    
34.         neib[8][3] = 0;
    
35. 
    
36. }
    
37. 
    
38. 
    
39. void cal_result_real(int start_num,int cnt)
    
40. {
    
41.         int i;
    
42.         int r;
    
43.         if(result[start_num][cnt])//因有这一步，降低时间复杂级别
    
44.                 return;
    
45.         if(cnt==1) {
    
46.                 result[start_num][cnt] = 1;
    
47.                 return;
    
48.         }
    
49.         r = 0;
    
50.         for(i=0;i<4;i++)
    
51.                 if(neib[start_num][i] >= 0) {
    
52.                         cal_result_real(neib[start_num][i],cnt-1);
    
53.                         r += result[neib[start_num][i]][cnt-1];
    
54.                 } else
    
55.                         break;
    
56.         result[start_num][cnt] = r;
    
57. 
    
58. 
    
59. }
    
60. 
    
61. int cal_result(void)
    
62. {
    
63.         int i,j;
    
64.         int ret;
    
65.         for(i=0;i<10;i++)
    
66.                 for(j=0;j<=code_len;j++)
    
67.                         result[i][j]=0;
    
68. 
    
69.         for(i=0;i<10;i++)//每个号码打头的都来一遍
    
70.                 cal_result_real(i,code_len);
    
71.         ret=0;
    
72.         for(i=0;i<10;i++)
    
73.                 ret+=result[i][code_len];
    
74.         return ret;
    
75. }
    
76. 
    
77. int main(int argc,char**argv)
    
78. {
    
79.         int ret;
    
80. 
    
81.         if(argc>1)
    
82.                 code_len = atoi(argv[1]);
    
83.         create_neib();
    
84.         ret = cal_result();
    
85.         printf("ret=%d\n",ret);
    
86.         return 0;
    
87. }
    

复制代码

hbmhalley

1. (define ls
   
2.   '((0 8)
   
3.     (1 2 4)
   
4.     (2 1 5 3)
   
5.     (3 2 6)
   
6.     (4 1 5 7)
   
7.     (5 4 2 6 8)
   
8.     (6 9 5 3)
   
9.     (7 4 8)
   
10.     (8 7 5 9 0)
    
11.     (9 8 6)))
    
12. 
    
13. (display
    
14.   (let iter ((x 8) (c #f))
    
15.     (if (zero? x) 1
    
16.       (fold + 0
    
17.             (map
    
18.               (lambda (c) (iter (1- x) c))
    
19.               (if c (assoc-ref ls c) (map car ls)))))))
    

复制代码

pitonas

算了，难了点，，，

linuxchyu

回复 3# bruceteen


    嗯是的，只求有多少种方法就行了

linuxchyu

回复 9# cjaizss


   不用递归，只用DP就行了

linuxchyu

回复 22# hbmhalley


    Lisp果然强大，不知运行结果和时间是多少？

linuxchyu

回复 20# bruceteen


    嗯。结果对了，看看能不能再改进下算法？

leeXsen

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define mem_test(x) if ((x) == NULL) { \
   
5.                         puts("Memory error!"); \
   
6.                         exit(1); \
   
7.                     }
   
8. 
   
9. typedef struct tree {
   
10.         int max;
    
11.         int value;
    
12.         struct tree **child;
    
13. } Tree;
    
14. 
    
15. static Tree t[10];
    
16. static unsigned int sum = 0;
    
17. 
    
18. static const int map[10][5] = {
    
19.         {8, -1, -1, -1, 1},                /* 0 */
    
20.         {2, 4, -1, -1, 2},                /* 1 */
    
21.         {1, 3, 5, -1, 3},                        /* 2 */
    
22.         {2, 6, -1, -1, 2},                /* 3 */
    
23.         {1, 5, 7, -1, 3},                        /* 4 */
    
24.         {2, 4, 6, 8, 4},                        /* 5 */
    
25.         {3, 5, 9, -1, 3},                        /* 6 */
    
26.         {4, 8, -1, -1, 2},                /* 7 */
    
27.         {0, 5, 7, 9, 4},                        /* 8 */
    
28.         {6, 8, -1, -1, 2}                        /* 9 */
    
29. };
    
30. 
    
31. void tree(Tree *p)
    
32. {
    
33.         int i;
    
34.         int value;
    
35.         static int layer = 0;
    
36. 
    
37.         if (++layer < 8) {
    
38.                 value = p->value;
    
39.                 p->max = map[value][4];
    
40.                 p->child = (Tree **)malloc(p->max * sizeof(Tree *));
    
41.                 mem_test(p->child);
    
42. 
    
43.                 for (i = 0; i < p->max; i++) {
    
44.                         p->child[i] = (Tree *)malloc(sizeof(Tree));                       
    
45.                         mem_test(p->child[i]);
    
46.                         p->child[i]->value = map[value][i];
    
47.                         tree(p->child[i]);
    
48.                 }
    
49.         }
    
50. 
    
51.         --layer;
    
52. }
    
53. 
    
54. void init_tree(void)
    
55. {
    
56.         int i;
    
57. 
    
58.         for (i = 0; i < 10; i++) {
    
59.                 t[i].value = i;
    
60.                 tree(&t[i]);
    
61.         }
    
62. }
    
63. 
    
64. void show_tree(Tree *p)
    
65. {
    
66.         int i;
    
67.         static int layer = 0;
    
68.        
    
69.         if (++layer < 9) {
    
70.                 if (layer != 8) {
    
71.                         for (i = 0; i < p->max; i++)
    
72.                                 show_tree(p->child[i]);
    
73.                 } else
    
74.                         ++sum;
    
75.         }
    
76. 
    
77.         --layer;
    
78. }
    
79. 
    
80. void show()
    
81. {
    
82.         int i;
    
83. 
    
84.         for (i = 0; i < 10; i++)
    
85.                 show_tree(&t[i]);
    
86. }       
    
87. 
    
88. void main(void)
    
89. {
    
90.         init_tree();
    
91.         show();
    
92.         printf("%d\n", sum);
    
93. }
    

复制代码

用递归简单点吧，我的好像有点长...

starwing83

话说这种题目需要数据结构和算法么= =

1. local trans = {
   
2.     [0] = { 8 },
   
3.     [1] = { 2, 4 },
   
4.     [2] = { 1, 3, 5 },
   
5.     [3] = { 2, 6 },
   
6.     [4] = { 1, 5, 7 },
   
7.     [5] = { 2, 4, 6, 8 },
   
8.     [6] = { 3, 5, 9 },
   
9.     [7] = { 4, 8 },
   
10.     [8] = { 0, 5, 7, 9 },
    
11.     [9] = { 6, 8 },
    
12. }
    
13. 
    
14. local function search(n, idx)
    
15.     idx = idx or 0
    
16.     local count = 0
    
17.     for _, v in ipairs(trans[n]) do
    
18.         count = count + (idx == 6 and 1 or search(v, idx + 1))
    
19.     end
    
20.     return count
    
21. end
    
22. 
    
23. local count = 0
    
24. for i = 0, 9 do
    
25.     count = count + search(i)
    
26. end
    
27. print(count)
    

复制代码

还有，对于指定了规模的题目而言，是无法说复杂度的，复杂度在【输入】发生变化时才有效果，这题没输入。

daybreakcx

动态规划的代码复杂度是O(N)，其中N为号码的长度
其实用矩阵乘法更快点，初始矩阵rela[j]表示用1步从i到j的可能情况数（初始是1），最后就是先求矩阵的7次方，然后对res[j]求和就行了，一次矩阵乘法的计算次数是10^3=1000次乘法，矩阵乘法用优化算法是log(N-1)次，所以计算次数大概是1000log(N-1)+100（100是对res[j]求和），也就是说，复杂度大概是O(logN)，代码如下，结果求出是14826：

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. int rela[10][10] = {{0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
   
5.         {0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
   
6.         {0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
   
7.         {0, 0, 1, 0, 0, 0, 1, 0, 0, 0},
   
8.         {0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
   
9.         {0, 0, 1, 0, 1, 0, 1, 0, 1, 0},
   
10.         {0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
    
11.         {0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
    
12.         {1, 0, 0, 0, 0, 1, 0, 1, 0, 1},
    
13.         {0, 0, 0, 0, 0, 0, 1, 0, 1, 0}};
    
14. int res[10][10], len = 7, i, j, ans;
    
15. 
    
16. void
    
17. mult(int s[][10], int t[][10]) {
    
18.         int temp[10][10], i, j, k;
    
19. 
    
20.         for (i = 0; i < 10; ++i)
    
21.                 for (j = 0; j < 10; ++j) {
    
22.                         temp[i][j] = 0;
    
23.                         for (k = 0; k < 10; ++k)
    
24.                                 temp[i][j] += s[i][k] * t[k][j];
    
25.                 }
    
26.         memcpy(s, temp, sizeof(temp));
    
27. }
    
28. 
    
29. int
    
30. main()
    
31. {
    
32.         for (i = 0; i < 10; ++i)
    
33.                 res[i][i] = 1;
    
34.         for (i = 1; ; ) {
    
35.                 if (len & i)
    
36.                         mult(res, rela);
    
37.                 if ((i <<= 1) > len)
    
38.                         break;
    
39.                 else
    
40.                         mult(rela, rela);
    
41.         }
    
42.         for (i = ans = 0; i < 10; ++i)
    
43.                 for (j = 0; j < 10; ++j)
    
44.                         ans += res[i][j];
    
45.         fprintf(stdout, "%d\n", ans);
    
46.         return 0;
    
47. }
    

复制代码

相比起动态规划，我认为矩阵乘法是最优的了