图解Blash数集题解

科技前沿 • 2025-03-14 10:17 • 阅读 47

大家好，我是讯享网，很高兴认识大家。

题目描述

大数学家高斯小时候偶然间发现一种有趣的自然数集合 Blash ，对应以 a 为基的集合 Ba 定义如下：
（1）a 是集合 Ba 的基，且 a 是 Ba 的第一个元素。
（2）如果 x 在集合 Ba 中，则 2x+1 和 3x+1 也都在集合 Ba 中。
（3）没有其他元素在集合 Ba 中了。
现在小高斯想知道如果将集合Ba中元素按照升序排列起来是什么样？

输入格式

输入集合的第一个数x

输出格式

按照从小到大的顺序输出集合的前20个，每个数字之间用一个空格分开

样例输入

讯享网

样例输出

讯享网2 5 7 11 15 16 22 23 31 33 34 45 46 47 49 63 67 69 70 91

分析

1、每个数进入集合之后，就会产生新的2个数，这两个数也都可以进入集合，这样就好像是一个二叉树。2x+1在左边，3x+1在右边。
在这里插入图片描述
讯享网

2、观察上面二叉树，同一层级的数不一定是左边<右边，比如左边5产生11和16，右边7产生15和22，其中左边5产生的16大于右边7产生的15，这样就决定了我们不可能按照基数增长的顺序一个一个输出了，否则就会变成这样：2 5 7 11 16 15 22，这样出来不能满足从小到大的排序。
3、基于以上思考，我们需要对两种方式产生的数进行判断，比较小的先输出并进入数组（方便进行另外一种方式的计算）。
4、因为产生的数有两种计算方式2x+1和3x+1，这样我们就需要跟踪同一个基数的这两种方式产生的数，为此我们需要两个数字变量来记录已经进行过2x+1的计算的数和已经进行过3x+1计算的数。

我们可以把计算过的数都存入数组，设置两个记录数组下标的整数，我们叫指针。一个指向左边Left，进行2x+1的计算；一个指向右边Right，进行3x+1的计算。

源代码

#include <iostream> #include <string> using namespace std; int que[1000]; int main() { 
    int r,left=0,right=0,tail=0; //r是基数，tail是执行数组最后一个元素的指针，方便对输出进行控制 int x,y; cin>>r; que[0]=r; cout<<r<<" "; tail=1; while(tail<20) { 
    x=2*que[left]+1; y=3*que[right]+1; if(x>y) { 
    cout<<y<<" "; que[tail]=y; right++; } else if(x<y) { 
    cout<<x<<" "; que[tail]=x; left++; } else { 
    cout<<x<<" "; que[tail]=x; left++; right++; } tail++; } }