[数据结构]C++递归算法作业

1 . 斐波那契数列

已知：

f(0)=1

f(1)=1

f(n)=f(n-1)+f(n-2)

请编程求解f(n)

答案

#include <iostream>
using namespace std;
int fabo(int n)
{
  if(n==0||n==1)
    return 1;
  else
    return fabo(n-1)+fabo(n-2);
}
int main()
{
    int n;
    cin >> n;
    cout << fabo(n);
    return 0;
}

2 . 整数分解

将一个正整数分解成若干个正整数之和

答案

#include <iostream>
using namespace std;
int a[100];
void comb(int n,int len)
{
    if(n==0){
        for(int i=0;i<len;i++)
            cout<<a[i]<<" ";
        
        cout<<endl;
    }else{
        int j;
        if(len==0 || a[len-1]>n)
            j=n;
        else
            j=a[len-1];
        for(;j>0;j--){
            a[len]=j;
            comb(n-j,len+1);
        }
    }

}
int main()
{
    int n;
    cin >> n;
    comb(n,0);
    return 0;
}

3 .整数分解(乘法)

将一个正整数分解成若干个大于1的正整数之积

答案

#include <iostream>
using namespace std;
int a[100];
void comb(int n,int len)
{
    if(n==1){
        for(int i=0;i<len;i++)
            cout<<a[i]<<" ";
        
        cout<<endl;
    }else{
        int j;
        if(len==0 || a[len-1]>n)
            j=n;
        else
            j=a[len-1];
        for(;j>1;j--){
            if(n%j==0){
                a[len]=j;
                comb(n/j,len+1);
            }
        }
    }

}
int main()
{
    int n;
    cin >> n;
    comb(n,0);
    return 0;
}