黑马程序员技术交流社区

标题: 算法：K尾相等数 [打印本页]

---

作者: 小骁叔    时间: 2013-11-19 16:14
标题: 算法：K尾相等数
从键盘输入一个自然数K(K>1)，若存在自然数M和N（M>N），使得K^M和K^N均大于或等于1000，且他们末尾三位数相等，则称M和N是一对“K尾相等数”。编写一程序，输出M+N值最小的K尾相等数。

---

作者: 小骁叔    时间: 2013-11-19 16:15
解题：

无论什么题目，首先是读懂题目意思。然后是分析题目中的关键词语和意思。

     1．四个重要量：K,M,N,1000，且K，M，N是自然数，k>1。

       2．K是M,N的底数，M,N是K的幂。

       3．K^M 和 K^N都必须大于1000

       4．K^M 和 K^N 末尾三位相等。

       5．要输出的的是M+N的值

       6．M>N（两个数不相等）

分析：

       1．上面的要点中，1，2，3，5,6都是辅助条件，关键是弄清楚第4点。末尾三位相等是什么意思？我第一次读这个题目，还以为是位运算，后来才弄清楚是幂运算，而且末尾三位数相等这个概念也容易混淆，是一个数的最后三位数字相同还是什么呢？我觉得这些题目写的不清楚，不应该让人捉摸你的字面意思，应该把有限的时间和精力用在真正的问题上面。这里指的是10进制数的末尾3位，如何取末尾3位的数字？很显然将这个数字对1000求模就可以了。

       2．仔细思考后，我们可以注意到，任何数对1000求模只有1000种可能（0~999），所以我们将K^Power 中的Power从1（为什么不是0？因为K^0=1<1000，而我们不考虑小于1000的情况，题解第3点）到1001逐个求值，总有相等的两个数字。因为结果只有1000种可能，但是有1001次求值，哪怕前1000次所求结果都不一样，最后一次的值必然与前面1000种其中的一种相等，而对于有限数字并不能有1001次的幂运算大于1000，但由于题目给出2的运算结果为120，可知，类似于2的数字，虽然不能够有1001次运算结果都大于1000，但是可以在1-1001次幂运算过程中取到结果，即出现k尾相等数。（相关知识：抽屉原理）。



流程：

       根据上面的理解和分析，解决流程大致如下：

       1．获得K的大小

       2．逐个求K^Power (Power= 1,2,3…….1001)的结果并记录下来，发现，影响一个数末尾三位数的仅限于末尾三位数，所以，每次结果都进行%1000操作。

       3．若在记录的时候发现之前该值已经出现过，那么上次记录该值时的Power值和本次尝试记录时的Power值就分别是N和M了

       4．输出M+N




数据结构与设计技巧：

       1．其实这个程序不需要什么数据结构，但是有一个技巧还是得提到一下，K^Power末尾的三位数字只可能是0~999中的一种，而我们如何记录哪一种结果曾经出现过？最好的方法是使用一个一维数组，维数刚好是1000，分别记录0~999每种情况出现时Power的值。存取的时候可以利用末尾三位数本身的值作为该数组的索引来进行（相关知识：重复计数）

       2．其实我们也不需要逐个求K^Power的值，那样的运算效率太低了。考虑到 K^Power = K^(Power-1)，所以，利用这一性质，我们可以求出K^1的值，然后据此推出K^2到K^1001的结果就行了。

   3. 当K或者Power比较大的时候它们相乘可能导致数据溢出，这就需要参考我的另一篇文章里的对大数进行求模运算的相关算法了，总之结果就是求M*N%R,当M*N可能溢出时，应该使用 ((M%R)*(N%R))%R 来计算。

---

作者: 小骁叔    时间: 2013-11-19 16:16
package test;

import java.util.Scanner;

public class Test {

       
public static  void main(String []args){
        while(true){
        System.out.println("请输入一大于1的自然数");
        Scanner scanner=new Scanner(System.in);
        String string =scanner.nextLine();
        int k=Integer.parseInt(string);
        if(k>1)
        {
        System.out.println(k+"尾相等数最小和为："+findNumber(k));
        }
        else
                System.out.println("你输入的数不合法，请重新输入");}
               
        }
       


public  static int  findNumber(int k) {
     boolean flag=false;
        int product=1;
        int []arr=new int[1000];
        if(k>=1000){
                flag=true;
                k=k%1000;
               
                        }
       
         for ( int Power = 1; Power<=1001; ++ Power)    // Power从1到1001
     {
         product *= k;               // Product = (K^Power-1)%1000 * K
         if ( flag || product>=1000 )     // 必须符合题目的条件 K^Power>=1000
         {
              flag = true;               // 考虑到有可能之前是false，再赋值
              product = product%1000;           // 去结果的末尾三位！！！！
            
              if ( arr[product]==0 )         // 这个结果之前没出现过，记录结果出现时的幂值
                   arr[product] = Power;     // 记录之
              else
                   return Power + arr[product];   // 如果出现过，则返回我们的结果
         }
       
}
        return -1;  
       
}

}

---

作者: FFF    时间: 2013-11-19 19:12
如果问题已经解决，请及时修改主题为“提问结束”。
修改主题的方法链接
http://bbs.itheima.com/thread-89313-1-1.html
如果没有解决，可能你的问题问得不够清楚。可以重新发问的哦~

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2