欢迎加入开源鸿蒙PC社区：
https://harmonypc.csdn.net/

atomgit仓库地址： https://atomgit.com/ai_lingshi/zhanzhuanxiangchufa

一、项目概述

1.1 项目背景

辗转相除法（Euclidean Algorithm）是计算两个整数最大公约数最古老且最高效的算法之一。本项目基于 Electron 运行时开发了一款可视化的辗转相除法计算器，能够直观展示算法的计算过程，帮助学习者理解数论基础。

1.2 功能定位

• 实时计算：输入两个整数，立即显示最大公约数
• 步骤展示：完整展示每一除法步骤，便于理解算法流程
• 扩展功能：同时计算扩展欧几里得算法，得出贝祖等式系数
• 跨平台运行：基于 Electron 支持 Windows、macOS、Linux 等多平台

1.3 技术架构

┌─────────────────────────────────────────────────────────────┐
│                    前端应用层                              │
│    (HTML5 + CSS3 + JavaScript)                            │
│    ┌─────────────┐  ┌─────────────┐  ┌─────────────┐      │
│    │  index.html │  │   style.css │  │    app.js   │      │
│    │  (结构层)   │  │   (样式层)   │  │   (逻辑层)  │      │
│    └─────────────┘  └─────────────┘  └─────────────┘      │
├─────────────────────────────────────────────────────────────┤
│              Electron + Preload 层                         │
│              (IPC 通信、API 暴露)                          │
├─────────────────────────────────────────────────────────────┤
│               HarmonyOS 原生层                             │
│         (libadapter.so + ETS Adapters)                     │
└─────────────────────────────────────────────────────────────┘

二、算法原理

2.1 辗转相除法核心原理

辗转相除法，又称欧几里得算法，其数学原理可以追溯到公元前300年古希腊数学家欧几里得的《几何原本》。

核心定理：对于任意两个正整数 a 和 b，有以下等式成立：

gcd(a, b) = gcd(b, a mod b)

直观理解：两个数的最大公约数，等于其中较小的数和两数相除余数的最大公约数。

2.2 算法终止性

算法的终止性基于以下数学事实：

条件	结果
b = 0	gcd(a, 0) =
a = 0, b = 0	gcd(0, 0) = 0（约定）
其他情况	迭代执行，直到余数为0

每一步迭代中，余数严格递减且始终非负，因此必然在有限步后达到 0。

2.3 时间复杂度

辗转相除法的时间复杂度为 O(log min(a, b))，这是因为：

1. 每一步迭代中，数值至少减少一半
2. 迭代次数不超过较小数的二进制位数
3. 在最坏情况下（如连续斐波那契数），迭代次数约为 5n 次（n 为位数）

空间复杂度为 O(1)，只需存储几个整数变量。

三、核心代码实现

3.1 标准辗转相除法

function gcd(a, b) {
    a = Math.abs(Math.floor(a));
    b = Math.abs(Math.floor(b));
    
    if (a === 0 && b === 0) return { gcd: 0, steps: [] };
    if (a === 0) return { gcd: b, steps: [] };
    if (b === 0) return { gcd: a, steps: [] };
    
    const steps = [];
    let stepNum = 1;
    
    while (b !== 0) {
        const quotient = Math.floor(a / b);
        const remainder = a % b;
        steps.push({
            num: stepNum++,
            a: a,
            b: b,
            quotient: quotient,
            remainder: remainder,
            isFinal: remainder === 0
        });
        a = b;
        b = remainder;
    }
    
    return { gcd: a, steps: steps };
}

代码流程图：

开始
  ↓
输入 a, b
  ↓
a = |a|, b = |b|
  ↓
┌─ a=0 且 b=0? ─┐
│     是        │→ 返回 {gcd: 0}
│     否        │
└───────────────┘
  ↓
┌─ a=0? ────────┐
│     是        │→ 返回 {gcd: b}
│     否        │
└───────────────┘
  ↓
┌─ b=0? ────────┐
│     是        │→ 返回 {gcd: a}
│     否        │
└───────────────┘
  ↓
循环：b ≠ 0
  ├─ 计算商: quotient = floor(a / b)
  ├─ 计算余数: remainder = a % b
  ├─ 记录步骤
  ├─ a = b
  └─ b = remainder
  ↓
b = 0 时退出
  ↓
返回 {gcd: a, steps: [...]}

3.2 扩展欧几里得算法

扩展欧几里得算法不仅能计算最大公约数，还能找到贝祖等式的系数：

function extendedGcd(a, b) {
    a = Math.abs(Math.floor(a));
    b = Math.abs(Math.floor(b));
    
    if (a === 0) return { gcd: b, x: 0, y: 1 };
    if (b === 0) return { gcd: a, x: 1, y: 0 };
    
    let x1 = 0, y1 = 1;
    let x2 = 1, y2 = 0;
    
    while (b !== 0) {
        const quotient = Math.floor(a / b);
        const remainder = a % b;
        
        a = b;
        b = remainder;
        
        const tempX = x2 - quotient * x1;
        const tempY = y2 - quotient * y1;
        x2 = x1;
        y2 = y1;
        x1 = tempX;
        y1 = tempY;
    }
    
    return { gcd: a, x: x2, y: y2 };
}

