函数(经典案例18例)
- 1.斐波那契
- 2.使用递归法对整数进行因数分解
- 3.编写并使用能够生成斐波那契数列的生成器函数
- 4 编写函数,接收字符串参数,返回一个元组,其中第一个元素为大写字母个数,第二个元素为小写字母个数
- 5.编写函数,接收一个整数t为参数,打印杨辉三角前t行
- 6. 编写函数,接收一个正偶数为参数,输出两个素数,并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数,则全部输出。
- 7 . 编写函数,计算字符串匹配的准确率。 以打字练习程序为例,假设origin为原始内容,userInput为用户输入的内容,下面的代码用来测试用户输入的准确率。
- 8. 编写函数模拟猜数游戏。系统随机产生一个数,玩家最多可以猜5次,系统会根据玩家的猜测进行提示,玩家则可以根据系统的提示对下一次的猜测进行适当调整。
- 9. 编写函数模拟报数游戏。有n个人围成一圈,顺序编号,从第一个人开始从1到k(假设k=3)报数,报到k的人退出圈子,然后圈子缩小,从下一个人继续游戏,问最后留下的是原来的第几号。
- 10 汉诺塔问题基于递归算法的实现。
- 11 .编写函数计算任意位数的黑洞数。黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数字是6174,因为7641-1467=6174。
- 12 编写函数,使用算法实现冒泡排序算法。
- 13.编写函数,模拟选择法排序。
- 14 编写函数,模拟二分法查找。
- 15 编写函数,查找给定序列的最长递增子序列。
- 16 编写函数,寻找给定序列中相差最小的两个数字。
- 17.利用蒙特.卡罗方法计算圆周率近似值。
- 18 模拟蒙蒂霍尔悖论游戏。
1.斐波那契
##编写斐波那契数列的函数并调用
def fib(n):##n是形参
a,b =1,1
while a<n:
print(a,end=' ')
a,b=b,a+b
print(a,b)
fib(1000)
2.使用递归法对整数进行因数分解
from random import randint
def factors(num, fac=[]):
#每次都从2开始查找因数
for i in range(2, int(num**0.5)+1):
#找到一个因数
if num%i == 0:
fac.append(i)
#对商继续分解,重复这个过程
factors(num//i, fac)
#注意,这个break非常重要
break
else:
#不可分解了,自身也是个因数
fac.append(num)
facs = []
n = randint(2, 10**8)
factors(n, facs)
result = '*'.join(map(str, facs))
if n==eval(result):
print(n, '= '+result)
3.编写并使用能够生成斐波那契数列的生成器函数
def f():
a, b = 1, 1 #序列解包,同时为多个元素赋值
while True:
yield a #暂停执行,需要时再产生一个新元素
a, b = b, a+b #序列解包,继续生成新元素
a = f() #创建生成器对象
for i in range(10): #斐波那契数列中前10个元素
print(a.__next__(), end=' ')
4 编写函数,接收字符串参数,返回一个元组,其中第一个元素为大写字母个数,第二个元素为小写字母个数
def demo(s):
result = [0, 0]
for ch in s:
if ch.islower():
result[1] += 1
elif ch.isupper():
result[0] += 1
return tuple(result)
5.编写函数,接收一个整数t为参数,打印杨辉三角前t行
def yanghui(t):
print([1])
line = [1, 1]
print(line)
for i in range(2, t):
r = []
for j in range(0, len(line)-1):
r.append(line[j]+line[j+1])
line = [1]+r+[1]
print(line)
6. 编写函数,接收一个正偶数为参数,输出两个素数,并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数,则全部输出。
def demo(n):
def IsPrime(p):
if p == 2:
return True
if p%2 == 0:
return False
for i in range(3, int(p**0.5)+1, 2):
if p%i==0:
return False
return True
if isinstance(n, int) and n>0 and n%2==0:
for i in range(2, n//2+1):
if IsPrime(i) and IsPrime(n-i):
print(i, '+', n-i, '=', n)
7 . 编写函数,计算字符串匹配的准确率。 以打字练习程序为例,假设origin为原始内容,userInput为用户输入的内容,下面的代码用来测试用户输入的准确率。
def Rate(origin, userInput):
if not (isinstance(origin, str) and isinstance(userInput, str)):
print('The two parameters must be strings.')
return
right = sum((1 for o, u in zip(origin, userInput) if o==u))
return round(right/len(origin), 2)
8. 编写函数模拟猜数游戏。系统随机产生一个数,玩家最多可以猜5次,系统会根据玩家的猜测进行提示,玩家则可以根据系统的提示对下一次的猜测进行适当调整。
from random import randint
def guess(maxValue=100, maxTimes=5):
#随机生成一个整数
value = randint(1,maxValue)
for i in range(maxTimes):
prompt = 'Start to GUESS:' if i==0 else 'Guess again:'
#使用异常处理结构,防止输入不是数字的情况
try:
x = int(input(prompt))
except:
print('Must input an integer between 1 and ', maxValue)
else:
#猜对了
if x == value:
print('Congratulations!')
break
elif x > value:
print('Too big')
else:
print('Too little')
else:
#次数用完还没猜对,游戏结束,提示正确答案
print('Game over. FAIL.')
print('The value is ', value)
9. 编写函数模拟报数游戏。有n个人围成一圈,顺序编号,从第一个人开始从1到k(假设k=3)报数,报到k的人退出圈子,然后圈子缩小,从下一个人继续游戏,问最后留下的是原来的第几号。
from itertools import cycle
def demo(lst, k):
#切片,以免影响原来的数据
t_lst = lst[:]
#游戏一直进行到只剩下最后一个人
while len(t_lst)>1:
#创建cycle对象
c = cycle(t_lst)
#从1到k报数
for i in range(k):
t = next(c)
#一个人出局,圈子缩小
index = t_lst.index(t)
t_lst = t_lst[index+1:] + t_lst[:index]
#游戏结束
return t_lst[0]
lst = list(range(1,11))
print(demo(lst, 3))
10 汉诺塔问题基于递归算法的实现。
据说古代有一个梵塔,塔内有三个底座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,在移动盘子的过程中可以利用B座,但任何时刻3个座上的盘子都必须始终保持大盘在下、小盘在上的顺序。如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C即可。和尚想知道这项任务的详细移动步骤和顺序。这实际上是一个非常巨大的工程,是一个不可能完成的任务。根据数学知识我们可以知道,移动n个盘子需要2^n-1步,64个盘子需要18446744073709551615步。如果每步需要一秒钟的话,那么就需要584942417355.072年。
def hannoi(num, src, dst, temp=None):
#声明用来记录移动次数的变量为全局变量
global times
#确认参数类型和范围
assert type(num) == int, 'num must be integer'
assert num > 0, 'num must > 0'
#只剩最后或只有一个盘子需要移动,这也是函数递归调用的结束条件
if num == 1:
print('The {0} Times move:{1}==>{2}'.format(times, src, dst))
times += 1
else:
#递归调用函数自身,
#先把除最后一个盘子之外的所有盘子移动到临时柱子上
hannuo(num-1, src, temp, dst)
#把最后一个盘子直接移动到目标柱子上
hannuo(1, src, dst)
#把除最后一个盘子之外的其他盘子从临时柱子上移动到目标柱子上
hannuo(num-1, temp, dst, src)
#用来记录移动次数的变量
times = 1
#A表示最初放置盘子的柱子,C是目标柱子,B是临时柱子
hannoi(3, 'A', 'C', 'B')
11 .编写函数计算任意位数的黑洞数。黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数字是6174,因为7641-1467=6174。
def main(n):
'''参数n表示数字的位数,例如n=3时返回495,n=4时返回6174'''
#待测试数范围的起点和结束值
start = 10**(n-1)
end = 10**n
#依次测试每个数
for i in range(start, end):
#由这几个数字组成的最大数和最小数
big = ''.join(sorted(str(i),reverse=True))
little = ''.join(reversed(big))
big, little = map(int,(big, little))
if big-little == i:
print(i)
n = 4
main(n)
12 编写函数,使用算法实现冒泡排序算法。
from random import randint
def bubbleSort(lst, reverse=False):
length = len(lst)
for i in range(0, length):
flag = False
for j in range(0, length-i-1):
#比较相邻两个元素大小,并根据需要进行交换,默认升序排序
exp = 'lst[j] > lst[j+1]'
#如果reverse=True则降序排序
if reverse:
exp = 'lst[j] < lst[j+1]'
if eval(exp):
lst[j], lst[j+1] = lst[j+1], lst[j]
#flag=True表示本次扫描发生过元素交换
flag = True
#如果一次扫描结束后,没有发生过元素交换,说明已经按序排列
if not flag:
break
13.编写函数,模拟选择法排序。
def selectSort(lst, reverse=False):
length = len(lst)
for i in range(0, length):
#假设剩余元素中第一个最小或最大
m = i
#扫描剩余元素
for j in range(i+1, length):
#如果有更小或更大的,就记录下它的位置
exp = 'lst[j] < lst[m]'
if reverse:
exp = 'lst[j] > lst[m]'
if eval(exp):
m = j
#如果发现更小或更大的,就交换值
if m!=i:
lst[i], lst[m] = lst[m], lst[i]
14 编写函数,模拟二分法查找。
def binarySearch(lst, value):
start = 0
end = len(lst)
while start < end:
#计算中间位置
middle = (start + end) // 2
#查找成功,返回元素对应的位置
if value == lst[middle]:
return middle
#在后面一半元素中继续查找
elif value > lst[middle]:
start = middle + 1
#在前面一半元素中继续查找
elif value < lst[middle]:
end = middle - 1
#查找不成功,返回False
return False
15 编写函数,查找给定序列的最长递增子序列。
from itertools import combinations
from random import sample
def subAscendingList(lst):
'''返回最长递增子序列'''
for length in range(len(lst), 0, -1):
#按长度递减的顺序进行查找和判断
for sub in combinations(lst, length):
#判断当前选择的子序列是否为递增顺序
if list(sub) == sorted(sub):
#找到第一个就返回
return sub
def getList(start=0, end=1000, number=20):
'''生成随机序列'''
if number > end-start:
return None
return sample(range(start, end), number)
def main():
#生成一个包含10个随机数的列表进行测试
lst = getList(number=10)
if lst:
print(lst)
print(subAscendingList(lst))
main()
16 编写函数,寻找给定序列中相差最小的两个数字。
import random
def getTwoClosestElements(seq):
#先进行排序,使得相邻元素最接近
#相差最小的元素必然相邻
seq = sorted(seq)
#无穷大
dif = float('inf')
#遍历所有元素,两两比较,比较相邻元素的差值
#使用选择法寻找相差最小的两个元素
for i,v in enumerate(seq[:-1]):
d = abs(v - seq[i+1])
if d < dif:
first, second, dif = v, seq[i+1], d
#返回相差最小的两个元素
return (first, second)
seq = [random.randint(1, 10000) for i in range(20)]
print(seq)
print(sorted(seq))
print(getTwoClosestElements(seq))
17.利用蒙特.卡罗方法计算圆周率近似值。
from random import random
def estimatePI(times):
hits = 0
for i in range(times):
x = random()*2 - 1 #random()生成介于0和1之间的小数
y = random()*2 - 1 #该数字乘以2再减1,则介于-1和1之间
if x*x + y*y <= 1: #落在圆内或圆周上
hits += 1
return 4.0 * hits/times
print(estimatePI(10000))
print(estimatePI(1000000))
print(estimatePI(100000000))
print(estimatePI(1000000000))
18 模拟蒙蒂霍尔悖论游戏。
from random import randrange
def init():
'''返回一个字典,键为3个门号,值为门后面的物品'''
result = {i: 'goat' for i in range(3)}
r = randrange(3)
#在某个随机的门后面放一辆汽车,其他两个门后面仍然是山羊
result[r] = 'car'
return result
def startGame():
#获取本次游戏中每个门的情况
doors = init()
#获取玩家选择的门号
while True:
try:
firstDoorNum = int(input('Choose a door to open:'))
assert 0<= firstDoorNum <=2
break
except:
print('Door number must be between {} and {}'.format(0, 2))
#主持人查看另外两个门后的物品情况
#字典的keys()方法返回结果可以当作集合使用,支持使用减法计算差集
for door in doors.keys()-{firstDoorNum}:
#打开其中一个后面为山羊的门
if doors[door] == 'goat':
print('"goat" behind the door', door)
#获取第三个门号,让玩家纠结
thirdDoor = (doors.keys()-{door, firstDoorNum}).pop()
change = input('Switch to {}?(y/n)'.format(thirdDoor))
finalDoorNum = thirdDoor if change=='y' else firstDoorNum
if doors[finalDoorNum] == 'goat':
return 'I Win!'
else:
return 'You Win.'
while True:
print('='*30)
print(startGame())
r = input('Do you want to try once more?(y/n)')
if r == 'n':
break
函数(经典案例18例)
- 1.斐波那契
- 2.使用递归法对整数进行因数分解
- 3.编写并使用能够生成斐波那契数列的生成器函数
- 4 编写函数,接收字符串参数,返回一个元组,其中第一个元素为大写字母个数,第二个元素为小写字母个数
- 5.编写函数,接收一个整数t为参数,打印杨辉三角前t行
- 6. 编写函数,接收一个正偶数为参数,输出两个素数,并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数,则全部输出。
- 7 . 编写函数,计算字符串匹配的准确率。 以打字练习程序为例,假设origin为原始内容,userInput为用户输入的内容,下面的代码用来测试用户输入的准确率。
- 8. 编写函数模拟猜数游戏。系统随机产生一个数,玩家最多可以猜5次,系统会根据玩家的猜测进行提示,玩家则可以根据系统的提示对下一次的猜测进行适当调整。
- 9. 编写函数模拟报数游戏。有n个人围成一圈,顺序编号,从第一个人开始从1到k(假设k=3)报数,报到k的人退出圈子,然后圈子缩小,从下一个人继续游戏,问最后留下的是原来的第几号。
- 10 汉诺塔问题基于递归算法的实现。
- 11 .编写函数计算任意位数的黑洞数。黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数字是6174,因为7641-1467=6174。
- 12 编写函数,使用算法实现冒泡排序算法。
- 13.编写函数,模拟选择法排序。
- 14 编写函数,模拟二分法查找。
- 15 编写函数,查找给定序列的最长递增子序列。
- 16 编写函数,寻找给定序列中相差最小的两个数字。
- 17.利用蒙特.卡罗方法计算圆周率近似值。
- 18 模拟蒙蒂霍尔悖论游戏。
1.斐波那契
##编写斐波那契数列的函数并调用
def fib(n):##n是形参
a,b =1,1
while a<n:
print(a,end=' ')
a,b=b,a+b
print(a,b)
fib(1000)
2.使用递归法对整数进行因数分解
from random import randint
def factors(num, fac=[]):
#每次都从2开始查找因数
for i in range(2, int(num**0.5)+1):
#找到一个因数
if num%i == 0:
fac.append(i)
#对商继续分解,重复这个过程
factors(num//i, fac)
#注意,这个break非常重要
break
else:
#不可分解了,自身也是个因数
fac.append(num)
facs = []
n = randint(2, 10**8)
factors(n, facs)
result = '*'.join(map(str, facs))
if n==eval(result):
print(n, '= '+result)
3.编写并使用能够生成斐波那契数列的生成器函数
def f():
a, b = 1, 1 #序列解包,同时为多个元素赋值
while True:
yield a #暂停执行,需要时再产生一个新元素
a, b = b, a+b #序列解包,继续生成新元素
a = f() #创建生成器对象
for i in range(10): #斐波那契数列中前10个元素
print(a.__next__(), end=' ')
4 编写函数,接收字符串参数,返回一个元组,其中第一个元素为大写字母个数,第二个元素为小写字母个数
def demo(s):
result = [0, 0]
for ch in s:
if ch.islower():
result[1] += 1
elif ch.isupper():
result[0] += 1
return tuple(result)
5.编写函数,接收一个整数t为参数,打印杨辉三角前t行
def yanghui(t):
print([1])
line = [1, 1]
print(line)
for i in range(2, t):
r = []
for j in range(0, len(line)-1):
r.append(line[j]+line[j+1])
line = [1]+r+[1]
print(line)
6. 编写函数,接收一个正偶数为参数,输出两个素数,并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数,则全部输出。
def demo(n):
def IsPrime(p):
if p == 2:
return True
if p%2 == 0:
return False
for i in range(3, int(p**0.5)+1, 2):
if p%i==0:
return False
return True
if isinstance(n, int) and n>0 and n%2==0:
for i in range(2, n//2+1):
if IsPrime(i) and IsPrime(n-i):
print(i, '+', n-i, '=', n)
7 . 编写函数,计算字符串匹配的准确率。 以打字练习程序为例,假设origin为原始内容,userInput为用户输入的内容,下面的代码用来测试用户输入的准确率。
def Rate(origin, userInput):
if not (isinstance(origin, str) and isinstance(userInput, str)):
print('The two parameters must be strings.')
return
right = sum((1 for o, u in zip(origin, userInput) if o==u))
return round(right/len(origin), 2)
8. 编写函数模拟猜数游戏。系统随机产生一个数,玩家最多可以猜5次,系统会根据玩家的猜测进行提示,玩家则可以根据系统的提示对下一次的猜测进行适当调整。
from random import randint
def guess(maxValue=100, maxTimes=5):
#随机生成一个整数
value = randint(1,maxValue)
for i in range(maxTimes):
prompt = 'Start to GUESS:' if i==0 else 'Guess again:'
#使用异常处理结构,防止输入不是数字的情况
try:
x = int(input(prompt))
except:
print('Must input an integer between 1 and ', maxValue)
else:
#猜对了
if x == value:
print('Congratulations!')
break
elif x > value:
print('Too big')
else:
print('Too little')
else:
#次数用完还没猜对,游戏结束,提示正确答案
print('Game over. FAIL.')
print('The value is ', value)
9. 编写函数模拟报数游戏。有n个人围成一圈,顺序编号,从第一个人开始从1到k(假设k=3)报数,报到k的人退出圈子,然后圈子缩小,从下一个人继续游戏,问最后留下的是原来的第几号。
from itertools import cycle
def demo(lst, k):
#切片,以免影响原来的数据
t_lst = lst[:]
#游戏一直进行到只剩下最后一个人
while len(t_lst)>1:
#创建cycle对象
c = cycle(t_lst)
#从1到k报数
for i in range(k):
t = next(c)
#一个人出局,圈子缩小
index = t_lst.index(t)
t_lst = t_lst[index+1:] + t_lst[:index]
#游戏结束
return t_lst[0]
lst = list(range(1,11))
print(demo(lst, 3))
10 汉诺塔问题基于递归算法的实现。
据说古代有一个梵塔,塔内有三个底座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,在移动盘子的过程中可以利用B座,但任何时刻3个座上的盘子都必须始终保持大盘在下、小盘在上的顺序。如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C即可。和尚想知道这项任务的详细移动步骤和顺序。这实际上是一个非常巨大的工程,是一个不可能完成的任务。根据数学知识我们可以知道,移动n个盘子需要2^n-1步,64个盘子需要18446744073709551615步。如果每步需要一秒钟的话,那么就需要584942417355.072年。
def hannoi(num, src, dst, temp=None):
#声明用来记录移动次数的变量为全局变量
global times
#确认参数类型和范围
assert type(num) == int, 'num must be integer'
assert num > 0, 'num must > 0'
#只剩最后或只有一个盘子需要移动,这也是函数递归调用的结束条件
if num == 1:
print('The {0} Times move:{1}==>{2}'.format(times, src, dst))
times += 1
else:
#递归调用函数自身,
#先把除最后一个盘子之外的所有盘子移动到临时柱子上
hannuo(num-1, src, temp, dst)
#把最后一个盘子直接移动到目标柱子上
hannuo(1, src, dst)
#把除最后一个盘子之外的其他盘子从临时柱子上移动到目标柱子上
hannuo(num-1, temp, dst, src)
#用来记录移动次数的变量
times = 1
#A表示最初放置盘子的柱子,C是目标柱子,B是临时柱子
hannoi(3, 'A', 'C', 'B')
11 .编写函数计算任意位数的黑洞数。黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数字是6174,因为7641-1467=6174。
def main(n):
'''参数n表示数字的位数,例如n=3时返回495,n=4时返回6174'''
#待测试数范围的起点和结束值
start = 10**(n-1)
end = 10**n
#依次测试每个数
for i in range(start, end):
#由这几个数字组成的最大数和最小数
big = ''.join(sorted(str(i),reverse=True))
little = ''.join(reversed(big))
big, little = map(int,(big, little))
if big-little == i:
print(i)
n = 4
main(n)
12 编写函数,使用算法实现冒泡排序算法。
from random import randint
def bubbleSort(lst, reverse=False):
length = len(lst)
for i in range(0, length):
flag = False
for j in range(0, length-i-1):
#比较相邻两个元素大小,并根据需要进行交换,默认升序排序
exp = 'lst[j] > lst[j+1]'
#如果reverse=True则降序排序
if reverse:
exp = 'lst[j] < lst[j+1]'
if eval(exp):
lst[j], lst[j+1] = lst[j+1], lst[j]
#flag=True表示本次扫描发生过元素交换
flag = True
#如果一次扫描结束后,没有发生过元素交换,说明已经按序排列
if not flag:
break
13.编写函数,模拟选择法排序。
def selectSort(lst, reverse=False):
length = len(lst)
for i in range(0, length):
#假设剩余元素中第一个最小或最大
m = i
#扫描剩余元素
for j in range(i+1, length):
#如果有更小或更大的,就记录下它的位置
exp = 'lst[j] < lst[m]'
if reverse:
exp = 'lst[j] > lst[m]'
if eval(exp):
m = j
#如果发现更小或更大的,就交换值
if m!=i:
lst[i], lst[m] = lst[m], lst[i]
14 编写函数,模拟二分法查找。
def binarySearch(lst, value):
start = 0
end = len(lst)
while start < end:
#计算中间位置
middle = (start + end) // 2
#查找成功,返回元素对应的位置
if value == lst[middle]:
return middle
#在后面一半元素中继续查找
elif value > lst[middle]:
start = middle + 1
#在前面一半元素中继续查找
elif value < lst[middle]:
end = middle - 1
#查找不成功,返回False
return False
15 编写函数,查找给定序列的最长递增子序列。
from itertools import combinations
from random import sample
def subAscendingList(lst):
'''返回最长递增子序列'''
for length in range(len(lst), 0, -1):
#按长度递减的顺序进行查找和判断
for sub in combinations(lst, length):
#判断当前选择的子序列是否为递增顺序
if list(sub) == sorted(sub):
#找到第一个就返回
return sub
def getList(start=0, end=1000, number=20):
'''生成随机序列'''
if number > end-start:
return None
return sample(range(start, end), number)
def main():
#生成一个包含10个随机数的列表进行测试
lst = getList(number=10)
if lst:
print(lst)
print(subAscendingList(lst))
main()
16 编写函数,寻找给定序列中相差最小的两个数字。
import random
def getTwoClosestElements(seq):
#先进行排序,使得相邻元素最接近
#相差最小的元素必然相邻
seq = sorted(seq)
#无穷大
dif = float('inf')
#遍历所有元素,两两比较,比较相邻元素的差值
#使用选择法寻找相差最小的两个元素
for i,v in enumerate(seq[:-1]):
d = abs(v - seq[i+1])
if d < dif:
first, second, dif = v, seq[i+1], d
#返回相差最小的两个元素
return (first, second)
seq = [random.randint(1, 10000) for i in range(20)]
print(seq)
print(sorted(seq))
print(getTwoClosestElements(seq))
17.利用蒙特.卡罗方法计算圆周率近似值。
from random import random
def estimatePI(times):
hits = 0
for i in range(times):
x = random()*2 - 1 #random()生成介于0和1之间的小数
y = random()*2 - 1 #该数字乘以2再减1,则介于-1和1之间
if x*x + y*y <= 1: #落在圆内或圆周上
hits += 1
return 4.0 * hits/times
print(estimatePI(10000))
print(estimatePI(1000000))
print(estimatePI(100000000))
print(estimatePI(1000000000))
18 模拟蒙蒂霍尔悖论游戏。
from random import randrange
def init():
'''返回一个字典,键为3个门号,值为门后面的物品'''
result = {i: 'goat' for i in range(3)}
r = randrange(3)
#在某个随机的门后面放一辆汽车,其他两个门后面仍然是山羊
result[r] = 'car'
return result
def startGame():
#获取本次游戏中每个门的情况
doors = init()
#获取玩家选择的门号
while True:
try:
firstDoorNum = int(input('Choose a door to open:'))
assert 0<= firstDoorNum <=2
break
except:
print('Door number must be between {} and {}'.format(0, 2))
#主持人查看另外两个门后的物品情况
#字典的keys()方法返回结果可以当作集合使用,支持使用减法计算差集
for door in doors.keys()-{firstDoorNum}:
#打开其中一个后面为山羊的门
if doors[door] == 'goat':
print('"goat" behind the door', door)
#获取第三个门号,让玩家纠结
thirdDoor = (doors.keys()-{door, firstDoorNum}).pop()
change = input('Switch to {}?(y/n)'.format(thirdDoor))
finalDoorNum = thirdDoor if change=='y' else firstDoorNum
if doors[finalDoorNum] == 'goat':
return 'I Win!'
else:
return 'You Win.'
while True:
print('='*30)
print(startGame())
r = input('Do you want to try once more?(y/n)')
if r == 'n':
break
函数(经典案例18例)
- 1.斐波那契
- 2.使用递归法对整数进行因数分解
- 3.编写并使用能够生成斐波那契数列的生成器函数
- 4 编写函数,接收字符串参数,返回一个元组,其中第一个元素为大写字母个数,第二个元素为小写字母个数
- 5.编写函数,接收一个整数t为参数,打印杨辉三角前t行
- 6. 编写函数,接收一个正偶数为参数,输出两个素数,并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数,则全部输出。
- 7 . 编写函数,计算字符串匹配的准确率。 以打字练习程序为例,假设origin为原始内容,userInput为用户输入的内容,下面的代码用来测试用户输入的准确率。
- 8. 编写函数模拟猜数游戏。系统随机产生一个数,玩家最多可以猜5次,系统会根据玩家的猜测进行提示,玩家则可以根据系统的提示对下一次的猜测进行适当调整。
- 9. 编写函数模拟报数游戏。有n个人围成一圈,顺序编号,从第一个人开始从1到k(假设k=3)报数,报到k的人退出圈子,然后圈子缩小,从下一个人继续游戏,问最后留下的是原来的第几号。
- 10 汉诺塔问题基于递归算法的实现。
- 11 .编写函数计算任意位数的黑洞数。黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数字是6174,因为7641-1467=6174。
- 12 编写函数,使用算法实现冒泡排序算法。
- 13.编写函数,模拟选择法排序。
- 14 编写函数,模拟二分法查找。
- 15 编写函数,查找给定序列的最长递增子序列。
- 16 编写函数,寻找给定序列中相差最小的两个数字。
- 17.利用蒙特.卡罗方法计算圆周率近似值。
- 18 模拟蒙蒂霍尔悖论游戏。
1.斐波那契
##编写斐波那契数列的函数并调用
def fib(n):##n是形参
a,b =1,1
while a<n:
print(a,end=' ')
a,b=b,a+b
print(a,b)
fib(1000)
2.使用递归法对整数进行因数分解
from random import randint
def factors(num, fac=[]):
#每次都从2开始查找因数
for i in range(2, int(num**0.5)+1):
#找到一个因数
if num%i == 0:
fac.append(i)
#对商继续分解,重复这个过程
factors(num//i, fac)
#注意,这个break非常重要
break
else:
#不可分解了,自身也是个因数
fac.append(num)
facs = []
n = randint(2, 10**8)
factors(n, facs)
result = '*'.join(map(str, facs))
if n==eval(result):
print(n, '= '+result)
3.编写并使用能够生成斐波那契数列的生成器函数
def f():
a, b = 1, 1 #序列解包,同时为多个元素赋值
while True:
yield a #暂停执行,需要时再产生一个新元素
a, b = b, a+b #序列解包,继续生成新元素
a = f() #创建生成器对象
for i in range(10): #斐波那契数列中前10个元素
print(a.__next__(), end=' ')
4 编写函数,接收字符串参数,返回一个元组,其中第一个元素为大写字母个数,第二个元素为小写字母个数
def demo(s):
result = [0, 0]
for ch in s:
if ch.islower():
result[1] += 1
elif ch.isupper():
result[0] += 1
return tuple(result)
5.编写函数,接收一个整数t为参数,打印杨辉三角前t行
def yanghui(t):
print([1])
line = [1, 1]
print(line)
for i in range(2, t):
r = []
for j in range(0, len(line)-1):
r.append(line[j]+line[j+1])
line = [1]+r+[1]
print(line)
6. 编写函数,接收一个正偶数为参数,输出两个素数,并且这两个素数之和等于原来的正偶数。如果存在多组符合条件的素数,则全部输出。
def demo(n):
def IsPrime(p):
if p == 2:
return True
if p%2 == 0:
return False
for i in range(3, int(p**0.5)+1, 2):
if p%i==0:
return False
return True
if isinstance(n, int) and n>0 and n%2==0:
for i in range(2, n//2+1):
if IsPrime(i) and IsPrime(n-i):
print(i, '+', n-i, '=', n)
7 . 编写函数,计算字符串匹配的准确率。 以打字练习程序为例,假设origin为原始内容,userInput为用户输入的内容,下面的代码用来测试用户输入的准确率。
def Rate(origin, userInput):
if not (isinstance(origin, str) and isinstance(userInput, str)):
print('The two parameters must be strings.')
return
right = sum((1 for o, u in zip(origin, userInput) if o==u))
return round(right/len(origin), 2)
8. 编写函数模拟猜数游戏。系统随机产生一个数,玩家最多可以猜5次,系统会根据玩家的猜测进行提示,玩家则可以根据系统的提示对下一次的猜测进行适当调整。
from random import randint
def guess(maxValue=100, maxTimes=5):
#随机生成一个整数
value = randint(1,maxValue)
for i in range(maxTimes):
prompt = 'Start to GUESS:' if i==0 else 'Guess again:'
#使用异常处理结构,防止输入不是数字的情况
try:
x = int(input(prompt))
except:
print('Must input an integer between 1 and ', maxValue)
else:
#猜对了
if x == value:
print('Congratulations!')
break
elif x > value:
print('Too big')
else:
print('Too little')
else:
#次数用完还没猜对,游戏结束,提示正确答案
print('Game over. FAIL.')
print('The value is ', value)
9. 编写函数模拟报数游戏。有n个人围成一圈,顺序编号,从第一个人开始从1到k(假设k=3)报数,报到k的人退出圈子,然后圈子缩小,从下一个人继续游戏,问最后留下的是原来的第几号。
from itertools import cycle
def demo(lst, k):
#切片,以免影响原来的数据
t_lst = lst[:]
#游戏一直进行到只剩下最后一个人
while len(t_lst)>1:
#创建cycle对象
c = cycle(t_lst)
#从1到k报数
for i in range(k):
t = next(c)
#一个人出局,圈子缩小
index = t_lst.index(t)
t_lst = t_lst[index+1:] + t_lst[:index]
#游戏结束
return t_lst[0]
lst = list(range(1,11))
print(demo(lst, 3))
10 汉诺塔问题基于递归算法的实现。
据说古代有一个梵塔,塔内有三个底座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,在移动盘子的过程中可以利用B座,但任何时刻3个座上的盘子都必须始终保持大盘在下、小盘在上的顺序。如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C即可。和尚想知道这项任务的详细移动步骤和顺序。这实际上是一个非常巨大的工程,是一个不可能完成的任务。根据数学知识我们可以知道,移动n个盘子需要2^n-1步,64个盘子需要18446744073709551615步。如果每步需要一秒钟的话,那么就需要584942417355.072年。
def hannoi(num, src, dst, temp=None):
#声明用来记录移动次数的变量为全局变量
global times
#确认参数类型和范围
assert type(num) == int, 'num must be integer'
assert num > 0, 'num must > 0'
#只剩最后或只有一个盘子需要移动,这也是函数递归调用的结束条件
if num == 1:
print('The {0} Times move:{1}==>{2}'.format(times, src, dst))
times += 1
else:
#递归调用函数自身,
#先把除最后一个盘子之外的所有盘子移动到临时柱子上
hannuo(num-1, src, temp, dst)
#把最后一个盘子直接移动到目标柱子上
hannuo(1, src, dst)
#把除最后一个盘子之外的其他盘子从临时柱子上移动到目标柱子上
hannuo(num-1, temp, dst, src)
#用来记录移动次数的变量
times = 1
#A表示最初放置盘子的柱子,C是目标柱子,B是临时柱子
hannoi(3, 'A', 'C', 'B')
11 .编写函数计算任意位数的黑洞数。黑洞数是指这样的整数:由这个数字每位上的数字组成的最大数减去每位数字组成的最小数仍然得到这个数自身。例如3位黑洞数是495,因为954-459=495,4位数字是6174,因为7641-1467=6174。
def main(n):
'''参数n表示数字的位数,例如n=3时返回495,n=4时返回6174'''
#待测试数范围的起点和结束值
start = 10**(n-1)
end = 10**n
#依次测试每个数
for i in range(start, end):
#由这几个数字组成的最大数和最小数
big = ''.join(sorted(str(i),reverse=True))
little = ''.join(reversed(big))
big, little = map(int,(big, little))
if big-little == i:
print(i)
n = 4
main(n)
12 编写函数,使用算法实现冒泡排序算法。
from random import randint
def bubbleSort(lst, reverse=False):
length = len(lst)
for i in range(0, length):
flag = False
for j in range(0, length-i-1):
#比较相邻两个元素大小,并根据需要进行交换,默认升序排序
exp = 'lst[j] > lst[j+1]'
#如果reverse=True则降序排序
if reverse:
exp = 'lst[j] < lst[j+1]'
if eval(exp):
lst[j], lst[j+1] = lst[j+1], lst[j]
#flag=True表示本次扫描发生过元素交换
flag = True
#如果一次扫描结束后,没有发生过元素交换,说明已经按序排列
if not flag:
break
13.编写函数,模拟选择法排序。
def selectSort(lst, reverse=False):
length = len(lst)
for i in range(0, length):
#假设剩余元素中第一个最小或最大
m = i
#扫描剩余元素
for j in range(i+1, length):
#如果有更小或更大的,就记录下它的位置
exp = 'lst[j] < lst[m]'
if reverse:
exp = 'lst[j] > lst[m]'
if eval(exp):
m = j
#如果发现更小或更大的,就交换值
if m!=i:
lst[i], lst[m] = lst[m], lst[i]
14 编写函数,模拟二分法查找。
def binarySearch(lst, value):
start = 0
end = len(lst)
while start < end:
#计算中间位置
middle = (start + end) // 2
#查找成功,返回元素对应的位置
if value == lst[middle]:
return middle
#在后面一半元素中继续查找
elif value > lst[middle]:
start = middle + 1
#在前面一半元素中继续查找
elif value < lst[middle]:
end = middle - 1
#查找不成功,返回False
return False
15 编写函数,查找给定序列的最长递增子序列。
from itertools import combinations
from random import sample
def subAscendingList(lst):
'''返回最长递增子序列'''
for length in range(len(lst), 0, -1):
#按长度递减的顺序进行查找和判断
for sub in combinations(lst, length):
#判断当前选择的子序列是否为递增顺序
if list(sub) == sorted(sub):
#找到第一个就返回
return sub
def getList(start=0, end=1000, number=20):
'''生成随机序列'''
if number > end-start:
return None
return sample(range(start, end), number)
def main():
#生成一个包含10个随机数的列表进行测试
lst = getList(number=10)
if lst:
print(lst)
print(subAscendingList(lst))
main()
16 编写函数,寻找给定序列中相差最小的两个数字。
import random
def getTwoClosestElements(seq):
#先进行排序,使得相邻元素最接近
#相差最小的元素必然相邻
seq = sorted(seq)
#无穷大
dif = float('inf')
#遍历所有元素,两两比较,比较相邻元素的差值
#使用选择法寻找相差最小的两个元素
for i,v in enumerate(seq[:-1]):
d = abs(v - seq[i+1])
if d < dif:
first, second, dif = v, seq[i+1], d
#返回相差最小的两个元素
return (first, second)
seq = [random.randint(1, 10000) for i in range(20)]
print(seq)
print(sorted(seq))
print(getTwoClosestElements(seq))
17.利用蒙特.卡罗方法计算圆周率近似值。
from random import random
def estimatePI(times):
hits = 0
for i in range(times):
x = random()*2 - 1 #random()生成介于0和1之间的小数
y = random()*2 - 1 #该数字乘以2再减1,则介于-1和1之间
if x*x + y*y <= 1: #落在圆内或圆周上
hits += 1
return 4.0 * hits/times
print(estimatePI(10000))
print(estimatePI(1000000))
print(estimatePI(100000000))
print(estimatePI(1000000000))
18 模拟蒙蒂霍尔悖论游戏。
from random import randrange
def init():
'''返回一个字典,键为3个门号,值为门后面的物品'''
result = {i: 'goat' for i in range(3)}
r = randrange(3)
#在某个随机的门后面放一辆汽车,其他两个门后面仍然是山羊
result[r] = 'car'
return result
def startGame():
#获取本次游戏中每个门的情况
doors = init()
#获取玩家选择的门号
while True:
try:
firstDoorNum = int(input('Choose a door to open:'))
assert 0<= firstDoorNum <=2
break
except:
print('Door number must be between {} and {}'.format(0, 2))
#主持人查看另外两个门后的物品情况
#字典的keys()方法返回结果可以当作集合使用,支持使用减法计算差集
for door in doors.keys()-{firstDoorNum}:
#打开其中一个后面为山羊的门
if doors[door] == 'goat':
print('"goat" behind the door', door)
#获取第三个门号,让玩家纠结
thirdDoor = (doors.keys()-{door, firstDoorNum}).pop()
change = input('Switch to {}?(y/n)'.format(thirdDoor))
finalDoorNum = thirdDoor if change=='y' else firstDoorNum
if doors[finalDoorNum] == 'goat':
return 'I Win!'
else:
return 'You Win.'
while True:
print('='*30)
print(startGame())
r = input('Do you want to try once more?(y/n)')
if r == 'n':
break