本文共 6759 字,大约阅读时间需要 22 分钟。
算法设计
第一次作算法设计的作业,感觉还是有点难度的.虽然以前上<<数据结构>>的时候也写过不少的复杂算法,但都是于课本为中心改来改去的.所以没觉得有什么.但自己写算法感觉还不算,特有成就感,(虽然写得不是很好).虽然方法与步骤不是很科学,但我觉得随着课程的深入学习,这方面会有所提高于规范化的.
最有体会的是数据结构与算法的那种密切联系的关系,还有是有用"栈"的思想来实现原本用递归来实现的算法,所得到的效果与好处,有时真是说不出good.大家就看看我所写的作业吧(一些实现的代码),代码所关的问题,大家可以去找算法的书,应该容易找到想关的主题的.希望大家多多指教呀!
/* 本程序利用霍纳规则计算型如:*//*p(x)=AnX*/#include<iostream.h>/* 函数1 (非递归算法)*/double heNaFunction_1(double Array[], double x, int n);/* 函数2 (递归算法)*/double heNaFunction_2(double Array[], double x, int n, int tag);/* 函数3 (' 栈' 算法)*/double heNaFunction_3(double Array[], double x, int n);/* 主函数*/void main(){/* 定义测试变量*/double Array_a[6] = {1,2,3,4,5,6};/* 用于存放多项式的各个系数*/double b = heNaFunction_1(Array_a, 2.0, 5);/* 算多项式的值*/double c = heNaFunction_2(Array_a, 2.0, 5, 1);/* 算多项式的值*/double d = heNaFunction_3(Array_a, 2.0,5);/* 算多项式的值*/cout<<"***********"<<endl;cout<<b<<endl;/* 输出结果*/cout<<c<<endl;/* 输出结果*/cout<<d<<endl;/* 输出结果*/cout<<"###########"<<endl;}/*-------------------------------------------------------------*//* 函数的功能:利用霍纳规则计算多项式的值(非递归算法)*//* 函数返回值:多项式的计算结果(浮点数)*//* 函数参数 第一个:多项式按降幂顺序的对应系数(浮点型数组)*//* 第二个:多项式x 当前的数值(浮点数)*//* 第三个:多项式的最高次幂/*-------------------------------------------------------------*/double heNaFunction_1(double a[], double x, int n){double sum = 0;/* 存放多项式的总和*/sum = a[0]*x + a[1];/* 先计算利用霍纳规则化简后的最内式的值*/for(int i=2; i<=n; i++)/* 循环从内到外的计算总和(从霍纳表达式*/{ /* 一层一层的算出总和)*/sum = sum*x +a[i];}return sum;/* 返回多项式的和*/}/*-------------------------------------------------------------*//* 函数的功能:利用霍纳规则计算多项式的值(递归算法)*//* 函数返回值:多项式的计算结果(浮点数)*//* 函数参数 第一个:多项式按降幂顺序的对应系数(浮点型数组)*//* 第二个:多项式x 当前的数值(浮点数)*//* 第三个:多项式的最高次幂*//* 第四个:递归的系数(赋值为1 )(整型数)*//*-------------------------------------------------------------*/double heNaFunction_2(double Array[], double x, int n, int tag){if(tag==n)/* 当递归次数到时停止(递归次数为多项系的最高次幂)*/{cout<<"last"<<endl;/* 方便查看递归过程*/return (Array[0]*x + Array[1]);}else{cout<<"mill"<<endl;/* 方便查看递归过程*/return (heNaFunction_2(Array, x, n, tag+1)*x + Array[n-tag+1]);/* 递归调用------------------ 递归次数加1---- 上一层的系数*/}}/*-------------------------------------------------------------*//* 函数的功能:利用霍纳规则计算多项式的值(递归算法)*//* 函数返回值:多项式的计算结果(浮点数)*//* 函数参数 第一个:多项式按降幂顺序的对应系数(浮点型数组)*//* 第二个:多项式x 当前的数值(浮点数)*//* 第三个:多项式的单项式个数*//*/*-------------------------------------------------------------*/double heNaFunction_3(double Array[], double x, int n){double temp = 0;for(int i=0;i<=n;i++){temp = temp*x + Array[i];}return temp;}/* 本程序演示AckermannFunction 函数的计算过程*/#include<iostream.h>/* 函数声名*/int AckermannFunction(int m, int n);void main(){int a = 0;a = AckermannFunction(2, 3);cout<<"AckermannFunction(2, 3)="<<a<<endl;}/*-------------------------------------------------------------*//* 函数的功能:计算Ackermann 函数的值(递归算法)*//* 函数返回值:Ackermann 函数的值(整型)*//* 函数参数 第一个:Ackermann 函数的第一个参数(整型)*//* 第二个:Ackermann 函数的第二个参数(整型)*//*-------------------------------------------------------------*/int AckermannFunction(int m, int n){if(m==0)/* 递归结束的条件*/{cout<<n+1<<endl;/* 方便查看过程*/return (n+1);}else if(n==0)/* 递归调用*/{ /* 方便查看过程*/cout<<"AckermannFunction("<<m-1<<","<<1<<")"<<endl;return AckermannFunction(m - 1,1);}else/* 递归调用*/{ /* 方便查看过程*/cout<<"AckermannFunction("<<m-1<<","<<"AckermannFunction("<<m<<","<<n-1<<") )"<<endl;return AckermannFunction(m -1, AckermannFunction(m, n -1));}}/* 本程序用堆栈思想实现AckermannFunction 函数功能*//* 编者:Lgw*//* 专业:04 计本二*//* 日期:07/3/13*/#include<iostream.h>/* 函数声名*/int AckermannFunction(int m, int n);/* 主函数*/void main(){int a =AckermannFunction(2,3);/* 调试数据*/cout<<"AckermannFunction(2,3)="<<a<<endl;/* 打印过程*/}/*-------------------------------------------------------------*//* 函数的功能:计算AckermannFunction 函数*//* 函数返回值:函数的值(整型数)*//* 函数参数 第一个:函数的 m (整型数)*//* 函数参数 第二个:函数的 n (整型数)*//*-------------------------------------------------------------*/int AckermannFunction(int m, int n){int a[100] ;/* 数组" 栈"++++ 看情况可以加大数组元素*/a[0]=m;/* 初使化*/a[1]=n;/* 初使化*/int i=1;/* 栈指针*/while(i!=0){if(a[i-1]==0)/* 第一种情况*/{ /*A(m,n)=n+1 当m=0*/a[i-1]=a[i]+1;i--;/* 出栈*/}else if(a[i]==0)/* 第二种情况*/{ /*A(m,n)=A(m-1,1)*/a[i]=1;a[i-1]=a[i-1]-1;}else{int temp=a[i];/* 第三种情况 A (m, n )=A(m-1,A (m,n-1 ))*/a[i]=a[i-1];a[i-1]=a[i-1]-1;i++;a[i]=temp-1;}for(int k=0;k<=i;k++)/* 输出运算过程*/cout<<a[k]<<" ";cout<<endl;}return a[0];}程序运行结果如同作业本上的运算过程~/* 本程序用于演示鸽巢原理*/#include<iostream.h>/* 函数声名*/double function(double x);void geChaoFunction(double Array[], int n);/* 主函数*/void main(){double Array_a[15];for(int i=0; i<15; i++)Array_a[i]=i;geChaoFunction(Array_a, 15);}/*-------------------------------------------------------------*//* 函数的功能:计算自定义的满足鸽巢原理的函数的值*//* 函数返回值:函数的值(浮点数)*//* 函数参数 第一个:函数的变量(浮点数)*//*-------------------------------------------------------------*/double function(double x){return (x-6)*(x-6);/* 函数表达式y=(x-6)*(x-6)*/}/*-------------------------------------------------------------*//* 函数的功能:演示过程与结果*//* 函数返回值:无*//* 函数参数 第一个:变量数组(浮点型数组)*//* 第二个:变量个数(整型)*//*-------------------------------------------------------------*/void geChaoFunction(double Array[], int n){for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ /* 如果a!=b 且f(a)==f(b) 就输出*/if((function(Array[i])==function(Array[j]))&&(i!=j))cout<<"f("<<Array[i]<<")=="<<"f("<<Array[j]<<")"<<endl;}}}#include<iostream.h>#define MaxSize_1 20#define MaxSize_2 50struct CharStruct/* 用于存放子集*/{char A[MaxSize_1+1];int p;/* 用于记录子集中有多少个字符*/};class PowSet/* 用来指挥计算的类*/{public:CharStruct Set[MaxSize_2+1];int Set_number;/* 记录有多少个子集*/public:PowSet(char a)/* 构造函数*/{Set_number = 2;Set[1].A[1]= a;Set[2].A[1]= ' ';Set[1].p = 1;Set[2].p = 1;}void SetPlay()/* 打印函数*/{for(int i=1;i<=Set_number;i++){cout<<"(";for(int k=1;k<=Set[i].p;k++){cout<<Set[i].A[k]<<" ";}cout<<")"<<endl;}}void SetCopyItSelf()/* 自身的复印函数*/{int j=1;for(int i=Set_number+1;i<=2*Set_number;i++){for(int k=1;k<=Set[j].p;k++){Set[i].A[k]=Set[j].A[k];}Set[i].p=Set[j].p;j++;}Set_number = 2*Set_number;}void AddNumber(char a)/* 一个子集中加入一个符的函数*/{for(int i=1; i<=Set_number/2;i++){Set[i].A[Set[i].p+1]=a;Set[i].p=Set[i].p+1;}}};/*-------------------------------------------------------------*//* 函数的功能:计算一个集合的子集*//* 函数返回值:无*//* 函数参数 第一个:变量数组(整型数组)*//* 第二个:集合元数个数(整型)*//*-------------------------------------------------------------*/void PowSetFunction(char a[], int n)/* 计算过程的函数*/{PowSet myset(a[0]);for(int i=1;i<=n-1;i++){myset.SetCopyItSelf();myset.AddNumber(a[i]);}myset.SetPlay();cout<<" 以上为(";for(int j=0;j<n;j++)cout<<a[j]<<" ";cout<<")"<<" 的子集"<<endl;cout<<" 一共有"<<myset.Set_number<<" 个"<<endl;}void main(){char Char_Array[5]={'A','B','C','D','E'};/ 调试用的数据**/PowSetFunction(Char_Array, 5);}
转载地址:http://gumbi.baihongyu.com/