ACM International Collegiate Programming Contest國際型的程式競賽

隨意逛網時，看到的網站ACM International Collegiate Programming Contest國際型的程式競賽, 網站提供了許多的題目，可以讓使用者註冊，並且在線上測試結果，這樣就不怕沒題目好練習。

目前該網站更換新的網站，網址為:http://uva.onlinejudge.org/

找了一題簡單的用Python試解玩玩
#100 ─ The 3n+1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

 
  1.    input n

  2.    print n

  3.    if n = 1 then STOP

  4.       if n is odd then   

  5.       else   

  6.    GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

說明：有一種數列型態如下：3、10、5、16、8、4、2、1，它的最後一項一定是 1，而第一項由使用者自行給予，它的規則是，如果這一項是奇數，則它的下一項為這一項的三倍加一，如果這一項是偶數，則它的下一項是這一項的一半，如此重覆下去，直到 1 為止。現在輸入一個整數 N ，計算以 N 為首的數列長度為 L，例如 N=3 時，L=8。

輸入：系統會連續輸入，每行輸入兩個數字 i、j ( 0 < i、j < 1,000,000 )，我們要計算以從 i 到 j 之間所有整數開頭的數列中，最大的數列長度 m (注意，i 不一定大於 j)。

輸出：根據系統每行輸入的 i、j，求出最大數列長度 m 後，依照原來的順序每行輸出  i、j、m 等三個整數。

我用Python 寫的如下:
# -*- coding: utf-8 -*-
# Python version: 2.5.4

i = input('請輸入一個大於0的數:')
j = input('請輸入一個小於1,000,000 的數:')

print '輸入的起始數為:%s 結束數字為:%s)' % (i,j)
m = 0

for n in range(i,j+1):
   print 'n=',n
   count = []
   count.append(n)
   while n != 1:
      if n == 1:
         break
      elif n % 2 == 1:
         n = n*3+1
         count.append(n)
                 
      elif n % 2 == 0:
         n = n/2
         count.append(n)

   print count        
   print '計算結果為',len(count)
   if len(count) > m:
      m = len(count)
   else:
      pass

   del(count)

print '所輸入的數最大值為:',m  
     
程式運算結果:
>>>
請輸入一個大於0的數:1
請輸入一個小於1000000的數:10
輸入的起始數為:1 結束數字為:10)
n= 1
[1]
計算結果為 1
n= 2
[2, 1]
計算結果為 2
n= 3
[3, 10, 5, 16, 8, 4, 2, 1]
計算結果為 8
n= 4
[4, 2, 1]
計算結果為 3
n= 5
[5, 16, 8, 4, 2, 1]
計算結果為 6
n= 6
[6, 3, 10, 5, 16, 8, 4, 2, 1]
計算結果為 9
n= 7
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
計算結果為 17
n= 8
[8, 4, 2, 1]
計算結果為 4
n= 9
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
計算結果為 20
n= 10
[10, 5, 16, 8, 4, 2, 1]
計算結果為 7
所輸入的數最大值為: 20
>>>