首页 > 专题系列 > Java解POJ > POJ 2183 Bovine Math Geniuses [解题报告] Java
2013
11-10

POJ 2183 Bovine Math Geniuses [解题报告] Java

Bovine Math Geniuses

问题描述 :

Farmer John loves to help the cows further their mathematical skills. He has promised them Hay-flavored ice cream if they can solve various mathematical problems.

He said to Bessie, “Choose a six digit integer, and tell me what it is. Then extract the middle four digits. Square them and discard digits at the top until you have another number six digits or shorter. Tell me the result.”

Bessie, a mathematical genius in disguise, chose the six digit number 655554. “Moo: 6 5 5 5 5 4″, she said. She then extracted the middle four digits: 5555 and squared them: 30858025. She kept only the bottom six digits: 858025. “Moo: 8 5 8 0 2 5″, she replied to FJ.

FJ nodded wisely, acknowledging Bessie’s prowess in arithmetic. “Now keep doing that until you encounter a number that repeats a number already seen,” he requested.

Bessie decided she’d better create a table to keep everything straight:


Middle Middle Shrunk to
Num 4 digits square 6 or fewer
655554 5555 30858025 858025
858025 5802 33663204 663204
663204 6320 39942400 942400
942400 4240 17977600 977600
977600 7760 60217600 217600 <-+
217600 1760 3097600 97600 |
97600 9760 95257600 257600 |
257600 5760 33177600 177600 |
177600 7760 60217600 217600 --+

Bessie showed her table to FJ who smiled and produced a big dish of delicious hay ice cream. “That’s right, Bessie,” he praised. “The chain repeats in a loop of four numbers, of which the first encountered was 217600. The loop was detected after nine iterations.”

Help the other cows win ice cream treats. Given a six digit number, calculate the total number of iterations to detect a loop, the first looping number encountered, and also the length of the loop.

FJ wondered if Bessie knew all the tricks. He had made a table to help her, but she never asked:


Middle Middle Shrunk to
Num 4 digits square 6 or fewer
200023 0002 4 4
4 0 0 0
0 0 0 0 [a self-loop]

whose results would be: three iterations to detect a loop, looping on 0, and a length of loop equal to 1.

Remember: Your program can use no more than 16MB of memory.

输入:

* Line 1: A single six digit integer that is the start of the sequence testing.

输出:

* Line 1: Three space-separated integers: the first number of a loop, the length of the loop, and the minimum number of iterations to detect the loop.

样例输入:

655554

样例输出:

217600 4 9

解题代码:

//* @author: 
import java.util.*;
public class Main
{
 private int t;
 private int b[];

 public Main(int t){
   this.t=t;
   b=new int[1000000];
 }

 private void doIt(){
   int st=0;
   while(true){
    t/=10;
    t%=10000;//取t的中间四位
    t*=t;//平方
    t%=1000000;//取t的后六位
    if (b[t]!=0){//如果t出现过,发现循环数
      st++;
      System.out.println(t+" "+(st-b[t])+" "+st);//循环节的第一个数,循环节大小和需要几次发现循环节

      break;
    }
    b[t]=++st;//记录计算的次数
  }
}
 public static void main(String[] args){
     Scanner sc=new Scanner(System.in);
     while(sc.hasNext()){
        int t=sc.nextInt();
        Main m=new Main(t);
        m.doIt();
     }
	
  }
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。