上一篇将讲解的内容是从整体流程思考递归函数的内容
这一篇我们衔接上一篇继续讲解从整体流程思考递归函数的内容。我们同样使用一个实例来分析。
【题目描述】
任何一个正整数都可以用2的幂次方表示。例如:
137=27+23+20
同时约定方次用括号来表示,即ab可表示为a(b)。由此可知,137可表示为:
2(7)+2(3)+2(0)
进一步:7=22+2+20(21用2表示)
3=2+20
所以最后137可表示为:
2(2(2)+2+2(0))+2(2+2(0))+2(0)
又如:
1315=210+28+25+2+1
所以1315最后可表示为:
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
【输入】 137
【输出】 2(2(2)+2+2(0))+2(2+2(0))+2(0)
这个问题看起来是比较棘手的。咋看一眼,我们能感受到其中有很多重复的操作,那就是将一个整数拆解成几个数字相加,然后在对拆解的数字再次进行拆分。这些步骤我们感受得到,但具体怎么实现呢?真是棘手。我们尝试分析一下。
-
1、程序首先考虑将整数
137
拆解成
2^7+2^3+2^0
。这与整数分解成
二进制
数字是类似的。如果将
137
拆解成
二进制
的话,得到结果为
010001001
。而对应的
1
的位置正好是指数。那么我们可以不可以通过这个得到呢?答案是可以的。根据分解的步骤,我们将统计分解的次数,并在输出时提供。但需要注意的是,我们分解得到的结果是颠倒的——第一次求余得到的结果是最右侧的
1
。因此,我们需要将输出的内容放在递归函数调用的后面,通过
归
的过程进行输出,这样就能保证在第一次输出的是最高位的
1
了。
我们尝试使用程序描述这样的情况。
//n 保存分解的数字
//i 统计位数
void f(int n, int i)
{
//如果n的值为0,是不需要分解的
if(n == 0)
return;
//不是0,则需要分解,分解的时候需要对分解的数字不断除以2,已获得余数--余数才是关键
int r = n % 2;
f(n / 2, i + 1); //进行下一次分解,位数相应增加1
//如果余数为1,才有输出的必要
if(r == 1)
cout << "2(" << i << ")" << endl;
}
实现完这一步,我们得到
步骤1
中的结果,接下来我们将继续分解。
-
2、我们将形如
2^7
中的
7
继续划分。那么也就是对程序中的
i
进行划分。但
i
的值是由多种数字组成。第一种
0
,也就是
2(0)
的形式。第二种
1
,需要输出成
2
的形式,并没有括号。第三种与第一种类似,
i
的值为
2
,我们输出成
2(2)
的形式。第四种
i
的值大于
2
,那么这时就需要将
i
的值再次进行分解了,分解的过程类似于对
137
的划分。
我们尝试划分一下。
void f(int n, int i)
{
if(n == 0)
return;
int r = n % 2;
f(n / 2, i +1);
if(r == 1)
{//对 i 进行划分情况
if( i == 0 || i == 2)
cout << "2(" << i << ")";
else if(i == 1)
cout << 2;
else
{//i > 2时, 需要重新划分
//划分时,需要将位数重新归0
cout << "2("; //格式
f(i, 0);
cout << ")";
}
}
}
到目前位置,我们已经可以顺利的拆解各个数字了。但对于格式来说,是很糟糕的——所有数字都连在一起。题目中要求是我们使用加法将他们连接起来。那么我们可以在每一个数字输出之前输出一个
+
。我们尝试进行修改,在
f(n/2, i+1)
的下一行加上输出
if(r == 1) cout << "+";
。添加条件是必要的——我们只在余数为
1
的位置添加
+
连接,而不是所有都添加。但问题随之而来,第一个位置会多一个
+
,这该怎么办呢?这对我们了解程序执行过程的程度是一种考验。我们接着进行分析。
-
3、第一个位置输出
+
。这个位置是第一次
归
时进行输出的,第一次
归
时,也就是
i
处于最大值时——位数最高时。按照分解整数获得
二进制
时,位数最高也就意味着
137
这个数字已经分解结束了,那么它就会变为
0
。此时,程序就好处理了,我们每次在程序运行时,都将
n
的值进行改变,并在输出
+
时判断
n
是否为
0
。如果为
0
,也就意味着最高位,也就不能输出了。
我们对程序进行改进。
void f(int n, int r)
{
if(n == 0)
return 0;
int r = n % 2;
n /= 2; //在调用函数的过程中修改n的值
f(n, i + 1);
if(n != 0 && r == 1)
cout << "+";
if(r == 1)
{
if(i == 0 || i == 2)
cout << "2(" << i << ")";
else if(i == 1)
cout << 2;
else
{
cout << "2(";
f(i, 0);
cout << ")";
}
}
}
那么通过这样的分析,这道题的完整程序就已经实现了。