算法学习 | 绪论

开学我也将加入考研的大军中，利用这个假期的时间复习一下《数据结构与算法》给后面的高数复习留下充足的时间，于是养蛙学算法成为了这个寒假的两件大事，代码使用C语言撰写，文中如果有不正确或不足的地方，恳请各位大佬拍砖指正。

什么是算法——从裁纸说起

现在我们需要将1张纸等分成4份

我们可以用直尺和裁纸刀将一张纸裁成相同大小的4份。

当然大部分人不会这么做，他们会将纸对折再对折，这样就可以很容易的分成大小相同的4份。

在程序中我们把这一系列操作的过程称为算法，虽然在这个例子中我们通过直接裁剪和折叠后裁剪两种不同的“算法”取得了相同的结果，但是每个人都知道把纸折叠起来更加容易进行剪裁，这时候我们就可以说第二种“算法”优于第一种“算法”。

体会一下不同算法之间的区别吧！

现在我们需要写一个程序求a、b两个数的最大公约数。

根据公约数的特点，我们可以从a、b两个值中较小的值作为i开始递减，直到出现能被a、b同时整除的数i，i就是这两个数的最大公约数。

打开IDE我们开始写代码~

#include <stdio.h>
/*
求最大公约式
*/
int god(int a,int b){
    if(b>a){int temp=a;a=b;b=temp;}
    for(int i=b;i>0;i--){

        if(a%i==0&&b%i==0) {printf("%d\n",i );break;}

    }

}

int main(){
     god(8,18);
    return 0;
}

输出结果：

2

在god（）这个函数里我们用一个for语句来对i进行递减，直到a、b可以被i整除。

但是如果计算的a、b两个值比较大，而公约数n比较小的时候，我们就需要进行多次if判断。比如45、40的最大公约数是5，那么我们需要进行（40-5）+1次if判断。

那么有没有让程序更简单的方法呢？我们好像忘了辗转相除法，使用辗转相除法可以使我们的函数更加简单。

在改进的god1（）中我们使用辗转相除法和递归进行最大公约数的计算。

#include <stdio.h>
/*
求最大公约式
*/
int god1(int x,int y){
        if(y==0){
            printf("%d\n",x );
        }
        else{
            
            return god1(y,x%y);
        }
}


int main(){
    
     god1(40,45);
 
     
 
 return 0;
}

用递归来解决问题是不是比之前的方法要简单很多？

什么你觉得两个方法看起来差不多？那么我们现在

再将递归的判断语句写法优化一下

#include <stdio.h>
/*
求最大公约式
*/
int god2(int a,int b)
 
{
    return b==0?printf("%d\n", a):god2(b,a%b);
 
}

int main(){
    
     god2(40,45);
    return 0;
    
}

这样的程序跟之前的相比是不是更加简洁了呢？新的算法更简洁，运行速度也较之前快了许多。这就是算法学习的乐趣所在吧~