程序员面试题（所有语言）

本地人

我的理解是：

1st: x == 0 什么都不输出
2nd : x == 3  应该打印eek
3rd: x == 6 什么都不输出
4th: x == 9 应该打印eek

本地人

硬要抠细节的话，你比我少递归一次吧

这个问题关键在于细节。比你少递归一次不证明什么。我正好递归了100次。

[ 本帖最后由 本地人 于 2011-5-11 12:00 编辑 ]

xxmplus

恩。。。ok

虽然你是这么说，可是你的程序却不是这么工作的

[ 本帖最后由 xxmplus 于 2011-5-11 12:29 编辑 ]

本地人

你输出的结果一样。但我原来指的是%的结果（也许我那样说是不对，汉语不是我的母语）。

[ 本帖最后由 本地人 于 2011-5-11 12:41 编辑 ]

本地人

可是你的程序却不是这么工作的

我的好像就是那么工作的。有什么问题，请指教。

[ 本帖最后由 本地人 于 2011-5-11 12:41 编辑 ]

qinxialin1979

学习了，以后有什么编程问题就上这个板块来请教了

乱码

原帖由 atransformer 于 2011-5-11 09:54 发表
使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的 ...

同意，best practise都是在avoid recursion,主要弊端是在它的push/pop stack，优点是对很多logic，傻子也能写，只要掌握好什么情况下弹栈就好。

有的logic通过recursion写出来很优雅，典型的代表就是ms电话号码那个面试题。

stack不比heap，它虽然性能好，但属于稀缺资源，by default，每个thread会allocate 1MB.虽然它可以改，size随便定，但这么做的人很少。

push/pop stack的问题本身也很有争议，很多教你写code的畅销书提倡一个method就是单独的职能，不能跟其他职能相混，这在design的时候很好，但本身performance由于过多地push/pop stack一定受影响，不过可能大家不那么care而已。

回到正题，如果把recursion放在面试题中，我觉得更多地考点在考你是否对program runtime内存的分布比较清晰，倒不是别的。

xxmplus

这是你程序的输出，我顺便把x也打印出来了

6 eek
12 eek
18 eek
24 eek
30 eek
36 eek
39 eep
42 eek
48 eek
54 eek
60 eek
66 eek
72 eek
78 eek
78 eep
84 eek
90 eek
96 eek
102 eek
102 yikes
108 eek
114 eek
117 eep
120 eek
126 eek
132 eek
138 eek
144 eek
150 eek
156 eek
156 eep
162 eek
168 eek
174 eek
180 eek
186 eek
192 eek
195 eep
198 eek
204 eek
210 eek
216 eek
222 eek
228 eek
234 eek
234 eep
240 eek
246 eek
252 eek
258 eek
264 eek
270 eek
273 eep
276 eek
282 eek
288 eek
294 eek
300 eek

本地人

你忘了，我是先加3的，所以你上面打印6 eek，进function时x是3.

试试这个就会明白：

1. #include <iostream>
   
2. 
   
3. using std::cout;
   
4. using std::endl;
   
5. 
   
6. const int INCREMENT = 3;
   
7. const int EEK_ITERATION = 2 * INCREMENT;
   
8. const int EEP_ITERATION = 13 * INCREMENT;
   
9. const int YIKES_ITERATION = (EEK_ITERATION * 17);
   
10. const int MAX_LOOP = (100 * INCREMENT);
    
11. 
    
12. void theLoop( int x, int count )
    
13. {
    
14.     cout << count << endl;
    
15.     x += INCREMENT;
    
16. 
    
17.     if ( x % EEK_ITERATION == 0 )
    
18.     {
    
19.         cout << "  eek" << endl;
    
20.     }
    
21. 
    
22.     if ( x % EEP_ITERATION == 0 )
    
23.     {
    
24.         cout << "  eep" << endl;
    
25.     }
    
26. 
    
27.     if ( x == YIKES_ITERATION )
    
28.     {
    
29.         cout << "  yikes" << endl;
    
30.     }
    
31. 
    
32.     if ( x < MAX_LOOP )
    
33.     {
    
34.         theLoop( x, count + 1 );
    
35.     }
    
36. }
    
37. 
    
38. int main()
    
39. {
    
40.     theLoop( 0, 1 );
    
41.     return 0;
    
42. }

复制代码

[ 本帖最后由 本地人 于 2011-5-11 13:03 编辑 ]

本地人

把recursion放在面试题中，我觉得更多地考点在考你是否对program runtime内存的分布比较清晰

我把recursion放在面试题中，就是为了看懂不懂recursion

xxmplus

无论你进函数的时候给的是什么参数，在if判断的时候，x的值已经变了，所以我才说你的程序实际上并不是按照你说的方式工作的。

如果按照你上面的逻辑，我的程序也完全可以这样啊
#!/bin/python3

