五大经典算法之<递归算法及经典实例分析>

#include<stdio.h>
//阶层函数
int Fact(int n){
if(n==0)return 1;
else return n*Fact(n-1);
}
int main(){
    int n,total;
    printf("请输入正整数n:\n");
    scanf("%d",&n);
    total=Fact(n);
    printf("%d的阶层为：%d\n",n,total);  
    return 0;
}

#include <iostream>
using namespace std;
#include <math.h>
#define PI       3.1415926535897932384626433832795

#define E 2.7182818284590452353602874713527

//结点
struct bigNum

{
       double n; //科学计数法表示的尾数部分

       int    e; //科学计数法表示的指数部分,若一个bigNum为x,这x=n * 10^e

};

//const修饰的量为一个常变量,需要初始化
const double a1[]=

{     1.00, 1.0/12.0, 1.0/288, -139/51840,-571.0/2488320.0 };//

const double a2[]=

{     1.0/12.0, -1.0/360, 1.0/1260.0 };

void printfResult(struct bigNum *p,char buff[])
{

       while (p->n >=10.00 )

       {p->n/=10.00; p->e++;}

       sprintf(buff,"%.14fe%d",p->n,p->e);

}


// n!=sqrt(2*PI*n)*(n/e)^n*(1+ 1/12/n+ 1/288/n^2 -139/51840/n^3-571/2488320/n^4+…)

void calcFac1(struct bigNum *p,int n)

{

       double logx,

              s,            //级数的和

              item;  //级数的每一项　　　

       int i;


       // x^n= pow(10,n * log10(x));

       logx= n* log10((double)n/E);

       p->e= (int)(logx);
       p->n= pow(10.0, logx-p->e);
       p->n *= sqrt( 2* PI* (double)n);


      //求(1+ 1/12/n+ 1/288/n^2 -139/51840/n^3-571/2488320/n^4+…)

       for (item=1.0,s=0.0,i=0;i<sizeof(a1)/sizeof(double);i++)

       {
              s=s + item * a1[i];//求和

              item= 1/(n^i);
       }

       p->n *=s;

}



//ln(n!)=0.5*ln(2*PI)+(n+0.5)*ln(n)-n+(1/12/n -1/360/n^3 + 1/1260/n^5 -...)

void calcFac2(struct bigNum *p,int n)

{

       double logR;

       double s, //级数的和

       item;       //级数的每一项

       int i;



       logR=0.5*log(2.0*PI)+((double)n+0.5)*log(n)-(double)n;



       //　s= (1/12/n -1/360/n^3 + 1/1260/n^5)

       for (item=1/(double)n,s=0.0,i=0;i<sizeof(a2)/sizeof(double);i++)

       {

              s+= item * a2[i];

              item /= (double)(n)* (double)n; //item= 1/(n^(2i+1))

       }

       logR+=s;

       //根据换底公式，log10(n)=ln(n)/ln(10)

       p->e = (int)( logR / log(10));

       p->n = pow(10.00, logR/log(10) - p->e);

}



int main(int argc, char* argv[])
{
       struct bigNum r;

       char buff[32];

       int n;

       printf("请输入正整数n:\n");
       scanf("%d",&n);

       calcFac1(&r,n);            //用第一种方法，计算n的阶乘
       printfResult(&r,buff);    //将结果转化一个字符串

       printf("方法一：%d!=%s ",n,buff);

       printf("\n");
       calcFac2(&r,n);            //用第二种方法，计算n的阶乘

       printfResult(&r,buff);    //将结果转化一个字符串

       printf("方法二：%d!=%s ",n,buff);


       return 0;

}

#include<stdio.h>
//斐波那契函数
int Fib(int n){
    if(n==1||n==2)return 1;         //递归终止条件
    else return Fib(n-1)+Fib(n-2);  //递归步骤
}
int main(){
    int n,total;
    printf("请输入几个月后：\n");
    scanf("%d",&n);
    total=Fib(n);
    printf("%d月后的兔子总数为：%d\n",n,total);
    return 0;
}

/*汉诺塔问题         规则：每次只能移动一个柱子          */
#include<stdio.h>
//函数声明
void move(char A,int n,int *m,char C);         //输出移动路线
void Hanoi(int n,int *m,char A,char B,char C); //汉诺塔函数
//主函数
int main(){
    int m=0;                                    //记录搬动次数
    int*q = &m;
    int n;
    char a='A';
    char b='B';
    char c='C';
    printf("请输入汉诺塔层数：\n");
    scanf("%d",&n);
    Hanoi(n,q,a,b,c);                           //调用汉诺塔函数
    printf("总移动次数为：%d\n",m);
    return 0;
}

void move(char A,int n,int* m,char C)
{
    printf("第 %d 次: 编号为%d 移动: %c -> %c\n",++(*m),n,A,C);
}
//汉诺塔函数
void Hanoi(int n,int *m,char A,char B,char C){
//将塔座A上的n个圆盘按规则搬到C上，B做辅助塔
    if(n==1) move(A,1,m,C);   //将编号为1的圆盘从A移动到C
    else{
        Hanoi(n-1,m,A,C,B);   //将A上编号为1至n-1的圆盘移动到B，C做辅助塔
        move(A,n,m,C);        //将编号为n的圆盘从A移动到C
        Hanoi(n-1,m,B,A,C);   //将B上编号为1至n-1的圆盘移动到C，A做辅助塔
    }
}

/*递归实现全排列*/

#include<stdio.h>

//交换函数值
void swap(int arr[],int m,int n)
{
    int temp=arr[m];
    arr[m]=arr[n];
    arr[n]=temp;
}
//全排列
void  All_permutation(int arr[],int p,int q)
{
    if(p==q)                          //递归出口
    {
        for( int i=0;i<=q;i++)
            printf(" %d ",arr[i]);
        putchar('\n');
    }
    else
    {
        for(int i=p;i<=q;i++)              //将每个数据依次放在第一个位置
        {
            swap(arr,p,i);
            All_permutation(arr,p+1,q);    //剩下的n-1个数进行全排列
            swap(arr,p,i);                 //将下一个数放在第一位之前应让之前调换的数据归位
        }

    }
}
int main()
{
    int i;
    int *arr;
    int N;
    printf("请输入你要全排列的数据个数:\n");
    scanf("%d",&N);
    for(i =0;i<N;i++)
        arr[i]=i+1;
    printf("全排列结果为：\n");
    All_permutation(arr,0,N-1);
    return 0;
}