具体数学-第4章-数论(4.4节-4.6节).pptx

第4章 数论（Number Theory） 鞠成东 E-mail：juchd@ M. P. 参考教材与书目 。 参考教材与书目 书名：具体数学：计算机科学基础（第2版） 原书名：Concrete Mathematics: A Foundation for Computer Science (2nd Edition) 作者：(美)Ronald L. Graham, Donald E. Knuth, Oren Patashnik 译者：张明尧，张凡 出版社：人民邮电出版社 ISBN：978-7-115-30810-8 课程教学内容 ● 第1章 递归问题 ● 第2章 和式（选讲） ● 第3章 整值函数 ● 第4章 数论 ● 第5章 二项式系数 ● 第6章 特殊的数 ● 第7章 生成函数（自学） ● 第8章 离散概率 ● 第9章 渐进式 课程教学内容 ● It introduces the mathematics that supports the analysis of algorithms, modeling probems in real world. See, Chap. 1 – Recurrence 递归的计数 Chap. 2 – Sum 各种求和，用于算法复杂度计算等 Chap. 6 – Special Numbers 调和数列及有关求和问题 ● Concrete mathematics is a blending of continuous and discrete mathematics. See, Chap. 3 – Integer Functions 实数的整数部分运算 Chap. 9 – Asymptotics 离散到连续的渐进 课程教学内容 ● The goal is for the student to have mathematical skills to solve complex problems, and to discover subtle patterns in data. Chap. 7 – Generating Functions 用于概率计算的母函数 Chap. 8 – Discrete Probability 离散问题概率(最有趣) 本章教学内容 ● 4.4 阶乘的因子（Factorial Factors） ● 4.2 互素（Relative Primality） ● 4.3 mod：同余关系（MOD: The Congruence Relation） 8 4.4 阶乘的因子 n 0 1 2 3 4 5 6 7 8 9 10 n! 1 1 2 6 24 120 720 5040 40320 362880 3628800 9 10 11 由于阶乘有广泛的应用，因此对大数阶乘算法的优化问题是很重要的，这就涉及到大数的存储、表示和计算的方式方法等问题。 菜鸟篇 程序1：一个最直接的计算阶乘的 程序2：稍微复杂了一些，使用了递归，一个C++初学者写的程序 12 程序1：一个最直接的计算阶乘的程序 #include stdio.h #include stdlib.h int main(int argc, char* argv[]){ long i,n,p=1; scanf(%d,n); for (i=1;i=n;i++) p*=i; printf(%d!=%d/n,n,p); return 0; } 13 程序2：稍微复杂了一些，使用了递归。 #include iostream.h long int fac(int n); void main() { int n; coutinput a positive integer:; cinn; long fa=fac(n); coutn! =faendl; } long int fac(int n) { 语句略; } 14 程序点评：这两个程序在计算12以内的数是正确的，但当n12时，程序的计算结果就完全错误了，单从算法上讲，程序并没有错，错误的原因在于long型整数能够表示的范围是很有限的。当n=13时，计算结果溢出，在C语言，整数相乘时发生溢出时不会产生任何异常，也不会给出任何警告。 怎么办？将程序1中的long型换成do