1樓：
上面的答案時間複雜度是最優的，但空間不是。要麼顯式存了x^i, 要麼用了遞迴(非尾遞迴)額外消耗了O(lgn)的棧空間。
intfast_exp
(intx,
intn
)else
}returnr;
}迴圈不變數
時間O(lg n), 空間O(1)
2樓：
defexp(x,
n):ifn
==0:return1if
n%2==
0:return
exp(x*
x,n//
2)else
:returnx*
exp(x,
n-1)
#時間複雜度O(logn) 遞迴深度O(logn)..還是非遞迴好=_3
3樓：zxoba
(define
(power
base
exp)
(cond
((=exp0)1
)((= exp1)
base)((
even?
exp)
(square
(power
base(/
exp2
))))
(else (*
base
(power
base(-
exp1
))))))
;;; 感覺和頂樓說的轉成二進位制也沒打的區別？
如果把乙個數m拆成n個數a1，a2，a3 an之和，使它們相乘達到最大，該怎麼拆？
陳浩 第乙個問題，動態規劃 public int IntegerBreak int nint cache new int n 1cache 1 1for int i 2 i n ifor int j 1 j i 2 jcache i Math.Max cache i cache j cache i ...
N個數進行排列,每乙個數都不待在原來位置的情況，有多少種？
1 若第2個數的位置 且 則此時共有 種情況 因為它等價於將位置1當作第2個數原來的位置，則此時相當於對N 1個數的排列，使其不再原來的位置 2 若第2個數的位置 則此時只需要保證剩下的 個數都不在原來的位置，共有 種可能。因此有 其中 2 eeimg 1 結合初始條件 即可得到 2 eeimg 1...
從1到N中隨機抽取乙個數（N為上限，不被抽取）作為新的上限繼續抽取，直到上限為1。求總抽取次數的期望？
可以直接解通項，先佔一坑。爪機打公式不方便望見諒。題主已經得出了 E n E 1 E 2 E 3 E n 1 n 1 這樣的遞推關係，分母是 n 還是 n 1 不再深究。令 S 為 E 的字首和，即 S n E 1E n 即可得S n S n 1 S n 1 n 1S n S n 1 n 1 n 1...