c++ - 有人可以向我解释一下这个 CodeForces 919B/Perfect Number 解决方案吗？

Question

这是我找到的 CodeForces 问题 919B - Perfect Number 的解决方案。我在技术上理解它在做什么，但我想了解它背后的“直觉”或想法/方法。

int main(){
    int k=0, m=19, c=0, sum=0;
    scanf("%d", &k);
    while(true){
        int n = m;
        sum = 0;
        while(n){
            sum+=n%10;
            n=n/10;
        }
        printf("%d %d %d\n", n, sum, c);
        if(sum == 10) c++;
        if(c == k) break;
        m++;
    }
    printf("%d", m);
    return 0;
}

Answer 1

用户0x499602D2已经给出了非常简洁的回答，我再详细说一下。超高级伪代码如下所示:

loop over natural numbers and check if they are perfect:
  if found k such numbers: 
    stop and output the last perfect number

这是一个更详细的伪代码，与您的 c++ 代码相匹配:

m   = 19 # first perfect number (1+9=10) - a good starting point
c   = 0  # total number of perfect numbers found so far
sum = 0  # temporary variable that will hold the sum of digits

read k from stdin # we're going to look for the k-th perfect number 

# we start an open-ended search but we know that we will find k-th number and stop
for m = 19 ... infinity:
  if m is perfect:
    increment c by one        # found c perfect numbers so far

  if c == k:           
    exit loop and return m    # m is the k-th perfect number! we're done!

看看 c 是如何对应于我们找到的“完全数”的？一旦 c 命中 k，我们的循环就可以停止。

还有一个技术问题:我们如何检查数字 1945 是否完美？我们需要对数字求和:1+9+4+5。从数字 n 中获取最低有效数字的一种简单方法是将除以 10 的余数(即 n 模 10):

1945 % 10 = 5
194  % 10 = 4
19   % 10 = 9
1    % 10 = 1

如何从 1945 到 194 再到 19 到 1？只需将整数除以 10:

1945/10 = 194
 194/10 = 19
  19/10 = 1
   1/10 = 0 -> stop the loop, since while(0) is the same as while(false)

这就是 printf 之前发生的事情。