欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

递推算法

程序员文章站 2024-03-16 11:07:16
...

1.斐波那契数列的前N项

Fibonacci 数列:0,1,1,2,3,5,8,13,21,34,……
f0 = 0
f1 = 1
fn = fn-1 + fn-2 ( n >= 2 )

使用前两项进行迭代,代码如下:

#include <iostream>
using namespace std ;
int main(){
   int n, i, a0, a1 ;
    cout << "n = " ;
    cin >> n ;
    a0 = 0 ;  a1 = 1 ;
    cout << a0 << "  "<< a1 << "  ";
    for ( i = 2; i <= n/2 ; i ++ ){
         a0 = a0 + a1 ;
         a1 = a1 + a0 ;
         cout << a0 << "  "<< a1 << "  ";
         if ( i % 5 == 0 )  cout << endl ;
    }
    if ( n > (i-1)*2 )  cout << a0+a1 << endl ;
    return 0;
} 

2.求N层汉诺塔的移动次数

递推算法

递推关系分析
f(n)=2*f(n-1)+1
边界条件:f(1)=1

代码如下:

#include <iostream>
using namespace std;
int main(){
	int f[1000]={0,1};
	int n;
	cin>>n;
	for(int i=2;i<=n;i++)
		f[i]=2*f[i-1]+1;
	cout<<f[n]<<endl;
	return 0;
}

3. 猴子吃桃问题

猴子第一天采摘了一些桃子,第二天吃了第一天的一半多一个,第三天吃了第二天的一半多一个…直到第十天就剩下一个。问:猴子第一天摘了多少桃子?

分析:
递推关系:
f(n)=f(n-1)/2-1
f(n-1)=(f(n)+1)*2
边界条件:f(10)=1

代码如下:

#include <iostream>
using namespace std;
int main(){
	int f[11];
	f[10]=1;
	for(int i=9;i>=1;i--)
		f[i]=2*(f[i+1]+1);
	cout<<f[1]<<endl;
	return 0;
}

4.数字三角形问题

递推算法(1)顺推法:
要求从(1,1)出发到最底层路径的最大权值和,路径中各个点串联而成;
定义F[x][y]表示从[1][1]出发到(x)(y)的最大权值和;

递推算法F[x][y]=?
向左:
F[x-1,y]+A[x][y];
向右:
F[x-1][y-1]+A[x][y];
递归边界条件:
F[1][1]=A[1][1];
最终答案:
Ans=max(F[N][1],F[N][2],…F[N][N]);

#include <iostream>
#include<algorithm>
using namespace std;

const int MAX=1005;

int main()
{
    int A[MAX][MAX],F[MAX][MAX],N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>A[i][j];
            }
        }
    F[1][1]=A[1][1];
    for(int i=2;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            F[i][j]=max(F[i-1][j],F[i-1][j-1])+A[i][j];
            }
        }
    int ans=0;
    for(int i=1;i<=N;i++)
    {
        ans=max(ans,F[N][i]);
        }
    cout<<"ANS:"<<ans<<endl;
    return 0;
}

(2)逆推法:

定义F[x][y]表示从N层出发到达(x,y)的路径的最大权值和;
即推出递归表达式:
F[i][j]=max(F[i+1][j],F[i+1][j+1])+A[i][j];
递归边界条件:
F[n][j]=A[n][j];

代码如下:

#include <iostream>
#include<algorithm>
using namespace std;

const int MAX=1005;

int main()
{
    int A[MAX][MAX],F[MAX][MAX],N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>A[i][j];
            }
        }
    F[1][1]=A[1][1];
    for(int i=1;i<=N;i++)
    {
        F[N][i]=A[N][i];
        }
    for(int i=2;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            F[i][j]=max(F[i-1][j],F[i-1][j-1])+A[i][j];
            }
        }

    cout<<"ANS:"<<F[1][1]<<endl;
    return 0;
}

相关标签: 递推算法