Friday, December 10, 2010

[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);
        }
結果下載

3 comments:

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

    ReplyDelete
  2. 好像是寫得太笨的關係XD

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

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

    ReplyDelete
  3. The quality of this replica Louboutin shoe is perfect, high quality cheap Louboutin Shoes Uk Online it is very comfortable to wear, wear this shoe when you travel, it will not be tired.cheap Louboutin casual shoes I recommended this site to my good friends, they are very happy, can buy such cheap Louboutin shoes

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...