公因数齿轮：数据结构与算法实验

互动实验 1 / 5

48 和 18 的最大公因数是多少？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
int a=48,b=18,steps=0;
while(b){int r=a%b; a=b; b=r; ++steps;}
cout << a << " " << steps;
}

48 和 18 的最大公因数是多少？

思路提示

余数序列为 12、6、0，最后非零数为 6。

可以回到前一步复查示例，理解后再独立验证。

互动实验 2 / 5

循环执行几次？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
int a=48,b=18,steps=0;
while(b){int r=a%b; a=b; b=r; ++steps;}
cout << a << " " << steps;
}

循环执行几次？

思路提示

依次计算 48%18、18%12、12%6。

可以回到前一步复查示例，理解后再独立验证。

互动实验 3 / 5

辗转相除法保持什么不变？

选择符合算法原理和适用条件的一项。

互动实验 4 / 5

gcd(a,0) 对正整数 a 等于什么？

选择符合算法原理和适用条件的一项。

互动实验 5 / 5

求最小公倍数时怎样降低中间乘积溢出风险？

选择符合算法原理和适用条件的一项。

公因数齿轮

准备探索公因数齿轮

48 和 18 的最大公因数是多少？

循环执行几次？

辗转相除法保持什么不变？

gcd(a,0) 对正整数 a 等于什么？

求最小公倍数时怎样降低中间乘积溢出风险？

引导实验已完成。

把发现，变成独立解决问题的能力。