算法初步全章 算法案例1孙子问题.ppt

《算法初步全章 算法案例1孙子问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、流程图算法的描述算法自然语言顺序结构条件结构循环结构顺序结构条件结构循环结构输语句伪代码循环语句赋值语句条件语句入出中国剩余定理(孙子问题)“孙子问题”记载在《孙子算经》中，原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”孙子问题的现代数学描述“孙子问题”相当于求关于x,y,z的方程组的正整数解。解题分析（1）如何依次检索正整数？（采用循环结构）（2）该循环何时结束？（找到满足条件的整数为止）（3）一个正整数m什么时候满足方程？（m同时满足被3除余2，被5除余3，被7除余2）引入记号：m被3除余2用符号表示为Mod(m，3)＝2；m被5除

2、余3用符号表示为Mod(m，5)＝3；m被7除余3用符号表示为Mod(m，7)＝2流程图伪代码m2WhileMod(m,3)≠2orMod(m,5)≠3orMod(m,7)≠2mm＋1EndWhilePrintm例1有3个连续的自然数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，求满足要求的一组三个连续的自然数。分析：本题的其实就是求下面不定方程组的正整数解.算法S1取m＝1；S2当m不能被15整除，或m＋1不能被17整除，或m＋2不能被19整除，则mm＋1，转S2；否则输出m，m＋1，m＋2，算法结束.流程图m1WhileMod(m,15)

3、≠2_orMod(m＋1,17)≠0_orMod(m＋2,19)≠0mm＋1EndWhilePrintm，m+1，m+2伪代码思考：以下伪代码是否可行？k1a15kWhileMod(a＋1,17)≠0or_Mod(a＋2,19)≠0kk＋1a15kEndWhilePrinta,a＋1,a＋2本课小结1．韩信点兵－孙子问题的求解算法；2．利用循环结构实现整数的搜索；3．利用逻辑运算符Or实现多条件的判断。