Posted on 2006-07-19 01:33
jimmyljb 閱讀(239)
評論(0) 編輯 收藏 所屬分類:
Algorithms
1.2) Lines in the plane.
??? What is the maximum number L, of regions defined by n lines in the plane?
??? L0 = 1
??? Ln = Ln-1 + n (n>0)
=>>?? Ln = n(n+1)/2 +1
Suppose that instead of straight lines we use bent lines, each containing one “zig!", such as "<"
??? Zn = L2n - 2n = 2n(2n+1)/2+1-2n = 2n^2-n+1 (n>=0)
1.3) THE JOSEPHUS PROBLEM
??? In our variation, we start with n people numbered 1 to n around a circle,and we eliminate every second remaining person until only one survives.
???
J(1) = 1 ;
??? J(2n) = 2J(n) - 1 , for n > 1;
??? J(2n + 1) = 2J(n) + 1
==>>J(2^m+l) = 2*l+1;
for binary number
??? J(ABCDEF) = 2*BCDEFA + 1 (A,B,C,D,E,F = 0,1)
??? J(1...1...) = 1...1... ? (A = 1)
習題有一個是漢諾塔的題目，說是A C B中不允許A和B之間交換，即只能to or from C。
這里得到一個簡單的遞歸就是A(n) = 3A(n-1)+2 (n >= 1)，理由是把n-1個塔從A經由C移到B，再把最底下的第n塊從A移動C，再把n-1塊從B經由C移到A，再把C中的第n塊從C移到B，最后把A的n-1塊從A移到B。