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

linuxchyu

1  2  3   
4  5  6
7  8  9
    0  
说某移动电信运营商开发了一个名为“争霸”的游戏，为鼓励用户参与，凡签约用户均可获得前三位为888的手机号码，但这样的话就有10的8次方种可能，现在给出一种限制条件减少号码数量，就是两个相邻号码之间的关系必须满足象棋里的“将步”
即：给你前三位都是888  后面8位是上面的数字  每个数的相邻只有有限个数字
比如8881*  那么与1相邻的只可以是2和4  
888812那么与2相邻的只可以是1，5，3  就是这个意思（888后面的第一个数字不受将步的限制）
如果选择5  那么可以选择的有2，4，6，8
问：
1  用什么算法比较好？为什么？
2  最优的算法是什么？为什么？
3  用什么数据结构最好？为什么？
4  时间复杂度和空间复杂度？
5  一共有多少种情况？


先确认下哈：答案是14826种。不过这种考试题肯定是要你寻找比较优化的方法。

bruceteen

这还要什么复杂算法？就一个个遍历呗
从最小的数 （888）08080808 开始
先动个位，个位动不了的话动十位，……，乃至动千万位，还动不了说明结束了
即
（888）08080852
（888）08080854
（888）08080856
……
（888）98989898

bruceteen

哦，明白了，主要是求“5  一共有多少种情况？”，而不是要求输出所有手机号码

shang2010

树的遍历，这种题蛮费脑汁的，

因为不小心就会有数学方法，套用一个公式直接要答案。。

hisptoot

帮LZ加一个问题 所有号码中 最后一位是0的概率是多少

zhlong8

递归就行了 47132

shang2010

@hisptoot

你相不相信，高中生都能解

zhlong8

表输错了， 43038

1. #!/usr/bin/perl -w
   
2. 
   
3. use strict;
   
4. use warnings;
   
5. 
   
6. my %map = (
   
7.     1 => [2, 4],
   
8.     2 => [1, 3, 5],
   
9.     3 => [2, 6],
   
10.     4 => [1, 5, 7],
    
11.     5 => [2, 4, 6, 8],
    
12.     6 => [3, 5, 9],
    
13.     7 => [4, 8],
    
14.     8 => [5, 7, 9, 0],
    
15.     9 => [6, 8],
    
16.     0 => [8],
    
17. );
    
18. 
    
19. sub solve {
    
20.     my($n, $last) = @_;
    
21. 
    
22.     if ($n == 1) {
    
23.         return map { [ $_ ] } @{$map{$last}};
    
24.     } else {
    
25.         my @ret = map solve($n-1, $_), @{$map{$last}};
    
26.         unshift @$_, $last for @ret;
    
27.         @ret
    
28.     }
    
29. }
    
30. 
    
31. print "@$_\n" for map {solve 8, $_} 0 .. 9

复制代码

cjaizss

先列递归式
然后动态规划

bruceteen

我计算出来怎么是 5251 个号码

递归法：

1. #include <stdio.h>
   
2. 
   
3. static const int maps[10][4] = { { 8, -1, -1, -1 } // 0
   
4.                                , { 2,  4, -1, -1 } // 1
   
5.                                , { 1,  3,  5, -1 } // 2
   
6.                                , { 2,  6, -1, -1 } // 3
   
7.                                , { 1,  5,  7, -1 } // 4
   
8.                                , { 2,  4,  6,  8 } // 5
   
9.                                , { 3,  5,  9, -1 } // 6
   
10.                                , { 4,  8, -1, -1 } // 7
    
11.                                , { 0,  5,  7,  9 } // 8
    
12.                                , { 6,  8, -1, -1 } // 9
    
13.                                };
    
14. 
    
15. int foo( int v, int n )
    
16. {
    
17.     if( v == -1 )
    
18.         return 0 ;
    
19.     if( n == 8 )
    
20.         return 1;
    
21. 
    
22.     return foo( maps[v][0], n+1 )
    
23.          + foo( maps[v][1], n+1 )
    
24.          + foo( maps[v][2], n+1 )
    
25.          + foo( maps[v][3], n+1 );
    
26. }
    
27. 
    
28. int main()
    
29. {
    
30.     printf( "%d\n", foo(8,0) );
    
31.     return 0;
    
32. }

复制代码

遍历法：

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     static const int maps[10][4] = { { 8, -1, -1, -1 } // 0
   
6.                                    , { 2,  4, -1, -1 } // 1
   
7.                                    , { 1,  3,  5, -1 } // 2
   
8.                                    , { 2,  6, -1, -1 } // 3
   
9.                                    , { 1,  5,  7, -1 } // 4
   
10.                                    , { 2,  4,  6,  8 } // 5
    
11.                                    , { 3,  5,  9, -1 } // 6
    
12.                                    , { 4,  8, -1, -1 } // 7
    
13.                                    , { 0,  5,  7,  9 } // 8
    
14.                                    , { 6,  8, -1, -1 } // 9
    
15.                                    };
    
16.     //             0  1  2  3  4  5  6  7  8
    
17.     int num[9] = { 8, 0, 8, 0, 8, 0, 8, 0, 8 };
    
18.     size_t count = 1;
    
19.     for( size_t i=8; i!=0; --i )
    
20.     {
    
21.         char cur = num[i];
    
22.         char pre = num[i-1];
    
23. 
    
24.         for( size_t j=0; j<4; ++j )
    
25.         {
    
26.             if( maps[pre][j] > cur )
    
27.             {
    
28.                 cur = maps[pre][j];
    
29.                 break;
    
30.             }
    
31.         }
    
32. 
    
33.         if( cur != num[i] )
    
34.         {
    
35.             num[i] = cur;
    
36.             for( ; i<8; ++i )
    
37.                 num[i+1] = maps[num[i]][0];
    
38.             ++count;
    
39. 
    
40.             for( size_t k=0; k<8; ++k )
    
41.                 printf( "%d", num[k+1] );
    
42.             printf( "\n" );
    
43.             
    
44.             i = 9;
    
45.             continue;
    
46.         }
    
47.     }
    
48. 
    
49.     printf( "%u\n", (unsigned)count );
    
50.     return 0;
    
51. }

复制代码

我还想用小白说的“动态规划”，不过，代码难写了点，算了