C中的算法 – 用数字进行数字 – 单位为3的数字
我在接受采访时遇到了这个问题。 任何单位位置为3的数字至少有一个包含所有1的数字。 例如，3的倍数是111,13的倍数是111111.给定一个以3结尾的数字，我被问到找到包含所有1的倍数的最佳方法。 现在，一种简单的方法是可能的，你不考虑空间问题，但随着数量的增长，有时即使它没有，C中的int （或者那个！中的long int ）也不能保持那个倍数。 在C中实现这种算法的最佳方法是什么？
更新 ：纳入Ante的观察并制作答案社区维基。
像往常一样，在这类问题中，编码任何工作powershell算法都比较容易，但算法越多。 你使用铅笔和纸，你可以获得更好（更快）的算法。
让我们使用简写符号：让M（i）表示1111 … 1（i）。
给定数n（假设n = 23），您希望找到一个数m，使得M（m）可被n整除。 一个简单的方法是检查1,11,111,1111 ……直到我们找到一个可被n整除的数字。 注意：可能存在用于查找给定n的闭合forms的解 ，因此该方法不一定是最优的。
当迭代M（1），M（2），M（3），…时，有趣的部分显然是如何检查给定数字是否可被n整除。 你可以实现长除法 ，但任意精度算术很慢。 相反，请考虑以下事项：
假设您已经从之前的迭代中知道了M(i) mod n 。 如果M(i) mod n = 0 ，那么你就完成了（ M(i)就是答案），所以让我们假设它不是。 你想找到M(i+1) mod n 。 由于M(i+1) = 10 * M(i) + 1 ，因此可以很容易地计算M(i+1) mod n ，因为它是(10 * (M(i) mod n) + 1) mod n 。 即使对于较大的n值，也可以使用固定精度算法计算。
这是一个函数，它计算可被n整除的最小数量（从Ante的Python答案转换为C）：
int ones(int n) { int i, m = 1; /* Loop invariant: m = M(i) mod n, assuming n > 1 */ for (i = 1; i <= n; i++) { if (m == 0) return i; /* Solution found */ m = (10*m + 1) % n; } return -1; /* No solution */ }
您不必以“大数”的方式考虑这个问题。 拿一张纸，手工繁殖，很快就会找到最好的答案:)
首先 ，让我们考虑3x结果的单位数字
x 0 1 2 3 4 5 6 7 8 9 3x 0 3 6 9 2 5 8 1 4 7
因此，这种关系是：
what we want 0 1 2 3 4 5 6 7 8 9 multiplier 0 7 4 1 8 5 2 9 6 3
其次 ，进行乘法运算，不要保存不必要的数字。 以13为例，生成’1’，我们必须选择乘数7，所以
13 * 7 = 91
好吧，保存’9’，现在我们面临的是9.我们必须选择乘数[（11-9）％10]：
13 * 4 = 52, 52 + 9 = 61
继续！ 保存’6’。 选择乘数[（11-6）％10]
13 * 5 = 65, 65 + 6 = 71
保存’7’。 选择乘数[（11-7）％10]
13 * 8 = 104, 104 + 7 = 111
保存’11’。 选择乘数[（11-11）％10]
13 * 0 = 0, 0 + 11 = 11
保存’1’。 选择乘数[（11-1）％10]
13 * 0 = 0, 0 + 1 = 1
保存’0’。 哇〜！ 当你看到’0’时，算法结束！
最后 ，如果您在上面的一步打印’1’，那么您将获得’1’字符串答案。
像Bolo的解决方案更简单M(i+1) = 10*M(i) + 1 。 这是python版本：
def ones( n ): i = m = 1 while i <= n: if m == 0: return i m = ( ( 10 * m ) + 1 ) % n i += 1 return None
23的倍数是1111111111111111111111
#include int main () { unsigned int ones = 1; double result, by = 23, dividend = 1; while (dividend) { result = dividend / by; if (result < 1) { dividend = dividend * 10 + 1; ++ones; } else { dividend -= by * (int)result; } } while (ones--) { printf("1"); } printf("\n"); return 0; }