知识卡片

结构图卡 · 6133.b

余数迭代逐步缩小公约数问题

理解等级:中级

对适用的非负整数,欧几里德算法反复把(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