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

hisptoot

1. #!/usr/bin/env perl
   
2. my $num = 8;
   
3. my %map = (
   
4.                 1 => [2,4],
   
5.                 2 => [1,3,5],
   
6.                 3 => [2,6],
   
7.                 4 => [1,5,7],
   
8.                 5 => [2,4,6,8],
   
9.                 6 => [3,5,9],
   
10.                 7 => [4,8],
    
11.                 8 => [5,7,0,9],
    
12.                 9 => [6,8],
    
13.                 0 => [8]
    
14.           );
    
15. 
    
16. my %cal = ( );
    
17. 
    
18. foreach my $key (keys %map) {
    
19.         $cal{"$key"."2"} = $#{$map{$key}} + 1;
    
20. }
    
21. 
    
22. for(my $i = 3; $i<=$num; $i++)
    
23. {
    
24.         foreach my $key (keys %map) {
    
25.                 my $count = 0;
    
26.                 my $j = $i - 1;
    
27.                 foreach my $pos (@{$map{$key}}) {
    
28.                         $count += $cal{"$pos$j"};
    
29.                 }
    
30.                 $cal{"$key$i"} = $count;
    
31.         }
    
32. }
    
33. 
    
34. my $count = 0;
    
35. foreach(0..9)
    
36. {
    
37.         $count += $cal{"$_$num"};       
    
38. }
    
39. 
    
40. print $count;
    

复制代码

  14826

zhlong8

回复 11# hisptoot


    嗯，合并那里写错了

shang2010

回复 10# bruceteen


    给你前三位都是888  后面8位是上面的数字  每个数的相邻只有有限个数字

题目有点理解不对，三个8后面（第四位）可以是任何数字，不受“将步”限制；所以还请高手再来一下{:3_200:}

shang2010

回复 9# cjaizss


  issue close......

shang2010

我的解答是递归，
table[][]=
0=>8
1=>2,4
2=>135
...

//key当前[号码位]，n后面跟随[位数]
int foo(int key, int n)
{
if(n=0) return 1;//没有跟随位了，基本号码一个算一，
foreach v as table(key)
  sum =+ foo(v, n-1);
return sum;
}

===
echo foo(0,7) \
+(foo(1,7)+foo(4,7)+foo(7,7))x2 \
+ foo(2,7) +foo(5, 7) + foo(8,7);




==
考试环节貌似可以用伪代码的吧

shang2010

回复 5# hisptoot


    你这个情况不麻烦，加个全局变量回答你的问题

在foo中，当n=0， key=0时，全局变量计数



唯一可惜的是，做递归代码优化时，代码结构会更加复杂

bruceteen

shang2010 发表于 2013-03-14 12:52
回复 10# bruceteen
题目有点理解不对，三个8后面（第四位）可以是任何数字，不受“将步”限制；所以还请高手再来一下

我想想先。。。。。。。。。。。

shang2010

发现现在代码风格，c/php已经绞不清了

hisptoot

43038个是生成9位数字时候的情况

LZ的题目里面是生成8位数字

bruceteen

shang2010 发表于 2013-03-14 12:52
回复 10# bruceteen
题目有点理解不对，三个8后面（第四位）可以是任何数字，不受“将步”限制；所以还请高手再来一下

刚才弄错了，应该是将
printf( "%d\n", foo(8,0) );
改为
printf( "%d\n", foo(0,1)+foo(1,1)+foo(2,1)+foo(3,1)+foo(4,1)+foo(5,1)+foo(6,1)+foo(7,1)+foo(8,1)+foo(9,1) );
就行了，如果这样理解的话，结果输出是 14826