中国剩余定理(孙子问题).pptx
《中国剩余定理(孙子问题).pptx》由会员分享,可在线阅读,更多相关《中国剩余定理(孙子问题).pptx(11页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、流 程 图算法的描述算法自然语言顺序结构条件结构循环结构顺序结构条件结构循环结构输 语句伪 代 码循环语句赋值语句条件语句入出中国剩余定理中国剩余定理 (孙子问题孙子问题)“孙子问题孙子问题”记载在孙子算经中,记载在孙子算经中,原文是:原文是:“今有物不知其数,三三今有物不知其数,三三数之剩二,五五数之剩三,七七数数之剩二,五五数之剩三,七七数之剩二,问物几何?之剩二,问物几何?”孙子问题的现代数学描述孙子问题的现代数学描述“孙子问题孙子问题”相当于求关于相当于求关于x,y,z的方程组的方程组的正整数解。的正整数解。解题分析解题分析(1)如何依次检索正整数?)如何依次检索正整数?(采用循环结构
2、)(采用循环结构)(2)该循环何时结束?)该循环何时结束?(找到满足条件的整数为止)(找到满足条件的整数为止)(3)一个正整数)一个正整数m什么时候满足方程?什么时候满足方程?(m同时满足被同时满足被3除余除余2,被,被5除余除余3,被,被7除余除余2)引入记号引入记号:m被被3除余除余2用符号表示为用符号表示为Mod(m,3)2;m被被5除余除余3用符号表示为用符号表示为Mod(m,5)3;m被被7除余除余3用符号表示为用符号表示为Mod(m,7)2 流程图流程图 伪代码伪代码 m 2While Mod(m,3)2)2 or Mod(m,5)3)3 or M or Mod(m,7)2)2 m
3、 m1End WhilePrint m例1 有3个连续的自然数,其中最小的能被15整除,中间的能被17整除,最大的能被19整除,求满足要求的一组三个连续的自然数。分析:本题的其实就是求下面不定方程组的正整数解分析:本题的其实就是求下面不定方程组的正整数解.算法S1 取取m1;S2 当当m不能被不能被15整除,或整除,或m1不能被不能被17整除,或整除,或m 2不能被不能被19整除,则整除,则mm1,转,转S2;否则输;否则输 出出m,m1,m2,算法结束,算法结束.流程图 m 1While Mod(m,15)2_)2_ or Mod(m1,17)0_)0_ orM orMod(m2,19)0)0 m m1End WhilePrint m,m+1,m+2伪代码伪代码思考:以下伪代码是否可行?思考:以下伪代码是否可行?k1a15kWhile Mod(a1,17)0 or_ Mod(a2,19)0 kk1 a15kEnd While Print a,a1,a2本课小结本课小结1韩信点兵孙子问题的求解算法;韩信点兵孙子问题的求解算法;2利用循环结构实现整数的搜索;利用循环结构实现整数的搜索;3利用逻辑运算符利用逻辑运算符Or实现多条件的判断。实现多条件的判断。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国 剩余 定理 孙子 问题
限制150内