1333：【例2-2】Blah数集
|
|
教学备忘录： 编辑 |
| 无 |
|
给学生提示： 编辑 |
| 无 |
题意：最开始集合中有一个数，每次需要把这个数的2倍加1和3倍加1放入这个集合，然后需要把新放入的这两个数他们的2倍加1和3倍加1也放进这个集合中，保证每个数的2倍加1和3倍加1都在这个集合中，那么可以知道我们这个集合是无限大的，让我们找到集合中，从小到大排在第n位的数。
解释样例：1 8 以1为基 找到第8个数
第1步. 集合中：1
待放入：3,4 把最小的放进去，下面以此类推
第2步.集合中：1,3
待放入：4,7,10
第3步.集合中：1,3,4
待放入：7,10,9,13（此时3*3+1大于后求的4*2+1，所以并不能依次把集合中的数的倍数加1放入集合中，要按升序放，需进行处理）
第4步.集合中：1,3,4,7
待放入：10,9,13,15,22
第5步.集合中：1,3,4,7,9
待放入：10,13,15,22,19,28
第6步.集合中：1,3,4,7,9,10
待放入：13,15,22,19,28,21,31
第7步.集合中：1,3,4,7,9,10,13
待放入：13,15,22,19,28,21,31,27,40
第8步.集合中：1,3,4,7,9,10,13,15
待放入：13,15,22,19,28,21,31,27,40,31,46 （此时待放入的数中有两个31，一个是10*3+1，另一个是15*2+1，需要处理两数相等的情况）
此时集合中最后一个数就是我们所求的第8位
方法1：找三个队列，一个储存集合数，一个储存集合中数的2倍加1的数，一个储存集合中数的3倍加1的数；
将集合队头的2倍加1和3倍加1分别放入其他两个队列，集合出队；
比较其他两个队列队头元素大小，每次把小的放进集合，出队；
遇到相同的就放入集合一次，并且2,3同时出队。
样例： 1 8
第1步：集合：1
2倍加1队列：3
3倍加1队列：4
第2步：集合：1，3
2倍加1队列：7
3倍加1队列：4，10
第3步：集合：1，3，4
2倍加1队列：7，9
3倍加1队列：10，13
第4步：集合：1，3，4，7
2倍加1队列：9，15
3倍加1队列：10，13，22
第5步：集合：1，3，4，7，9
2倍加1队列：15，19
3倍加1队列：10，13，22，28
第6步：集合：1，3，4，7，9，10
2倍加1队列：15，19，21
3倍加1队列：13，22，28，31
第7步：集合：1，3，4，7，9，10，13
2倍加1队列：15，19，21，27
3倍加1队列：22，28，31，40
第8步：集合：1，3，4，7，9，10，13，15
2倍加1队列：15，19，21，27，31
3倍加1队列：22，28，31，40，46
此时后两个队列中都有31，在入队时要进行判断，判断2,3队列队头元素是否相等，想等的话入队一个。
#include <iostream>
#include <queue>
using namespace std;
int n, a, cnt2, cnt3, num2, num3, x;
int main()
{
while (cin >> a >> n) {
queue<int> q2, q3, q;
q.push(a);
int i;
for (i = 1; i < n; i++) {
q2.push(q.front()*2+1);
q3.push(q.front()*3+1);
if (q2.front() < q3.front())
q.push(q2.front()), q2.pop();
else if (q2.front() > q3.front())
q.push(q3.front()), q3.pop();
else
q.push(q3.front()), q2.pop(), q3.pop();
q.pop();
}
cout << q.front() << endl;
}
return 0;
}方法2：只用一个队列或数组储存集合，再用两个标记变量记录该哪个数的2倍加1或3倍加1放入集合了；其实跟上面用3个队列的原理相同。
样例： 1 8
第1步：集合q：1
该放哪个数的2倍加1，即下标：1 ，q[1]*2+1 = 3（假设从1位置开始存）
该放哪个数的3倍加1，即下标：1 ，q[1]*3+1 = 4
第2步：集合：1，3
该放哪个数的2倍加1，即下标：2 ，q[2]*2+1 = 7
该放哪个数的3倍加1，即下标：1 ，q[1]*3+1 = 4
第3步：集合：1，3，4
该放哪个数的2倍加1，即下标：2 ，q[2]*2+1 = 7
该放哪个数的3倍加1，即下标：2 ，q[2]*3+1 = 10
第4步：集合：1，3，4，7
该放哪个数的2倍加1，即下标：3 ，q[3]*2+1 = 9
该放哪个数的3倍加1，即下标：2 ，q[2]*3+1 = 10
第5步：集合：1，3，4，7，9
该放哪个数的2倍加1，即下标：4 ，q[4]*2+1 = 15
该放哪个数的3倍加1，即下标：2 ，q[2]*3+1 = 10
第6步：集合：1，3，4，7，9，10
该放哪个数的2倍加1，即下标：4 ，q[4]*2+1 = 15
该放哪个数的3倍加1，即下标：3 ，q[3]*3+1 = 13
第7步：集合：1，3，4，7，9，10，13
该放哪个数的2倍加1，即下标：4 ，q[4]*2+1 = 15
该放哪个数的3倍加1，即下标：4 ，q[4]*3+1 = 22
第8步：集合：1，3，4，7，9，10，13，15
该放哪个数的2倍加1，即下标：5 ，q[5]*2+1 = 19
该放哪个数的3倍加1，即下标：4 ，q[4]*3+1 = 22
仍需记得处理第一种方法两数都为31的情况
#include <iostream>
using namespace std;
int a, n, q[10000005], tail, cnt2, cnt3, num2, num3;
int main()
{
while (cin >> a >> n) {
q[1] = a;
tail = 2, cnt2 = 1, cnt3 = 1;
while (tail <= n) {
num2 = q[cnt2]*2+1;
num3 = q[cnt3]*3+1;
if (num2 < num3) q[tail++] = q[cnt2++]*2+1;
else if (num2 > num3) q[tail++] = q[cnt3++]*3+1;
else q[tail++] = q[cnt2++]*2+1, cnt3++;
}
cout << q[n] << endl;
}
}