算法学习 | 绪论-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

算法学习 | 绪论

简介: 算法是一组完成任务的指令。任何代码片段都可视为算法。——《算法图解》

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

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

image

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

1 2
3 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;
    
}

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章