Tower of Hanoi

Tower of Hanoi
The Tower of Hanoi puzzle was invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks (initially four in the applet below), initially stacked in increasing size on one of three pegs. The objective is to transfer the entire tower to one of the other pegs (the rightmost one in the applet below), moving only one disk at a time and never a larger one onto a smaller.

The puzzle is well known to students of Computer Science since it appears in virtually any introductory text on data structures or algorithms. Its solution touches on two important topics discussed later on:

* recursive functions and stacks
* recurrence relations

def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print a, '->', c
        hanoi(n-1, b, a, c)

for n in (2, 3, 5):
        print 'hanoi:', n
        hanoi(n, 'a', 'b', 'c')

hanoi: 2
a -> b
a -> c
b -> c
hanoi: 3
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
hanoi: 5
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
a -> b
c -> b
c -> a
b -> a
c -> b
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
b -> a
c -> b
c -> a
b -> a
b -> c
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

野人传教士问题

问题描述：
从前有一条河，河的左岸有m个传教士(Missionary)和m个野人(Cannibal)，和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。

在我的实现中设定了n＝2。

def ferry(s, p, q):
    global _his, _t
    _t = []
    _his = [ (p, s[0], s[1]) ]
    _ferry(p, s[0], s[1], q, 0, 0)

def _ferry(p, a, b, q, x, y):
    if len(_his) % 2 == 0 and x == y == 0:
        _prt()
        return
    for m, n in _comp(a, b):
        if _push_f(m, n, p, a-m, b-n, q, x+m, y+n):
            _ferry(q, x+m, y+n, p, a-m, b-n)
            _pop_f()

def _push_f(m, n, p, a, b, q, x, y):
    if 0 < a < b or 0 < x < y or (q, x, y) in _his:
        return False
    _his.append( (q, x, y) )
    _t.append( (m, n) )
    return True

def _pop_f():
    _his.pop()
    _t.pop()

def _comp(m, n):
    i = 0
    while i <= m and i <= 2:
        j = 0
        while j <= n and j <= 2:
            if 0 < i + j <= 2:
                yield i, j
            j += 1
        i += 1

def _prt():
    u, v = '--(%d,%d)->', '<-(%d,%d)--'
    for x, y in _t:
        print u % (x, y)
        u, v = v, u
    print '--------------------done', _his[0]

for x in (2,2), (3,3), (4,4):
    ferry( x, 'east', 'west' )

--(0,2)->
<-(0,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 2, 2)
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 2, 2)
--(1,1)->
<-(1,0)--
--(2,0)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 2, 2)
--(1,1)->
<-(1,0)--
--(2,0)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 2, 2)
--(0,2)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 3, 3)
--(0,2)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 3, 3)
--(1,1)->
<-(1,0)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(0,1)--
--(0,2)->
--------------------done ('east', 3, 3)
--(1,1)->
<-(1,0)--
--(0,2)->
<-(0,1)--
--(2,0)->
<-(1,1)--
--(2,0)->
<-(0,1)--
--(0,2)->
<-(1,0)--
--(1,1)->
--------------------done ('east', 3, 3)

任意自然数分解为连续自然数和问题

http://blog.csdn.net/justrun2005/archive/2006/10/13/1332539.aspx

def f(x):
   n = 1
   while x > 0:
       if x % n == 0:
           yield n, x / n
       x -= n
       n += 1

for x in 133350, 1000000, 0xffffffff:
    print x, '--------------------'
    for n, v in f(x):
        print n, v, '+ ...'

133350 --------------------
1 133350 + ...
3 44449 + ...
4 33336 + ...
5 26668 + ...
7 19047 + ...
12 11107 + ...
15 8883 + ...
20 6658 + ...
21 6340 + ...
25 5322 + ...
28 4749 + ...
35 3793 + ...
60 2193 + ...
75 1741 + ...
84 1546 + ...
100 1284 + ...
105 1218 + ...
127 987 + ...
140 883 + ...
175 675 + ...
300 295 + ...
381 160 + ...
420 108 + ...
508 9 + ...
1000000 --------------------
1 1000000 + ...
5 199998 + ...
25 39988 + ...
125 7938 + ...
128 7749 + ...
625 1288 + ...
640 1243 + ...
4294967295 --------------------
1 4294967295 + ...
2 2147483647 + ...
3 1431655764 + ...
5 858993457 + ...
6 715827880 + ...
10 429496725 + ...
15 286331146 + ...
17 252645127 + ...
30 143165562 + ...
34 126322551 + ...
51 84215020 + ...
85 50528985 + ...
102 42107472 + ...
170 25264429 + ...
255 16842882 + ...
257 16711807 + ...
510 8421250 + ...
514 8355711 + ...
771 5570260 + ...
1285 3341745 + ...
1542 2784552 + ...
2570 1669909 + ...
3855 1112202 + ...
4369 980871 + ...
7710 553210 + ...
8738 487159 + ...
13107 321132 + ...
21845 185689 + ...
26214 150736 + ...
43690 76461 + ...
65535 32770 + ...
65537 32767 + ...

一道网易笔试题

http://blog.csdn.net/chinainvent/archive/2006/10/13/1332494.aspx

如图：

　

设“1”的坐标为（0，0） “7”的坐标为（－1，－1） 编写一个小程序，使程序做到输入坐标（X,Y）之后显示出相应的数字。

#! /usr/bin/env python
def f(x, y):
    w = max(abs(x), abs(y))
    x += w
    y += w
    w *= 2

    if y == 0:
        s = w * 3 + x
    elif x == 0:
        s = w * 2 + (w - y)
    elif y == w:
        s = w + (w - x)
    else:
        s = y
    return s + (w - 1) ** 2

for x, y in [(0,0), (0,1), (1,2), (-1,-2), (8, 9)]:
    print (x, y), f(x, y)

###################

将问题转化为求一个内部正方形中包含的点的个数与外部正方形的边上的点的个数.
设外部正方形的边长为U(=代码中w*2+1), 则内部正方形内包含的点数为: (U-2)^2，外部正方形边上的点个数求法为代码中的s。

简单解释一下代码：

w = max(abs(x),abs(y));
x += w;
y += w;
w *= 2;

///上面这几句做了坐标变换，便于随后的算术运算。

if (y == 0)
s = 3*w + x;
else if (x == 0)
s = 2*w + (w - y);
else if (y == w)
s = w + (w - x);
else
s = y;

///上面这几句求外部边上的点个数s。

return s + (w-1) ** 2;

///答案为s + 内部正方形内点的个数。