半数集问题 (非递归递归版本)

半数集问题 (非递归递归版本)

什么是半数集?

给定一个自然数n给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。

1. n∈set(n);
2. 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
3. 按此规则进行处理，直到不能再添加自然数为止。

例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6个元素。

思路: 运用队列存储待处理(添加数字)的元素, 需要判断数字位数以调整判断的数字, 输出半数集的数量以及具体的半数集元素

非递归的代码

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;vector<int> result;int checkDigit(int number){if(number == 0) return 1;int count = 0;// 使用循环除以 10 的幂，直到数字变为 0while (number > 0) {number /= 10;count++;}return count;
}void HalfSet(int n) {queue<int> queue;result.clear(); // 初始化去除垃圾值result.push_back(n);queue.push(n);while (!pty()) {int current = queue.front();int current_level = checkDigit(current);int index = current / pow(10, current_level-1);queue.pop();for (int i = 1; i <= index / 2; i++) {int next = current + i * pow(10, current_level);result.push_back(next);queue.push(next);}}}int main() {int n;cin >> n;HalfSet(n);cout << "n=" << n << "的半数集有"<<result.size()<<"个"<<endl;for (int num : result) {cout << num << " ";}return 0;
}

递归版本 (其实这题十分适合使用递归的) 只需要修改处理的函数即可, 返回半数集数量

int HalfSet2(int n){ // 返回半数集数量int sum = 1; // 自身也算是半数集的一个if(n <= 1) return 1;for(int i = 1; i <= n/2; i++){sum += set(n/2);}return sum;
}

该递归写法 可以用一数组存储其中的值以减少重复值的出现达到优化的效果

欢迎如果有大佬们看出有问题, 在评论区或是私聊我批评指正。谢谢！