在1到100中找10个不同的数,使其倒数和为1。从小到大排列这10个数,有一个不同就视为不同的解。求所有的解。
程序的原始版本不是我写的,是quantek@HiPDA。
基本思路是用抽屉原则,确定每重循环/递归的搜索上限,进行剪枝。 比如:最开始的和是1,这个和需要分给10个数,那么至少有一个数分到的值是不小于1/10的,那么第一重循环的上限不大于10。
计算出来后,用大数运算库GMP校验一下。校验的时候,第10个整数分别用(int)i10、(int)i10 + 1、(int)i10 - 1去尝试。
整个代码也可以不用double来运算,而是用GMP的自然数库来运算。
ReciprocalSearch2.cpp这个用GMP算出来的是69014个解,详见txt文件。5800 X3D CPU上算了1241秒。
ReciprocalSearch3.cpp这个改用uint64_t进行大整数运算,也可以在30秒以内完成。