递归算法:10进制整数的2的次幂表示
2021-12-30 本文已影响0人
疋瓞
1、环境配置:
- 系统:win10
- 编程语言:C
- 编译器:DevC++
2、算法思想:
算法说明.png3、代码:
/*
思路:
int f_2(int n){
if(n=1) then print(2(0)); return 0;//递归终止条件
if(n=0) then print(0); return 0;//递归终止条件
else{
i=found_max(n);//找到比n小的最大的2的i次幂对应的i。
j=2^i;
print(2(i));
if((n-j)>0) then print(+); f_2(n-j);
}
}
*/
#include <stdio.h>
int f_2(int n);//第一代任务
int f_2_1(int n);//第二代任务
int main()
{
// f_2(137);
f_2_1(137);
return 0;
}
int f_2(int n)
{
if(n==1){
printf("2(0)");
return 0;
}
if(n==0){
return 0;
}
int j=0;//计数
int i=2;
while(i<=n)
{
i = 2*i;
j = j+1;
// printf("i=%d,j=%d\n",i,j);
}
printf("2(%d)",j);
if(n-(i/2)>0)
{
printf("+");
f_2(n-(i/2));
}
}
int f_2_1(int n)
{
if(n==1){
printf("2(0)");
return 0;
}
if(n==0){
return 0;
}
int j=0;//计数
int i=2;
while(i<=n)
{
i = 2*i;
j = j+1;
}
//改动位置
if(j>2){
printf("2(");
f_2(j);
printf(")");
}
//改动位置
if(n-(i/2)>0)
{
printf("+");
f_2_1(n-(i/2));
}
}
6、结果展示:
2.png7、反思总结:
顺着题目的意思,我先实现简单的137=2(7)+2(3)+2(0),我发现用一个子程序f_2()完全可以。然后我们再次升级137=2(2(2)+2+2(0))+2(2+2(0))+2(0),这个时候我想要在f_2()的基础上实现升级任务,我修改了很多次f_2()之后,发现本案例不是简单的一个递归程序就能够解决的,当我尝试用一个子程序去实现的时候,我发现非常困难。这个时候我再去阅读题目,梳理其中的逻辑,我发现f_2()实现的功能没有必要再去修改,我完全可以再写一个f_2_1()来实现升级任务。在升级任务中,f_2_1()本身沿用了f_2()的功能,同时在2(j)中j大于2的时候,我完全可以调用f_2()来分解j。所以我得出两个思考问题:1、我们书写这个案例,子程序深刻理解这个子程序的功能很重要。2、反思能否用一个子程序就实现升级功能?我想到的答案是不可以,因为f_2_1()和f_2()虽然逻辑非常相像,但功能却不相同。