一道算术题🧮背后的算法迭代

前段时间看到一道题，觉得是无聊开会时绝佳的消遣项目：

一个 10 位数 ab,cdef,ghij，各位不同，且满足：

题干

有天开了半天会，结果还是没有手算出来。就想着用脚本跑跑呗。

第一版·傻大粗黑

10.times do |a|
    10.times do |b|
        10.times do |c|
            10.times do |d|
                10.times do |e|
                    10.times do |f|
                        10.times do |g|
                            10.times do |h|
                                10.times do |i|
                                    10.times do |j|
                                        next if a % 1 != 0
                                        next if "#{a}#{b}".to_i % 2 != 0
                                        next if "#{a}#{b}#{c}".to_i % 3 != 0
                                        next if "#{a}#{b}#{c}#{d}".to_i % 4 != 0
                                        next if "#{a}#{b}#{c}#{d}#{e}".to_i % 5 != 0
                                        next if "#{a}#{b}#{c}#{d}#{e}#{f}".to_i % 6 != 0
                                        next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}".to_i % 7 != 0
                                        next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}".to_i % 8 != 0
                                        next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}#{i}".to_i % 9 != 0
                                        next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}#{i}#{j}".to_i % 10 != 0
                                        
                                        next if [a, b, c, d, e, f, g, h, i, j].uniq.size != 10
                                        
                                        puts "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}#{i}#{j}"
                                    end
                                end
                            end
                        end
                    end
                end
            end        
        end 
    end
end

跑了几分钟还没出结果。想着不对啊。算了一下：就算每秒算 100,0000 条，跑完 10^10 也得 2.7 个小时。等不起，等不起☹️。

第二版 ·剪枝✂️：

稍稍改进下吧。原本是预计会提高一倍，结果出奇地块😱：0.18 秒找到答案 3816547290

10.times do |a|
    next if a % 1 != 0
    10.times do |b|
        next if "#{a}#{b}".to_i % 2 != 0
        10.times do |c|
            next if "#{a}#{b}#{c}".to_i % 3 != 0
            10.times do |d|
                next if "#{a}#{b}#{c}#{d}".to_i % 4 != 0
                10.times do |e|
                    next if "#{a}#{b}#{c}#{d}#{e}".to_i % 5 != 0
                    10.times do |f|
                        next if "#{a}#{b}#{c}#{d}#{e}#{f}".to_i % 6 != 0
                        10.times do |g|
                            next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}".to_i % 7 != 0
                            10.times do |h|
                                next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}".to_i % 8 != 0
                                10.times do |i|
                                    next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}#{i}".to_i % 9 != 0
                                    10.times do |j|
                                        next if "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}#{i}#{j}".to_i % 10 != 0
                                        next if [a, b, c, d, e, f, g, h, i, j].uniq.size != 10
                                        
                                        puts "#{a}#{b}#{c}#{d}#{e}#{f}#{g}#{h}#{i}#{j}"
                                    end
                                end
                            end
                        end
                    end
                end
            end        
        end 
    end
end

第三版·用上排列：

想到如果一开始就用 0 ～ 9 的排列来排查，应该会省很多计算吧。

(0..9).to_a.permutation.each do |ary|
    found_it = true
    ary.each_with_index do |v, i|
        if ary[0 .. i].join.to_i % (i + 1) != 0
            found_it &= false
        end
    end
    puts ary.join if found_it
end

代码是省了不少，但反而慢了很多（101.8 秒），怪了🤔。加个 break 试试：

(0..9).to_a.permutation.each do |ary|
    found_it = true
    ary.each_with_index do |v, i|
        if ary[0 .. i].join.to_i % (i + 1) != 0
            found_it &= false
            break # 如果是 next 就没用。
        end
    end
    puts ary.join if found_it
end

快了一点 17.3 秒。

第四版·手工计算

当然，我们的终极梦想是能笔算出来😝。

（挖坑🕳️）

---

从这个例子可以看出，数学不过是在找出内在结构，罢了。