求自守数

【原理】
【算法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; }

【测试结果】
求自守数
文章图片


    推荐阅读