py编程基础及导论 11

第7章跨学科编程案例素数探究·概率游戏·二进制·凯撒密码·分形面向师范生的Python编程导论本章概述2第7章跨学科编程案例本章将运用编程方法探索数学、概率、计算机科学中的经典问题7.1素数探究判断素数、孪生素数、素数计数、哥德巴赫猜想7.2概率游戏掷骰子、帕斯卡游戏、蒙提霍尔问题7.3二进制二进制概念、进制转换、小数精度问题7.4凯撒密码加密原理、加密函数、解密与破解7.5探索分形海龟绘图、分形树、科赫雪花通过跨学科案例，感受编程在数学探究、概率模拟、信息安全和图形艺术中的强大力量本章学习目标4第7章跨学科编程案例知识目标理解素数的概念与判断方法了解孪生素数和哥德巴赫猜想理解概率模拟的基本思想掌握二进制与十进制的转换理解凯撒密码的加密原理了解分形图形的自相似性掌握turtle模块的基本使用能力目标能够编写is_prime()等判断函数能够用计算机模拟概率实验能够实现进制转换函数能够实现凯撒密码加密解密能够用turtle绘制基本图形能够用递归绘制分形树能够综合运用编程解决跨学科问题本章课时安排（6课时）6第7章跨学科编程案例课时教学内容重点/难点活动设计第1课时素数判断、孪生素数试除法优化编程实践+数据探究第2课时素数计数、哥德巴赫猜想高勒公式验证数据分析+实验验证第3课时掷骰子、帕斯卡游戏概率模拟方法模拟实验+理论对比第4课时蒙提霍尔问题、二进制三门问题分析游戏模拟+进制转换第5课时凯撒密码加密与解密ord/chr函数加密解密+密码破解第6课时海龟绘图、分形树与雪花递归分形图形绘制+创意设计提示本章为跨学科综合应用章节，建议每课时预留充足时间进行编程实践和探究。7.1素数探究利用编程方法探索素数世界：判断素数、孪生素数、素数计数与哥德巴赫猜想7.1.1判断素数9第7章跨学科编程案例·7.1素数探究什么是素数？素数（PrimeNumber，也称作质数）是非常重要的数学概念，是指只有1和其本身两个因数的自然数，例如：2、3、5、7等。许多著名的数学猜想都与素数有关。素数的特点只有1和其本身两个因数2是唯一的偶素数素数有无限多个（已证明）是数论的核心研究对象密码学的重要基础相关数学猜想哥德巴赫猜想孪生素数猜想黎曼猜想素数分布规律本节将用编程探索这些问题素数的定义与判断11第7章跨学科编程案例·7.1素数探究素数的数学定义对于大于1的自然数n，如果n只能被1和n整除（即n只有两个因数），则n是素数。否则n是合数。1既不是素数也不是合数。判断方法遍历1到n的所有整数统计n的因数个数如果因数个数等于2，则为素数否则不是素数该方法直观但效率较低前10个素数2,3,5,7,1113,17,19,23,29注意：2是唯一的偶素数1不是素数0和负数不是素数代码7.1：判断素数函数13第7章跨学科编程案例·7.1素数探究函数设计基于循环判断的方法，统计n的因数个数。如果只有2个因数（1和n本身），则返回True。代码7.1#定义函数defis_prime(n):k=0

foriin

range(1,n+1):

ifn%i==0:k+=1

ifk==2:

return

True

else:

return

False#输入数据进行测试print("请输入一个正整数：")n=int(input())ifis_prime(n):

print(f"{n}是素数")else:

print(f"{n}不是素数")运行结果请输入一个正整数：1717是素数代码7.1分析15第7章跨学科编程案例·7.1素数探究代码解析is_prime()函数的参数是一个整数n，函数体中的循环用于计算n的因数个数。如果n只有两个因数，则返回True，表示n是素数；否则返回False。输入n因数因数个数k返回值结论171,172True素数151,3,5,154False合数21,22True素数111False非素数注意该方法需要对1到n的所有整数进行遍历，当n很大时效率非常低。代码7.2：素数判断计时测试17第7章跨学科编程案例·7.1素数探究效率问题如果使用一个较大的数（例如73939133）进行测试，程序可能运行较长时间。代码7.2为程序加入计时代码。代码7.2importtime#定义函数defis_prime(n):k=0

foriin

range(1,n+1):

ifn%i==0:k+=1

ifk==2:

return

True

else:

return

False#输入数据进行测试n=73939133start=time.time()ifis_prime(n):

print(f"{n}是素数")else:

print(f"{n}不是素数")t=time.time()-startprint(f"计算用时为{t:.3f}秒")运行结果73939133是素数计算用时为2.223秒效率问题分析19第7章跨学科编程案例·7.1素数探究注意判断一个8位数是否为素数，程序计算用时为2.223秒。如果使用更大数字，运行时间会更长。问题根源上述方法遍历了从1到n的所有整数来检查因数。但实际上，我们并不需要对所有小于n的数都进行测试。如果n可以分解为a*b（a<=b），则只需要测试到a即可判断n是否为素数。优化思路因为a*a<=n（当a<=b且a*b=n时），所以只需要遍历到sqrt(n)即可。这一算法叫作试除法，由斐波那契提出。试除法（TrialDivision）21第7章跨学科编程案例·7.1素数探究试除法的核心思想由斐波那契提出的试除法：如果n可以分解为a*b（a<=b），则a<=sqrt(n)。因此只需要测试2到sqrt(n)之间的数能否整除n，就可以判断n是否为素数。n=a*b(a<=b)→则a<=sqrt(n)即a*a<=n→只需测试2到sqrt(n)→大幅减少循环次数效率对比对于n=73939133，原方法需要循环约73939133次，试除法只需循环约8600次（sqrt(73939133)≈8600）。代码7.3：试除法优化23第7章跨学科编程案例·7.1素数探究代码7.3importtime#定义函数（试除法优化）defis_prime(n):

