第5章
函数




5.1引例
例5.1.1逆序数的逆序和(HLOJ 1987)


Problem Description

输入两个正整数，先将它们分别倒过来，然后再相加，最后再将结果倒过来输出。注意： 前置的零将被忽略。例如，输入305和794。倒过来相加得到1000，输出时只要输出1就可以了。测试数据保证结果在int类型的表示范围内。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入两个正整数a、b。


Output

对于每组测试，将a、b逆序后求和并逆序输出(前导0不需输出)。





Sample Input

2

21 6

123 456


Sample Output

81

579

本题需求3次逆序数，若每次都重复写一个循环实现，则代码将较冗长。因为求逆序数的方法是一样的，可以编写一个求逆序数的函数，调用3次即可完成两个输入的整数及一个结果整数的逆序。
思考： 当x=1234，如何得到x的逆序数？
设r为x的逆序数，可以这样考虑： r=((4×10+3)×10+2)×10+1=4321，即让r一开始为0，再不断地把x的个位取出来加上r×10重新赋值给r，直到x为0(通过x=x//10不断去掉个数),具体代码如下。



def revNum(x):#自定义函数，求参数n的逆序数，此行是函数头

#函数体

r=0

while x>0:

r=r*10+x%10

x=x//10

return r                  			#返回逆序数






T=int(input())

for t in range(T):

m,n=map(int,input().split())

res=revNum(revNum(m)+revNum(n))#3次调用revNum()函数

print(res)




运行结果： 



2 

1234 5708 

69321

305 794

1




函数定义以关键字def开始，revNum是函数名，其后小括号()及其后的冒号是必需的，()中的x是形式参数，用于调用时接收传递过来的实际参数(如m、n)的值，完成逆序的代码写在冒号之后构成函数体； 函数需调用才起作用。程序员在编写程序时，通常会把一个程序中多次使用的代码写成一个函数再调用多次，如本例所示。实际上，一些常用功能即使在一个程序中不被调用多次，也经常写成一个个自定义函数。例如，判断一个数是否素数，求两个整数的最大公约数或最小公倍数、二分查找及排序等。另外，本例所写的revNum()函数能够忽略前导0，原因请读者自行分析。

第
5
章

函数


程序设计竞赛入门（Python版）
5.2函数基础知识
5.2.1函数概述

简言之，函数是一组相关语句组织在一起所构成的整体，并以函数名标注。
从用户的角度而言，函数分为库函数和用户自定义函数。库函数有很多，包括可以直接调用的内置函数及其他标准库或扩展库中的函数，例如，range()、print()、abs()、max()、min()、sum()、sqrt()、randint()等，具体用法举例如下。



>>> a=range(10);s=sum(a);print(s)#内置函数range()、sum()、print()	

45

>>> b=［1,13,52,6,8］

>>> m=max(b);n=min(b);print(m,n)			#内置函数max()、min()、print()

52 1

>>> c=-123.45;print(abs(c))					#内置函数abs()、print()

123.45

>>> from math import sqrt					#导入数学库(或称数学模块)math中的sqrt()函数

>>> print(sqrt(2)) 						#调用sqrt()函数

1.4142135623730951

>>> from random import randint				#导入随机库(或称随机模块)random中的randint()函数

>>> randint(10,99)						#调用randint()函数

52




本章主要介绍用户自定义函数。读者可以自行查阅并测试感兴趣的库函数。
一个大的程序一般分为若干个程序模块，每个模块用来实现一个特定的功能，每个模块一般写一个函数定义来实现。
5.2.2函数的定义与调用
1. 函数定义

函数定义由函数头和函数体两部分组成。一般形式如下。

def 函数名(［形参列表］): 

函数体


说明： 
(1) “def 函数名(［形参列表］)：”是函数头，函数定义必须以关键字def开头，函数名后的小括号“()”不能缺少； 冒号之后缩进量相同的若干语句构成函数体。
(2) 函数名必须是合法的标识符。
(3) 函数定义中的参数为形式参数，简称形参。根据是否有形参，函数可分为带参函数和无参函数。形参列表的每个参数指定参数名即可(参数类型根据函数调用时的实参确定)，形参列表若有多个参数，则以逗号间隔。Python支持参数带默认值，而且默认值参数须放在最右部分，即任意一个默认值参数之后的所有参数都应该带默认值。
(4) 根据是否有返回值，函数可分为有返回值函数(一般作为表达式调用)和无返回值函数(返回None，一般作为语句调用)。通过函数中的return语句返回函数的返回值。return语句的一般格式如下。

return ［返回值表达式］

若返回值表达式省略，即仅用 return 将控制程序流程返回到调用点； 若return语句后带返回值表达式，则在控制程序流程返回调用点的同时带回一个值。
2. 函数调用
函数定义好之后必须调用才能起作用。函数的调用形式一般如下。

［变量=］函数名(［实参列表］)

无返回值的函数一般以语句形式调用，有返回值的函数一般以表达式形式调用，否则其返回值没有意义。
调用时的参数称为实际参数，简称实参。一般情况下，参数的类型、顺序、个数必须与函数定义中的一致； 但带默认值参数的函数调用时实参个数可以与形参个数不一致； 若调用时指定形参名(关键字参数)，则实参的顺序可与函数定义的形参列表中指定的顺序不一致。
函数调用时，把实参依序传递给形参，然后执行函数定义体中的语句，执行到return语句或函数结束时，程序流程返回到调用点。
3. 函数定义与调用示例
下面给出若干函数定义与调用的例子。



def sayHello():#无参函数，也是无返回值函数，()不能省略

print("Hello")



def max(a,b):       				#带参函数，也是有返回值函数，有两个形参(用逗号分隔)

if a>=b:

return a    				#返回语句，在流程返回的同时带回变量a的值

else:

return b



def cal(a,b,c='+'): 			#带默认值参数的函数，默认值参数写在最右边

if c=='+':

return a+b 

elif c=='-':

return a-b



sayHello()                  		#无返回值的函数一般作为语句调用

print(max(123,321))         		#根据实参确定形参类型

print(max("abcde","abcDE")) 	#根据实参确定形参类型

print(cal(1,2))             		#因第三个参数未提供，故其使用默认值

print(cal(1,2,'-'))         		#为默认值参数指定实参

print(cal(c='-',b=1,a=2))   	#若调用时指定形参名，则实参顺序可与形参不一致




运行结果： 



Hello

321

abcde

3

-1

1




上面这些函数的实参都是常量。实际上，函数调用经常使用变量作为实参，若实参变量是不变类型的引用，则把实参变量的值传递给形参(此类参数简称值参，形参的改变不影响实参)，否则形参成为实参变量的引用(此类参数称为引用参数，形参的改变即是实参的改变)。实参和形参可以同名，但它们实际上是各自作用域内的不同变量。对于带默认值参数的函数，若在调用时不指定对应的实参，则该参数使用定义时指定的默认值。
形参和函数体中创建的变量是仅在该函数中有效的局部变量； 而在函数外创建的变量则是全局变量(或称外部变量)，从创建处开始往下都有效。
注意，在Python中，若全局变量定义在某个函数f()的调用之前，则该全局变量可在f()的函数定义中使用。例如： 



def f():

print(n**3)#使用本函数定义之后调用之前创建的全局变量n，可行

print(m**2)     				#使用本函数定义及调用之后创建的全局变量m，出错



n=3                 				#在调用f()函数之前创建全局变量n，则f()函数中可以使用n

f()

m=5                 				#在调用f()函数之后创建全局变量m，则f()函数中不能使用m




运行结果： 



27

Traceback (most recent call last):

File "D:/Python/test.py", line 6, in <module>

f()

File "D:/Python/test.py", line 3, in f

print(m**2)     #使用本函数定义及调用之后的创建的全局变量m，出错

NameError: name 'm' is not defined




注意，若要在函数定义中修改全局变量，则需用关键字global声明该全局变量。例如： 



n=123#n是全局变量



def f(t):               			#定义无参函数f，参数t是局限于f函数的局部变量

m=456               			#m是局部变量，仅在f函数中有效

global n            			#若无此语句，则下一条语句将创建局部变量n

n=789               			#因上一条全局变量声明语句，此处是在修改全局变量n

print(m+n+t) 				#输出1368



f(n)                    			#函数需要调用才有效果

print(n)                			#输出修改后的全局变量n的值:789




5.2.3不定长参数
在Python中，可以使用不定长参数，即在形参之前加一个星号“*”(该参数接收实参后成为一个元组)或两个星号“**”(该参数接收实参后成为一个字典，且实参应包含参数名和值，其中，参数名成为字典中的一个键，参数值成为该键对应的值)。注意，这与可迭代对象作为实参时在其之前加的*(把可迭代对象中的元素逐个取出成为值参)是不同的。
在形参之前加一个星号的不定长参数的示例如下。



def f(a,b,*c):#形参c之前带*，表示不定长参数

print("first:",a)

print("second:",b)

print("third:",c)  			#参数c接收实参后成为一个元组

print(*c)           			#此处的*表示逐个取元组c中的元素作为print()函数的值参



#第一个参数1传递给a，第二个参数2传递给b，剩余的三个参数传递给c

f(1,2,3,4,5)

#列表之前的*表示逐个取列表中的元素作为f()函数的值参

f(*［1,2,3,4,5］)         			#相当于f(1,2,3,4,5)




运行结果： 



first: 1

second: 2

third: (3, 4, 5)

3 4 5






first: 1

second: 2

third: (3, 4, 5)

3 4 5




在形参之前加两个星号的不定长参数的示例如下： 



def f(a,b,**c):#形参c之前带**，表示不定长参数

print("first:",a)

print("second:",b)

print("third:",c)   			#参数c接收实参后成为一个字典

print(*c)           			#此处的*表示逐个取字典c中的键作为print()函数的值参



#第一个参数1传递给a，第二个参数2传递给b，剩余的三个参数传递给c

f(1,2,x=3,y=4,z=5)      			#前两个参数之外的其他参数需有参数名和值




运行结果： 



first: 1

second: 2

third: {'x': 3, 'y': 4, 'z': 5}

x y z




5.2.4列表作函数参数
列表元素作为函数实参时，与普通变量作为函数实参是一致的，即把列表元素的值传递给实参，形参的变化不会影响实参。例如： 



def f(a):

a=123



b=［2,5,6］

f(b［1］)

print(b)




运行结果： 



［2, 5, 6］




列表名作为函数的参数，指的是形参和实参都使用列表名。此时形参列表是实参列表的引用，即在函数调用期间形参列表与实参列表是同一个列表，因此对形参列表的改变就是对实参列表的改变。例如： 



def g(a):

for i in range(len(a)):

a［i］=a［i］**3



b=［2,5,6］

g(b)

print(b)




运行结果： 



［8, 125, 216］




例5.2.1m趟选择排序
先在第一行输入整数n和m，再在第二行输入n个整数构成的数列，要求利用选择排序进行排序，并输出第m趟排序后的数列状况。请把选择排序定义为一个函数。
选择排序的思想和方法在前面的章节中已经讨论过，这里以函数的形式表达，且排序趟数以参数m控制,具体代码如下。



def selectSort(a,n,m):#对包含n个元素的整型列表a进行m趟排序

for i in range(0,m):            	#共进行m趟

for j in range(i+1,n):      	#扫描列表，若后面的数小于当前最前面的数，则交换

if a［j］<a［i］:    

a［i］,a［j］=a［j］,a［i］ #交换当前最前面的数和当前最小数的位置



n,m=map(int,input().split())        	#输入n,m

b=list(map(int,input().split()))    #输入列表b

selectSort(b,n,m)                   	#调用m趟选择排序的函数

print(*b)							#调用输出函数






运行结果： 



6 3 

3 5 1 2 8 6 

1 2 3 5 8 6




从运行结果可见，实参列表b在调用selectSort()函数之后发生了改变，即形参列表a的改变影响到了实参列表b。因为列表名作为函数参数时，传递的是引用，即形参列表是实参列表的别名，因此，在函数调用期间a［i］和b［i］(0≤i<n)同占一个存储单元，则对a［i］的改变就是对b［i］的改变。
5.2.5匿名函数
Python语言使用关键字lambda创建匿名函数，定义的形式如下。

［函数名=］lambda ［参数1［,参数2,…,参数n］］ : 表达式

lambda创建包含简单逻辑的函数，其参数位于lambda和冒号“：”之间，可以用0个或若干个参数，若有多个参数则以逗号“,”分隔，其主体部分(冒号之后)是一个表达式。可以通过赋值语句给匿名函数取名。例如： 



f1=lambda a,b: a if a>=b else b#创建包含两个参数的匿名函数，并取名为f1

print(f1(12,34))



c=1

f2=lambda a,b: c if a>b else 0   	#匿名函数的主体中只能使用参数和全局变量






print(f2(123,78))



f3=lambda a: a**3#一个参数的匿名函数，并取名为f3

print(f3(3))



f4=lambda : "Hello"              		#无参匿名函数，并取名为f4




运行结果： 



34

1

27

Hello




5.3函 数 举 例
例5.3.1素数判定函数
输入一个正整数n，判断n是否素数，是则输出“yes”，否则输出“no”(引号不必输出)。要求写一个判断一个正整数是否素数的函数。
关于n是否素数，根据前面章节所述，可以从2至n判断是否有n的因子，有则不是素数。这里只要把相关代码作为一个整体写成一个函数； 因为要判断一个数是否素数，所以该函数需要一个参数，具体代码如下。



from math import sqrt#导入函数sqrt()

def isPrime(n):                     	#判断n是否素数的函数

flag=True                       	#假设n是素数，标记设为True

k=int(sqrt(n))             		#求得sqrt(n)，整数部分存放在k中

for i in range(2,k+1):          	#从2到k判断是否存在n的因子

if n%i==0:                  	#若i是n的因子，则n不是素数，结束循环

flag=False

break

if n==1: flag=False             	#对1进行特判

return flag



n=int(input())

if isPrime(n)==True:                	#若n是素数

print("yes")

else:

print("no")




运行结果： 



2147483647 

yes




例5.3.2最小回文数
输入整数n，输出比该数大的最小回文数。其中回文数指的是正读、反读一样的数，如131，1221等。要求写一个判断一个整数是否为回文数的函数。
判断是否回文数可以调用例5.1.1中的求逆序数的函数revNum，判断该数与逆序数是否相等。因为要找比n大的最小回文数，可以从n+1开始逐个检查是否满足回文数的条件，第一个满足条件的数即为结果。



def revNum(n):#求逆序数的函数

s=0

while n>0:

s=s*10+n%10

n=n//10

return s



def isSymmetric(n):           #判断是否是回文数的函数

return n==revNum(n)      #若n等于其逆序数，则返回True，否则返回False



n=int(input())    

while True:

n+=1

if isSymmetric(n)==True:  #若n是回文数，则输出结果并结束循环

print(n)

break




运行结果： 



1234 

1331




5.4递 归 函 数
5.4.1递归函数基础

递归函数是直接或间接地调用自身的函数，可分为直接递归函数和间接递归函数。本书仅讨论直接递归函数。递归函数的两个要素是边界条件(递归出口)与递归方程(递归式)，只有具备了这两个要素，才能在有限次计算后得出结果。
对于简单的递归问题，关键是分析得出递归式，并在递归函数中用if语句表达。
例5.4.1递归函数求n!
递归式 n!=1,n=0,1

n(n-1)!,n>1
根据n!的递归式，直接用if语句表达。



def f(n):#函数定义

if n==1 or n==0:        	#递归出口

return 1

else:

return f(n-1)*n     #递归调用



n=int(input())

res=f(n)

print(res)                  	#调用，函数在调用之前定义




运行结果： 



5 

120




递归函数的执行分为扩展和回代两个阶段。例如，f(5)的调用先不断扩展到递归出口求出结果为1，然后逐步回代结果到各个调用点，最终的调用结果为120，如图51所示。



图51递归调用过程示意图


可以在Python教学网站(网址http://www.pythontutor.com/)可视化代码执行过程，下面给出调用f(5)的可视化执行过程的部分截图，如图52~图54所示。




图52可视化执行过程示意图1






图53可视化执行过程示意图2







图54可视化执行过程示意图3


递归是实现分治法和回溯法的有效手段。分治法是将一个难以直接解决的大问题，分割成一些规模较小的相似问题，各个击破，分而治之。回溯法是一种按照选优条件往前搜索，在不能再往前时回退到上一步再继续搜索的方法。
例5.4.2最大公约数函数
输入两个正整数a、b，求这两个整数的最大公约数。要求定义一个函数求最大公约数。
已知两个正整数的最大公约数是能够同时整除它们的最大正整数。求最大公约数可以用穷举法，也可以用辗转相除法(欧几里得算法)。
利用辗转相除法确定两个正整数a和b的最大公约数的算法思想如下。
若a%b=0，则b即为最大公约数，否则gcd(a，b) = gcd(b，a%b)。
即递归式如下。
gcd(a,b)=b,a%b=0

gcd(b,a%b),a%b!=0
根据辗转相除法的思想，求最大公约数的递归版和迭代版函数如下。



def gcd(m,n):#求最大公约数的递归函数

if m%n==0:                	#递归出口

return n

else:

return gcd(n,m%n)   	#递归调用



def gcdIt(m,n):             	#使用迭代法求最大公约数的函数

while m%n>0:

m,n=n,m%n

return n



a,b=map(int,input().split())

print(gcd(a,b))				#或调用gcdIt():print(gcdIt(a,b))




运行结果： 



27 63 

9




迭代法是一种不断地用变量的原值(旧值)递推出其新值的方法。例如，上面的迭代法代码中，不断地用m、n的旧值递推出新值。
通过调用以上定义的最大公约数函数，可以方便地求得两个整数的最小公倍数，也可以方便地求得多个整数的最大公约数或最小公倍数，具体代码实现留给读者自行完成。
5.4.2典型递归问题
例5.4.3斐波那契数列
意大利数学家列奥纳多·斐波那契(Leonardo Fibonacci)是12~13世纪欧洲数学界的代表人物。他提出的“兔子问题”引起了后人的极大兴趣。
“兔子问题”假定一对大兔子每一个月可以生一对小兔子，而小兔子出生后两个月就有繁殖能力，问从一对小兔子开始，n个月后能繁殖成多少对兔子？
这是一个递推问题，可以构造一个递推的表格（如表51）。


表51兔子问题递推表




时间/月
小兔/对
大兔/对
总数/对

1
1
0
1
2
0
1
1
3
1
1
2
4
1
2
3
5
2
3
5
6
3
5
8
7
5
8
13

从表51可得每月的兔子总数构成如下数列。
1，1，2，3，5，8，13，…
可以发现此数列的规律： 第一、二项是1，从第三项起，每一项都是前两项的和。
因此，可得递归式如下。
f(n)=1,n=1,2

f(n-1)+f(n-2),n>2
根据递归式，容易写出求斐波那契数列第n项的递归函数，具体代码如下。



def fib(n):#使用递归函数求斐波那契数列第n项

if n==1 or n==2:                	#递归出口

return 1

else:

return fib(n-1)+fib(n-2)   	#递归调用



n=int(input())

res=fib(n)

print(res)




运行结果： 



10 

55




若在本地运行时输入n为40，程序需要运行较长的时间才能得到结果，若在线提交一般将得到超时反馈。一般而言，递归的深度不宜过大，否则递归程序的执行效率过低，在线做题时将导致超时。此时可以考虑在递归的过程中，把已经计算出来的结果保存起来，在之后递归计算时先判断需要用的项的结果是否已保存，若是则直接取出来，否则再递归计算。这种在递归求解过程把中间结果保存起来，避免重复计算的方法称为记忆化搜索，具体代码如下。



N=47                            			#下标从1开始用，最多计算到第46项

s=［0］*N                         		#初值都为0，表示结果尚未计算出来  

s［1］=s［2］=1                   			#第一、二项为1

def f(n):

if n==1 or n==2:

return s［n］

else:

if s［n-2］==0:#若第n-2项未计算过，则递归计算

s［n-2］=f(n-2)

if s［n-1］==0:           		#若第n-1项未计算过，则递归计算

s［n-1］=f(n-1)

return s［n-1］+s［n-2］    		#直接使用已经计算出来的结果



n=int(input())

res=f(n)

print(res)




运行结果： 



46 

1836311903




另外，也可以采用迭代法求解以避免递归法求解时因递归深度过大而导致的超时。但是，在线做题时经常是多组测试的，设控制结构为T组测试，当T较大时，若每输入一个n就重新去计算一次则依然可能导致超时。为了避免在线做题超时，可以把斐波那契数列的所有项一次性算出来存放在外部列表(定义在函数之外的列表)中，输入数据后直接从列表中把结果取出来，即空间换时间，具体代码如下。



N=1001#设最多计算到第1000项

f=［0］*N                     			#外部列表

def init():                	 		#初始化函数

f［1］=f［2］=1

for n in range(3,N):

f［n］=f［n-1］+f［n-2］



init()                      			#调用一次，完成所有的计算

T=int(input())              			#输入测试组数T

for t in range(T):          			#循环T次

n=int(input())          			#输入n 

print(f［n］)             			#直接从列表中取出第n项并输出




运行结果： 



2 

40 

102334155

46 

1836311903




当然，把调用init()函数改为调用前面记忆化搜索方法的f()函数，即init()改为f(46)，也可以达到空间换时间的目的。实际上，记忆化搜索本身也体现了空间换时间的思想。
关于斐波那契数列，有许多有趣的知识，例如，斐波那契数列螺旋线(当海螺被切成两半的时候，它内腔壁的形状是“斐波那契螺旋线”形状)，或当斐波那契数列趋向于无穷大时，相邻两项的比值趋向于黄金分割比例0.618，读者可自行了解。
例5.4.4快速幂
输入两个整数a、b，如何高效地计算ab？
若b=32，设s=1，则用循环“for i in range(b) s *= a”将需要运算32次。
如果用二分法，则可以按a32→a16→a8→a4→a2→a1→a0的顺序来分析，在计算出a0后可以倒过去计算出a1直到a32。这与递归函数的执行过程是一致的，因此可以用递归方法求解。
二分法计算ab的要点举例说明如下。 
(1)  a10 = a5×a5
(2)  a9 = a4×a4×a 
即根据b的奇偶性来做不同的计算，b=0是递归出口。因此可得递归式如下： 
ab=1,b=0
ab2·ab2,b%2=0
ab2·ab2·a,b%2=1
根据递归式可以方便地实现递归函数。为减少重复计算从而提高程序执行效率，可以先计算ab2并存入临时变量中，具体代码如下。



def f(m,n):

if n==0:#递归出口

return 1

else:

t=f(m,n//2)         	#递归调用，用t暂存递归调用的结果，注意取整除//

if n%2==0:

return t*t

else:

return t*t*m



a,b=map(int,input().split())

res=f(a,b)

print(res)




运行结果： 



2 10 

1024




例5.4.5汉诺塔问题
设A、B、C是三个塔座。开始时，在塔座A上有n(1≤n≤64)个圆盘，这些圆盘自下而上，由大到小地叠在一起。例如，3个圆盘的汉诺塔问题初始状态如图55所示。现在要求将塔座A上的这些圆盘借助塔座B移到塔座C上，并仍按同样顺序叠放。在移动圆盘时应遵守以下移动规则。
规则(1)： 每次只能移动一个圆盘。
规则(2)： 任何时刻都不允许将较大的圆盘压在较小的圆盘之上。
规则(3)： 在满足移动规则(1)和(2)的前提下，可将圆盘移至A、B、C中任何一个塔座上。


图55汉诺塔问题示意图(3个圆盘)


设an表示n个圆盘从一个塔座全部转移到另一个塔座的移动次数，显然有a1 =1。当n≥2时，要将塔座A上的n个圆盘全部转移到塔座C上，可以采用以下步骤。
(1) 先把塔座A上的n-1个圆盘转移到塔座B上，移动次数为an-1。
(2) 然后把塔座A上的最后一个大圆盘转移到塔座C上，移动次数等于1。
(3) 最后再把塔座B上的 n-1个圆盘转移到塔座C上，移动次数为an-1。
经过这些步骤后，塔座A上的n个圆盘就全部转移到塔座C上。
由组合数学的加法规则，移动次数为2an-1+1。计算总的移动次数的递归关系式如下。
an=1,n=1

2an-1+1,n>1
求解该递归关系式，可得an=2n-1。例如： 
当n=3，移动7次； 
当n=4，移动15次； 
……
当n=64，移动264-1=18446744073709551615次，设每秒移动一次，完成所有64个圆盘的移动需要18446744073709551615/(365×24×60×60)/100000000≈5849.42（亿年）。
如果想知道具体是如何移动的，可以根据前面的步骤，把每次只有1个圆盘时的移动情况输出(调用下面的move()函数)。模拟汉诺塔问题中圆盘移动过程的具体程序如下。



def move(a,b):#输出移动状态

print(a,'-->',b, sep='')



def hanoi(n,a,b,c):         		#把n个圆盘从a移动到c，借助b

if n==1:                		#只有一个圆盘时直接移动

move(a,c)

else:

hanoi(n-1,a,c,b)    		#把n-1个圆盘从a移动到b，借助c

move(a,c)           		#最后一个圆盘直接移动

hanoi(n-1,b,a,c)    		#把n-1个圆盘从b移动到c，借助a



n=int(input())

hanoi(n,'A','B','C')




运行结果： 



3 

A-->C

A-->B

C-->B

A-->C

B-->A

B-->C

A-->C




若要输出总的移动次数，则该如何修改以上代码？若要输出移动的圆盘号，则又该如何修改以上代码？具体代码留给读者自行思考后实现。
5.5OJ题目求解
例5.5.1验证歌德巴赫猜想(HLOJ 1922)


Problem Description

歌德巴赫猜想之一是指一个偶数(2除外)可以拆分为两个素数之和。请验证这个猜想。
因为同一个偶数可能可以拆分为不同的素数对之和，这里要求结果素数对彼此最接近。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入一个偶数n(6≤n≤10000)。


Output

对于每组测试，输出两个彼此最接近的素数a、b(a≤b)，两个素数之间留一个空格。





Sample Input

2

30

40


Sample Output

13 17

17 23

本题可以先写一个判断某个正整数是否素数的函数，然后循环变量i从n//2处开始到2进行循环(请读者思考为什么)，若发现i(≤n//2)和n-i(≥n//2)同时是素数则得到结果并结束循环，具体代码如下。



from math import sqrt#导入sqrt()函数

def isPrime(n):#判断素数的函数

if (n<2):

return False

m=int(sqrt(n))

for i in range(2,m+1):

if n%i==0:

return False

return True



T=int(input())

for t in range(T):

n=int(input())

for i in range(n//2,1,-1):	#i从n//2到2循环，若i与n-i都是素数，则输出并结束

if isPrime(i)==True and isPrime(n-i)==True:

print(i,n-i)

break;




运行结果： 



3 

100 

47 53

50 

19 31

20 

7 13




回到请读者思考的问题，原因何在？因为两个素数的差值d=(n-i)-i=n-2i，当i越大时d越小，所以循环变量i从n//2处开始到2进行循环即可。
例5.5.2素数的排位(HLOJ 1954)


Problem Description

已知素数序列为2、3、5、7、11、13、17、19、23、29,…，即素数的第一个是2，第二个是3，第三个是5,…
那么，对于输入的一个任意整数n，若是素数，能确定是第几个素数吗？若不是素数，则输出0。


Input

测试数据有多组，处理到文件尾。每组测试输入一个正整数n(1≤n≤1000000)。


Output

对于每组测试，输出占一行，如果输入的正整数n是素数，则输出其排位，否则输出0。





Sample Input

13



Sample Output

6


Source
ZJUTOJ 1341

本题可以利用上题的isPrime()函数及空间换时间的思想一次性把排位计算出来放在列表中，输入数据时再直接从列表中取结果输出。但这种方法对每个数都要调用isPrime()函数，效率依然较低。若用筛选法的思想，则能较好地提高效率。实际上，可以改写筛选法的代码，筛选和排位同时进行，具体代码如下。



N=1000000

index=［1］*(N+1)#若i非素数则index［i］=0，否则index［i］为其排位

def init():#根据筛选法的思想确定各个素数的排位或筛去素数的倍数

index［0］=index［1］=0  

cnt=1;                         		#排位计数器

for i in range(2,N+1):       	#对2~N的每个数，确定素数的排位或筛去该数

if index［i］==0:continue 	#若i不是素数，则不需要用i作因子去筛其倍数

index［i］=cnt             		#若i是素数，则index［i］填上排位

cnt+=1                          #排位计数器加1

for j in range(i*i,N+1,i): 	#从i的平方开始，把i的倍数筛去






index［j］=0



init()#输入前调用一次把所有结果计算到index列表中

try:

while True:

n=int(input())

print(index［n］)          		#输入n后直接从index列表中取得结果并输出

except EOFError:pass




运行结果： 



13 

6

6 

0




例5.5.3母牛问题(HLOJ 1955)


Problem Description

设想一头小母牛从第4个年头开始每年生育一头小母牛。现有一头小母牛，按照此设想，第n年时有多少头母牛？


Input

测试数据有多组，处理到文件尾。每组测试输入一个正整数n(1≤n≤40)。


Output

对于每组测试，输出第n年时的母牛总数。





Sample Input

15



Sample Output

129


Source
ZJUTOJ 1182

本题也是一道递推题，递推表如表52所示。



表52母牛问题递推表



时间/年
小牛
中牛
大牛
总数

1
1
0
0
1
2
0
1
0
1
3
0
0
1
1
4
1
0
1
2
5
1
1
1
3
6
1
1
2
4
7
2
1
3
6
8
3
2
4
9
9
4
3
6
13
10
6
4
9
19

根据表52，可以得到如下数列： 
1、1、1、2、3、4、6、9、13、19，…
观察数列，可得递归式如下。
f(n)=1,n=1,2,3

f(n-1)+f(n-3),n≥4
根据递归式，容易写出使用递归法的函数，具体代码如下。



def f(n):#递归法

if n<4:

return 1

else:

return f(n-1)+f(n-3)



try:

while True:

n=int(input())

print(f(n))             	#调用递归函数

except EOFError:pass




运行结果： 



10 

19

20 

872




读者不妨再观察数列，尝试找到其他的递归式并编程实现。
另外，本题也可以采用空间换时间的思想： 一次性先把结果计算出来并放在列表中，然后在输入数据时从列表中取出数据。



N=41

a=［1］*N#外部列表，保存结果，空间换时间

a［0］=0

def init():                      	#一次性把所有结果计算出来存放在列表中                          

for i in range(4,N):

a［i］=a［i-1］+a［i-3］



init()



try:

while True:

n=int(input())

print(a［n］)           	#输入数据时直接从结果列表取得结果并输出

except EOFError:pass




运行结果： 



15 

129

30 

39865

40 

1822473




例5.5.4特殊排序(HLOJ 1923)


Problem Description

输入一个整数n和n个各不相等的整数，将这些整数从小到大进行排序，要求奇数在前，偶数在后。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入一个整数n(1<n<100)，再输入n个整数。
Ontput
对于每组测试，在一行上输出根据要求排序后的结果，数据之间留一个空格。





Sample Input


3

5 1 2 3 4 5

3 12 4 5

6 2 4 6 8 0 1


Sample Output

1 3 5 2 4

5 4 12

1 0 2 4 6 8


本题的关键函数是一个表明排序规则的比较函数cmp()，该函数要表达出奇数在前，偶数在后，并都按从小到大排序的要求； 可以先比较两个参数a，b的奇偶性，若奇偶性不一致，则判断a是否为奇数，若a为奇数则返回-1，否则返回1； 若奇偶性一致，则返回a-b(若a<b返回负数表示正序，若a==b返回0，若a>b返回正数表示逆序)。列表排序可采用成员函数sort()或者直接调用内置函数sorted()，在这两个函数中使用比较函数时需要使用从functools模块导入的cmp_to_key()函数把传统比较函数转换为一个关键字函数。这里调用sorted()函数实现排序，具体代码如下。



from functools import cmp_to_key 



def cmp(a,b):#比较函数

if a%2!=b%2:                    	#若a、b奇偶性不同

if a%2==1:                  	#若a为奇数则返回-1，否则返回1

return -1

else:

return 1

return a-b                      	#a-b为负数表示从小到大的正序，为正数表示逆序



T=int(input())






for t in range(T):

a=list(map(int,input().split()))

n=a［0］

a=a［1:］

a=sorted(a,key=cmp_to_key(cmp))#调用内置函数sorted()，返回结果赋值给a

print(*a)




运行结果： 



3 

5 1 2 3 4 5 

1 3 5 2 4

3 12 4 5 

5 4 12

6 2 4 6 8 0 1 

1 0 2 4 6 8




对于使用函数cmp_to_key()转换的比较函数，若要按题意正序则返回负数，否则返回正数。例如，上面的cmp(a,b)函数中，若奇偶性不同，则奇数在前为正序，因此在a为奇数时返回负数-1，在a为偶数时则是按题意的逆序，故返回正数1； 若奇偶性相同，则按题意的正序是从小到大，那么返回的a-b在正序时为负数，在逆序时为正数。请读者仔细体会本题的cmp()函数。
若使用列表的成员函数sort()实现排序，则可把上面代码的倒数第二句改为如下表达。



a. sort(key=cmp_to_key(cmp))




实际上，对于OJ做题，也可以从小到大直接排好序，在输出时先输出奇数，再输出偶数，具体代码留给读者自行完成。
例5.5.5平方和排序(HLOJ 1958)


Problem Description

输入N个非负整数，要求按各个整数的各数位上数字的平方和从小到大排序，若平方和相等则按数值从小到大排序。
例如，三个整数9、31、13各数位上数字的平方和分别为81、10、10，则排序结果为13、31、9。 


Input

测试数据有多组。每组数据先输入一个整数N(0<N<100)，然后输入N个非负整数。若N=0，则输入结束。


Output

对于每组测试，在一行上输出按要求排序后的结果，数据之间留一个空格。





Sample Input

9

12 567 91 33 657 812 2221 3 77

0


Sample Output

12 3 2221 33 812 91 77 567 657



Source
ZJUTOJ 1038


本题排序调用列表的成员函数sort()，其key参数为cmp_to_key()的返回结果，作为该函数的参数的比较函数cmp()根据题意编写，即在平方和不等时，按平方和从小到大正序，则返回前后两个参数的平方和之差即可； 在平方和相等时，按数值从小到大正序，则返回前后两个参数之差即可。方便起见，写一个函数求一个整数各数位上数字的平方和，具体代码如下。



from functools import cmp_to_key 



def cmp(a,b):#比较函数cmp()

sa=squareSum(a)

sb=squareSum(b)

if sa!=sb:                  	#若平方和不等，则按平方和从小到大

return sa-sb

return a-b                  	#若平方和相等，则按数值本身从小到大



def squareSum(n):               	#求各个数位平方和的函数

sum=0

while n:

sum+=(n%10)**2

n=n//10

return sum



while True:

n=int(input())

if n==0: break

a=list(map(int,input().split()))

a.sort(key=cmp_to_key(cmp))	#调用列表成员函数sort()实现排序

print(*a)




运行结果： 



5 

1 3 11 33 9 

1 11 3 33 9

0 




例5.5.6按长度排序(HLOJ 1956)


Problem Description

先输入一个正整数N，再输入N个整数，要求对N个整数进行排序： 先按长度从小到大排，若长度一样则按数值从小到大排。


Input

测试数据有多组。每组测试数据的第一行输入一个整数N(0<N<100)，第二行输入N个整数(每个整数最多可达80位)。若N=0，则输入结束。


Output

对于每组测试，输出排序后的结果，每个数据占一行。每两组测试结果之间留一个空行。





Sample Input

3

123

12

3333

0


Sample Output

12

123

3333


Source
ZJUTOJ 1030

本题用函数的方法来实现，数据存放在列表中，排序可调用列表的成员函数sort()。因此，本题主要是定义比较函数cmp()。根据题意，若长度不等，则长度从小到大为正序，否则数值从小到大为正序，与上一题类似，故可参照前一题的方法编写cmp()函数。为方便求得整数的长度，数据作为字符串类型处理。但字符串不能做减法，比较数据本身大小时可转换为整数处理。另外，输出时每两组测试结果之间留一个空行的要求，可用计数器的方法控制，具体代码如下。



from functools import cmp_to_key 

def cmp(a,b):#比较函数cmp()

la=len(a)

lb=len(b)

if la!=lb:                  	#若长度不等，则按长度前小后大

return la-lb

return int(a)-int(b)        	#若长度相等，则按数值前小后大



def output(a):                  	#输出函数

for i in range(len(a)):

print(a［i］)



cnt=0 							#控制每两组数据之间留一个空行的计数器

while True:

n=int(input())

if n==0: break

a=［""］*n                    	#为方便求长度，数据作为字符串处理

for i in range(n):

a［i］=input()

a.sort(key=cmp_to_key(cmp))	#调用列表成员函数sort()实现排序

cnt+=1                         	#每测试一组数据，计数器加1

if cnt>1:print()              #若不是第一组测试，则先输出一个空行

output(a)




运行结果： 



3 

31 

13 

9 

9

13

31

0 




例5.5.7按日期排序(HLOJ 1957)


Problem Description

输入若干日期，按日期从小到大排序。


Input

本题只有一组测试数据，且日期总数不超过100个。按“MM/DD/YYYY”(月/日/年，其中月份、日份各2位，年份4位)的格式逐行输入若干日期。


Output

按“MM/DD/YYYY”的格式输出已从小到大排序的各个日期，每个日期占一行。





Sample Input

12/31/2020

10/21/2021

02/12/2021

07/16/2009

01/01/2021


Sample Output

07/16/2009

12/31/2020

01/01/2021

02/12/2021

10/21/2021

Source
ZJUTOJ 1045


本题输入的日期格式是“月/日/年”的格式，而日期排序实际上是按年、月、日的顺序进行的，即先比年，若年相等再比月，若月也相等则再比日。因为日期格式固定为“MM/DD/YYYY”，可以分别取出年、月、日三个部分并连接为“YYYYMMDD”格式，再直接进行比较，具体代码如下。



from functools import cmp_to_key 



def cmp(a,b):#比较函数cmp()

a=a［6:］+a［:2］+a［3:5］	#a［6:］、a［:2］、a［3:5］分别取得a的年、月、日份

b=b［6:］+b［:2］+b［3:5］	#b［6:］、b［:2］、b［3:5］分别取得b的年、月、日份

if a<b:					#若前一个年份小于后一个年份，则返回-1，否则返回1

return -1

else:

return 1



def output(a): 				#输出函数






for i in range(len(a)):

print(a［i］)



a=［］  #a设置为空列表

try:                          	#控制输入数据到文件尾

while True:

t=input()

a.append(t)       	#输入数据添加到列表a中

except EOFError:pass

a.sort(key=cmp_to_key(cmp))	#列表a按比较函数指定规则排序

output(a)                    	#输出列表a




运行结果： 



10/29/2021 

10/29/2020 

07/16/2020 

07/15/2020 

07/15/2020

07/16/2020

10/29/2020

10/29/2021




本题还可以用字典列表或对象列表进行排序的方法求解，读者可自行尝试编程实现。
例5.5.8解题排行(HLOJ 1925)


Problem Description

解题排行榜中，按解题总数生成排行榜。假设每个学生信息仅包括学号、解题总数； 要求先输入n个学生的信息； 然后按“解题总数”降序排列，若“解题总数”相同则按“学号”升序排列。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。
每组测试数据先输入一个正整数n(1≤n≤100)，表示学生总数。然后输入n行，每行包括一个不含空格的字符串s(不超过8位)和一个正整数d，分别表示一个学生的学号和解题总数。


Output

对于每组测试数据，输出最终排名信息，每行一个学生的信息： 排名、学号、解题总数。每行数据之间留一个空格。注意，解题总数相同的学生其排名也相同。





Sample Input

1

4

0010 200

1000 110

0001 200

0100 225


Sample Output

1 0100 225

2 0001 200

2 0010 200

4 1000 110


根据题意，宜把学生信息，即学号和解题总数作为一个整体，此要求可以把每个学生信息作为一个字典(键分别设为"id"、"solved")； 在比较规则的表达方面，可以写一个比较函数cmp()： 若解题总数不等，则按解题总数从大到小为正序，否则按学号从小到大为正序； 排序方面，对按输入数据创建的字典列表排序(直接使用列表的sort()函数，并指定其key参数为cmp_to_key()的返回值)； 排名处理方面，设排名变量r初值为1，可以在按要求排好序之后先输出第一个人的排名及其学号和解题总数，从第二个人开始与前一个人的解题总数相比，若不等则r改为序号(即其下标加1)，否则r保持不变，具体代码如下。



from functools import cmp_to_key#导入函数cmp_to_key()



def cmp(x,y):                           			#比较函数

if x［"solved"］!=y［"solved"］:        			

return y［"solved"］-x［"solved"］			#以解题总数从大到小为正序

if x［"id"］<y［"id"］:                 			#以学号从小到大为正序

return -1

else:

return 1



T=int(input())

for t in range(T):

n=int(input())

a=［］                                    			#创建空列表

for i in range(n):                      		#根据输入数据创建字典列表

idx,solved=input().split()

a.append({"id":idx,"solved":int(solved)})     

a.sort(key=cmp_to_key(cmp))             		#列表排序

print(1,a［0］［"id"］,a［0］［"solved"］)      		#输出第一名的信息

r=1                                     			#排名变量设置初值

for i in range(1,n):                    		#输出其他人的信息

if a［i］［"solved"］!=a［i-1］［"solved"］:	#若后一个人的解题数与前一个不等

r=i+1                           		#则排名变量设为序号

print(r,a［i］［"id"］,a［i］［"solved"］)




运行结果： 



4 

0010 200 

1000 110 

0001 200 

0100 225 

1 0100 225

2 0001 200

2 0010 200

4 1000 110




上面的代码中，比较函数cmp()是比较简洁的写法，其效果与以下比较函数相同。



def cmp(x,y):#比较函数,第一个参数为x，第二个参数为y

if x［"solved"］<y［"solved"］:     	#若x的解题总数小于y的解题总数

return 1                       	#则返回正数表示逆序

elif x［"solved"］>y［"solved"］: 	#若x的解题总数大于y的解题总数

return -1                  	#则返回负数表示正序

elif x［"id"］<y［"id"］:         	#当解题总数相等时，若x的学号小于y的学号

return -1                		#则返回负数表示正序

else:                       		#若x的学号大于y的学号

return 1                   	#则返回正数表示逆序




若本题的排序要求去掉“若解题总数相同则按学号升序排列”的要求，则可以不定义比较函数cmp()，直接使用匿名函数作为列表成员函数sort()的关键字(key)参数，具体代码如下。



n=int(input())

a=［］#创建空列表

for i in range(n):                              	#根据输入数据创建字典列表

idx,solved=input().split()

a.append({"id":idx,"solved":int(solved)})     

a.sort(key=lambda it:it［"solved"］,reverse=True)#列表排序，按解题总数逆序

print(1,a［0］［"id"］,a［0］［"solved"］)              	#输出第一名的信息

r=1                                             		#排名变量设置初值

for i in range(1,n):                            	#输出其他名次信息

if a［i］［"solved"］!=a［i-1］［"solved"］:        	#若后一个人的解题总数与前一个不等

r=i+1                                   		#则排名变量设为序号

print(r,a［i］［"id"］,a［i］［"solved"］)




运行结果： 



4 

0010 200 

1000 110 

0001 200 

0100 225 

1 0100 225

2 0010 200

2 0001 200

4 1000 110




上面调用列表的成员函数sort()时，其参数key设为lambda it： it［"solved"］，表示按匿名函数的参数it的键"solved"对应的值升序排序，而参数reverse设为True，则表示对排序结果进行逆序处理。
例5.5.9确定最终排名(HLOJ 1926) 


Problem Description

某次程序设计竞赛时，最终排名采用的排名规则如下。
根据成功做出的题数(设为solved)从大到小排序，若solved相同则按输入顺序确定排名先后顺序(请结合Sample Output)。请确定最终排名并输出。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。
每组测试数据先输入一个正整数n(1≤n≤100)，表示参赛队伍总数。然后输入n行，每行包括一个字符串s(不含空格且长度不超过50)和一个正整数d(0≤d≤15)，分别表示队名和该队的解题数量。


Output

对于每组测试数据，输出最终排名。每行一个队伍的信息： 排名、队名、解题数量。





Sample Input

1

8

Team22 2

Team16 3

Team11 2

Team20 3

Team3 5

Team26 4

Team7 1

Team2 4


Sample Output

1 Team3 5

2 Team26 4

3 Team2 4

4 Team16 3

5 Team20 3

6 Team22 2

7 Team11 2

8 Team7 1



本题宜把队名和解题数作为一个整体处理，可以采用字典列表求解。从题面看，本题的字典包含队名("name")和解题数("solved")两个键。由于题目要求“在解题数相同时按输入顺序确定名次”，因此增加一个序号("index")作为键，在比较函数中先按解题数比较，解题数相同再按序号比较。排序直接使用列表的成员函数sort()。另外，因为本题中的排名即排好序之后的顺序号，可以直接输出顺序号(下标加1)而不需要做特别处理，具体代码如下。



from functools import cmp_to_key#导入函数cmp_to_key()

def cmp(x,y):                           		#比较函数cmp()

if x［"solved"］!=y［"solved"］:			#以解题数从大到小为正序

return y［"solved"］-x［"solved"］

return x［"index"］-y［"index"］			#以序号从小到大为正序



T=int(input())

for t in range(T):

n=int(input())

a=［］                                    		#a设置为空列表

for i in range(n):                      	#根据输入数据构建字典添加到列表a中

name,solved=input().split()

a.append({"name":name,"solved":int(solved),"index":i+1})     

a=sorted(a,key=cmp_to_key(cmp))         	#按比较函数进行排序

for i in range(n):                      	#输出数据

print(i+1,a［i］［"name"］,a［i］［"solved"］)




运行结果： 



8 

Team22 2 

Team16 3 

Team11 2 

Team20 3 

Team3 5 

Team26 4 

Team7 1 

Team2 4 

1 Team3 5

2 Team26 4

3 Team2 4

4 Team16 3

5 Team20 3

6 Team22 2

7 Team11 2

8 Team7 1




习题
一、 选择题
1. Python语言中自定义函数的关键字是()。

A. classB. returnC. defD. for
2. Python语言中的自定义函数若未用return语句返回值，则该函数返回的是()。
A.  随机数B. NoneC. 0D. 不确定
3. 被调函数返回给主调函数的值称为()。
A.  形参B. 实参C. 返回值D. 参数
4. 关于Python语言中的自定义函数，说法错误的是()。
A.  函数可以嵌套调用
B. 函数可以嵌套定义
C.  函数的参数不需要指定类型
D. 无参函数定义可以省略函数名后的()
5. 以下代码段不可能输出的是()。

from random import *

a=randint(10,20)

print(a)

A.  10B. 15C. 20D. 25
6. 被调函数通过()语句，将值返回给主调函数。
A.  returnB. forC. whileD. if
7. 以下代码段的执行结果为()。

def f(a,b=3,c=5):

return a+b**2+c**3

print(f(b=4,a=2),f(3,8),f(7,2,3))

A. 143 192 38B. 192 143 38C. 38 143 192D. 语句出错
8. 以下代码段的执行结果为()。

def f(b):

b［1］=5



a=［0,1,2,3］

f(a)

print(a)

A. ［5, 1, 2, 3］B. ［0, 1, 2, 3］C. ［0, 5, 2, 3］D. 以上都不对
9. 以下代码段的执行结果为()。

def f(b):

b=5



a=［0,1,2,3］

f(a［1］)

print(a)

A. ［5, 1, 2, 3］B. ［0, 1, 2, 3］C. ［0, 5, 2, 3］D. 以上都不对
10. 递归函数的两个要素是()。

A.  函数头、函数体B. 递归出口、边界条件
C.  边界条件、递归方程D. 递归式、递归方程
11. 以下代码段的执行结果为()。

def f(n):

if n<3:

return n

else:

return f(n-1)+f(n-2)



print(f(8))

A.  34B. 21C.13D. 以上都不对
12. 关于列表名作为函数参数的说法错误的是()。
A.  参数传递时，把实参列表的引用传递给形参列表
B.  在函数调用期间，形参列表的改变就是实参列表的改变
C.  通过列表名作为函数参数，可以达到返回多个值的目的
D.  在函数调用期间，形参列表和实参列表是不同的
13. 以下代码段的执行结果为()。

m=3

def f():

global m

m=1

f()

print(m)

A.  3B. 1C. 随机数D. 以上都不对
二、 OJ编程题
1. 进制转换(HLOJ 2053) 


Problem Description

将十进制整数n(-231≤n≤231-1)转换成k(2≤k≤16)进制数。注意，10~15分别用字母A、B、C、D、E、F表示。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据输入两个整数n和k。 


Output

对于每组测试，先输出n，然后输出一个空格，最后输出对应的k进制数。





Sample Input

3

123 16

0 5

-12 2


Sample Output

123 7B

0 0

-12 -1100


2. 整数转换为字符串(HLOJ 2054)


Problem Description

将一个整数n转换成字符串。例如,输入483，应得到字符串"483"。其中，要求用一个递归函数实现把一个正整数转换为字符串。


Input

测试数据有多组，处理到文件尾。每组测试数据输入一个整数n(-231≤n≤231-1)。


Output

对于每组测试，输出转换后的字符串。





Sample Input

1234


Sample Output

1234


3. 多个数的最小公倍数(HLOJ 2093)


Problem Description

两个整数公有的倍数称为它们的公倍数，其中最小的一个正整数称为它们两个的最小公倍数。当然，n个数也可以有最小公倍数，例如,5，7，15的最小公倍数是105。
输入n个数，请计算它们的最小公倍数。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。
每组测试先输入一个整数n(2≤n≤20)，再输入n个正整数(属于［1，100000］范围内)。这里保证最终的结果在［-231, 231-1］范围内。


Output

对于每组测试，输出n个整数的最小公倍数。





Sample Input

2

3 5 7 15

5 1 2 4 3 5


Sample Output

105

60

4. 互质数(HLOJ 2055)


Problem Description

Sg认识到互质数很有用。若两个正整数的最大公约数为1，则它们是互质数。要求编写函数判断两个整数是否互质数。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入一个整数n(1≤n≤100)，再输入n行，每行有一对整数a、b(0<a，b<109)。


Output

对于每组测试数据，输出有多少对互质数。





Sample Input

1

2

3 11

5 11


Sample Output

2




5. 五位以内的对称素数(HLOJ 2094)


Problem Description

判断一个数是否为对称且不大于五位数的素数。要求判断对称和判断素数各写一个函数。


Input

测试数据有多组，处理到文件尾。每组测试输入一个正整数n(0<n<232)。


Output

对于每组测试，若n是不大于五位数的对称素数，则输出“Yes”，否则输出“No”。每个判断结果单独列一行。引号不必输出。





Sample Input

101


Sample Output

Yes


Source
ZJUTOJ 1187

6. 最长的单词(HLOJ 2056)


Problem Description

输入一个字符串，将此字符串中最长的单词输出。要求至少使用一个自定义函数。


Input

测试数据有多组，处理到文件尾。每组测试数据输入一个字符串(长度不超过80)。


Output

对于每组测试，输出字符串中的最长单词，若有多个长度相等的最长单词，输出最早出现的那个。这里规定，单词只能由大小写英文字母构成。





Sample Input

Keywords insert, two way insertion sort,

Abstract This paper discusses three method for two way insertion


Sample Output

insertion

discusses


7. 按1的个数排序(HLOJ 2057)


Problem Description

对于给定若干由0、1构成的字符串(长度不超过80)，要求将它们按1的个数从小到大排序。若1的个数相同，则按字符串本身从小到大排序。要求至少使用一个自定义函数。


Input

测试数据有多组，处理到文件尾。对于每组测试，首先输入一个整数n(1≤n≤100)，然后输入n行，每行包含一个由0、1构成的字符串。


Output

对于每组测试，输出排序后的结果，每个字符串占一行。






Sample Input

3

10011111

00001101

1010101


Sample Output

00001101

1010101

10011111


8. 旋转方阵(HLOJ 2058)


Problem Description

对于一个奇数n阶方阵，请给出经过顺时针方向m次旋转后的结果。每次旋转90°。


Input

测试数据有多组，处理到文件尾。每组测试的第一行输入两个整数n，m(1<n<20，1≤m≤100)，接下来输入n行数据，每行n个整数。


Output

对于每组测试，输出奇数阶方阵经过m次顺时针方向旋转后的结果。每行中各数据之间留一个空格。 





Sample Input

3 2

4 9 2

3 5 7

8 1 6


Sample Output

6 1 8

7 5 3

2 9 4

9. 求矩阵中的逆鞍点(HLOJ 2059)


Problem Description

求出n×m二维整数列表中的所有逆鞍点。这里的逆鞍点是指在其所在的行上最大，在其所在的列上最小的元素。若存在逆鞍点，则输出所有逆鞍点的值及其对应的行、列下标。若不存在逆鞍点，则输出“Not”。要求至少使用一个自定义函数。


Input

测试数据有多组，处理到文件尾。每组测试的第一行输入n和m(都不大于100)，第二行开始的n行每行输入m个整数。


Output

对于每组测试，若存在逆鞍点，则按行号从小到大、同一行内按列号从小到大的顺序逐行输出每个逆鞍点的值和对应的行、列下标，各行每两个数据之间一个空格； 若不存在逆鞍点，则输出“Not”(引号不必输出)。





Sample Input

3 3

97 66 96

85 36 35

88 67 91


Sample Output

85 1 0





10. 数字螺旋方阵(HLOJ 2060)


Problem Description

已知n=5时的螺旋方阵如Sample Output所示。输入一个正整数n，要求输出n×n个数字构成的螺旋方阵。


Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入一个正整数n(n≤20)。


Output

对于每组测试，输出n×n的数字螺旋方阵。各行中的每个数据按4位宽度输出。





Sample Input

1

5





Sample Output

2524232221

1098720

1121619

1234518

1314151617

2524232221

1098720

1121619

1234518

1314151617
















第6章
类 与 对 象





6.1引例
例6.1.1进步排行榜(HLOJ 1924)


Problem Description

假设每个学生信息包括“用户名”“进步总数”和“解题总数”。解题进步排行榜中，按“进步总数”及“解题总数”生成排行榜。要求先输入n个学生的信息； 然后按“进步总数”降序排列； 若“进步总数”相同，则按“解题总数”降序排列； 若“进步总数”和“解题总数”都相同，则排名相同，但输出信息时按“用户名”升序排列。


Input

首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据先输入一个正整数n(1<n<50)，表示学生总数。然后输入n行，每行包括一个不含空格的字符串s(不超过8位)和两个正整数d和t，分别表示用户名、进步总数和解题总数。


Output

对于每组测试，输出最终排名。每行一个学生的信息，分别是排名、用户名、进步总数和解题总数。每行的各个数据之间留一个空格。注意，进步总数和解题总数都相同的学生其排名也相同。





Sample Input

1

6

usx15131 21 124

usx15101 27 191

usx15113 31 124

usx15136 18 199

usx15117 27 251

usx15118 21 124


Sample Output

1 usx15113 31 124

2 usx15117 27 251

3 usx15101 27 191

4 usx15118 21 124

4 usx15131 21 124

6 usx15136 18 199




对于本题，根据本章之前的知识，一种方法是定义三个一维列表，根据排序要求，分情况进行调整，但要注意三个列表同步进行，代码比较冗长，也不便于使用一个列表成员函数sort()完成排序。有没有更好的方法呢？能否把学生的信息作为一个整体呢？
答案是肯定的，可以用字典或类把学生信息作为一个整体组织在一起。这里采用定义一个类并用该类变量(对象)列表处理学生信息的方法，本题具体代码如下。



from functools import cmp_to_key

class S:#定义类S

def __init__(self, name, diff, total): 	#初始化函数

self.name=name                      	#"用户名"成员

self.diff=diff                      	#"进步总数"成员

self.total=total                    	#"解题总数"成员



def cmp(x,y):                               		#比较函数cmp()

if x.diff!=y.diff:                      	#若"进步总数"不等

return y.diff-x.diff                	#则按"进步总数"从大到小

if x.total!=y.total:                    	#若"解题总数"不等

return y.total-x.total              	#则按"解题总数"从大到小

if x.name<y.name:                       	#按"用户名"从小到大

return -1

else:

return 1



T=int(input())

for t in range(T):

n=int(input())

a=［］#定义空列表a

for i in range(n):

name,diff,total=input().split()

#按输入数据构造S类对象并添加到列表中

a.append(S(name,int(diff),int(total)))

#列表排序，使用cmp_to_key()把比较函数转换为键函数

a.sort(key=cmp_to_key(cmp)) 

r=1                                     		#名次变量置初值1

print(r,a［0］.name,a［0］.diff,a［0］.total)	#输出第1名的信息    

for i in range(1,n):                    	#输出头名之外的其他人信息

#若进步总数或解题总数与前一个对象不同，则名次改为序号

if a［i］.diff!=a［i-1］.diff or a［i］.total!=a［i-1］.total:

r=i+1                           

print(r,a［i］.name,a［i］.diff,a［i］.total)