求查autocheck VIN：3VWCK31C35M413775# Automobile - 车轮上的传奇
h*2
1 楼
先是写pow(x, n)
recursive和iterative哗哗哗写完了
面试官来了个，
What is the minimum number of multiplications for calculating pow(x, n)?
然后给我举了个例子，要算x^45
iterative的方法是
x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32
然后把x, x^4, x^8, x^32 乘起来
总共需要5 + 3 = 8次乘法
recursive的方法是
x^45 = x^22 * x^22 * x
x^22 = x^11 * x^11
x^11 = x^5 * x^5 * x
x^5 = x^2 * x^2 * x
x^2 = x * x
这样也是需要8次乘法
但是有更好的办法是
x --> x^2 --> x^4 --> x^8
x * x^8 = x^9
x^9 --> x^18 --> x^36
x^9 * x^36 = x^45
这样只需要3 + 1 + 2 + 1 = 7次乘法
然后我就傻了。
查了下，这个问题还蛮出名：
https://en.wikipedia.org/wiki/Addition-chain_exponentiation
不过也太超出45分钟面试的范畴了吧……
虽然整个过程还挺和谐，走的时候人家还说了句最后那题是bonus, 心里还是惴惴不安
recursive和iterative哗哗哗写完了
面试官来了个，
What is the minimum number of multiplications for calculating pow(x, n)?
然后给我举了个例子，要算x^45
iterative的方法是
x --> x^2 --> x^4 --> x^8 --> x^16 --> x^32
然后把x, x^4, x^8, x^32 乘起来
总共需要5 + 3 = 8次乘法
recursive的方法是
x^45 = x^22 * x^22 * x
x^22 = x^11 * x^11
x^11 = x^5 * x^5 * x
x^5 = x^2 * x^2 * x
x^2 = x * x
这样也是需要8次乘法
但是有更好的办法是
x --> x^2 --> x^4 --> x^8
x * x^8 = x^9
x^9 --> x^18 --> x^36
x^9 * x^36 = x^45
这样只需要3 + 1 + 2 + 1 = 7次乘法
然后我就傻了。
查了下，这个问题还蛮出名：
https://en.wikipedia.org/wiki/Addition-chain_exponentiation
不过也太超出45分钟面试的范畴了吧……
虽然整个过程还挺和谐，走的时候人家还说了句最后那题是bonus, 心里还是惴惴不安