ifn<2:

return

Falsea=2

whilea*a<=n:

ifn%a==0:

return

Falsea+=1

return

True#测试n=73939133start=time.time()ifis_prime(n):

print(f"{n}是素数")else:

print(f"{n}不是素数")t=time.time()-startprint(f"计算用时为{t:.3f}秒")运行结果73939133是素数计算用时为0.003秒2.223s优化前0.003s优化后7.1.2孪生素数25第7章跨学科编程案例·7.1素数探究什么是孪生素数？孪生素数是指一对相差为2的素数，例如：3和5，5和7，11和13等。欧几里得已证明素数有无穷多个，那么孪生素数是否也有无穷多对呢？孪生素数示例(3,5)差为2(5,7)差为2(11,13)差为2(17,19)差为2(29,31)差为2(41,43)差为2孪生素数猜想希尔伯特提出：孪生素数有无穷多对目前尚未被证明或否定2013年张益唐取得重大突破证明了存在无穷多对差小于7000万的素数对代码7.4：孪生素数函数27第7章跨学科编程案例·7.1素数探究代码7.4#定义函数defis_prime(n):

ifn<2:

return

Falsea=2

whilea*a<=n:

ifn%a==0:

return

Falsea+=1

return

Truedeftwin_prime(n):

ifis_prime(n)andis_prime(n+2):

return

True

return

False#测试函数n=1000k=0print(f"{n}以内的孪生素数有：")foriin

range(2,n-1):

iftwin_prime(i):k+=1

print((i,i+2))print(f"共{k}对")运行结果1000以内的孪生素数有：(3,5)(5,7)(11,13)...(857,859)(881,883)共35对孪生素数数量与占比（表7.1）29第7章跨学科编程案例·7.1素数探究n的值孪生素数对数kk/n百分比10220%10088%1000353.5%100002052%10000012241.2%100000081690.8%数据分析数值越大，孪生素数的占比似乎越少从20%下降到0.8%，呈递减趋势孪生素数猜想是否成立，有待数学家们进一步探索7.1.3素数个数31第7章跨学科编程案例·7.1素数探究素数计数函数π(x)在素数的探究中，素数出现的规律一直困扰着数学界。数学界定义了一个素数计数函数π(x)，用来表示小于等于x的素数个数。高斯和勒让德的猜想十八世纪末数学家高斯和勒让德提出：π(x)≈x/ln(x)当时没有计算机验证这个猜测非常困难编程验证我们现在掌握了编程工具可以尝试用编程来验证设计素数计数函数pi(x)再设计高勒公式计算函数对比两者的计算结果代码7.5：素数计数函数33第7章跨学科编程案例·7.1素数探究代码7.5#定义函数defis_prime(n):

ifn<2:

return

Falsea=2

whilea*a<=n:

ifn%a==0:

return

Falsea+=1

return

Truedefpi(x):k=0

foriin

range(2,x+1):

ifis_prime(i):k+=1

returnk#测试函数n=1000000k=pi(n)print(f"不大于{n}的素数个数有{k}个")运行结果不大于1000000的素数个数有78498个代码7.6：高勒公式验证35第7章跨学科编程案例·7.1素数探究代码7.6import

math#定义函数defis_prime(n):

ifn<2:

return

Falsea=2

whilea*a<=n:

ifn%a==0:

return

Falsea+=1

return

Truedefpi(x):k=0

foriin

range(2,x+1):

ifis_prime(i):k+=1

returnkdefGaussian(x):

returnx/math.log(x)#验证猜测data=[10,100,1000,10000,100000,1000000]fornindata:k=pi(n)g=Gaussian(n)

print(f"n={n},素数计数={k},高勒猜测={g:.2f},比例={k/g:.2f}")高勒公式验证结果37第7章跨学科编程案例·7.1素数探究n实际素数计数π(n)高勒公式x/ln(x)比例π(n)/g(x)1044.340.921002521.711.151000168144.761.161000012291085.741.1310000095928685.891.1010000007849872382.411.08结论分析随着n的增大，素数的实际计数与高勒公式计算结果的比例越来越接近1以此类推，随着n趋向于无穷大，素数的实际个数应该与高勒公式无限接近这验证了高斯和勒让德的猜想7.1.4哥德巴赫猜想39第7章跨学科编程案例·7.1素数探究数学皇冠上的明珠哥德巴赫猜想（Goldbach’sconjecture）是极为重要的一个猜想，由数学家哥德巴赫于1742年在与欧拉的通信中提出。猜想内容任意一个大于2的偶数，都可以表示成两个素数之和。验证示例4=2+2,6=3+3,8=3+5,10=3+7=5+5,100=3+97哥德巴赫猜想验证历史41第7章跨学科编程案例·7.1素数探究年份验证者验证范围1938尼尔斯·皮平所有小于10^5的偶数1964M·L·斯坦恩和P·R·斯坦恩小于10^7的偶数1989A·格兰维尔扩大到2×10^101993MattiK.Sinisalo10^11以内的偶数2000JörgRichstein4×10^14以内的偶数2014数学家团队4×10^18以内的偶数陈景润的贡献目前最好的结果是我国数学家陈景润在1973年发表的陈氏定理证明了每个充分大的偶数都可以表示为一个素数与一个不超过两个素因数之积的和代码7.7-7.8：哥德巴赫猜想验证43第7章跨学科编程案例·7.1素数探究代码7.8defis_prime(n):

ifn<2:

return

Falsea=2

whilea*a<=n:

ifn%a==0:

return

Falsea+=1

return

