[ACM ][ 100] The 3n + 1 problem

[linjrming (風之信使)]

今天面試的被問到的題目

除了暴力解以外，有沒有更快的解法

回家把那時候嘴砲的東西實作一下，大概只花了我08年用暴力解的20%時間
http://acm.uva.es/p/v1/100.html


#include <iostream>
#include <stdio.h>
using namespace std;
int output [1000000]={1,1};  //宣告一個DP用的陣列，題目說最大是1M

int f(int n)
{
    if(n<1000000)            //超過1M就放棄DP，反正很少用到
    {
        if(output[n]!=0)                    //遞迴解(DP部分)
                return output[n];
        else if(n%2)
                output[n]=1+f(3*n+1);
        else
                output[n]=1+f(n/2);
        return output[n];
    }
    else
    {
        if(n%2)                             //遞迴解(不用DP部分)
                return 1+f(3*n+1);
        else
                return 1+f(n/2);

    }
}

int main()
{
        int a,b;                //input兩個數字丟給a,b
        while(cin >> a >> b)
        {
                int e,g,max=0;

                if(a>b) e=b, g=a;  //確保e>g
                else  e=a ,g=b;

                for(int j=e;j<=g;j++)      //比大小
                         if(f(j)>max)
                                max=output[j];

                cout << a << " " << b << " " << max << endl;  //Output
        }
        return 0;
}


感覺面試考得比研究所還簡單...

誰能教我帥氣的命名變數，不打註解過1小時回來就看不懂了

--
   ◥◣ ∞ ◢◤
    ◢◣◤◢◣         萃まる夢、幻、そして百鬼夜行
﹒  ▕● ＜◥▍              伊吹  萃香
●  ▕▄▄▄ ▎§
● §∕ ︽ ﹨▏▲            伊吹の西瓜
  ● ◢▄▄◥               Suika Ibuki                               ψgbwind

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.34.74.139
推 jyc180:帥哥
推 Disintegrate:竟然還有人會來這QQ
推 hsiang915:而且樓上還發現了XD
→ hsiang915:駝峰式命名法XD
推 Disintegrate:boolean isSidIdiot = true;