[ACM ][ 100] The 3n + 1 problem
今天面試的被問到的題目
除了暴力解以外，有沒有更快的解法
回家把那時候嘴砲的東西實作一下，大概只花了我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
推
03/26 23:20, , 1F
03/26 23:20, 1F
推
03/26 23:48, , 2F
03/26 23:48, 2F
推
03/27 08:48, , 3F
03/27 08:48, 3F
→
03/27 08:49, , 4F
03/27 08:49, 4F
推
03/31 05:33, , 5F
03/31 05:33, 5F