一、公约数二、素数三、置换四、解递推方程的几个实例公约数欧几里德辗转相除法n个数的最大公约数不定方程的整数解扩展欧几里德算法程序框架素数(prime)Eraosthenes筛法（筛选法）伪素数测试伪素数测试例Fibonacci素数分析分析推论置换n个元素1,2,…,n之间的一个置换1，2，3，4，……，na1,a2,a3,a4,……，an表示1被1到n中的某个数a1取代，2被1到n中的某个数a2取代，直到n被1到n中的某个数an取代，且a1,a2,…,an互不相同。置换群置换群的元素是置换，运算是置换的连接置换的循环节12345=(134)(25)这个置换有两个循环节35412例1循环节个数例2不变状态汉诺塔问题分析直线与平面Josephus问题一般约瑟夫问题的解法：线性表模拟。时间复杂度O(nm)本题的特殊性：m=2第一圈报完数后，编号为偶数的人就全部出圈了。此时圈中剩下[n/2]个人。若n是偶数，此时又从编号为1的人开始报1；若n是奇数，编号为1的人出圈，从编号为3的人开始报1。第二圈与第一圈有类似性！如何利用？1分析扩展-THEEND-