恶搞 qsort 测试代码

//Array类的交换和判断是否有序的方法
Array.prototype.swap = function (a, b) {
var tmp = this[a];
this[a] = this[b];
this[b] = tmp;
}

Array.prototype.isInOrder = function () {
for (var i =0; i <> this[i+1]) return false;
return true;
}

//简短的快速排序，只需一个数组作参数
function qsort (arr, l, u) {
l = l || 0;
u = ((u != 0) &&amp; (u == undefined)) ? arr.length : u;
if (l >= u) return;
var m = l;
for (var i = l+1; i <= u; i++)
if (arr[i] < arr[l])
arr.swap(++m, i);
arr.swap(l, m);
qsort(arr, l, m-1);
qsort(arr, m+1, u);
}

Math.rand = function (start, end) {
if (end == undefined) {
end = start;
start = 0;
}
return start+Math.random()*(end-start);
}

Math.randInt = function (start, end) {
return Math.round(Math.rand(start, end));
}

//生成待排序的大规模随机整数数组
function randRange (len, start, end) {
var range = new Array(len);
for (var i = 0; i < len; i++)
range[i] = Math.randInt(start, end);
return range;
}

//把测试代码绑定在qsort()函数上
qsort.test = function (len, start, end) {
var tmpArr = randRange(len, start, end);
this(tmpArr);
return tmpArr.isInOrder();
}

PS: 我一个同学在电脑课上用Firefox玩randRange(10000)之类的东西玩了半节课……

比Boyer-Moore更快的字符串查找算法（转）

字符串查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的c库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍。但是BM算法还不是最快的算法，这里介绍一种比BM算法更快一些的查找算法。

例如我们要在"substring searching algorithm"查找"search"，刚开始时，把子串与文本左边对齐：

substring searching algorithm
search
^

结 果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用 已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的 'i')。

显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下一步匹配到了，这个字符必须在子串内。所以，可以 移动子串，使子串中的最右边的这个字符与它对齐。现在子串'search'中并不存在'i'，则说明可以直接跳过一大片，从'i'之后的那个字符开始作下 一步的比较，如下图：

substring searching algorithm
　　　　search
　　　　^

比较的结果，第一个字符就不匹配，再看子串后面的那个字符，是'r',它在子串中出现在倒数第三位，于是把子串向前移动三位，使两个'r'对齐，如下：

substring searching algorithm
　　　　　 search
　　　　　　　^

哈！这次匹配成功了！回顾整个过程，我们只移动了两次子串就找到了匹配位置，是不是很神啊?!可以证明，用这个算法，每一步的移动量都比BM算法要大，所以肯定比BM算法更快。

下面是这个算法的c代码。注意我假设了每个字符的值都介于0-127之间（即纯ascii码）。

char *qsearch(const char *text, int n, const char *patt, int m)
{
// get the length of the text and the pattern, if necessary
if (n < 0)
n = strlen(text);
if (m < 0)
m = strlen(patt);
if (m == 0)
return (char*)text;

// construct delta shift table
int td[128];
for (int c = 0; c < 128; c++)
td[c] = m + 1;
const char* p;
for (p=patt; *p; p++)
td[*p] = m - (p - patt);

// start searching...
const char *t, *tx = text;

// the main searching loop
while (tx + m <= text + n) {
for (p = patt, t = tx; *p; ++p, ++t) {
if (*p != *t) // found a mismatch
break;
}
if (*p == 0) // Yes! we found it!
return (char*)tx;
tx += td[tx[m]]; // move the pattern by a distance
}
return NULL;
}

注：这个查找算法称为Sunday算法，它是BM算法的一种改进型。

谈谈数组元素左旋问题（下）