def loopme(x, n, step):
    if x <= step*n:
        if x % (step*2) == 0 and x >= (step*2): print(x-step, 'eek')
        if x % (step*13) == 0 and x >= (step*13): print(x-step, 'eep')
        if x % (step*17*2) == 0 and x // (step*17*2) == 1: print(x-step, 'yikes')
        loopme(x+step, n, step)
if __name__ == '__main__':
    loopme(0, 100, 3)

dalaohu

Is the recursive version usually faster?
No — it’s usually slower (due to the overhead of maintaining the stack)

Does the recursive version usually use less memory?
No — it usually uses more memory (for the stack).

Then why use recursion??
It makes the code beautiful – recursion is a beauty of programming. Sometimes it is much simpler to write the recursive version.

Recursion 更慢，更占资源。 连唯一的优点我也不认同，我认为 readibility 很差。 Recursive 没call一次就占用一个stack， 最终会Stack overflow.
Recursion 的代码一定会少一点，有些人称他为优雅。

dalaohu

记得以前那个语言里有个goto line #, 好像是basic吧。 太牛逼了，更recursion 有异曲同工。

line 1.  goto line 10

line 10. goto line 1

本地人

我的程序也完全可以这样啊

不一样。关键不在于x在if里的值， 而是在于进function进了几次、在第几次打印什么。

你对比一下我上面修改的程序的输出和下面修改的程序的输出：

1. #!/bin/python3
   
2. def loopme(x, n, step, count):
   
3.     print( count )
   
4.     if x <= step*n:
   
5.         if x % (step*2) == 0 and x >= (step*2): print(' eek')
   
6.         if x % (step*13) == 0 and x >= (step*13): print(' eep')
   
7.         if x % (step*17*2) == 0 and x // (step*17*2) == 1: print(' yikes')
   
8.         loopme(x+step, n, step, count + 1)
   
9. 
   
10. if __name__ == '__main__':
    
11.     loopme(0, 100, 3, 1)

复制代码

xxmplus

你是对的。虽然我的程序结果看起来一样，但是的确是错了，没有按照题意在规定的loop里打印字符串。

不过你的解释我也不满意，按照题意，31楼的解释肯定不对。

x初始值为0，第一个loop时应为3，第二个loop时应为6。严格来说，
cout << count << endl;
x += INCREMENT;

这两句对调一下才对。

本地人

不过你的解释我也不满意，按照题意，31楼的解释肯定不对

是的，31楼写得不清楚。我的汉语水平有限，有时表达不出我想说的意思。

cout << count << endl;
x += INCREMENT;
这两句对调一下才对。

9楼的程序没有cout << count << endl;这行。

乱码

原帖由 dalaohu 于 2011-5-11 14:20 发表
Recursive 没call一次就占用一个stack

用recursion的caller/callee都在一个stack，stackoverflow不过是这个stack的1M空间(by default)不够了。

不是在用不同的stack.

dalaohu

debugger 里看，每call一次，就是一个新的stack了。

本地人

是个新的stack frame，但还是同一个stack.

乱码

原帖由 dalaohu 于 2011-5-11 17:40 发表
debugger 里看，每call一次，就是一个新的stack了。

stack跟一个thread allocation的，每个thread只有一个stack,多个thread共享一个heap.

MaxChan

recursion里有一种叫tail recursion，但凡tail recursion的代码都可以被optimization成非recursion的，现在的编译器在编译时基本都把tail recursion编译成非recursion版本，因此，关于堆栈溢出的问题其实不用多考虑，只要把recursion尽量写成tail recursion就是了。如果可以选的话，我其实更喜欢recursion版本的代码，确实优雅。

porcorosso

我错过了。。。

porcorosso

一般做N-deep Menu Generator 就需要Recursion，跑不了的

Anihc

当初在看这个贴时，根本没有想到本地人是个纯鬼佬，直到看到那个征婚贴。。。(monkey1)

minami

我也是看了那个征婚帖子才来看这个帖子的。

dalaohu

http://www.oursteps.com.au/bbs/viewthread.php?tid=369965

太牛X 了吧！ pfpf啊。

非诚勿扰 在悉尼开专场，赶紧去报名啊。
http://www.aohua.com.au/bbs/thread-109235-1-1.html

GL GL

frankren

基本所有人看到这就都转到征婚帖去了，没人回来了……

交易人生

本地人的代码公正、逻辑清晰、可读性强，c++高手。

porcorosso

我的php版

1. <?function recurse($x=0,$loop=1)
   
2. {
   
3.         echo "Loop $loop X $x";
   
4.         if($loop%2 == 0) echo " eek";
   
5.         if($loop%13 == 0) echo " eep";
   
6.         if($loop%(2*17) == 0) echo " yikes";
   
7.         echo PHP_EOL;       
   
8.         $x += 3;       
   
9.        
   
10.         if($loop<100) recurse($x,++$loop);
    
11. }
    