贝祖等式：对于任意整数 a 和 b，存在整数 x 和 y 使得：

ax + by = gcd(a, b)

应用场景：

• 模逆元计算：a⁻¹ mod m（当 gcd(a, m) = 1 时）
• 解线性同余方程：ax ≡ c (mod m)
• RSA 加密算法中的密钥生成

四、交互界面实现

4.1 HTML 结构设计

<div class="calculator-section">
    <div class="input-row">
        <div class="input-group">
            <label for="num1">整数 a</label>
            <input type="number" id="num1" value="48">
        </div>
        
        <div class="operator">÷</div>
        
        <div class="input-group">
            <label for="num2">整数 b</label>
            <input type="number" id="num2" value="18">
        </div>
        
        <button id="calculateBtn">计算 GCD</button>
    </div>
    
    <div id="result" class="result-container"></div>
    <div id="steps" class="steps-container"></div>
</div>

设计要点：

• 横向布局：输入框 + 除号 + 输入框 + 按钮
• 默认值 48 和 18 是经典示例
• 语义化标签，便于无障碍访问

4.2 事件处理

function initCalculator() {
    const calculateBtn = document.getElementById('calculateBtn');
    const num1Input = document.getElementById('num1');
    const num2Input = document.getElementById('num2');
    
    // 绑定按钮点击事件
    calculateBtn.addEventListener('click', calculate);
    
    // 绑定回车键事件
    num1Input.addEventListener('keypress', (e) => {
        if (e.key === 'Enter') calculate();
    });
    
    num2Input.addEventListener('keypress', (e) => {
        if (e.key === 'Enter') calculate();
    });
    
    // 初始化时自动计算一次
    calculate();
}

交互设计：

• 按钮点击触发计算
• 回车键快捷计算
• 页面加载时自动计算默认值

4.3 结果展示模块

function displayResult(result, extResult, num1, num2) {
    const resultDiv = document.getElementById('result');
    const stepsDiv = document.getElementById('steps');
    
    // 主结果展示
    resultDiv.innerHTML = `
        <h3>计算结果</h3>
        <div class="gcd-value">GCD(${num1}, ${num2}) = ${result.gcd}</div>
        <p class="formula">
            验证：${num1} = ${result.gcd} × ${Math.floor(num1 / result.gcd)}
        </p>
    `;
    
    // 步骤展示
    let stepsHtml = '<h3>计算步骤</h3>';
    
    result.steps.forEach((step) => {
        if (step.isFinal) {
            stepsHtml += `
                <div class="step final">
                    <div class="step-number">✓</div>
                    <div class="step-equation">
                        ${step.a} ÷ ${step.b} = ${step.quotient} ... 
                        <span class="step-remainder">${step.remainder}</span>
                    </div>
                    <span class="step-note">余数为0，计算结束</span>
                </div>
            `;
        } else {
            stepsHtml += `
                <div class="step">
                    <div class="step-number">${step.num}</div>
                    <div class="step-equation">
                        ${step.a} ÷ ${step.b} = ${step.quotient} ... 
                        <span class="step-remainder">${step.remainder}</span>
                    </div>
                    <span class="step-note">继续</span>
                </div>
            `;
        }
    });
    
    // 扩展算法结果
    stepsHtml += `
        <div class="extended-section">
            <h3>扩展欧几里得算法</h3>
            <p class="bezout-equation">
                ${num1} × ${extResult.x} + ${num2} × ${extResult.y} = ${extResult.gcd}
            </p>
        </div>
    `;
    
    stepsDiv.innerHTML = stepsHtml;
}

五、视觉样式设计

5.1 整体风格

应用采用现代深色主题设计：

