PAT BASIC 1005

2019-11-11 04:46:53

字体：大中小

来源：转载

供稿：网友

思路：

给1~100的数做一个state标记数组

state[1]=1;state[i]=0; //i!=1

每个数进来之后都做那个1001操作，遇到

state[i]==1

的情况停止，否则都将state[i]赋值为1；需要注意的一点就是state数组一定要开的大，虽然说n最大是100，但是我开了1000的数组依然出错了。

代码：

#include<iostream>using namespace std;int num[201], state[10001], isNum[201], ans[201];int n;int main(){ int i, j; int sam; cin >> n; for (i = 2; i <= 100; i++) { state[i] = 0; isNum[i] = 0; } state[1] = 1; for (i = 0; i < n; i++) { cin >> num[i]; isNum[num[i]] = 1; } for (i = 0; i < n; i++) { sam = num[i]; if (sam == 1) continue; if (sam % 2 == 1) sam = sam * 3 + 1; sam = sam / 2; while (state[sam] == 0) { state[sam] = 1; if (sam % 2 == 1) sam = sam * 3 + 1; sam = sam / 2; } } ans[0] = 0; for (i = 100; i > 1; i--) { if (isNum[i] && state[i] == 0) { ans[0]++; ans[ans[0]] = i; } } for (i = 1; i < ans[0]; i++) cout << ans[i] << " "; cout << ans[ans[0]]; //while (1) //{ //} return 0;}

上一篇：上机练习1-2

下一篇：动态规划（一）