12. recurse();?>

复制代码

Output:

1. Loop 1 X 0
   
2. Loop 2 X 3 eek
   
3. Loop 3 X 6
   
4. Loop 4 X 9 eek
   
5. Loop 5 X 12
   
6. Loop 6 X 15 eek
   
7. Loop 7 X 18
   
8. Loop 8 X 21 eek
   
9. Loop 9 X 24
   
10. Loop 10 X 27 eek
    
11. Loop 11 X 30
    
12. Loop 12 X 33 eek
    
13. Loop 13 X 36 eep
    
14. Loop 14 X 39 eek
    
15. Loop 15 X 42
    
16. Loop 16 X 45 eek
    
17. Loop 17 X 48
    
18. Loop 18 X 51 eek
    
19. Loop 19 X 54
    
20. Loop 20 X 57 eek
    
21. Loop 21 X 60
    
22. Loop 22 X 63 eek
    
23. Loop 23 X 66
    
24. Loop 24 X 69 eek
    
25. Loop 25 X 72
    
26. Loop 26 X 75 eek eep
    
27. Loop 27 X 78
    
28. Loop 28 X 81 eek
    
29. Loop 29 X 84
    
30. Loop 30 X 87 eek
    
31. Loop 31 X 90
    
32. Loop 32 X 93 eek
    
33. Loop 33 X 96
    
34. Loop 34 X 99 eek yikes
    
35. Loop 35 X 102
    
36. Loop 36 X 105 eek
    
37. Loop 37 X 108
    
38. Loop 38 X 111 eek
    
39. Loop 39 X 114 eep
    
40. Loop 40 X 117 eek
    
41. Loop 41 X 120
    
42. Loop 42 X 123 eek
    
43. Loop 43 X 126
    
44. Loop 44 X 129 eek
    
45. Loop 45 X 132
    
46. Loop 46 X 135 eek
    
47. Loop 47 X 138
    
48. Loop 48 X 141 eek
    
49. Loop 49 X 144
    
50. Loop 50 X 147 eek
    
51. Loop 51 X 150
    
52. Loop 52 X 153 eek eep
    
53. Loop 53 X 156
    
54. Loop 54 X 159 eek
    
55. Loop 55 X 162
    
56. Loop 56 X 165 eek
    
57. Loop 57 X 168
    
58. Loop 58 X 171 eek
    
59. Loop 59 X 174
    
60. Loop 60 X 177 eek
    
61. Loop 61 X 180
    
62. Loop 62 X 183 eek
    
63. Loop 63 X 186
    
64. Loop 64 X 189 eek
    
65. Loop 65 X 192 eep
    
66. Loop 66 X 195 eek
    
67. Loop 67 X 198
    
68. Loop 68 X 201 eek yikes
    
69. Loop 69 X 204
    
70. Loop 70 X 207 eek
    
71. Loop 71 X 210
    
72. Loop 72 X 213 eek
    
73. Loop 73 X 216
    
74. Loop 74 X 219 eek
    
75. Loop 75 X 222
    
76. Loop 76 X 225 eek
    
77. Loop 77 X 228
    
78. Loop 78 X 231 eek eep
    
79. Loop 79 X 234
    
80. Loop 80 X 237 eek
    
81. Loop 81 X 240
    
82. Loop 82 X 243 eek
    
83. Loop 83 X 246
    
84. Loop 84 X 249 eek
    
85. Loop 85 X 252
    
86. Loop 86 X 255 eek
    
87. Loop 87 X 258
    
88. Loop 88 X 261 eek
    
89. Loop 89 X 264
    
90. Loop 90 X 267 eek
    
91. Loop 91 X 270 eep
    
92. Loop 92 X 273 eek
    
93. Loop 93 X 276
    
94. Loop 94 X 279 eek
    
95. Loop 95 X 282
    
96. Loop 96 X 285 eek
    
97. Loop 97 X 288
    
98. Loop 98 X 291 eek
    
99. Loop 99 X 294
    
100. Loop 100 X 297 eek

复制代码

对吗？

[ 本帖最后由 porcorosso 于 2011-7-12 10:43 编辑 ]

菜地一块

呵呵，刚看到kr2000的帖子，思考了一下（顺便也到“本地人”那个征婚帖子里发了个找工作帖子，哈哈哈），我也来试试：
我是这样考虑的，这里的难点主要是要知道当前是第几个LOOP，以便好按照要求打印出那几个串。
因此我引入一个loop变量，代表被调用的轮数。

C/C++:
void f()
{
        static int loop = 1; //loop count
        static int x = 0;
        if ( loop % 2 == 0 )                cout << "eek" << endl;
        if ( loop % 13 == 0 )                cout << "eep" << endl;
        if ( loop == 34 )                cout << "yikes" << endl;
        x += 3;
        if ( loop == 100 )                return;
        loop++;
        f();
}