下面我以这样一个数学问题开篇：
有一个十位数. 第一位代表这9个数字里有几个1. 第二位代表这9个数字里有几个2. ... 第9位代表这9个数字里有几个9。 最后一位（第十位）代表这9个数字里有几个0.
请问这个十位数是几？
如果我们换个角度，从程序员的角度来看，我们能不能写一个程序来快速的解决这个问题？比如，我们可以用backtracking。那么这问题的搜索空间是大约是9,000,000,000。实际上我们写一个程序快速的试一下，可以发现由于backtracking的缘故，下面的IsValid()函数大约只会被调用1674次。
| 1 | #include <cassert> |
| 2 | #include <iostream> |
| 3 | #include <span> |
| 4 | bool IsValid(std::span<int> candidate, std::span<int> counts) { |
| 5 | assert(counts.size() == 10)(static_cast <bool> (counts.size() == 10) ? void (0) : __assert_fail ("counts.size() == 10", "/tmp/temp.cpp", 5, __extension__ __PRETTY_FUNCTION__ )); |
| 6 | assert(candidate.size() == 10)(static_cast <bool> (candidate.size() == 10) ? void (0) : __assert_fail ("candidate.size() == 10", "/tmp/temp.cpp", 6 , __extension__ __PRETTY_FUNCTION__)); |
| 7 | for (size_t i = 0; i != candidate.size(); ++i) { |
| 8 | if (counts[(i + 1) % 10] != candidate[i]) return false; |
| 9 | } |
| 10 | return true; |
| 11 | } |
| 12 | |
| 13 | int main() { |
| 14 | std::array<int, 10> candidate; |
| 15 | for (size_t index = 0; index != candidate.size(); ++index) { |
| 16 | candidate[index] = -1; |
| 17 | } |
| 18 | // The highest one cannot be zero |
| 19 | candidate[0] = 1; |
| 20 | |
| 21 | std::array<int, 10> counts; |
| 22 | int sum = 0; |
| 23 | for (size_t index = 0; index != counts.size(); ++index) { |
| 24 | counts[index] = 0; |
| 25 | } |
| 26 | counts[1] = 1; |
| 27 | sum = 1; |
| 28 | for (size_t index = 1; index != candidate.size();) { |
| 29 | if (candidate[index] == 9) { |
| 30 | if (index > 0) { |
| 31 | --counts[candidate[index]]; |
| 32 | sum -= candidate[index]; |
| 33 | candidate[index] = -1; |
| 34 | --index; |
| 35 | continue; |
| 36 | } else { |
| 37 | std::cout << "Finished" << std::endl; |
| 38 | break; |
| 39 | } |
| 40 | } |
| 41 | if (candidate[index] >= 0) { |
| 42 | sum -= candidate[index]; |
| 43 | --counts[candidate[index]]; |
| 44 | } |
| 45 | int next_number = ++candidate[index]; |
| 46 | sum += next_number; |
| 47 | ++counts[next_number]; |
| 48 | if (next_number == 0) { |
| 49 | if (counts[(index + 1) % 10] != 0) { |
| 50 | continue; |
| 51 | } |
| 52 | } |
| 53 | if (sum > 10) { |
| 54 | continue; |
| 55 | } |
| 56 | if (index + 1 == candidate.size()) { |
| 57 | if (IsValid(candidate, counts)) { |
| 58 | // Found a valid answer |
| 59 | continue; |
| 60 | } |
| 61 | } else { |
| 62 | if (next_number != 0 && next_number <= static_cast<int>(index + 1) && |
| 63 | (counts[next_number] > candidate[next_number - 1] || |
| 64 | (counts[next_number] + 9 - static_cast<int>(index) < candidate[next_number - 1]))) { |
| 65 | continue; |
| 66 | } |
| 67 | ++index; |
| 68 | } |
| 69 | } |
| 70 | return 0; |
| 71 | } |
但是如果我们换一种方式来枚举，问题就会变得简单很多。原问题中该数字的每一位加起来一定等于10。原因如下：
假设有n个一位数（每个数字大于等于0小于等于9），我们统计下这n个数字里有多少个1，记做 。统计下这n个数字里有多少个2，记做 ，...,统计下这n个数字里有多少个0，记做 。 那么显然有 。
如果把10写成几个大于0且小于10的正整数的和，有多少种可能性呢？ 答案是：41。 数学上这个问题被称为 Integer Paritition。显然，遍历这41个数字花不了多少时间。正是因为这样，当我们给小学生讲这道题的时候，也一定是从所有位加起来一定等于10这个角度来开始分析的。因为这是最有效的缩减解空间的办法。所以这个问题对我自己来说很有启发性。对于很多初等数学问题，我们可以通过写程序的方式来寻找有效的缩减解空间的方式，从而帮助我们寻找简短、人类可读的证明。