递归算法设计中的最小值（算法递归参数）

威哥 2023-05-22 01:23:44 199

递归算法设计中的最小值（算法递归参数）十进制整数部分：除二取余，逆向处理。#include <stdio.h> #include <stack> using namespace std; typedef struct Node{ int para1; int lv1; }node; // 用一个结构体为保存参数与局部变量 void counting2(int n) { stack<node> sf; int init = n; while(n<=3) { int lv=10; lv*=n; printf("数据的顺序输出，参数n和局部变量lv：%d %d\n" n lv); node newnode = {n lv}; sf.push(n

迭代使用单一关系式，要考虑迭代次数或结束条件，分精确迭代（如最大公约数）和近似迭代（如求平方根）。

递推的递推变量和递推关系式（包含初始表达式，已知条件或结果，形成初始或边界条件），分为顺推（如斐波那契数列）、逆推（如五猴分桃）。

由编译器隐式实现一个函数调用栈，函数可以自己调用自己，参数之间相互迭代，所以使用递推法能解决的问题也可以通过递归法来解决，递推形成递归的一个阶段。递归调用语句前的部分，一般包含返回的边界条件及其它部分，可用一个局部变量及参数顺序迭代的循环来简单代替，即递推阶段；递归语句本身即回归阶段；递归调用语句的后面部分，可用一个局部变量及参数逆序迭代的循环来代替，但需要程序员自己维护一个显式栈来记忆参数、局部变量和返回值。

#include <stdio.h> void counting(int n) { int lv=10; lv*=n; if(n>3) return; printf("递归调用语句前面部分数据的顺序输出，参数n和局部变量lv：%d %d\n" n lv); counting(n 1); printf("递归调用语句后面部分数据的逆序输出，参数n和局部变量lv：%d %d\n" n lv); } int main() { counting(1); getchar(); return 0; } /* 递归调用语句前面部分数据的顺序输出，参数n和局部变量lv：1 10 递归调用语句前面部分数据的顺序输出，参数n和局部变量lv：2 20 递归调用语句前面部分数据的顺序输出，参数n和局部变量lv：3 30 递归调用语句后面部分数据的逆序输出，参数n和局部变量lv：3 30 递归调用语句后面部分数据的逆序输出，参数n和局部变量lv：2 20 递归调用语句后面部分数据的逆序输出，参数n和局部变量lv：1 10 */

其顺序如下：

递归算法设计中的最小值（算法递归参数）(1)

在逆序时为什么能够记忆参数值和局部变量？

函数调用时编译器使用了一个隐式栈，每一个函数使用一个栈帧来记录需要返回的函数地址、参数值、局部变量值。为了能够在出发后经过一系列调用能回到最初的出发地，需要一个后进先出的数据结构，这就是栈。

当递归用递推的循环来实现时，对于递归调用语句后面的部分，需要由程序员使用一个显式栈来记录参数值和局部变量，并逆序输出：

#include <stdio.h> #include <stack> using namespace std; typedef struct Node{ int para1; int lv1; }node; // 用一个结构体为保存参数与局部变量 void counting2(int n) { stack<node> sf; int init = n; while(n<=3) { int lv=10; lv*=n; printf("数据的顺序输出，参数n和局部变量lv：%d %d\n" n lv); node newnode = {n lv}; sf.push(newnode); // 压栈操作，后面要逆序输出数据 n ; } while(!sf.empty()) { node newnode = sf.top(); printf("数据的顺序输出，参数n和局部变量lv：%d %d\n" newnode.para1 newnode.lv1); sf.pop(); } } int main() { counting2(1); getchar(); return 0; } /* 数据的顺序输出，参数n和局部变量lv：1 10 数据的顺序输出，参数n和局部变量lv：2 20 数据的顺序输出，参数n和局部变量lv：3 30 数据的顺序输出，参数n和局部变量lv：3 30 数据的顺序输出，参数n和局部变量lv：2 20 数据的顺序输出，参数n和局部变量lv：1 10 */

如浮点数的二进制编码输出：

十进制整数部分：除二取余，逆向处理。

十进制小数部分：乘二取整，顺向处理。

#include<stdio.h> #include<math.h> #define N 16 void itobin(int n) { if(n==0) return; itobin(n/2); printf("%d" n%2); } void ftobin(double x) { for(int i=1;i<=N;i ) { x*=2; if(x>=1.0) { x-=1; printf("1"); } else printf("0"); } } void main() { int a[N 1] b[N 1] i k=0 value; float x; double ipart; for(i=0;i<=N;i ) b[i]=0; printf("请输入一个十进制小数:"); scanf("%f" &x); x=modf(x &ipart);//x为小数部分，ipart为整数部分 value=(int)ipart; while(value) // 十进制整数部分：除二取余 { b[k ]=value%2; value/=2; } float d = x; for(i=1;i<=N;i ) // 十进制小数部分：乘二取整 { x*=2; if(x>=1.0) { x-=1; a[i]=1; } else a[i]=0; } printf("二进制数:"); for(i=k;i>=0;i--) // 逆向输出整数 printf("%d" b[i]); printf("."); for(i=1;i<=N;i ) // 顺向输出小数 { if(a[i]==0) printf("0"); else printf("1"); } printf("\n"); itobin(ipart); printf("\n"); ftobin(d); getchar();getchar(); } /* 请输入一个十进制小数:22.62525 二进制数:010110.1010000000010000 10110 1010000000010000 */

