设函数 $f(n)$ 返回正整数 $n$ 的二进制表示中 1 的个数.
证明: 若 $n=2k+1$, 则 $f(n)=f(k)+1$; 若 $n=2k$, 则 $f(n)=f(k)$.
Hint:
\[k=a_0 2^m+a_1 2^{m-1}+\cdots+a_{m-1}2+a_m\]
\[N=2k+1=a_0 2^{m+1}+a_1 2^{m}+\cdots+a_{m-1} 2^2+ a_m 2+ 1\]
请编程实现.
1
/* Ex1.5
* 编写一个递归方法 f(N), 它返回数 N 的二进制表示中 1 的个数.
* 利用下面的命题.
* Prop. 若 $N=2k+1$, 则 $f(N)=f(k)+1$; 若 $N=2k$, 则 $f(N)=f(k)$.
* Pf. 设 $k=a_0 2^m+a_1 2^{m-1}+\cdots+a_{m-1}2+a_m$,
* 则 $N=2k+1=a_0 2^{m+1}+a_1 2^{m}+\cdots+a_{m-1} 2^2+ a_m 2+ 1$,
* 于是 $N$ 的二进制表示中 1 的个数就是
* $a_0+a_1+a_2+\cdots+a_m+1$.
* 因此如果要输出其二进制表示, 也可以这样来做.
* 如 1=>1, (这里十进制=>二进制)
* 2=>10,
* 3=>11 (在 1 的后面添上 1)
* 4=>100,(在 2 的后面添上 0)
* 5=>101, (在 (5-1)/2=2 所对应的 2 的二进制表示 10 后添上 1)
* 6=>110, (在 6/2=3 的二进制表示后面添上 0)
*/
#include <iostream>
#include <vector>
using namespace std;
int f(long int N)
{
int num=0;
if(N==1 or N==2)
{
return 1;
}else if( N%2==0)
{
N=N/2;
num=f(N);
}else
{
N=(N-1)/2;
num=f(N)+1;
}
return num;
}
/*
编写一个函数, 对于 N, 输出其二进制表示
N=a_0 2^m+a_1 2^{m-1}+\cdots+a_{m-1} 2^1+a_m
则输出 a_0 a_1 a_2 ... a_m
可以考虑用向量来实现.
*/
string g(long int N)
{
string s="";
if(N==1){
s="1";
}else if(N==2){
s="10";
}else if( N%2==0){
N=N/2;
s=g(N)+"0";
}else{
N=(N-1)/2;
s=g(N)+"1";
}
return s;
}
int main()
{
cout << "请输入正整数 N 的值, 然后回车" <<endl;
cout << "N=";
long int N;
cin >> N;
cout << "N 的二进制表示中 1 的个数为: " << f(N) << endl;
cout << "N 的二进制表示为: " << g(N) << endl;
return 0;
}