題目描述
任意給定一個正整數(shù)N，
如果是偶數(shù)，執(zhí)行： N / 2
如果是奇數(shù)，執(zhí)行： N * 3 + 1

生成的新的數(shù)字再執(zhí)行同樣的動作，循環(huán)往復。

通過觀察發(fā)現(xiàn)，這個數(shù)字會一會兒上升到很高，
一會兒又降落下來。
就這樣起起落落的，但最終必會落到“1”
這有點像小冰雹粒子在冰雹云中翻滾增長的樣子。

比如N=9
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
可以看到，N=9的時候，這個“小冰雹”最高沖到了52這個高度。
輸入
一個正整數(shù)N（N<1000000）
輸出
一個正整數(shù)，表示不大于N的數(shù)字，經過冰雹數(shù)變換過程中，最高沖到了多少。
樣例輸入
10
樣例輸出
52
思路：在dotcpp上，就算是不暴力也一樣可以過，但是總感覺不是很對。時間還是有點多。
我的做法是暴力打表，保存1-1000000的值。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; map<ll,ll> dp; int n;inline ll dfs(ll u) {if(dp[u]!=0) return dp[u];if(u==1) return dp[u]=1ll;ll _max;if(u&1) _max=u*3ll+1ll;else _max=u/2ll;_max=max(_max,dfs(_max));return dp[u]=_max; } int main() {scanf("%d",&n);ll _max=0;freopen("out.txt","w",stdout);for(int i=1;i<=n;i++) {_max=max(dfs((ll)i),_max);printf("%lld ",_max);}return 0; }

打表如圖：

我門可以發(fā)現(xiàn)很多重復的。
那么我們把所有重復的區(qū)間找出來就可以O(1)查詢了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; map<ll,ll> dp; int n;int main() {ll _max=0;freopen("out.txt","r",stdin);ll l=1,r,x;ll pre=1;for(ll i=1;i<=1000000;i++) {scanf("%lld",&x);if(i==0) continue;if(x==pre) r=i;else{printf("else if(n>=%lld&&n<=%lld) cout<<%lldll<<endl;\n",l,r,pre);pre=x,l=r=i;}}printf("else if(n>=%lld&&n<=%lld) cout<<%lldll<<endl;",l,r,pre);return 0; }

最后就是正式代碼了：

#include<bits/stdc++.h> #define ll long long using namespace std;ll n;int main() {scanf("%d",&n);if(n>=1&&n<=2) cout<<1ll<<endl;else if(n>=3&&n<=6) cout<<16ll<<endl;else if(n>=7&&n<=14) cout<<52ll<<endl;else if(n>=15&&n<=26) cout<<160ll<<endl;else if(n>=27&&n<=254) cout<<9232ll<<endl;else if(n>=255&&n<=446) cout<<13120ll<<endl;else if(n>=447&&n<=638) cout<<39364ll<<endl;else if(n>=639&&n<=702) cout<<41524ll<<endl;else if(n>=703&&n<=1818) cout<<250504ll<<endl;else if(n>=1819&&n<=4254) cout<<1276936ll<<endl;else if(n>=4255&&n<=4590) cout<<6810136ll<<endl;else if(n>=4591&&n<=9662) cout<<8153620ll<<endl;else if(n>=9663&&n<=20894) cout<<27114424ll<<endl;else if(n>=20895&&n<=26622) cout<<50143264ll<<endl;else if(n>=26623&&n<=31910) cout<<106358020ll<<endl;else if(n>=31911&&n<=60974) cout<<121012864ll<<endl;else if(n>=60975&&n<=77670) cout<<593279152ll<<endl;else if(n>=77671&&n<=113382) cout<<1570824736ll<<endl;else if(n>=113383&&n<=138366) cout<<2482111348ll<<endl;else if(n>=138367&&n<=159486) cout<<2798323360ll<<endl;else if(n>=159487&&n<=270270) cout<<17202377752ll<<endl;else if(n>=270271&&n<=665214) cout<<24648077896ll<<endl;else if(n>=665215&&n<=704510) cout<<52483285312ll<<endl;else if(n>=704511&&n<=1000000) cout<<56991483520ll<<endl;return 0; }

雖然暴力可以過，但是更正規(guī)一點的比賽應該不會出現(xiàn)數(shù)據(jù)水的情況，所以還是需要更準確一點的。
努力加油a啊，(^o)/~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的[蓝桥杯][2016年第七届真题]冰雹数(暴力打表找规律)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。