附整数与浮点数的表示与存储：

对于浮点数的存储，却是用记阶法表示的，如：

1001.011B = 0.1001011B×2^ 100

-0.0010101B = -0.10101B×2^－10

可见，任一个二进制实数 N 均可表示为：

N=±S×2^P

其中， ±是该数的符号； S是N 的尾数；P是N的阶码。

因此，32位的单精度浮点数在计算机中可表示为：

由于指数（阶码）可以选用不同的编码（原码、补码等），尾数的格式和小数点位置也可以有不同的规定，因此早期计算机中浮点数的表示方法互不相同。

现代计算机中，一般都以IEEE 754标准存储浮点数，这个标准的在内存中存储的形式为：

对于不同长度的浮点数，阶码与小数位分配的数量不一样，如对于32位的单精度浮点数，数符分配是1位，阶码分配了8位，尾数分配了是23位：

递归算法设计中的最小值（算法递归参数）(2)

符号位：0表示正；1表示负；

偏移阶码e：e=指数的实际值 127。

假有一个浮点数10110010.001，则指数是7，阶码就要用7 127的二进制数表示，也就是：111 01111111 = 10000110

尾数使用原码表示，绝对值在1与2之间，其中1和小数点都是隐含的，并不直接表示。

递归算法设计中的最小值（算法递归参数）(3)

根据这个标准，我们来尝试把一个十进制的浮点数转换为IEEE754标准表示。

例如：178.125

先把浮点数分别把整数部分和小数部分转换成2进制：

整数部分用除2取余的方法，求得：10110010

小数部分用乘2取整的方法，求得：001

合起来即是：10110010.001

转换成二进制的浮点数，即把小数点移动到整数位只有1，即为：1.0110010001 * 2^111，111是二进制，由于左移了7位，所以是111

把浮点数转换二进制后，这里基本已经可以得出对应3部分的值了：

数符：由于浮点数是正数，故为0(负数为1)。

阶码 : 阶码的计算公式：阶数偏移量阶码是需要作移码运算，在转换出来的二进制数里，阶数是111(十进制为7)，对于单精度的浮点数，偏移值为01111111(127)[偏移量的计算是：2^(e-1)-1 e为阶码的位数，即为8，因此偏移值是127]，即：111 01111111 = 10000110

尾数：小数点后面的数，即0110010001

最终根据位置填到对位的位置上：

递归算法设计中的最小值（算法递归参数）(4)

可能有个疑问：小数点前面的1去哪里了？由于尾数部分是规格化表示的，最高位总是“1”，所以这是直接隐藏掉，同时也节省了1个位出来存储小数，提高精度。

浮点数的二进制显示可以使用以下代码：

//位运算结合union输出int和float的二进制位 #include <iostream> using namespace std; union { //用于将浮点数的二进制位解析为int位输出 float input; int output; } data; void int2binary(unsigned n)//位运算只能用于整形 { unsigned b32 = 1<<31;//32位二进制，最高位是1，其它位是0 cout<<((n&b32)>>31)<<" ";//最高位与运算，移位后最高位输出 for(int i=1;i<32; i) { n=n<<1;//循环左移一位，用于最高位的与运算 cout<<((n&b32)>>31);//最高位与运算，移位后最高位输出 if(i==7) cout<<" "; if(i>8 && (i-7)%8==0) cout<<" "; } cout<<"\n"; } void float2binary(unsigned n) { unsigned b32 = 1<<31;//32位二进制，最高位是1，其它位是0 cout<<((n&b32)>>31)<<" ";//最高位与运算，移位后最高位输出 for(int i=1;i<32; i) { n=n<<1;//循环左移一位，用于最高位的与运算 cout<<((n&b32)>>31);//最高位与运算，移位后最高位输出 if(i%8==0) cout<<" "; } cout<<"\n"; } void main() { while(1) { int n; cout<<"please input a int:"; cin>>n; int2binary(n); cout<<endl; cout<<"please input a float:"; cin>>data.input; float2binary(data.output); cout<<endl; } } /* please input a int:178 0 0000000 00000000 00000000 10110010 please input a float:178.625 0 10000110 01100101 01000000 0000000 please input a int:-178 1 1111111 11111111 11111111 01001110 please input a float:-178.625 1 10000110 01100101 01000000 0000000 please input a int:134 0 0000000 00000000 00000000 10000110 please input a float: 10110010的阶数是7，最高位总是1，直接隐藏掉；阶码=阶数偏移量 =阶数 2^(e-1)-1 =阶数 2^(8-1)-1 =7 127 =134(10000110) */

要区别整数的补码和浮点数的符号位存储，虽然两者都是以高位0表示正数，1表示负数，但两者规定的规则却是不一样的，负整数是通过正整数的二进制自然码（最高位是0）取反 1而来的。而负浮点数却是直接取1而来的，阶码、尾数都是用自然码来表示的。

还需要注意的是，编码的数据在内存中的存储还要区分大头、小头，如以下小头存储：

递归算法设计中的最小值（算法递归参数）(5)