Scheme学习笔记（四）

（下一篇是最后一篇，讨论宏，结构和面向对象（其实没什么用））

四. 流程控制

• Scheme中只有if操作是内置的，其它用宏实现。
• 应尽量用尾递归代替循环。

• (if (测试表达式) (操作) (else操作))
• 由多个语句构成的操作用(begin)语句组合

• (when (测试表达式) (多个操作))
• (when (非测试表达式) (多个操作))
• 其它的操作式不必用begin组合
• case语句：

(case c
((#\a) 1)
((#\b) 2)
((#\c) 3)
(else 4)) => 3

• 逻辑表达式操作：
• and在无非比较时返回后一个值：(and 1 2) => 2
  (and #f 1) => #f
• r在无非比较时返回前一个值：(or 1 2) => 1
  (or #f 1) => 1

六. 递归

• 不能工作的代码，因为let或let*会将操作名绑定到各自的词法定界，导致互相递归调用的函数不能互访：
  

(let ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))

• 把绑定操作换成letrec即可。
• 由begin引导的语句序列返回最后一个语句的值。
• 命名let可简化局部递归调用：

(let countdown ((i 10))
(if (= i 0) ’liftoff
(begin
(display i)
(newline)
(countdown (- i 1))))) ;输出一个整数递减过程中的每个值

• 迭代器(for-each 操作 (被操作list))
• 迭代器(map 操作 (被操作list))，返回list中每一个被操作项构成的list（python里的那个函数的同名被复制品）。

Scheme学习笔记（三）

（另一些参考资料：Scheme语言介绍，语言概要（上）（下））

三. 过程

• lambda形式：((lambda 参数 (过程)) 可选的实际参数)

((lambda (x) (+ x 2)) 5) => 7

• 带括号时为形式参数，否则被认为是一个参数list

((lambda someFriends ; 参数周围没有括号 ! (DisplayLine "hi there " someFriends)) 'mole 'bear 'tiger)

• 定义函数用define：(define add2 (lambda (x) (+ x 2)))，省略lambda：(define (add6 x) (+ x 6))
• 谓词(procedure?)来测试一个对象实际上是否为过程
• 函数名即操作名：(add2 9) => 11
• (apply 函数名 参数列表)强制调用。
• 过程的套嵌定义遵循词法定界。

五. 词法定界（下篇讲“四”）

• define定义当前定界以下对象。
  
• (set!)仅改变当前定界中的对象：

(define counter 0)
(define bump-counter (lambda ()
(set! counter (+ counter 1))
counter))

(bump-counter) => 1
(bump-counter) => 2
(bump-counter) => 3

• 相对define，(let (定义局部变量) (其它代码))绑定局部变量到过程：

(let ((x 2) (y 5)) (* x y)) => 10


• let*内的定义不改变上级定界定义的局部变量

• letrec的定义可互交引用？

(letrec ((even?
             (lambda(x)
             (if (= x 0) #t
                     (odd? (- x 1)))))
         (odd?
             (lambda(x)
             (if (= x 0) #f
                     (even? (- x 1))))))
(even? 88))  =>  #t

• letrec帮助局部过程实现递归。

• 非标准的(fluid-let)不改变上级定界变量却引作当前定界局部变量——无聊。。。

(fluid-let ((counter 99))
(display (bump-counter)) (newline)
(display (bump-counter)) (newline)
(display (bump-counter)) (newline))
输出100，101，102，但原counter不变。

Scheme学习笔记（二）

（都忘了说了，我复习用的教材是Teach Yourself Scheme in Fixnum Days，还有一本The Scheme Programming Language也很好，但太长，没看过）

2. 复合类型

比较谓词：

(eqv?   (list 'a) (list 'a)) ; 它们 "看起来一样"，
;()
(eq?    (list 'a) (list 'a)) ; 存储在不同的内存单元中。
;()
(equal? (list 'a) (list 'a))
;#t

• 字符串：申明(define str "This is a string.")
• 用字符申明：(string #\h #\e #\l #\l #\o) => "hello"
• (string-ref 字符串 位置（整数）)返回字符串该位置上的字符
• (string-append "E " "Pluribus " "Unum") => "E Pluribus Unum"
• 改变字符串（重新赋值）(string-set!)
• (string-length "mumble") => 6

• 向量（貌似数组）：值以"#"开头
• 申明(vector 0 1 2 3 4) => #(0 1 2 3 4)或(make-vector 长度)

• 对（不知道怎么翻译pairs这个词~~）
• 分为左右值，左值叫car，右值叫cdr，用他们作操作符获取左右值
• 申明(cons 左值 右值)
• (cons 1 #t) => ’(1 . #t)
• (set-car!)，(set-cdr!)
• 重要！经常右值套嵌！(cons 1 (cons 2 (cons 3 (cons 4 ’()))))形成list：(list 1 2 3 4)

• list（太有名，懒得翻译）
  

• list操作：取值(list-ref)
• list-tail 通过除去前面的 n 个元素来获得一个子表
• 添加元素(append)
• (null?) 检查它的操作对象是否是空表。
• 长度(length)
• member 和 memq 将返回它的 car 是一个指定元素的一个子表。
• 查找(assoc 'LittleBear '((HappyMole vampire) (LittleBear banshee) (LittleTiger troll))) => (LittleBear banshee)

• 类型转换：(原类型-新类型 对象)
• 类型转换方式非常自由：

(string->number "16") => 16
(symbol->string ’symbol) => "symbol"
尤其是这个：
(string->list "hello") => (#\h #\e #\l #\l #\o)

Scheme学习笔记（一）

（写这个文档并非我初学Scheme，只是为开始全面使用它作点复习准备）

一. HelloWorld

• Scheme语法即抽象语法树，只有仅有的几个内部语法支持。
• ;开启一行注释
• 用括号进行文法定界，第一项为操作，空格（换行）分割操作对象，如：

(diplay "hello, world!")
即对"hello, world!"字符串进行 display 操作。

• Scheme和Lisp一样是自描述的，脚本用 .scm 作为后缀，进入解释器后，使用(load "文件名字符串")启动程序，用(exit)退出解释器。

• 完整程序：

(begin (display "hello, world!") (newline));newline用来刷新缓存

二. 数据类型
1. 简单类型

• 布尔值：有两个取值，#t和#f
• 操作(类型名? 变量)返回一个布尔值，确认该变量是否为此类型。如：

(boolean? #t) => #t
(boolean? 32) => #f

• 宏(not 布尔值)返回这个布尔值的反取值。如：

（not (boolean? #t)) => #f

• 数字：分为complex，rational，real，integer，但申明时不必指出。
• (= 操作对象1 操作对象2)操作仅用于比较类型相同的变量值是否相同；(= 43 43) => #t，但(= 43 "ok")会报错。
• (eqv?)操作是(=)的范型版本
• 指数运算(expt 2 3) => 8，取绝对值(abs -7) => 7
  
• 字符：以#\开头的单个字符

(char=? #\a #\a) ? #t
(char=? #\a #\b) ? #f

• 忽略大小写比较：(char-ci=? #\a #\A) => #t
  
• 大小写转换（不影响原值）(char-downcase #\A) => #\a，(char-upcase #\a) => #\A
• 符号：编译原理中的东西，可作变量名，用(quote)申明，(quote a) => 'a
• 变量不与其类型绑定：
  

(quote abc) (define xyz 9) (set! xyz #\c)

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

本来要继续写数组左旋下篇（上篇在此）的，今天在课堂上忽然想到一个新办法 ：既然可以证明每一个元素的新位置是((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平台)在程序调试方面给予的帮助。