上篇中 ，我给出了一些解决数组元素左移问题的不符合要求或很慢的解法。在下篇中，我将讲解3个很有“来头”（至少出现在《编程珠玑》里了:)）的O(n)级算法。
第一个算法思想上和我曾经想到的一个直接插入元素的算法基本相同，也是通过递归地逐个放置数组元素来左旋数组的。只不过我使用的方法是逐个临时测试是否可以按照公式放置，而这个算法经过周密计算，直接给出了符合各种情况的通用下标计算方法：
对于任意的元素下标 i，它的新下标 i` = ((k - m) + i ) % k。
代码如下：

//先求最大公约数，其实有很多方法，这个叫“辗转相除法”
int facter (int i, int j) {
while (i != j) {
if (i > j) {
i -=j;
} else {
j -= i;
}
}
return i;
}
//元素互换函数，无聊。。。
void swap (int *n1, int *n2) {
int tmp;
tmp = *n1;
*n1 = *n2;
*n2 = *tmp;
}
void turn_left (int *a, int m, int k) {
int i, tmp, f;
k = k % m;
if (k == 0) {
return;
}
f = facter(m, k);
if (f == 1) {
i = 0;
do {
i = (i+k)%m;
swap(a, a+1);
} while (i != 0);
} else {
for (i = 0; i < tmp =" i;" tmp =" (tmp+k)%m;" href="http://lichray.blogspot.com/2006/09/blog-post_25.html">那篇文章中用图示详细分析了数组元素的位移过程。如果你想找到一点新的灵感，可以把一些代表元素的卡片（凯库勒？！）用线穿起来反复地排，看看开始时和结束时，数组产生了哪些变化：
似乎看不出什么端倪。。。但如果把每种颜色的线都反序一下，
呵，很漂亮啊。再分析一下——原来，要让数组元素左旋m位，只需先将数组全部反序，然后将下标0~m-1和m~k-1的两部分分别反序就行了！最快的算法居然就这么简单！
用Python表示一下（这个代码是可运行的）：

def turn_left (a, m):
a.reverse()
a[:m].reverse()
a[m:].reverse()
return

C代码就不用写了吧，用上面那个swap()函数＋循环将数组反序而已啊。
最后一个方法，说真的，我没看懂。。。据说利用了数论知识，也很快，原理和本文第一个其实区别不大，只是计算新下标的算法更先进了：

/*照抄编程珠玑，伪代码（汗~），懒得翻译。n是数组长度，r是左旋位数，gcd()函数计算最大公约数，for后面的式子表示i的取值范围。*/
for i = [0, gcd(r, n))
t = x[i]
j = i
loop
k = j + r
if k >= i
k -= n
if k == i
break
x[j] = x[k]
j = k
x[j] = t

还得好好学数学啊！理解这个会有时！
真希望所有的程序员（代码书写er就算了）人手一本《编程珠玑》（Programming Pearls），书中自有黄金物，早日摆脱索然无趣的代码！

关于数组左移问题的一个新想法

本来要继续写数组左旋下篇（上篇在此）的，今天在课堂上忽然想到一个新办法 ：既然可以证明每一个元素的新位置是((k - m) + i ) % k，我何不再仔细分析一下数组的直接移动过程？
对于k = 5，m = 2：
#注：蓝色线表示元素向右的移动过程，绿色表示向左的移动过程。
不难发现，向右移动时，元素下标从 i 改变到 i + k - m，而向左移动时是 i - m（显然）。
再验证一下吧：为什么这个用了两次直接移动？似乎 k % m == 0 时就需要做 m 次，否则要做1次。
没错。但算法写得可不能如此精神分裂——这个现象肯定有更深层次的原因。
再演算一下，终于弄明白了：每种方向的移动其实是个循环过程，每次寻找 k 中可存放元素的下标位置；当期望的下标大于 k 时，元素就要向反方向找位置了。
理清了算法的操作过程，大致的想法也就成型了：有一个分两种情况找位置的递归函数，当 k % m == 0 时循环调用它 m 次，当 k % m == 1时一次即可。比如：
显然这个算法只进行了 k 次赋值（计算次数可以忽略不计），效率应当非常高。
具体代码等我写完《谈谈数组左旋问题（下）》再说吧！

我设计的Lua数据结构List的接口

代码还没有测试完，先把接口并注释发一下，将来和着代码一起发看起来很不方便。
设计参考了Python的相关函数，但比Python更强。不过python中的数组分片功能不知道能否真的实现，如果不行我只好用其它函数对分片功能的支持来代替。

--域，没有多余的域
List = {n = 0}

--静态方法接口
function List.new (...) end --构造函数，将整个参数列表转为List
local function List.cons (table) end --内部构造函数，将表转为List

--成员方法接口
function List:insert (item, n) end --在位置n之前插入item，默认插在List头部
function List:append (item) end --在list尾部插入item，等价于insert(item, list.n)
function List:remove (item) end --弹出第一个等于item的项并返回
function List:pop (n) end --弹出下标为n的项并返回，默认弹出末项，pop(0)等价于pop(1)
function List:index (item) end --返回第一个值为item的项的下标
function List:qindex (item) end --对于已排序list使用二分法查找
function List:count (item) end --返回list中该item的出现次数
function List:sub (from, to) end --返回从from到to的子list，下标为from的项不包括在内；from默认为0，to默认为list.n
function List:subl (from, l) end --等价于sub(from, from+l)
function List:cut (from, to) end --从list删除下标从from到to的子list并返回...
function List:cutl (from, l) end --等价于cut(from, from+l)
function List:extend (list) end --直接在self后添加list子列表
function List:reverse () end --倒排这个list
--function List:reverse (from, to) end #如果sub函数不能实现，这个功能就十分必要了
function List:sort (func) end --接受一个函数，它比较两个参数arg1
function List:qsort (func) end --sort()的快速排序版本
function List:bsort (func) end --sort()的基数排序版本，要求所有项都为正整数
--下面3个函数是python中的同名函数，充作迭代器
local function List:map(func)
local function UNM () end --每项取负访问器
local function EXP2 () end --每项取平方访问器
local function EXP3 () end --每项取立方访问器
end
local function List:filter(func)
local function DEL (item) end --返回并删除所有等于item的项的过滤器
local function EQUAL (item) end --返回所有等于item的项的过滤器
local function MORE (item) end--返回所有大于item的项的过滤器
local function LESS (item) end--返回所有小于item的项的过滤器
end
local function List:reduce(func)
local function MAX (pre, next) end --求最大递归访问器
local function MIX (pre, next) end --求最小递归访问器
local function MUL (pre, next) end --求list各项之积递归访问器
local function SUM (pre, next) end --求list各项之和递归访问器
local function SUM_MAX (pre, next) end --求最大子序列递归访问器
end

赶快写~~赶快写~~
×补充：我已经有办法解决数组分片问题了——给list加两个域：_stat和_end，再使用函数代理访问下标，玩“虚拟下标”即可！

极度经典的二分法搜索

很easy。闲着无聊写出来。建议背下来。

#define datatype
#define ERROR -1

int bsearch (datatype * arr, int n, datatype obj) {
int l = 0;
int u = n-1;
int m;
while (l <= u) {
m = (l+u)/2;
if (arr[m] <>
l = m+1;
} else if (arr[m] == obj) {
return m;
} else {
u = m-1;
}
}
return ERROR;
}
这么简单注释就免了吧，哈哈~~

《称球问题》的完整代码

晕死，上次发的那篇文章居然忘了给代码。现在把它贴出来，顺便加点注释。
（最近拼命写Lua数据结构实现中...）

#metga.py
#useage: python metga.py datefile
import sys
import string

#比较结果代码（左盘?右盘）
HEAVY = 1
LIGHT = -1
EQUAL = 0
QUESTION = 0 #问题球的问题
ANSWER = ""

#球的数据结构
class Ball:
def __init__ (self, weight):
self.weight = weight
self.number = 0

#求总质量
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp

#天平函数，计算左右盘质量返回比较结果
def metage (leftBalls, rightBalls):
left = sum(leftBalls)
right = sum(rightBalls)
if left > right: return HEAVY
if left < style="color: rgb(51, 51, 255);">return LIGHT
return EQUAL

#对球进行预处理，判断问题球是轻是重
def pre (balls):
global QUESTION
n = len(balls) / 3
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
statu = metage(parts[0], parts[1])
if statu == EQUAL:
QUESTION = metage(parts[2], parts[0])
return balls[2*n:]
QUESTION = statu
if metage(parts[0], parts[2]) == EQUAL:
return parts[1]
else:
return parts[0]

#递归地分3片称球
def test (balls):
l = len(balls)
if l == 1:
return balls[0].number
n = l / 3
if l < n =" 1" parts =" [balls[:n]," statu =" metage(parts[0]," style="color: rgb(51, 51, 255);">if statu == EQUAL:
return test(balls[2*n:])
elif statu == QUESTION:
return test(balls[:n])
else:
return test(balls[n:2*n])

#读取数据文件（内容为n个数字，每个一行，其中有一个与其它不等）
weight_list = map(string.atoi, open(sys.argv[1]).readlines())
ball_list = map(Ball, weight_list) #创建球组成的list
i = 1
for ball in ball_list: #初始化下标
ball.number = i
i += 1
if QUESTION == 1:
ANSWER = "heavier"
else:
ANSWER = "lighter"
print "The No.%d ball is %s than others." % (test(pre(ball_list)), ANSWER)

可恶的Blogger对于程序的排版支持约等于无，忙死我了。等我学完编译原理，我一定要开发一个JavaScript实现的词法分析器！

参考AllStartFromGame写了一个排列组合算法

--昨天想了半个小时才想到的一个不错的方法。
--Lua果然号称“只用表的Scheme”，库基本没有。
--代码写得很零乱，还有问题——该死的Lua默认变量为全局，搞得递归有问题。
--不过想法还是很强的，把书本上的知识扩展了一下。
--下次我来扩充一下库，顺便把这个东西改写一下，至少让它能跑起来。

function turn_left (list) --数组左移函数
table.insert(list, list[1])
table.remove(list, 1)
end
function table.extend (t1, t2) --Python中的同名函数
for i = 1, table.getn(t2) do
table.insert(t1, t2[i])
end
end
function list_all (...) --启动函数，接受n个参数作为待排列的项
h_result = list_half(arg)
table.extend(h_result, reverse(h_result))
return h_result
end
function reverse (list) --数组假反序（返回一个新数组）
temp = {}
for i = 0, table.getn(list)-1 do
table.insert(temp, list[table.getn(list)-i])
end
return temp
end
function list_half (list, n) --列表半个排列组合
result = {} or result --保存结果的二维数组
tmp = {list[1], list[2]} or tmp
if n == nil then --处理起始情况
list_half(tmp, table.getn(list)-1)
end
if n == 1 then --处理基准情况——最终排序
for i = 1, table.getn(tmp) do
turn_left(tmp)
table.insert(result, tmp)
end
return result
else --递归列出最一般的排序
table.insert(tmp, list[table.getn(list)-n])
for i = 1, n do
turn_left(tmp)
list_half(tmp, n-1)
end
return result
end
end

找到的一个八皇后问题Python版解法

原文称参考了All Start From A Game。
觉得有参考价值，虽然好像还不够快和简洁。以后我来自己写一个递归版的罢。
排版了一下，加了点注释。

size = 8 # 棋盘大小
EMPTY = "O" # 空位
QUEEN = "X" # 皇后

# 查看棋盘的信息
def show_board(cols):
for i in range(size):
for j in range(size):
if j == int(cols[i]) - 1:
print QUEEN,
else:
print EMPTY,
print "\n",

# 检测棋盘上皇后摆法是否合法
# return:
# True(不冲突), False(有冲突)
def check_board(cols):
for i in range(size - 1):
for j in range(i + 1, size):
if j - i == abs(int(cols[j]) - int(cols[i])):
return False
return True

# 得到全排列
def permute(seq):
seqn = [ seq.pop() ]
while seq:
newseq = []
new = seq.pop()
#print "seq:",seq,'seqn', seqn ,'new', new
for i in range(len(seqn)):
item = seqn[i]
for j in range(len(item)+1):
newseq.append(''.join([item[:j],new,item[j:]]))
seqn = newseq
#print 'newseq',newseq
return seqn

#测试代码
if __name__ == "__main__":
solve_count = 0
numbers = ''.join([str(i) for i in range(1, size + 1)])

for x in permute(list(numbers)):
y = list(x)
if check_board(y):
solve_count += 1
show_board(y)
print "\n",

print "found %i solves." % solve_count

谈谈数组元素左旋问题（上）

终于把《编程珠玑》那本书给买来了。第一章2.3提出了一个“数组元素左旋问题”，《程序员》杂志上出过，描述如下：
对于有K个元素的数组int a[K] = {...}，写一个高效算法将数组内容循环左移m位。比如：int a[6] = {1,2,3,4,5,6}循环左移3位结果是{4,5,6,1,2,3}。注：不允许返回其它内存空间，但可使用少许变量。
《程序员》上面给的解答抄自书后答案，网友给出的两次倒排算法抄自书上解法1~~晕死。
对于这个问题有已经有不少解决办法了。我上个星期教网友算法时讲到了这个问题，现在把这些算法整理出来罢。
先将一个不符合要求但很基本的想法：先在数组后扩充数组的前一部分，然后再删掉数组自己的前一部分。用Python表示一下：
def move(a,m):
a.extend(a[:m])
return a[m:]
这个算法用C来实现我用了溢出的方法获得了更多内存（没必要管它能否通过编译），然后直接返回一个假的数组首地址。
int * move (int *a, int k, int m){
for (int i = 0; i <>
*(a+k+i) = *(a+i);
}
return (a+m-1);
}
很甩是不是？太猥琐了（但它说明了一个问题：大家都赞扬动态语言灵活，其实C也很灵活）。
更合适一点的做法是用一个线形数据结构保存前半部，再将原数组左移，最后将前半部分加回去。用Python表示一下（其实和上面那个也没多大区别）：
def move (a, m):
j = i = 0
tmp = []
while i <>
tmp[i] = a[i]
a[i] = a[i+m]
i += 1
while j <>
a[j+m] = tmp[j]
i += 1
return a #其实数组已改变，这句可以不要
后悔了——实在是没有比这更别扭的Python代码了~~改成C就免了吧，初始化tmp是把长度设为m，编译时要加这个参数：-std=c99（gcc）。
好了，我就不再无聊了，开始讲点正经的吧：在原数组上操作。
先回忆一下冒泡排序法：当处理一个处在最左边但又是最大的项时，这个项是怎样移动的？
在纸上画一画——哦，它和每个元素交换，然后到了最右边……等等，呓？其它的项的顺序都没有变？！整个数组左移了！
那么，我们第一个符合要求的答案就出来了：把数组当成是反排序的，从最左边进行m次冒泡即可！
吸取教训，我还是写C代码吧：
int * move (int a[], int k, iny m) {
for (int j = 0, j <>
for (int i = 0; i <>
int tmp = a[i+1];
a[i+1] = a[i];
a[i] = tmp;
}
} //算了，不写返回语句了
}
嗯，两层循环，照书上的说法这个算法的时间复杂度应当是O(n2)——但是，那个m好像不足k吧？可以认为是O(n*m)，但这样说是不严密的，因为O()仅处理上界情况。
好了，不多罗嗦了，下篇将揭晓真正有效率的算法——3个都是O(n)级的。

递归算法入门-pascal（转）

程序调用自身的编程技巧称为递归（ recursion）。
　　一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
　　 注意：
　　 (1) 递归就是在过程或函数里调用自身;
　　 (2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

　　一个比较经典的描述是老和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在讲故事，他说从前有座山， ……。这样没完没了地反复讲故事，直到最后老和尚烦了停下来为止。

　　反复讲故事可以看成是反复调用自身，但如果不能停下来那就没有意义了，所以最终还要能停下来。递归的关键在于找出递归方程式和递归终止条件。即老和尚反复讲故事这样的递归方程式要有，最后老和尚烦了停下来这样的递归的终止条件也要有。

阶乘的算法可以定义成函数

当 n>0时，用 f(n-1)来定义 f(n)，用 f(n-1-1)来定义 f(n-1)……，这是对递归形式的描述。

当 n=0时， f(n)=1，这是递归结束的条件。

例：用递归策略求N!的解。
　　　 N!=1*2*3*...*N
　　 分析：
　　　 (1) 不运用递归的解法
　　　 (2) 运用递归策略
　　　　　 N!=1*2*3*...*N
　　　　　　 =[1*2*3*...*(N-1)]*N
　　　 (N-1)!=1*2*3*...*(N-1)
　　　 设 f(N)=N!
　　　 那么 f(N-1)=(N-1)!
　　　 则 f(N)=f(N-1)*N
　　　 这就是递归式子，由于式子中有N-1，所以N>=1，递归出口的条件是N=1时。
　　 函数模式：
　　　 function f(n:integer):longint;
　　　 var
　　　　 ...
　　　 begin
　　　　 if 递归出口的时候 then
　　　　　　 f:=1
　　　　 else
　　　　　　 f:=f(n-1)*n;
　　　　 end;

递归算法一般用于解决三类问题：

⑴. 数据的定义形式是按递归定义的。

比如阶乘的定义。

例 1　又如裴波那契数列的定义： f(n)=f(n-1)+f(n-2); f(0)=1; f(1)=2

对应的递归程序为：

var n:integer;
function f(n:integer):longint;
begin
case n of
0:f:=1; { 递归结束条件 }
1:f:=2;
else
f:=f(n-1)+f(n-2) 　　｛递归调用｝
end
end;
begin
readln(n);
writeln(f(n))
end.

这类递归问题往往又可转化成递推算法，递归边界作为递推的边界条件。

⑵. 问题解法按递归算法实现。例如回溯等。

⑶. 数据的结构形式是按递归定义的。如树的遍历 , 图的搜索等。

递归解决实际问题的例子很多，如经典的梵塔问题。

例 2　梵塔问题：有 n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在 A柱上，另外还有 B、 C两根空柱。要求将 A柱上的 n个圆盘全部搬到 C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。

在移动盘子的过程当中发现要搬动 n个盘子，必须先将 n-1个盘子从 A柱搬到 B柱去，再将 A柱上的最后一个盘子搬到 C柱，最后从 B柱上将 n-1个盘子搬到 C柱去。搬动 n个盘子和搬动 n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。

程序如下：

var a,b,c,number:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'->',c)
else
begin
move(n-1,a,c,b);
writeln(a,'->',c);
move(n-1,b,a,c)
end;
end;
begin
write('the number of dish:');
readln(number);
move(number,1,2,3);
readln
end.

自然数的拆分，数字的拆分等都可以用到递归算法。

例 3　要求找出具有下列性质的数的个数 (包含输入的自然数 n)：

先输入一个自然数 n(n<=500),然后对此自然数按照如下方法进行处理 : ①. 不作任何处理 ; ②. 在它的左边加上一个自然数 ,但该自然数不能超过原数的一半 ; ③. 加上数后 ,继续按此规则进行处理 ,直到不能再加自然数为止 . 样例 : 输入 : 6 满足条件的数为 6 16 26 126 36 136 输出 : 6 这道题只需求出满足条件的数的个数，在 n值不大的情况下用递归求解比较方便，因为它本身题目的条件就是递归定义的。 递归的样例程序如下： var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x<>0 then
begin
s:=s+1;
for k:=1 to x div 2 do qiu(k)
end
end;
begin
readln(n);
s:=0;
qiu(n);
writeln(s:2:0)
end.

递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。



[习题] 用递归完成：
1、如下图，打印0－N的所有路径(0=〈N〈=9)：
　 1―> 3―> 5―> 7―> 9
　 ^　　 ^　　 ^　 ^　　 ^
　 |　　 |　　 |　　 | 　　 |
　 0―> 2―> 4―> 6―> 8
(说明：图中须加上0－>3，2－>5，4－>7，6－>9的连线)
2、打印杨辉三角。
3.用递归的算法把数组中的N个数按颠倒的次序重新存放。
4. 用递归算法完成：有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三轮从第4张牌开始，凡是4的倍数位置上的牌按上面相同规则翻转，以此类推，直到第一张要翻的牌超过52为止。统计最后有几张牌正面朝上，以及它们的位置号。

看到一道NOI2005的题目，高手上吧

篝火晚会
(fire.pas/c/cpp)
【问题描述】
佳佳刚进高中，在军训的时候，由于佳佳吃苦耐劳，很快得到了教官的赏识，成为了“小教官”。在军训结束的那天晚上，佳佳被命令组织同学们进行篝火晚会。一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。
佳佳可向同学们下达命令，每一个命令的形式如下：
(b1, b2,... bm -1, bm)
这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，…… bm –1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。
执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要佳佳用最少的总代价实现同学们的意愿，你能帮助佳佳吗？
【输入文件】
输入文件fire.in的第一行是一个整数n（3 <= n <= 50000），表示一共有n个同学。其后n行每行包括两个不同的正整数，以一个空格隔开，分别表示编号是1的同学最希望相邻的两个同学的编号，编号是2的同学最希望相邻的两个同学的编号，……，编号是n的同学最希望相邻的两个同学的编号。 【输出文件】 输出文件fire.out包括一行，这一行只包含一个整数，为最小的总代价。如果无论怎么调整都不能符合每个同学的愿望，则输出-1。 【样例输入】 4 3 4 4 3 1 2 1 2 【样例输出】 2 【数据规模】 对于30%的数据，n <= 1000； 对于全部的数据，n <= 50000。

发生在我身边的一个算法笑话

当年老师教我们算法入门，讲到一道题目，说输入一个整数 N，要求输出所以不大于这个整数的除3可以整除的正整数。
大家都是这么写的（伪代码）：
for X from 1 to N step 1
if X%3=0
print X
end if
end for
我们班体委突然发彪，给出了一个惊世骇俗的解答：
for X from 3 to N step 3
print X
end for
老师晕死，全班人疯了~~

一个线形复杂度的菲波那契函数

所谓菲波那契数列，就是这个东西：1,1,2,3,5,8...题目为，写一个函数fib(int n)给出数列中某个数的下标，返回这个数。
菲波那契函数的数学定义为fib(x)，x=1 ? fib(x)=1 : fib(x)=fib(x-1)+fib(x-2)。
只用这个就可以给出解答：
unsigned long fib (int x) {
if (x > 2) {
return fib(x - 1) + fib(x - 2);
} else {
return 1;
}
}
测试函数如下：
int main () {
int arg;
printf("Input the length:");
scanf("%d", &arg);
printf("fibonacci(%d)=%lu\n", arg, fib(arg));
return 0;
}
但是，学过算法的人都知道，这个算法的时间复杂度是O(n2)级的，慢的要命。教科书上给出了循环方法的解答。（注：这个解答有一个超变态的一句话版本，知道的人请跟贴）
事实上，确实可以给出线形复杂度的菲波那契函数，原理来源于数列本身的性质。我大概写了一下，程序本身不好看，但肯定不会更快了：
#include
int i = 3;
unsigned long fib (int x, int y, int n) {
if (i <= n) { i++; return fib(y, x + y, n); } else { return y; } } int main () { int arg; printf("Input the length:"); scanf("%d", &arg); printf("fibonacci(%d)=%lu\n", arg, fib(1, 1, arg)); return 0; } 觉得怎么样？是不是很直白？

附：菲波那契数列有通项公式...
#python代码
import math
q = math.sqrt
def fib ( n ) :#看清楚了，这可是O( 1 )级的哦~~
return ((1 + q(5) / 2) ** n / q(5) - ((1 - 1(5)) / 2) ** n / q(5)

《称球问题》的 python 版解答

《程序员》杂志第8期上讲解了这样一个问题：在N个球中，有一个球重量与其他球重不同（偏重或偏轻），在没有砝码的天平上进行k（N<=(3^k-1)/2）次称量，得到这个球的编号，并判断它比其它球轻或重。

《程序员》上使用了将球分为0～n-1，n～2n-1，2n～N-1（n=(N%3)?(N/3+1):(N/3)）两两递归比较的方法。但由于在整个比较过程中，这个球到底偏轻还是偏重一直没有确定而进行了多次无效的比较，而且使用C++描述，对于这个需要大量出来数组的算法来说十分繁琐。我采用了支持函数式编程的Python语言优化了这个算法，脚本和测试用数据文件（举例）在附件中有下载。

主要思想与《程序员》中的类似，不过对球的列表的分片有所不同：
parts = [balls[:n], balls[n:2*n], balls[2*n:3*n]]
保证3片球数相同。确定是那一片出了问题后返回它时，最后一片由于可能不是balls[2*n:3*n]（len(balls)%3!=0），所以返回balls[2*n:]。

球包括号码和质量两个属性，类定义如下：
class Ball:
def __init__ (self, weight):
self.weight = weight
self.number = 0
（注：number的默认值0是无效的，号码从1开始）
sum()用于给质量求和：
def sum (balls):
tmp = 0
for ball in balls:
tmp += ball.weight
return tmp
天平函数，返回比较结果——HEAVY = 1，LIGHT = -1，EQUAL = 0：
def metage (leftBalls, rightBalls):
left = sum(leftBalls)
right = sum(rightBalls)
if left > right: return HEAVY
if left < right: return LIGHT
return EQUAL

用全局变量QUESTION保存问题球是轻是重，这由预测量函数pre()给出，它工作后还返回有问题的分片。这样test()函数在工作时可以少一半比较次数。

test函数递归调用自身，可以采用折半比较的方式。但那样会提供算法的时间复杂度。假设n个质量数据求和要进行n次运算，折3片比较共需p=2*(x/3+x/3^2+...x/3^(N-1))次运算，化简得p=x-x/3^n，即求和运算次数不会大于球总个数。而折半比较则需(2^(N+1)-1)x（不准）次运算，明显多于使用分3片比较。

具体比较的条件详见代码，自行阅读。

最后解释一下数据文件的读入情况。数据文件是普通文本文件，每行一个数字，其中一个与其它不同。open(sys.argv[1]).readlines()返回一个由每行的字符串构成的列表，weight_list = map(string.atoi, open(sys.argv[1]).readlines())对这个列表中的每一项进行转数字操作并存入weight_list。ball_list = map(Ball, weight_list)把表中每一项创建Ball对象，最后test(pre(ball_list)计算返回球的编号。

关于python的函数式编程请初学者自己参考教材理解。感谢网友孔辉GID2257990(Lava-Lava平台)在程序调试方面给予的帮助。