算法複習筆記之重要算法（一）

算法複習筆記之重要算法（一）

序言：這次對于這部分進行了修改，一是為了備考，也順便梳理以下算法的一些，同時交待一下總共需要介紹的算法總類

分類：

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;
 }