8.字数论公开课.pptx

该【8.字数论公开课 】是由【286919636】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【8.字数论公开课 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第八讲数论2019-05-171一、数论质数公约数斐波那契数列2019-05-172二、质数质数又称素数,指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。,只有1和本身能整除,其它都不能整除,该数就是质数;利用数学知识可以将判断的条件改为[2,int(n**)+1]。2019-05-173二、质数输出100以内的质数思路1:枚举100以内的每个数,若是质数,则输出该数。2019-05-174二、质数思路2:埃拉托斯特尼筛法先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。2019-05-175三、最大公约数最大公因数,指几个整数中公有的约数,其中最大的一个,叫做这几个数的最大公约数。例如:12、16的公约数有1、2、4,其中最大的一个是4,4是12与16的最大公约数,一般记为(12,16)=4。12、15、18的最大公约数是3,记为(12,15,18)=3。求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法。2019-05-176三、最大公约数方法1枚举法求两数a,b(num为a,b中较小者)的最大公约数,步骤如下:①用a,b去整除num,若两数都能整除,则输出num并结束,否则转②。②num减1,当num=1,输出最大公约数1,否则转①。2019-05-177三、最大公约数方法2质因数分解法把每个数分别分解质因数,再把各数中的公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。例如:求24和60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24与60的全部公有的质因数是2、2、3,它们的积是2×2×3=12,所以,(24,60)=12。2019-05-178三、最大公约数方法3辗转相除法辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。步骤如下:①求num1除以num2的余数r;②当r==0,则输出最大公约数num2并结束,否则,转到③;③num2赋值num1,r赋值num2,再求num1除以num2的余数r;转到②;2019-05-179四、斐波那契数列斐波那契数列(isequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(i)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用。求斐波那契数列第n项的实现方法有递归,递推,生成器等。2019-05-1710