Posted on 2006-07-19 01:33
jimmyljb 阅读(231)
评论(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。