当前位置:码农谷 > 算法与程序 > 求自守数的程序源代码(完整源码)

求自守数的程序源代码(完整源码)

所属学科:Java语言 难度: 关注度:645

一、自守数

如果一个正整数的平方的末尾几位数等于这个数本身,那么这个数便称为自守数。自守数包含了很多特殊的性质。

8.5.1 什么是自守数

依照自守数的定义,很容易找到一些简单的自守数,例如: 

5是一个一位自守数,因为5^2=25,末尾仍然为5。

6是一个一位自守数,因为6^2=36,末尾仍然为6。

25是一个两位自守数,因为25^2=625,末尾两位仍然为25。

76是一个两位自守数,因为76^2=5 776,末尾两位仍然为76。

625是一个三位自守数,因为625^2=390 625,末尾两位仍然为625。 

376是一个三位自守数,因为376^2=141 376,末尾两位仍然为376。

……

不过,细心的读者可能会说,0和1也是自守数,因为0^2=0, 1^2=1,满足自守数的定义。不过,由于0和1这两个数过于简单,没有什么奇特的性质,因此没有太多的研究价值。故一般在数学上不将其归为自守数。

自守数有许多奇特的性质,内容如下。

1) 以自守数为后几位的两数相乘,结果的后几位仍是这个自守数

自守数的一个最基本的特点便是,以自守数为后几位的两数相乘,结果的后几位仍是这个自守数。例如,76是一个两位自守数,以76为后两位的两个数相乘,那么乘积的结果的后两位仍然是 76,示例如下:

图片29.png 

2) n+1位的自守数出自n位的自守数

在所有的自守数中,n+1位的自守数出自《位的自守数。例如:

• 625是一个三位自守数,其末尾两位为25,仍然是一个自守数。而25是一个两位自守数,其末尾一位为5,而5是一个一位自守数。

• 376是一个三位自守数,其末尾两位为76,仍然是一个自守数。而76是一个两位自守数,其末尾一位为6,而6是一个一位自守数。

这样,如果知道了n位的自守数,那么在其前面增加一位数即可成为n+1位的自守数,在有的场合可以减轻计算量。

3) 两个n位自守数的和等于10^n+1

两个n位自守数的和等于10^n+1,示例如下:

图片30.png 

1.2 计算自守数算法

计算自守数的算法需遵循自守数的定义,代码示例如下:

在上述代码中,输入参数n为待判断的整数,如果n为自守数则该方法返回1,否则返回0。程序中,首先判断输入整数n的位数,然后按照自守数的定义,计算n的平方,并对末几位进行判断,看其是否满足自守数的定义。

该算法比较简单,但是存在一定的问题。当输入参数n比较大,n和n乘积的结果将非常大,这一方面影响计算速度,另一方面容 易造成数据范围溢出。因此需要寻找更为合理的算法。

简单分析一下整数平方的计算过程,从中寻找算法的灵感。这 里以计算625的平方为例,如图1所示。

图片31.png 

图1 平方的计算过程

对于判断自守数,只需知道平方的后面3位数即可,而不必计 算整个平方的结果。从这里的计算过程可知,在每一次的部分乘积 中,并不是它的每一位都会对积的后3位产生影响。可以找到如下 规律:

•对于个位数与被乘数相乘的积中,用被乘数的后3位(625)与乘数的个位(5)相乘; 

•对于十位数与被乘数相乘的积中,用被乘数的后2位(25)与乘数的十位(20)相乘; 

•对于百位数与被乘数相乘的积中,用被乘数的后1位(5)与乘数的百位(600)相乘。

将以上各位相乘的积累加,再取最后3位即可。将上述规律推广,即可用来对多位数进行处理。按照此思路,可以编写如下自守数计算算法:

在上述代码中,输入参数n为待判断的整数,如果n为自守数则该函数返回1,否则返回0。该程序严格遵循了前面介绍的算法,读者可以对照来加深理解。

下面通过一个完整的例子来分析计算自守数算法的应用,完整的程序代码示例如下:

在该程序中,主方法分别调用了两种计算自守数的算法来列举一定范围内的自守数。

程序源码

完整的程序源代码如下:

public class Demo_4 {
   static int zishounum1(long n)           //判断自守数算法1
   {
      long temp,m,k;
      int count;
 
      k=1;
      count=0;
      while(k>0)                  //判断位数
      {
         k=n-(long)Math.pow(10,count);
         count++;
      }
      m=count-1;               //位数
      temp=(n*n)%((long)(Math.pow(10,m))); 
      if(temp==n)              //判断是否为自守数
      {
         return 1;
      }
      else

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1