马踏棋盘

马踏棋盘问题，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。

#include <tr1/tuple>
#include <cstdio>

template <int width, int height>
struct chess
{
    static const int x_[8];
    static const int y_[8];

    int nodelinks_[width * height];
    int cat(int x, int y) const { return nodelinks_[x + width * y]; }
    int& at(int x, int y) { return nodelinks_[x + width * y]; }

    chess();

    void go(int x, int y)
    {
        for (int i = 0; i < 8; ++i)
        {
            int a = x + x_[i], b = y + y_[i];
            if (a >= 0 && b >= 0 && a < width && b < height && cat(a,b) > 0)
                at(a,b) -= 1;
        }
        static int number = 0;
        at(x,y) = --number;
    }

    std::pair<int, int> next(int x, int y) const
    {
        int j = 0;
        for (int i = 0, v = 8; i < 8; ++i)
        {
            int a = x + x_[i], b = y + y_[i];
            if (a >= 0 && b >= 0 && a < width && b < height)
                if (cat(a,b) > 0 && cat(a,b) < v)
                    j = i, v = cat(a,b);
        }
        return std::make_pair(x + x_[j], y + y_[j]);
    }

    void print() const
    {
        for (int x = 0; x < width; ++x)
        {
            for (int y = 0; y < height; ++y)
                printf("%3d ", cat(x,y));
            puts("");
        }
    }
};

template <int width, int height>
chess<width, height>::chess()
{
    const int X = width - 1;
    const int Y = height - 1;
    for (int x = 2; x < width-2; ++x)
        for (int y = 2; y < height-2; ++y)
            at(x,y) = 8;
    for (int x = 2; x < width-2; ++x)
    {
        at(x,1) = at(x,Y-1) = 6;
        at(x,0) = at(x,Y) = 4;
    }
    for (int y = 2; y < height-2; ++y)
    {
        at(1,y) = at(X-1,y) = 6;
        at(0,y) = at(X,y) = 4;
    }
    at(0,0) = at(X,0) = at(0,Y) = at(X,Y)= 2;
    at(1,1) = at(X-1,1) = at(1,Y-1) = at(X-1,Y-1)= 4;
    at(0,1) = at(0,Y-1) = at(1,0) = at(X-1,0) = at(X,1) = at(X,Y-1) = at(X-1,Y) = at(1,Y) = 3;
}

template <int width, int height> const int chess<width, height>::x_[] = { -1, -1,  1, 1, -2, -2,  2, 2 };
template <int width, int height> const int chess<width, height>::y_[] = { -2,  2, -2, 2, -1,  1, -1, 1 };


////
namespace tr1 = std::tr1;

int main(int argc, char* argv[])
{
    chess<8, 8> tab;
    int x = 0, y = 0;
    tab.go(x, y);
    for (int i = 1; i < 64; ++i)
    {
        tr1::tie(x, y) = tab.next(x, y);
        tab.go(x, y);
    }
    tab.print();
}



#if 0
 -1 -16 -59 -34  -3 -18 -21 -36 
-58 -33  -2 -17 -60 -35  -4 -19 
-15 -54 -57 -62 -43 -20 -37 -22 
-32 -63 -46 -53 -56 -61 -42  -5 
-49 -14 -55   0 -47 -44 -23 -38 
-28 -31 -48 -45 -52 -41  -6  -9 
-13 -50 -29 -26 -11  -8 -39 -24 
-30 -27 -12 -51 -40 -25 -10  -7 


  0   1   2   3   4   5   6   7
0 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
1 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
2 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
3 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
4 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
5 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
6 +---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
7 +---+---+---+---+---+---+---+

      @---+---@
      |   |   |
  @---+---+---+---@
  |   |   |   |   |
  +---+---@---+---+
  |   |   |   |   |
  @---+---+---+---@
      |   |   |
      @---+---@
#endif

combination

#include <boost/range.hpp>
#include <vector>

template <typename t, typename op_t>
struct combination : private op_t, boost::noncopyable
{
    std::vector<t> res_;
    combination(int n, op_t op) : op_t(op), res_(n) {}
    template <typename iterator> void com(iterator begin, iterator end, int n);
};

