[C++知识库]求解幸运数问题(C/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的幸运数个数。

输入样例：
21
输出样例：
3

根据题目叙述，我的思路是：
先把十进制数转化为二进制，然后每位相加，把g（x）、f(x)的函数值进行比较判断是否为幸运数
利用一般十进制转化二进制的解法

	while(x!=0){
		r=x%2;
		x=x/2;
		k+=r;
	}
	return k;//所求g（x）的值

求g(x)也是如此

	while(x!=0){
		r=x%10;
		x=x/10;
		k+=r;
	}
	return k;//所求f（x）的值

我们对上述两个函数进行合并 用NUM代替2 和 10

int change(int x,int NUM){
	int r=0;//储存余数
	int k=0;//求各个位的数值和
	while(x!=0){
		r=x%NUM;
		x=x/NUM;
		k+=r;
	}
	return k;//返回函数（g（x）、f(x)）的值
}

调用如下

k2=change(i,2);
k10=change(i,10);

C语言实现

#include<stdio.h>
int change(int x,int NUM){
	int r=0;//储存余数
	int k=0;//求各个位的数值和
	while(x!=0){
		r=x%NUM;
		x=x/NUM;
		k+=r;
	}
	return k;//返回函数（g（x）、f(x)）的值
}
int  main()
{
	int num=0;
	int i=0;
	int k2=0;//存储f(x)的值
	int k10=0;//存储g(x)的值
	int lucky=0;//统计是幸运数的个数
	scanf("%d",&num);//输入一个小于等于100000的整数
	for(i=1;i<=num;i++){
		//先把十进制数转化为二进制数并对每位的数求和
		k2=change(i,2);
		k10=change(i,10);
		if(k2==k10){
			lucky++;
			//printf("%d\n",i);
		}
	} 
	printf("%d",lucky);
	return 0;
}

C++实现
利用了递归算法

#include<iostream>
using namespace std;
int twoSum(int n)            //计算二进制各位数的数字之和 
{
	if(n == 1)
		return 1;
	return (n%2)+twoSum(n/2);
}

int tenSum(int n)            //计算十进制各位数的数字之和 
{
	if(n<10)
		return n;
	return n%10+tenSum(n/10);
}

int main()
{
	int n,sum = 0;
	cin>>n;
	for(int i=1;i<=n;i++)
		if(twoSum(i) == tenSum(i))
			sum++;
	cout<<sum;
}