Truedefgdbh(n):

foriin

range(2,n//2):

ifis_prime(i)andis_prime(n-i):

return(i,n-i)

return(-1,-1)#验证哥德巴赫猜想n=10000m=5print(f'从{n}开始的{m}个偶数验证:')foriin

range(m):r=gdbh(n)

print(f"{n}={r[0]}+{r[1]}")n+=2哥德巴赫猜想验证结果45第7章跨学科编程案例·7.1素数探究运行结果从10000开始的5个偶数验证:10000=59+994110002=29+997310004=31+997310006=83+992310008=41+9967验证分析每个偶数都能找到两个素数之和的表示最后一条返回语句应该不会被触发，否则说明哥德巴赫猜想被推翻这只是数据验证，并不能证明哥德巴赫猜想但至今在4×10^18的范围内，仍然没有找到反例7.1小结：素数探究素数是只有1和其本身两个因数的自然数is_prime()函数通过试除法优化，将效率从2.2秒提升到0.003秒孪生素数是相差为2的素数对，其猜想尚未被证明素数计数函数π(x)可以统计素数个数高勒公式x/ln(x)可以近似估算素数个数，随n增大比例趋近1哥德巴赫猜想：任意大于2的偶数可表示为两个素数之和编程可以验证数学猜想，但验证不等于证明陈景润的陈氏定理是目前最好的结果7.2概率游戏用计算机模拟概率实验：掷骰子、帕斯卡游戏与蒙提霍尔问题7.2.1掷骰子49第7章跨学科编程案例·7.2概率游戏掷骰子与概率掷一次骰子，得到6种点数的概率是相同的，都是1/6。如果通过实际操作来验证这个理论概率，需要重复执行许多次掷骰子的动作。借助计算机可以模拟上百万次实验。理论概率每个点数出现的概率=1/6约等于16.67%6种结果等概率出现是古典概型的典型例子计算机模拟使用random模块生成随机数random.randint(1,6)可以模拟掷骰子一秒钟可进行上百万次实验random模块51第7章跨学科编程案例·7.2概率游戏随机数生成Python的random模块提供了生成随机数的函数。其中random.randint(a,b)可以随机生成[a,b]之间的整数。函数功能示例返回值random.randint(a,b)生成a到b的随机整数random.randint(1,6)1-6的整数random.random()生成0到1的随机浮点数random.random()0.0-1.0的floatrandom.choice(seq)从序列中随机选择random.choice([1,2,3])序列中的元素random.uniform(a,b)生成a到b的随机浮点数random.uniform(1,10)1.0-10.0的float提示random.randint(a,b)包含端点a和b，即生成[a,b]闭区间内的整数。代码7.9：掷骰子函数53第7章跨学科编程案例·7.2概率游戏代码7.9import

random#定义函数defroll_dice():

return

random.randint(1,6)#进行测试foriin

range(1,6):a=roll_dice()

print(f"第{i}次实验，点数为：{a}")运行结果第1次实验，点数为：6第2次实验，点数为：3第3次实验，点数为：6第4次实验，点数为：2第5次实验，点数为：3提示每次运行结果可能不同，因为点数是随机出现的。多次运行程序可以看到不同的结果。代码7.10：大量掷骰子实验55第7章跨学科编程案例·7.2概率游戏代码7.10import

random#定义函数defroll_dice():

return

random.randint(1,6)#进行大量实验n=100data=[0]*7

#索引1-6记录各点数次数foriin

range(n):a=roll_dice()data[a]+=1#输出结果print(f'一共掷骰子{n}次')foriin

range(1,7):

print(f'点数{i}的出现次数为：{data[i]}')运行结果一共掷骰子100次点数1的出现次数为：16点数2的出现次数为：11点数3的出现次数为：29点数4的出现次数为：11点数5的出现次数为：15点数6的出现次数为：18大数定律57第7章跨学科编程案例·7.2概率游戏实验次数与概率从代码7.10的运行结果看，n为100时，各个点数的出现次数并不相同。但如果将n设置为100万，就会发现各个点数的出现次数非常接近。实验次数n各点数出现频率与理论值1/6的偏差10011%-29%较大偏差100014%-19%中等偏差1000015%-18%较小偏差10000016%-17%接近理论值1000000约16.67%非常接近这就是大数定律：实验次数越多，事件发生的频率越接近理论概率。7.2.2帕斯卡的游戏59第7章跨学科编程案例·7.2概率游戏帕斯卡与概率论帕斯卡（Pascal）是法国科学家、数学家。1654年，一位名为德·梅雷的法国贵族向帕斯卡请教了一个分赌注问题。在解决这个问题的过程中，帕斯卡和好友费马提出了一种著名的数学理论——概率论。游戏规则掷一个骰子4次，如果出现6，帕斯卡赢如果4次都不是6，费马赢问题：如果玩这个游戏N次，帕斯卡和费马谁会赢？游戏实验记录表（表7.2）61第7章跨学科编程案例·7.2概率游戏手动实验准备一个骰子，和朋友一起玩20个回合，记录游戏过程数据，统计每个人的胜利次数。回合第1次第2次第3次第4次胜利者12541费马2116-帕斯卡33241费马..................192235费马206---帕斯卡提示有限次数的游戏结果并不能说明概率分布，利用计算机模拟是更好的方案。代码7.11：帕斯卡游戏函数63第7章跨学科编程案例·7.2概率游戏函数设计函数实现了帕斯卡游戏一个回合的过程。通过4次循环掷骰子，如果出现6，则返回1表示帕斯卡赢；循环结束时没有出现6，则返回0表示帕斯卡输。代码7.11import

randomdefroll_dice():

return

random.randint(1,6)defpascal():

foriin

range(4):

ifroll_dice()==6:

return

1

#帕斯卡赢

return

0

#费马赢提示函数返回1表示帕斯卡赢，返回0表示费马赢。返回值可以直接用于统计胜率。代码7.12：帕斯卡游戏模拟65第7章跨学科编程案例·7.2概率游戏代码7.12import

randomdefroll_dice():

return

random.randint(1,6)defpascal():

foriin

range(4):

ifroll_dice()==6:

return

1

return

0defsimulation(n):count=0

foriin

range(n):count+=pascal()

returncount#进行测试data=[10,100,1000,10000,100000,1000000]fornindata:p=simulation(n)win_rate=p/n

print(f'模拟{n}次游戏，帕斯卡胜率={win_rate:.3f}')运行结果模拟10次游戏，帕斯卡胜率=0.400模拟100次游戏，帕斯卡胜率=0.480模拟1000次游戏，帕斯卡胜率=0.521模拟10000次游戏，帕斯卡胜率=0.523模拟100000次游戏，帕斯卡胜率=0.517模拟1000000次游戏，帕斯卡胜率=0.518帕斯卡的理论胜率67第7章跨学科编程案例·7.2概率游戏从概率角度计算理论胜率根据代码7.12的运行结果，帕斯卡的胜率约为0.518。下面从概率角度计算理论值。事件概率掷骰子1次，得到61/6掷骰子1次，不是65/6掷骰子4次，都不是6(5/6)^4掷骰子4次，出现6（帕斯卡赢）1-(5/6)^4理论计算结果帕斯卡的胜率p=1-(5/6)^4≈0.51774模拟结果0.518与理论值0.51774非常接近！模拟与理论对比69第7章跨学科编程案例·7.2概率游戏模拟次数模拟胜率理论胜率偏差100.4000.51770.1181000.4800.51770.03810000.5210.51770.003100000.5230.51770.0051000000.5170.51770.00110000000.5180.51770.000结论随着模拟次数增加，模拟胜率越来越接近理论胜率0.5177帕斯卡是最终的胜利者！这再次验证了大数定律：实验次数越多，结果越接近理论值7.2.3蒙提霍尔问题71第7章跨学科编程案例·7.2概率游戏三门问题蒙提霍尔问题（MontyHallproblem）源于美国电视游戏节目Let’sMakeaDeal。前面有三扇关着的门，其中一扇门背后有一辆汽车，另外两扇门背后是山羊。玩家选择一扇门后，主持人打开剩下两扇门中一扇有山羊的门，并询问玩家是否要改变选择。核心问题玩家应该坚持最初的选择还是改变选择？哪种策略获奖的概率更高？代码7.13：蒙提霍尔函数73第7章跨学科编程案例·7.2概率游戏模拟策略：始终改变选择首先在三扇门背后随机放置汽车，然后玩家随机选择其中一扇门。因为玩家会选择改变最初选择，所以如果最初的选择正好是有汽车的那扇门，则无法赢得奖品。代码7.13import

random#定义函数defmonty_hall():car=random.randint(1,3)#随机放置汽车choice=random.randint(1,3)#玩家随机选择

ifcar==choice:

return

0

#最初选对了，改变后输

else:

return

1

#最初选错了，改变后赢提示关键逻辑：如果最初选择正好是汽车（概率1/3），改变后必输；否则改变后必赢（概率2/3）。代码7.14：蒙提霍尔模拟75第7章跨学科编程案例·7.2概率游戏代码7.14import

randomdefmonty_hall():car=random.randint(1,3)choice=random.randint(1,3)

ifcar==choice:

return

0

else:

return

1defsimulation(n):count=0

foriin

range(n):count+=monty_hall()

returncount#进行测试data=[10,100,1000,10000,100000,1000000]print('策略：每次都改变最初选择')fornindata:wins=simulation(n)win_rate=wins/n

print(f'模拟{n}次，胜率={win_rate:.3f}')运行结果策略：每次都改变最初选择模拟10次，胜率=0.600模拟100次，胜率=0.600模拟1000次，胜率=0.691模拟10000次，胜率=0.676模拟100000次，胜率=0.665模拟1000000次，胜率=0.667穷举法分析蒙提霍尔问题77第7章跨学科编程案例·7.2概率游戏假设玩家最初选择1号门所有可能的情况如下：情况汽车位置主持人打开改变选择后结果11号门2或3号门选3或2号门输22号门3号门选2号门赢33号门2号门选3号门赢结论3种情况中，改变选择后赢了2次，输了1次改变选择的胜率=2/3≈0.667坚持选择的胜率=1/3≈0.333改变选择是更好的策略！蒙提霍尔问题结论79第7章跨学科编程案例·7.2概率游戏1/3坚持选择的胜率2/3改变选择的胜率为什么改变选择更好？最初选对的概率只有1/3，选错的概率是2/3主持人打开一扇有山羊的门后，如果改变选择就相当于选了另外两扇门所以改变选择的胜率是2/3，是坚持选择的两倍这个结论与直觉相悖，但数学和模拟都证明了它的正确性注意这个结论似乎不合常理，但实验结果和理论分析都明确表明：改变选择是更好的策略。7.2小结：概率游戏计算机可以模拟大量随机实验，验证理论概率掷骰子：random.randint(1,6)模拟，大数定律保证频率趋近概率帕斯卡游戏：模拟胜率0.518≈理论值1-(5/6)^4≈0.5177蒙提霍尔问题：改变选择的胜率2/3，是坚持选择的2倍模拟实验次数越多，结果越接近理论概率计算机模拟能够验证直觉难以判断的概率问题simulation()函数是概率模拟的通用模式7.3二进制理解二进制数的概念，掌握进制转换，了解浮点数精度问题7.3.1看懂二进制数83第7章跨学科编程案例·7.3二进制什么是二进制？二进制（binary）是指以2为基数的记数系统，该系统中只有0和1两个数字。因为数字电路中的高低电位正好是两种状态，因此计算机设备都采用二进制。二进制基础知识只有0和1两个数字基数为2每一位代表2的幂次是计算机的基础语言所有数据最终都以二进制存储比特（Bit）一位二进制数字称为比特BinaryDigit的缩写是信息的最小单位1bit可以表示2种状态8bit=1byte（字节）从十进制理解二进制85第7章跨学科编程案例·7.3二进制十进制的含义十进制数123的1表示100（1×10^2），2表示20（2×10^1），3表示3（3×10^0），三者相加是123。二进制的原理相同，只是基数为2。进制基数可用数字示例含义十进制100-91231×10^2+2×10^1+3×10^0二进制20,11011×2^2+0×2^1+1×2^0八进制80-7171×8^1+7×8^0十六进制160-FFF15×16^1+15×16^0二进制转换为十进制87第7章跨学科编程案例·7.3二进制二进制数101010转换为十进制的过程：二进制位101010位置5432102的幂次2^52^42^32^22^12^0十进制值3208020计算过程32+0+8+0+2+0=42所以二进制101010=十进制427.3.2进制转换89第7章跨学科编程案例·7.3二进制编程实现进制转换理解二进制数之后，我们尝试设计程序来实现二进制与十进制之间的相互转换。将二进制数当作字符串来处理，计算过程非常简单。二进制转十进制遍历二进制数的每一位将每位数字乘以2的对应次方将所有结果相加得到对应的十进制数十进制转二进制基数除法：除以2取余逆序排列余数重复直到商为0得到对应的二进制数代码7.15：二进制转十进制91第7章跨学科编程案例·7.3二进制代码7.15#定义函数defbinary_to_decimal(b):d=0

foriin

range(len(b)):place=len(b)-1-id+=int(b[i])*(2**place)

returnd#测试函数print('请输入一个二进制数：')a=input()d=binary_to_decimal(a)print(f'{a}转为十进制={d}')运行结果请输入一个二进制数：101010101010转为十进制=42十进制转二进制：基数除法93第7章跨学科编程案例·7.3二进制基数除法将十进制数转换为二进制数一般采用基数除法，可以简单描述为：除以2取余，逆序排列余数。步骤操作商余数142/2210221/2101310/25045/22152/21061/201余数逆序排列：101010，即42(十进制)=101010(二进制)代码7.16：十进制转二进制95第7章跨学科编程案例·7.3二进制代码7.16#定义函数defdecimal_to_binary(d):b=''

whiled!=0:r=d%2

#取余数b=str(r)+b#余数放在前面（逆序）d=d//2

#整除2

returnb#测试函数print('请输入一个正整数：')n=int(input())b=decimal_to_binary(n)print(f'{n}转为二进制={b}')运行结果请输入一个正整数：4242转为二进制=101010提示b=str(r)+b是将新余数放在前面，实现逆序排列。字符串拼接非常适合这种操作。7.3.3小数转二进制97第7章跨学科编程案例·7.3二进制注意在Python中执行0.1+0.1+0.1==0.3，返回值为False！这是不合常理的。浮点数精度问题>>>0.1/0.30.33333333333333337>>>0.1+0.1+0.1==0.3False原因这是因为二进制浮点数只是一种近似，与小数的进制转换有关。大部分十进制小数都无法精确转换为二进制小数。小数转二进制的规则99第7章跨学科编程案例·7.3二进制小数转二进制的规则十进制小数转换为二进制小数的规则是乘以2取整：步骤操作整数部分小数部分10.625×210.2520.25×200.530.5×210.00.625转为二进制=0.101（整数部分顺序排列）代码7.17：小数转二进制函数101第7章跨学科编程案例·7.3二进制代码7.17#定义函数defdecimal_to_binary(d,k):b='0.'i=0

whilei<k:r=int(d*2)#取整数部分b+=str(r)d=d*2-r#去掉整数部分

ifd==0:

break

#没有小数部分了i+=1

returnb#测试函数print('请输入一个小数：')n=float(input())b=decimal_to_binary(n,20)print(f'{n}转为二进制={b}')运行结果请输入一个小数：0.6250.625转为二进制=0.101请输入一个小数：0.10.1转为二进制=0.000110011001100110010.1的精度问题103第7章跨学科编程案例·7.3二进制0.1的二进制表示从运行结果来看，0.625可以转换为一个有限的二进制小数0.101，但是0.1是一个无限循环的二进制小数：0.0001100110011...十进制小数二进制表示是否精确0.50.1精确0.250.01精确0.1250.001精确0.6250.101精确0.10.0001100110011...不精确（无限循环）0.20.001100110011...不精确（无限循环）0.30.0100110011001...不精确（无限循环）注意大部分十进制小数无法精确转换为二进制小数，这就是浮点数运算产生误差的根本原因。浮点数使用建议105第7章跨学科编程案例·7.3二进制注意事项浮点数运算可能有精度误差不要直接用==比较浮点数使用abs(a-b)<1e-9判断相等银行系统使用整数表示金额高精度计算使用decimal模块科学计算注意误差累积正确做法importdecimaldecimal.Decimal('0.1')+decimal.Decimal('0.1')+decimal.Decimal('0.1')==decimal.Decimal('0.3')返回True！需要用字符串初始化避免float传入Decimal7.3小结：二进制二进制是以2为基数的记数系统，只有0和1两个数字一位二进制数字称为比特（Bit），是信息的最小单位二进制转十进制：各位数字乘以2的对应幂次后相加十进制转二进制：除以2取余，逆序排列余数十进制小数转二进制：乘以2取整，顺序排列整数部分大部分十进制小数无法精确转换为二进制小数0.1+0.1+0.1==0.3返回False，原因是浮点数精度问题高精度计算应使用decimal模块或整数表示7.4凯撒密码了解信息加密原理，实现凯撒密码的加密与解密函数7.4.1信息加密109第7章跨学科编程案例·7.4凯撒密码信息加密的需求在传递信息时，我们希望信息经过加密处理，以保证只有接收信息的人才能理解信息的内容。例如，战争时期的情报通常都需要进行加密。凯撒密码一种简单而古老的加密技术设置整数k作为密钥将字母表中的字母以k为偏移量移动向后移动生成密文也叫移位加密或替换加密加密与解密加密：用密钥对明文进行移位解密：用密钥反向移位还原明文只有知道密钥的人才能解密密钥是加密系统的关键凯撒密码的密钥空间为25凯撒密码加密示意图111第7章跨学科编程案例·7.4凯撒密码密钥（偏移量）为2时的加密过程：明文ABCD...XYZ偏移+2+2+2+2...+2+2+2密文CDEF...ZAB加密示例A被替换成C，B被替换成D，Z被替换成B（循环回到字母表开头）PYTHON→RAVJQP（密钥k=2）凯撒密码的数学描述113第7章跨学科编程案例·7.4凯撒密码加密函数的数学表达式将所有字母对应成数字：A=0,B=1,...,Z=25加密函数：e(x)=(x+k)%26参数说明x—要加密的字符对应的数字k—密钥（偏移量）%—取余数运算26—字母表中的字母总数结果转换回字母即得密文加密示例密钥k=2P对应数字15e(15)=(15+2)%26=1717对应字母R所以P加密后得RPYTHON加密完整过程115第7章跨学科编程案例·7.4凯撒密码密钥k=2，对PYTHON应用加密函数：字母PYTHON数字x+2)%261702191615密文字母RAVJQP加密结果PYTHON经过加密后成为RAVJQP密文几乎没有任何含义，使原来的明文信息得到了保护7.4.2实现加密函数117第7章跨学科编程案例·7.4凯撒密码编程实现的关键了解凯撒密码的数学描述后，我们可以尝试通过编程的方式实现加密过程。算法本身非常简单，难点是如何将字母转换为数字。字符编码计算机用二进制存储数据字母以数字形式保存Python使用统一编码系统ord()函数：字母转数字chr()函数：数字转字母ASCII编码A对应整数值65B对应整数值66...Z对应整数值90小写字母a对应97ord()与chr()函数119第7章跨学科编程案例·7.4凯撒密码Python内置函数Python的内置函数ord()可以将字母转换为整数，chr()可以将整数转换为对应的字符。ord_chr.py>>>ord('A')65>>>ord('a')97>>>ord('Z')90>>>chr(65)'A'>>>chr(98)'b'凯撒密码中的应用A需要对应0：将ord(c)的值减去65整数转回字母：将整数值加上65再用chr()转换代码7.18：加密函数121第7章跨学科编程案例·7.4凯撒密码encrypt()函数加密函数命名为encrypt（加密的英文单词），有两个参数：需要加密的字母c和密钥k。代码7.18#凯撒密码加密函数defencrypt(c,k):x=ord(c)-65

#字母转数字（A=0）x=(x+k)%26+65

#加密并转回ASCII

returnchr(x)#数字转字母代码解析第1行：ord(c)-65将字母转换为0-25的数字第2行：(x+k)%26实现移位和循环，+65转回ASCII范围第3行：chr(x)将数字转换回字母代码7.19：加密测试123第7章跨学科编程案例·7.4凯撒密码代码7.19#凯撒密码加密函数defencrypt(c,k):x=ord(c)-65x=(x+k)%26+65

returnchr(x)#测试部分plaintext="PYTHON"

#明文key=2

#密钥ciphertext=""

#密文forcinplaintext:ciphertext+=encrypt(c,key)print(f'明文：{plaintext}')print(f'密钥：{key}')print(f'密文：{ciphertext}')运行结果明文：PYTHON密钥：2密文：RAVJQP提示加密结果与图7.8所示的结果一致，我们成功实现了凯撒密码的加密函数！7.4.3解密信息125第7章跨学科编程案例·7.4凯撒密码加密与解密在密码学中，明文信息经过加密成为密文，密文经过解密重新成为明文。解密是加密的逆操作。明文plaintext→加密encrypt→密文ciphertext→解密decrypt→明文plaintext解密函数的数学描述解密函数：d(x)=(x-k)%26与加密函数的区别：加号变为减号代码7.20：解密函数127第7章跨学科编程案例·7.4凯撒密码decrypt()函数解密函数命名为decrypt，与加密函数的结构相同，只是将加法变为减法。代码7.20#凯撒密码解密函数defdecrypt(c,k):x=ord(c)-65

#字母转数字x=(x-k)%26+65

#解密并转回ASCII

returnchr(x)#数字转字母#测试部分ciphertext="RMZCMPLMRRMZCRFYRGQRFCOSCQRGML"key=24plaintext=""forcinciphertext:plaintext+=decrypt(c,key)print(f'密文：{ciphertext}')print(f'密钥：{key}')print(f'明文：{plaintext}')运行结果密文：RMZCMPLMRRMZCRFYRGQRFCOSCQRGML密钥：24明文：TOVBEVORVNOTVTOVBEVTHATVISVTHEVQUESTION代码7.21：完整加解密程序129第7章跨学科编程案例·7.4凯撒密码处理非字母字符密文中可能包含空格或标点，这些无须解密。需要设置函数只处理字母。代码7.21alphabet='ABCDEFGHIJKLMNOPQRSTUVWXYZ'defencrypt(c,k):

ifcnot

inalphabet:returnc#非字母不处理x=ord(c)-65x=(x+k)%26+65

returnchr(x)defdecrypt(c,k):

ifcnot

inalphabet:returnc#非字母不处理x=ord(c)-65x=(x-k)%26+65

returnchr(x)#测试plaintext="TOBEORNOTTOBETHATISTHEQUESTION"key=24ciphertext=""forcinplaintext:ciphertext+=encrypt(c,key)print(f'明文：{plaintext}')print(f'密文：{ciphertext}')print(f'解密：{"".join(decrypt(c,key)forcinciphertext)}')凯撒密码的破解131第7章跨学科编程案例·7.4凯撒密码注意凯撒密码安全吗？密钥的可能只有25种，只要进行穷举测试就可以破解密钥！穷举破解凯撒密码的密钥k的取值范围是1-25。对于一段密文，我们只需要尝试所有25种密钥，查看哪种结果是有意义的明文，即可破解密码。brute_force.py#破解凯撒密码defdecrypt(c,k):x=ord(c)-65x=(x-k)%26+65

returnchr(x)ciphertext="RAVJQP"#尝试所有25种密钥forkin

range(1,26):plaintext=""

forcinciphertext:plaintext+=decrypt(c,k)

print(f"密钥{k:2d}:{plaintext}")7.4小结：凯撒密码凯撒密码是一种简单而古老的加密技术，通过字母移位实现加密加密公式：e(x)=(x+k)%26，k为密钥解密公式：d(x)=(x-k)%26ord()函数将字母转换为整数，chr()函数将整数转换为字母A对应65，加密时先减65转为0-25，运算后加65转回字母加密和解密只处理字母，空格和标点保持不变凯撒密码的密钥空间只有25，容易被穷举破解密码学中，明文→加密→密文→解密→明文7.5探索分形使用海龟绘图模块绘制基本图形，用递归实现分形树和科赫雪花7.5.1海龟绘图135第7章跨学科编程案例·7.5探索分形什么是分形？分形（fractal）是指局部类似于整体缩小后的形状，或者有自相似性的几何图形。分形树是典型的分形图案：树的主干有两个树杈，每个树杈又有两个分支，取某个分支可以发现它与完整的树具有相同的形状和结构。turtle模块俗称为海龟绘图模块Python内置的图形绘制模块最早由MIT的SeymourPapert开发是Logo语言的一部分能直观呈现数学概念分形的特点局部类似于整体缩小后的形状具有自相似性分形的实质是递归可以用递归函数来绘制自然界中广泛存在代码7.22：绘制正方形137第7章跨学科编程案例·7.5探索分形代码7.22#导入海龟绘图模块import

turtle#创建绘图海龟t=turtle.Turtle()#设置画笔颜色t.pencolor("red")#绘制正方形t.forward(100)t.left(90)t.forward(100)t.left(90)t.forward(100)t.left(90)t.forward(100)t.left(90)前进和左转的代码重复了4次，可以使用循环语句进行优化。代码7.23：循环优化绘制正方形139第7章跨学科编程案例·7.5探索分形代码7.23import

turtlet=turtle.Turtle()t.shape("turtle")#设置画笔形状为海龟t.pencolor("red")#设置画笔颜色foriin

range(4):t.forward(100)t.left(90)优化说明使用for循环替代重复代码t.shape('turtle')将画笔形状设置为海龟代码更简洁，逻辑更清晰turtle模块常用函数（表7.3）141第7章跨学科编程案例·7.5探索分形函数别称作用示例forward()fd()前进n步t.fd(100)backward()bk()后退n步t.bk(100)right()rt()右转x度t.rt(90)left()lt()左转x度t.lt(90)goto()setpos()移动至坐标t.goto(0,100)penup()up()提起画笔t.up()pendown()down()放下画笔t.down()pensize()width()画笔宽度t.pensize(5)pencolor()/画笔颜色t.pencolor('red')shape()/画笔形状t.shape('turtle')speed()/绘画速度t.speed('fast')hideturtle()ht()隐藏画笔t.hideturtle()7.5.2绘制分形树143第7章跨学科编程案例·7.5探索分形分形树的基本结构分形树的特点是每个树杈都是树的形状。我们首先需要绘制出分形树的整体，即树杈的样子：一个树干，两个树杈。绘制步骤1.绘制树干（向上前进）2.右转一定角度，绘制右树杈3.退回树干顶点4.左转一定角度，绘制左树杈5.退回原点注意事项树杈应比树干稍短符合树的形状规律使用goto()时需要提起画笔否则移动过程中会绘图设置初始位置使图形居中代码7.24：树的基本轮廓145第7章跨学科编程案例·7.5探索分形代码7.24import

turtlet=turtle.Turtle()t.shape("turtle")t.pencolor("green")t.pensize(5)t.left(90)#左转90度，画笔朝向正上方#绘制树干t.fd(100)#绘制右方树杈t.right(30)t.fd(100)#退回树干顶点t.bk(100)#绘制左方树杈t.left(60)t.fd(100)注意代码7.24并未完全完成任务：海龟没有回到原点，且树杈应比树干短。代码7.25：优化的树结构147第7章跨学科编程案例·7.5探索分形代码7.25import

turtlet=turtle.Turtle()t.shape("turtle")t.pencolor("green")t.pensize(5)t.left(90)t.up()#提起画笔t.goto(0,-100)#设置海龟初始位置t.down()#放下画笔#绘制树干t.fd(100)#绘制右方树杈t.right(30)t.fd(80)#树杈比树干短t.bk(80)#绘制左方树杈t.left(60)t.fd(80)t.bk(80)#回到原点t.right(30)t.bk(100)提示使用goto()移动时必须提起画笔，否则会画出多余的线条。纵坐标y=-100使画笔处于画布下半部分。代码7.26：递归分形树149第7章跨学科编程案例·7.5探索分形用递归实现真正的分形树分形的实质是递归。因为分形树的每一个树杈都是树的形状，所以绘制树的过程可以设计成函数，递归调用即可绘制树杈。代码7.26import

turtledeftree(t,length):

iflength<10:#基本情况

return

else:#递归步骤t.forward(length)t.right(30)tree(t,length-20)#绘制右边树杈t.left(60)tree(t,length-20)#绘制左边树杈t.right(30)t.backward(length)#退回起点t=turtle.Turtle()t.shape("turtle")t.pencolor("green")t.pensize(5)t.left(90)t.up()t.goto(0,-100)t.down()tree(t,100)分形树递归分析151第7章跨学科编程案例·7.5探索分形递归结构基本情况：length<10时停止绘制递归步骤：1.forward(length)画树干2.right(30)右转3.tree(t,length-20)画右树杈4.left(60)左转5.tree(t,length-20)画左树杈6.right(30)调正方向7.backward(length)退回设计要点每次递归length减少20确保最终收敛到基本情况backward(length)保证画笔回到起点这样才能正确绘制上一个层级可以调整length递减值和角度不同参数产生不同效果尝试调整参数对比绘图结果7.5.3科赫雪花153第7章跨学科编程案例·7.5探索分形科赫雪花科赫雪花是另一种经典的分形图形。它的基本思路是：用一条带有角的折线重复三次拼接而成。将顶部形状旋转120度重复两次即可绘制雪花的基本形状。科赫曲线的构造取一条线段将中间三分之一替换为两段形成一个等边三角形的两条边对每段重复上述过程无限重复得到科赫曲线雪花的特点由三条科赫曲线组成具有无限长度但围成有限面积是有限空间中的无限曲线体现了分形的奇妙性质代码7.27：绘制科赫雪花155第7章跨学科编程案例·7.5探索分形代码7.27import

turtlet=turtle.Turtle()t.shape("turtle")t.speed('fast')t.pencolor("red")t.pensize(3)size=100#科赫曲线（递归）defkoch(t,length,depth):

ifdepth==0:t.forward(length)

else:

foranglein[60,-120,60,0]:koch(t,length/3,depth-1)t.left(angle)#绘制雪花（3条科赫曲线）foriin

range(3):koch(t,size,3)t.right(120)提示depth参数控制递归深度，深度越大图形越精细。尝试调整depth参数观察效果变化。分形在自然界中157第7章跨学科编程案例·7.5探索分形自然界中的分形分形不仅是数学概念，在自然界中也广泛存在。许多自然现象都具有自相似性的特征。自然界中的分形海岸线的形状雪花的结构树枝和闪电的分叉花椰菜的表面河流的支流系统肺部的支气管结构血管的分布网络分形的应用计算机图形学：生成逼真地形图像压缩：分形压缩算法天线设计：小型化分形天线医学影像：分析血管结构金融市场：分析价格波动艺术创作：分形艺术作品自然界模拟：动画特效7.5小结：探索分形分形是具有自相似性的几何图形，局部类似于整体缩小后的形状turtle模块是Python内置的图形绘制工具，可以直观呈现数学概念forward()前进、left()/right()转向、penup()/pendown()控制画笔分形的实质是递归，可以用递归函数绘制分形图形分形树的基本情况是树杈长度小于阈值时停止绘制科赫雪花由科赫曲线组成，具有无限长度但围成有限面积分形在自然界中广泛存在，在计算机图形学等领域有重要应用第7章总结：跨学科编程案例素数探究：试除法优化is_prime()，探索孪生素数、素数计数和哥德巴赫猜想概率游戏：用random模块模拟掷骰子，验证帕斯卡游戏和蒙提霍尔问题的理论概率二进制：掌握二进制与十进制的相互转换，理解浮点数精度问题的根源凯撒密码：用ord()和chr()实现加密解密函数，了解密码学基础概念分形探索：用turtle模块和递归绘制分形树和科赫雪花编程不仅是工具，更是探索数学、自然科学和艺术的有力武器跨学科应用体现了编程的强大力量和广泛应用前景关键术语161第7章跨学科编程案例术语英文含义素数primenumber只有1和其本身两个因数的自然数孪生素数twinprime相差为2的一对素数试除法trialdivision只需测试到sqrt(n)的素数判断法哥德巴赫猜想Goldbach'sconjecture大于2的偶数可表示为两素数之和概率模拟probabilitysimulation用计算机模拟随机实验大数定律lawoflargenumbers实验次数越多频率越接近概率二进制binary以2为基数的记数系统比特bit一位二进制数字，信息的最小单位凯撒密码Caesarcipher通过字母移位实现的加密方法分形fractal具有自相似性的几何图形课堂测验（一）：素数探究163第7章跨学科编程案例1.试除法判断素数时，最多需要测试到哪个数？A.nB.n/2C.sqrt(n)D.n-12.孪生素数是指什么？A.两个相邻的素数B.相差为2的一对素数C.都是偶数的素数D.大于100的素数3.哥德巴赫猜想的内容是什么？A.素数有无限多个B.大于2的偶数可表示为两素数之和C.孪生素数有无限多对D.素数计数趋近于x/ln(x)课堂测验（二）：概率游戏165第7章跨学科编程案例1.帕斯卡游戏中，帕斯卡的理论胜率是多少？A.1/3B.1/2C.1-(5/6)^4≈0.518D.2/32.蒙提霍尔问题中，改变选择的胜率是多少？A.1/3B.1/2C.2/3D.1/63.大数定律告诉我们什么？A.实验次数越多结果越随机B.实验次数越多频率越接近概率C.大数比小数更准确