求解幸运数问题（C++）

【问题描述】
小明同学在学习了不同的进制之后用一些数字做起了游戏。小明同学知道，在日常生活中最常用的是十进制数，而计算机中的二进制数也很常用。现在对于一个数字x，小明同学定义出两个函数f（x）和g（x），f（x）表示把x这个数用十进制写出后各数位上的数字之和，例如f（123）=1+2+3=6；g（x）表示把x这个数用二进制写出后各数位上的数字之和，例如123的二进制表示为1111011，那么g（123）=1+1+1+1+0+1+1=6。小明同学发现对于一些正整数x满足f（x）= g（x），他把这种数称为幸运数，现在他想知道小于等于n的幸运数有多少个？

输入描述：每组数据输入一个数 n（n≤100 000）。
输出描述：每组数据输出一行，小于等于n的幸运数个数。

输入样例：

输出样例：

【思路】

【代码】

#include<iostream>
using namespace std;

int number = 0;

/*
思路：输入N，求解包含的幸运数问题 用递归来解决问题
*/

//十进制
long int f(int x) {
	long int sum = 0;
	while (x != 0) {
		sum += x % 10;
		x = x / 10;
	}
	return sum;
}

//二进制
long int g(int x) {
	long int sum = 0;
	while (x != 0) {
		sum += x % 2;
		x = x / 2;
	}
	return sum;
}

int G(int x) {

	if (x == 0) {//递归结束条件
		return number;
	}
	if (f(x) == g(x)) {
		number += 1;	
	}
	G(x - 1);

	return number;
}

int main()
{
	int x;
	cin >> x;
	

	if (x <= 100000) {
		G(x);
	}
	else {
		printf("数字过大\n");
	}
		
	cout << "number=" << number << endl;
	
	system("pause");
	return 0;
}