posts - 2, comments - 0, trackbacks - 0, articles - 0

concrete mathematics(1)

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

只有注册用户登录后才能发表评论。


网站导航: