瑞の資訊備忘錄

一、目的：計算機科學中常見的問題是將問題依照其特性進行分類，因此這個問題主要的目的是如何依照

            特定的演算法將所有未知的輸入資料進行分類。(連結UVa online原文題庫)

二、問題說明：

     考慮下列的演算法：

    當輸入整數值22時則會依序輸出如右的數值序例：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

    由於該演算法是假設對於輸入任何的整數會結束(n=1), 因此必須依照上述的演算法對於所有輸入的整數

    (0~1,000，000)進行驗證。驗證的方式為給一整數n 則可以決定輸出數值的數量，即是cycle-length of n.

    因此當輸入兩個數值時，程式必須輸出兩個數值區間的最大cycle-length值。(EX:n=22,cycle-length=16)

    EX: Sample Input             Sample Output   

             1 10              ==>    1 10 20

             100 200                   100 200 125

             201 210                   201 210 89

             900 1000      ==>    900 1000 174

三、輸入與輸出的規則：

     所有的輸入值都是由兩個整數值成組一筆測試資料，測試時將會依序輸入多筆的測試資料且所有整數

    的區間值為0< n <1,000,000。輸入結果時必須同時輸出每筆測試資料的數值並且輸出其區間中最

    大的cycle-length。

四、演算法說明：

      在不考慮執行速度的情況下，該問題可以說非常的簡單；因此如何加快執行速度是本篇主要討論的方向：

    4-1： 使用位移運算和位元運算來取代算術運算 ( / ,%  =>  >>, & ). 

    4-2： 當n為奇數時進行3n+1的運算後必定為偶數，因此可以直接將該值除2來減少判斷的次數。

    4-3： 使用Lookup-Table的方式來儲存已經計算過整數的cycle-length，當其他未計算的整數在計算過程

            中遇見LookupTable中已計算過的整數時，即可直接將目前的cycle-length加上LookupTable

            中的cycle-length；藉此來減少重覆計算，提高執行速度。

           (TableSize= 20000 * sizeof(unsigned short) )

Run time of UVa online web : 0.080  (Table Size = 20000)

Run time of UVa online web : 0.128  (Table Size = 10000)

Run time of UVa online web : 0.512  (No use table size)

Download : UVa100_The3n+1Problem.tar.gz

Result：