2010年12月10日 星期五

[ACM] Q100 : The 3n + 1 problem

題目 : The 3n + 1 problem

簡單解釋 :
有個演算法,先暫且叫3N+1演算法,給他一個整數N,有三種可能
1.N=1 -> 結束
2.N為偶數 -> N=N/2
3.N為奇數 -> N=N*3+1

舉個例子,如果N為7,出來的數列為
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
數列長度為17

題目會輸入幾行數字,每行內容為 i j 兩個整數,你要將從 i 到 j 的每個整數套進3N+1演算法,然後將其中數列最長的長度(姑且叫做M)加在 i j 後輸出,也就是輸出時為 i j M ,下面是官方給的輸入輸出範例。

輸入範例

1 10
100 200
201 210
900 1000

輸出範例

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



我的解法大致如下,請多指教。
public int TempN = 0;

        private void button1_Click(object sender, EventArgs e)
        {
            
            string[] ar=textBox1.Text.Split('\n');
            
            for (int i = 0; i < ar.Length;i++ )
            {
                string[] ar2 = ar[i].Split(' ');
                int Diff=Convert.ToInt32(ar2[1])-Convert.ToInt32(ar2[0]);
                int[] NumList = new int[Diff];
                for (int j = 0; j < Diff; j++)
                {
                    TempN = 0;
                    NumList[j] = ACM100(j + Convert.ToInt32(ar2[0]));
                }
                Array.Sort(NumList);
                ar[i] = ar[i].Substring(0,ar[i].Length-1)+" " + NumList[Diff - 1].ToString(); ;
                label1.Text += ar[i] + "\n";
            }
            
        }

        private int ACM100(int n)
        {
            TempN = TempN + 1;
            if (n == 1)
                return TempN;
            else if (n % 2 == 0)
                return ACM100(n / 2);
            else
                return ACM100(n * 3 + 1);
        }
結果下載

2 則留言:

  1. 你這結果如果拿去 submit 的話, 99% 的機會是 fail 的... time limit exceeded

    回覆刪除
  2. 好像是寫得太笨的關係XD

    C#我想應該是不能submit的,很可惜,所以我只有寫到可以把範例解出來。

    不曉得ijliao可以舉一下哪邊可以加強的 ?

    回覆刪除

Related Posts Plugin for WordPress, Blogger...