template <typename t, typename op_t>
template <typename iterator>
void combination<t, op_t>::com(iterator begin, iterator end, int n)
{
    if (n == 1)
    {
        for ( ; begin != end; ++begin)
        {
            res_.back() = *begin;
            this->operator()(boost::begin(res_), boost::end(res_));
        }
        return;
    }

    while (begin + n < end)
    {
        res_[res_.size()-n] = *begin;
        this->com(++begin, end, n-1);
    }

    for ( ; begin != end; ++begin, --n)
        res_[res_.size()-n] = *begin;
    this->operator()(boost::begin(res_), boost::end(res_));
}

template <typename rng_t, typename op_t>
inline void combine(rng_t& r, int n, op_t op)
{
    typedef typename boost::range_value<rng_t>::type type;
    combination<type, op_t>(n, op).com(boost::begin(r), boost::end(r), n);
}


#include <algorithm>
#include <iostream>

struct Print
{
    template <typename iterator>
    void operator()(iterator begin, iterator end) const
    {
        typedef typename std::iterator_traits<iterator>::value_type type;
        std::vector<type> buf(begin, end);
        do
        {
            std::copy(buf.begin(), buf.end(), std::ostream_iterator<type>(std::cout));
            std::cout << " ";
        } while (std::next_permutation(buf.begin(), buf.end()));
        std::cout << std::endl;
    }
};

int
main(int argc, char* const argv[])
{
    char s[] = "12345";
    combine(s, 3, Print());
}


#if 0
123 132 213 231 312 321 
124 142 214 241 412 421 
125 152 215 251 512 521 
134 143 314 341 413 431 
135 153 315 351 513 531 
145 154 415 451 514 541 
234 243 324 342 423 432 
235 253 325 352 523 532 
245 254 425 452 524 542 
345 354 435 453 534 543 
#endif

8 queens

在8×8的国际象棋棋盘上放置8个皇后，要求任意两个皇后不能在同一行、同一列或同一条对角线上。

#include <cstdio>
#include <cstdlib>

void print(int cols[], int N);

inline bool is_safe(int cols[], int y)
{
        for (int i = 0; i < y; ++i)
                if (cols[i] == cols[y] || abs(cols[i] - cols[y]) == y - i)
                        return false;
        return true;
}

void queens(int cols[], int n, int N)
{
        if (n == N)
                return print(cols, N);
        for (int i = 0; i < N; ++i)
        {
                cols[n] = i;
                if (is_safe(cols, n))
                        queens(cols, n+1, N);
        }
}

int main()
{
        int cols[8] = { 0 };
        queens(cols, 0, sizeof(cols) / sizeof(int));
}

inline void prtn(const char* s, int n, const char* t = "")
{
        for (int i = 0; i < n; ++i)
                printf(s);
        printf(t);
}

void print(int cols[], int N)
{
        for (int y = 0; y < N; ++y)
                prtn("+---", N, "+\n"),
                prtn("|   ", cols[y], "| Q "), prtn("|   ", N-cols[y]-1, "|\n");
        prtn("+---", N, "+\n\n");
}

+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | Q |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+

约瑟夫问题

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再重新报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的序号。

#include <cstdio>
#include <cstdlib>

inline int next(unsigned int x, int m, int vec[], int n)
{
    do
        while (vec[x % n])
            ++x;
    while (--m && ++x);
    return x % n;
}

int ysf(int n, int m)
{
    int x = 0, *vec = (int*)calloc(n, sizeof(int));
    for (int i = 1; i < n; ++i)
        vec[x = next(x, m, vec, n)] = 1;
    x = next(x, 1, vec, n);
    free(vec);

    return x + 1;
}

int main(int argc, char* const argv[])
{
    printf("%d\n", ysf(atoi(argv[1]), atoi(argv[2])));
}

十三张牌

有十三张牌, 将最上面的抽出来放在最下面,之后将最上面的牌抽走, 若抽走的顺序是
1 2 3 4 5 6 7 8 9 10 11 12 13 问原始的顺序是什么?

what = []

for x in range(13):
    what.append(13 - x)
    what.append(what.pop(0))

what.reverse()
print what

#include <iostream>

int main(int argc, char *argv[])
{
    int vec[13] = { 0 };

    for (int i = 0, x = -1; i < 13; ++i)
    {
        for (++x; vec[x % 13]; ++x)
            ;
        for (++x; vec[x % 13]; ++x)
            ;
        vec[x % 13] = i + 1;
    }

    for (int i = 0; i < 13; ++i)
        std::cout << vec[i] << " ";
    std::cout << std::endl;
}

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 + 内部正方形内点的个数。