求自守数 C语言

【原理】
【算法1代码】

#include #define N 100000//Get Automorphic Number from 1 to N void AutoNumber() { int i,tail, number, k, a, b; for (number = 376; number < N; number++) { for (i = number, k = 1; (i /= 10) > 0; k *= 10); //确定number是几位数，如376就是3位数，k=100，接下来while循环也会执行3次，对应获取的三次部分积a = k * 10; //确定要截取的部分积的位数，通常为10^尾数的位数，如376位数为3，平方后要截取3位数，所以应该用1000去截取（即除余）部分积的位数，获得的才是3位数 tail = 0; //要求的平方的尾数，如376平方为141376，平方数最后三位376是要求的位数 b = 10; //截取乘数的位数，如376第一截取的就是6.总的来说，第一拿376作为被乘数，6作为乘数while (k > 0) { int m, n, p,q,t; m = number % (k * 10); //截取被乘数的后N位，如376，第一次求部分积时，全部位数会影响到平方的尾数，所以要乘以10 n = number % b; //截取乘数的倒数第M位，如376，第二次部分积为76 p = number % (b / 10); //减去倒数第M-1位，如376第二次部分积乘数为70，所以应该用76-6 q = m * (n - p); //得到包含后N位的第M次部分积 t = tail + q; //加到上一个部分积中去tail = t % a; //获得部分积的尾数k /= 10; //在乘法中，被乘数向左移位，所以此时被乘数的后N-1位影响平方的尾数，所以除以10 b *= 10; //进入下一个部分积，乘数应该往高位移动/*总结：公式=（部分积+截取被乘数的后N位*截取乘数的第M位）%要分离的位数对应的10的倍数*/ }if (number == tail) printf("%d ", number); }}int main() { AutoNumber(); return 0; }

【求自守数】【算法2代码】

#include #define N 10000int Count(int num) { int c = 1; while ((num = num / 10) != 0) { c++; } return c; }//Get the last several numbers of n int TailNum(int num, int s) { int i, radix, tail = 0; radix = 1; for (i = 0; i < s; ++i) { tail += radix * (num % 10); radix *= 10; num /= 10; } return tail; }//Get Automorphic Number from 1 to N void AutoNumber() { int i, s, t; for (i = 0; i <= N; ++i) { s = Count(i); t = TailNum(i*i, s); if (i == t) printf("%d ", i); } }int main() { AutoNumber(); return 0; }

【测试结果】