《孙子算经》编程解法

"物不知数"问题的筛选法可视化

通过交互式演示,理解古代数学问题的现代编程解法

问题描述

《孙子算经》记载:

"今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?"

现代数学解释:

寻找满足以下条件的整数 x

筛选法步骤

步骤1: 初始化标记数组,所有数标记为0
步骤2: 筛选除以3余2的数,符合条件的标记+1
步骤3: 筛选除以5余3的数,符合条件的标记+1
步骤4: 筛选除以7余2的数,符合条件的标记+1
步骤5: 找出标记值为3的数(满足所有条件)

核心代码

// 筛选法核心代码
for (i = 1; i <= 3; i = i + 1) {
    y = 0;  // y是a[i]的倍数
    
    while (y <= N) {
        x = y + b[i];  // x符合除以a[i]余b[i]
        
        if (x <= N) 
            f[x] = f[x] + 1;  // 符合当前条件的数标记+1
        
        y = y + a[i];  // 跳到下一个a[i]的倍数
    }
}

筛选过程可视化

选择筛选条件,查看符合条件的数字:

未标记 (f[x]=0)
满足1个条件 (f[x]=1)
满足2个条件 (f[x]=2)
满足3个条件 (f[x]=3)

筛选结果

当前符合条件的数字:

数学原理

这个问题是中国剩余定理的特例。由于3、5、7两两互质,解的形式为:

x = 23 + 105k (k为整数,105是3、5、7的最小公倍数)

所以在500以内,满足条件的数为:23, 128, 233, 338, 443