知识卡片
余数迭代逐步缩小公约数问题
对适用的非负整数,欧几里德算法反复把(a,b)换成(b,a%b),直到b为0,此时a为最大公约数。示例85与187先调整次序,187除以85余17,85除以17余0,故结果为17。算法依赖合适整数输入,原文明确省略类型检查,不能拿这段演示处理任意浮点数或非法值。
结构图:
flowchart TD
A[接收两个合格整数] --> B[按需要交换先后]
B --> C{第二数为零}
C -->|是| D[返回第一数]
C -->|否| E[计算第一数除第二数的余数]
E --> F[第二数成为第一数 余数成为第二数]
F --> C
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
while(b!=0)t=b,b=a%b,a=t;//这是求最大公约数的欧几里德算法 return a; } var gcdmemo=memorize(gcd); gcdmemo(85,187)//=>17//注意,当我们写一个递归函数时,往往需要实现记忆功能 //我们更希望调用实现了记忆功能的递归函数,而不是原递归函数 var factorial=memo
参考来源
- 位置:《JavaScript权威指南(原书第6版)》第8章《8.8.4 记忆》(spine26;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part0020.html;u196-ch08-035)。
- 结论依据:原文在“while(b!=0)”附近的定义、例子或代码支撑本卡核心说明:对适用的非负整数,欧几里德算法反复把(a,b)换成(b,a%b),直到b为0,此时a为最大公约数。边界按已读前提解释;示例未执行。
- 原始内容:while(b!=0)t=b,b=a%b,a=t;//这是求最大公约数的欧几里德算法 return a; } var gcdmemo=memorize(gcd); gcdmemo(85,187)//=>17//注意,当我们写一个递归函数时,往往需要实现记忆功能 //我们更希望调用实现了记忆功能的递归函数,而不是原递归函数 var factorial=memo