Polpid's World

[Programming Challenges] The 3n+1 Problem 본문

Development/Algorithm

[Programming Challenges] The 3n+1 Problem

폴피드 2011.09.01 23:41

정수 n에서 시작해 n이 짝수면 2로 나누고 홀수면 3을 곱한 다음 1을 더한다.
이렇게 해서 새로 만들어진 숫자를 n으로 놓고 n=1이 될때까지 같은 작업을 반복한다.
1이 나올때까지 만들어진 수의 개수(1포함)를 n의 사이클 길이라고 한다.

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
22의 사이클은 16


입력 
- 입력은 일련의 정수 쌍 i와 j로 구성되며 한 줄에 한쌍의 수가 입력된다. 모든 정수는 1,000,000보다 작고 0보다 크다

출력
- i, j를 입력된 순서대로 출력
- i, j의 최대 사이클 길이 출력 

입력 예          출력 예
1  10            1 10 20
100 200       100 200 125
210 210        201 210 89 

풀이) 풀긴 했는데  http://www.programming-challenges.com 들어가서 돌려보면 계속 틀렸다고 나온다 -_-;;젠장 . 뭐가 문제야

  1. import java.io.*;
  2.  
  3. class Main implements Runnable{
  4.     static String ReadLn(int maxLength){  // utility function to read from stdin,
  5.                                           // Provided by Programming-challenges, edit for style only
  6.         byte line[] = new byte [maxLength];
  7.         int length = 0;
  8.         int input = -1;
  9.         try{
  10.             while (length < maxLength){//Read untill maxlength
  11.                 input = System.in.read();
  12.                 if ((input < 0) || (input == ' ')) break//or untill end of line ninput
  13.                 line [length++] += input;
  14.             }
  15.  
  16.             if ((input < 0) && (length == 0)) return null;  // eof
  17.             return new String(line, 0, length);
  18.         }catch (IOException e){
  19.             return null;
  20.         }
  21.     }
  22.  
  23.     public static void main(String args[])  // entry point from OS
  24.     {
  25.         Main myWork = new Main();  // Construct the bootloader
  26.         myWork.run();            // execute
  27.     }
  28.  
  29.     public void run() {
  30.         new MyStuff().run();
  31.     }
  32. }
  33.  
  34. class MyStuff implements Runnable{
  35.     public void run(){
  36.             String input = (Main.ReadLn(20));
  37.             calcCycle(input);       
  38.     }
  39.    
  40.     // You can insert more classes here if you want.
  41.    
  42.     public void calcCycle(String input){
  43.         String[] inputArray     = input.trim().split(" ");
  44.         int startInput    = Integer.parseInt(inputArray[0]);
  45.         int endInput          = Integer.parseInt(inputArray[1]);
  46.         int maxCount            = 0;
  47.         int maxNumber         = 0;
  48.        
  49.         if (startInput > endInput){
  50.             int temp    = endInput;
  51.             endInput        = startInput;
  52.             startInput  = temp;
  53.         }
  54.                
  55.         while(startInput <= endInput){    
  56.             int count      = 1;             
  57.             int number   = startInput;
  58.            
  59.             if (number != 1){
  60.                 while (number > 1){
  61.                     if (number % 2 == 0){
  62.                         number = number /2;
  63.                     }else {        
  64.                         number = number * 3 + 1;           
  65.                     }
  66.                     count++;
  67.                 }             
  68.             }
  69.  
  70.             if (maxCount < count){
  71.                 maxCount    = count;
  72.             }
  73.             startInput++;
  74.         }
  75.  
  76.         System.out.println( inputArray[0] + " " + inputArray[1] + " " + maxCount);
  77.     }
  78.    
  79. }


'Development > Algorithm' 카테고리의 다른 글

에라토스테네스의 체  (0) 2016.12.07
[Try-catch]대문자 출력  (0) 2013.11.04
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Find the Min  (0) 2013.02.01
[Hacker Cup]Balanced Smileys  (0) 2013.01.31
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01
0 Comments
댓글쓰기 폼