渥太华IT面试编程试题 (中级)

[旭日阳刚]

这是n=1 to 50 的结果

1
1
1
1
2
2
2
2
2
4
4
4
4
4
6
6
6
6
6
9
9
9
9
9
13
13
13
13
13
18
18
18
18
18
24
24
24
24
24
31
31
31
31
31
39
39
39
39
39
49

 

[山阳手]

刚发现cfc过滤了我代码里头的不少关键字啊

安全考虑吧。试试把 i f r a m e 五个字母连着敲进去。。。 老大因为有一次俺这样贪玩把俺的一个新爱地给封了。。。

 

[hcloud]

int scaleCalc(int n, boolean done[nMax])
{
  if(n < 0 || done[n])return 0;
  if(n == 0)return 1;
  done[n] = true;

  return scaleCalc(n-1, done) + scaleCalc(n-5, done) + scaleCalc(n-10, done)+ scaleCalc(n-25, done);
}

代码不太对， 但就这个algorithm， 懒得写了…… bool[] 一定会被人耻笑的………………

 

[旭日阳刚]

应该是i<=0 return 0
i==1 return 1

int scaleCalc(int n, boolean done[nMax])
{
  if(n < 0 || done[n])return 0;
  if(n == 0)return 1;
  done[n] = true;

  return scaleCalc(n-1, done) + scaleCalc(n-5, done) + scaleCalc(n-10, done)+ scaleCalc(n-25, done);
}

代码不太对， 但就这个algorithm， 懒得写了…… bool[] 一定会被人耻笑的………………

 

[hcloud]

应该是i<=0 return 0
i==1 return 1

不是啊 ==0就是正好凑足
<0 等于凑不上

不过其实运行起来是一样的， ==1到==4结果应该都一样。
但是得<0才return 0

 

[旭日阳刚]

我是从结果来推的，可能我理解错了你的递归算法？
如果n=1，结果应该是1
不是零。

不是啊 ==0就是正好凑足
<0 等于凑不上

 

[苦逼热狗]

手算了一下，我那个应该是错误的。

 

[hcloud]

我是从结果来推的，可能我理解错了你的递归算法？
如果n=1，结果应该是1
不是零。

如果n=1， 继续递归=) 还是return 1
n=1..4都是一样。 你说得没错。
只不过必须n<0才return 0

怎么说呢，如果按照最节省，应该是
n<0 return 0
n<=4 return 1
不过为了直观不这么写吧。

 

[旭日阳刚]

不好意思。等过一段时间，闲下来了，再把C/C++捡起来。

如果n=1， 继续递归=) 还是return 1
n=1..4都是一样。 你说得没错。
只不过必须n<0才return 0

 

[hcloud]

来搞个look-up table! =)

 

[闲得慌]

这是n=1 to 50 的结果

1
1
1
1
2
2
2
2
2
4
4
4
4
4
6
6
6
6
6
9
9
9
9
9
13
13
13
13
13
18
18
18
18
18
24
24
24
24
24
31
31
31
31
31
39
39
39
39
39
49

这个结果跟我的结果一样

 

[旭日阳刚]

算法一样吗？也是4个循环？有更快的算法吗？
除了递归。

这个结果跟我的结果一样

 

[闲得慌]

算法一样吗？也是4个循环？有更快的算法吗？
除了递归。

我用递归：

public class CoinMain {
    public static void main(String[] args) {
        int n = 102;  // total money in cents
        try {
            for (int i = 0; i < n; i++) {
                System.out.println("scaling " + i + " :   " + unitScalingCalculator(i, 25));
            }
        }
        catch(Throwable e) {
            e.printStackTrace();
        }
    }
    
    public static int unitScalingCalculator(int n, int token) {
        int next_token = 0;
        switch (token) {
            case 25: 
                next_token = 10;
                break;
            case 10: 
                next_token = 5;
                break;
            case 5: 
                next_token = 1;
                break;
            case 1: 
                return 1;
        }
        
        int totalWays = 0;
        for (int i = 0; i * token <= n; i++) {
            totalWays += unitScalingCalculator(n - i * token, next_token);
        }
        return totalWays;
    }
}

 

[闲得慌]

scaling 0 :   1
scaling 1 :   1
scaling 2 :   1
scaling 3 :   1
scaling 4 :   1
scaling 5 :   2
scaling 6 :   2
scaling 7 :   2
scaling 8 :   2
scaling 9 :   2
scaling 10 :   4
scaling 11 :   4
scaling 12 :   4
scaling 13 :   4
scaling 14 :   4
scaling 15 :   6
scaling 16 :   6
scaling 17 :   6
scaling 18 :   6
scaling 19 :   6
scaling 20 :   9
scaling 21 :   9
scaling 22 :   9
scaling 23 :   9
scaling 24 :   9
scaling 25 :   13
scaling 26 :   13
scaling 27 :   13
scaling 28 :   13
scaling 29 :   13
scaling 30 :   18
scaling 31 :   18
scaling 32 :   18
scaling 33 :   18
scaling 34 :   18
scaling 35 :   24
scaling 36 :   24
scaling 37 :   24
scaling 38 :   24
scaling 39 :   24
scaling 40 :   31
scaling 41 :   31
scaling 42 :   31
scaling 43 :   31
scaling 44 :   31
scaling 45 :   39
scaling 46 :   39
scaling 47 :   39
scaling 48 :   39
scaling 49 :   39
scaling 50 :   49
scaling 51 :   49
scaling 52 :   49
scaling 53 :   49
scaling 54 :   49
scaling 55 :   60
scaling 56 :   60
scaling 57 :   60
scaling 58 :   60
scaling 59 :   60
scaling 60 :   73
scaling 61 :   73
scaling 62 :   73
scaling 63 :   73
scaling 64 :   73
scaling 65 :   87
scaling 66 :   87
scaling 67 :   87
scaling 68 :   87
scaling 69 :   87
scaling 70 :   103
scaling 71 :   103
scaling 72 :   103
scaling 73 :   103
scaling 74 :   103
scaling 75 :   121
scaling 76 :   121
scaling 77 :   121
scaling 78 :   121
scaling 79 :   121
scaling 80 :   141
scaling 81 :   141
scaling 82 :   141
scaling 83 :   141
scaling 84 :   141
scaling 85 :   163
scaling 86 :   163
scaling 87 :   163
scaling 88 :   163
scaling 89 :   163
scaling 90 :   187
scaling 91 :   187
scaling 92 :   187
scaling 93 :   187
scaling 94 :   187
scaling 95 :   213
scaling 96 :   213
scaling 97 :   213
scaling 98 :   213
scaling 99 :   213
scaling 100 :   242
scaling 101 :   242

 

[旭日阳刚]

估计递归的时间效率高的多。
用4个循环，到后来得到结果要浪费掉97%以上的循环。

0.5
0.6666666667
0.75
0.8
0.7142857143
0.7777777778
0.8181818182
0.8461538462
0.8666666667
0.7894736842
0.8333333333
0.8666666667
0.8888888889
0.9047619048
0.88
0.8965517241
0.9090909091
0.9189189189
0.9268292683
0.9032258065
0.9142857143
0.9237288136
0.9318181818
0.9387755102
0.921686747
0.9304812834
0.9383886256
0.9453781513
0.9514925373
0.9411764706
0.9484240688
0.9545454545
0.9596412556
0.9638554217
0.9569892473
0.9612903226
0.9649122807
0.9679144385
0.9704433498
0.9650112867
0.9677754678
0.9701923077
0.9723214286
0.9742096506
0.9698608964
0.9719020173
0.9737196765
0.9753476612
0.9768133175
0.9727019499