body {
    font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Roboto, sans-serif;
    background: linear-gradient(135deg, #1a1a2e 0%, #16213e 50%, #0f3460 100%);
    min-height: 100vh;
    color: #fff;
}

设计特点：

• 深蓝紫色渐变背景，营造专业感
• 玻璃态卡片效果，增强层次感
• 紫色渐变作为主题色

5.2 输入框设计

.input-group input {
    width: 100%;
    padding: 14px 18px;
    background: rgba(255, 255, 255, 0.08);
    border: 1px solid rgba(255, 255, 255, 0.15);
    border-radius: 10px;
    color: #fff;
    font-size: 1.2rem;
    font-family: 'Courier New', monospace;
    transition: all 0.3s ease;
}

.input-group input:focus {
    outline: none;
    border-color: #667eea;
    background: rgba(102, 126, 234, 0.1);
    box-shadow: 0 0 20px rgba(102, 126, 234, 0.2);
}

设计要点：

• 等宽字体 (Courier New) 便于数字对齐
• 聚焦时边框发光，提供即时反馈
• 半透明背景保持深色主题一致性

5.3 步骤展示卡片

.step {
    display: flex;
    align-items: center;
    gap: 20px;
    padding: 12px 0;
    border-bottom: 1px solid rgba(255, 255, 255, 0.05);
}

.step.final {
    margin-top: 20px;
    padding-top: 20px;
    border-top: 2px solid rgba(102, 126, 234, 0.3);
}

.step.final .step-number {
    background: rgba(0, 255, 136, 0.2);
    color: #00ff88;
}

视觉效果：

• 圆形编号标识步骤顺序
• 最终步骤使用绿色高亮
• 等宽字体确保数字对齐

六、计算示例演示

6.1 示例一：GCD(48, 18)

输入：a = 48, b = 18

计算过程：

步骤	操作	说明
1	48 ÷ 18 = 2 … 12	第一步，48 = 2×18 + 12
2	18 ÷ 12 = 1 … 6	第二步，18 = 1×12 + 6
3	12 ÷ 6 = 2 … 0	余数为0，结束

结果：GCD(48, 18) = 6

扩展结果：

• 48 × (-1) + 18 × 3 = -48 + 54 = 6
• 验证：48 = 6×8，18 = 6×3

6.2 示例二：GCD(1071, 462)

输入：a = 1071, b = 462

计算过程：

步骤	操作	说明
1	1071 ÷ 462 = 2 … 147	1071 = 2×462 + 147
2	462 ÷ 147 = 3 … 21	462 = 3×147 + 21
3	147 ÷ 21 = 7 … 0	结束

结果：GCD(1071, 462) = 21

应用：这个例子来自经典的"稻田问题"——测量者每隔21步留下脚印。

6.3 示例三：互质数 GCD(17, 13)

输入：a = 17, b = 13

计算过程：

步骤	操作	说明
1	17 ÷ 13 = 1 … 4	17 = 1×13 + 4
2	13 ÷ 4 = 3 … 1	13 = 3×4 + 1
3	4 ÷ 1 = 4 … 0	结束

结果：GCD(17, 13) = 1

扩展结果：

• 17 × (-3) + 13 × 4 = -51 + 52 = 1
• 模逆元：17⁻¹ ≡ -3 ≡ 10 (mod 13)

七、算法变体

7.1 递归版本

function gcdRecursive(a, b) {
    a = Math.abs(Math.floor(a));
    b = Math.abs(Math.floor(b));
    
    if (b === 0) return a;
    return gcdRecursive(b, a % b);
}

特点：

• 代码更简洁优雅
• 但大数计算时有栈溢出风险

7.2 二进制 GCD（Stein 算法）

function gcdBinary(a, b) {
    a = Math.abs(Math.floor(a));
    b = Math.abs(Math.floor(b));
    
    if (a === 0) return b;
    if (b === 0) return a;
    
    let shift = 0;
    
    // 同时除以2
    while ((a & 1) === 0 && (b & 1) === 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    
    // a为奇数
    while ((a & 1) === 0) a >>= 1;
    
    // 主循环
    while (b !== 0) {
        while ((b & 1) === 0) b >>= 1;
        if (a > b) [a, b] = [b, a];
        b -= a;
    }
    
    return a << shift;
}

优化点：

• 只使用移位和减法，避免除法
• 在硬件实现中效率更高

八、实际应用

8.1 分数化简

function simplifyFraction(numerator, denominator) {
    const gcdValue = gcd(numerator, denominator);
    return {
        numerator: numerator / gcdValue,
        denominator: denominator / gcdValue,
        gcd: gcdValue
    };
}

// 示例
simplifyFraction(48, 18);
// 返回 { numerator: 8, denominator: 3, gcd: 6 }
// 48/18 化简为 8/3

8.2 模逆元计算

function modInverse(a, m) {
    const g = gcd(a, m);
    if (g !== 1) return null;  // 模逆元不存在
    
    const result = extendedGcd(a, m);
    let x = result.x % m;
    return x < 0 ? x + m : x;
}

// 示例
modInverse(3, 11);
// 返回 4，因为 3 × 4 = 12 ≡ 1 (mod 11)

九、总结

9.1 核心要点

要点	说明
算法原理	gcd(a, b) = gcd(b, a mod b)
时间复杂度	O(log min(a, b))
空间复杂度	O(1)
终止条件	余数为0时的除数即为最大公约数
扩展功能	可计算贝祖等式系数

9.2 实现亮点

1. 步骤可视化：每一步除法清晰展示，便于学习理解
2. 双向计算：同时提供标准算法和扩展算法
3. 现代 UI：玻璃态效果，流畅交互动画
4. 响应式设计：适配桌面端和移动端
5. 自动计算：页面加载即显示结果

9.3 扩展方向

扩展功能	实现难度	说明
质因数分解	中	基于 GCD 的质因数分解
最小公倍数	低	LCM(a, b) = a × b / GCD(a, b)
可视化动画	中	逐步动画展示算法过程
大数支持	中	使用 BigInt 处理超大整数

辗转相除法作为数论中最基础的算法之一，其简洁性和高效性使其在计算机科学中具有重要地位。本项目通过可视化的方式，帮助学习者深入理解算法的本质。