算法复习笔记之重要算法（一）

序言：这次对于这部分进行了修改，一是为了备考，也顺便梳理以下算法的一些，同时交待一下总共需要介绍的算法总类

分类：

KMP、0/1背包(0，1位向量)、 任务分配问题

数字螺旋方阵、归并排序、最大字段和（蛮力、分治、动态）

折半查找、选择问题

数塔问题、 最长公共子序列、

付款问题、钱币兑换、背包问题、多机调度算法

目录：

    1.斐波那契

    2.钱币问题

主要算法介绍：

    一、求斐波那契数列的第N项

        1.1 斐波那契数数列的性质：

        方法：

              1.1.1 递推

              1.1.2递归

              1.1.3动态规划

              1.1.4数学方法

   1.1.1递推方法代码：

#include<iostream>
usaing namespace std;
int main()
{
    int n,a,b,t,i;
    a=1;b=1;
    scanf("%d",&n);
    if(n==1||n==2)
        coutMM1<<endl;
    else
    {
        for(i-1;i<=n;i++)
        cout<<t<<endl;
    }
    return 0;
}
           

1.1.2 递归方式

#include<iostream>
using namespace std;
int f(int k)
{
    if(k<=2) return 1;
    else
 return f(k-1)+f(k-2);
}

 int main()
{
    int n,a,b,i;
    a=1;b=1;
    cin>>n;
    cout<<(n)<<endl;
     return 0;
}
           

1.1.3 动态规划

#include<iostream>
using namespace std;
const int n=20；
int a[n]={0,1,1};
 int main()
{
    int n,i;
    scanf("%d",&n);
    for(i=3;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    cout<<a[n]<<endl;
    return 0;
 }
           

1.1.4 数学公式

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n,i;
    float t;
    scanf("%d",&n);
    t=(pow(1+sqrt(5)/2,n)-pow((1-sqrt(5)/2),n))/sqrt(5);
    printf("%.0f\n",t);
    return 0;
 }
           

二、钱币兑换”问题

    2.1枚举法

#include<iostream>
using namespace std;
int main()
{
    int x,y,z,total=0;
    for(x=0;x<=100;x++)
        for(y=0;y<=50;y++)
            for(z=0;z<=20;z++)
                if(x+2*y+5*z==100)
                    totol++;
    cout<<total<<endl;
    return 0;            
 }

           

   2.2 贪心法

#include<iostream>
using namespace std;
int main()
{
    int x,n,total=0;
    cin>>n;
    while(n>=5)
    {
        total++;
        n-=5;
    }
    while(n>2)    
    {
        total++;
        n-=2;
    }
    cout<<total<<endl;
    return 1;
 }