A*******e
发帖数: 2419 | 1 不可能出现无限不循环的情况吗？如何证明？停机条件怎么写呢？ | h*c
发帖数: 23 | 2 During the processing, it will get smaller (see Wiki), so detecting looping
or 1 works:
To see this fact, first note that if n has m digits, then the sum of the
squares of its digits is at most 9^2 m, or 81m.
For m=4 and above, n > 10^{m-1} > 81m
so any number over 1000 gets smaller under this process and in particular
becomes a number with strictly fewer digits. Once we are under 1000, the
number for which the sum of squares of digits is largest is 999, and the
result is 3 times 81, that is, 243. | i******o
发帖数: 171 | 3 solution0: while(n != 1)
solution1: while(n != 1 && n != 4);
solution2: for(int i = 0; i < 8; i++);
all above three solution works and pass the leetcode OJ.
【在 A*******e 的大作中提到】
: 不可能出现无限不循环的情况吗？如何证明？停机条件怎么写呢？
| A*******e
发帖数: 2419 | 4 why they work? any proof like the 2nd floor?
passing OJ doesn't mean it's right. the correctness of an algorithm cannot
be assured by a set of test cases.
【在 i******o 的大作中提到】
: solution0: while(n != 1)
: solution1: while(n != 1 && n != 4);
: solution2: for(int i = 0; i < 8; i++);
: all above three solution works and pass the leetcode OJ.
| l******s
发帖数: 3045 | 5 不会。个位数平方最大81，不管起始多么长的数字，到最后都会缩短到不超过三位数内
的循环，循环一千次总有重复的。
【在 A*******e 的大作中提到】
: 不可能出现无限不循环的情况吗？如何证明？停机条件怎么写呢？
|
|
