基础算法(一)

最近看了《Java编程那些事》博客专栏,在讲到Java流程控制那块,提到了很多自己当初学习过程中涉及到的小算法,都很经典,以后会不断的将接触到的算法更新到本博文中,供自己以后查看,也可以作为大家学习的一个小资料。

1. 最大公约数

问题:求两个自然数的最大公约数。

这两个都是基础的数学问题,最大公约数指两个数字公共的约数中最大的,例如数字6的约数有1、2、3、6,数字9的约数有1、3、9,则数字6和数字9的公共约数有1和3,其中3是最大的公约数。

       第一种思路:从1开始循环,每次把符合要求(即同时是两个数字的约数)的值都存储起来,那么最后一个存储起来的就是最大的约数。

       则实现的代码如下:      

int n = 6;
int m = 9;
int result = 1;
for(int i = 1;i <= n;i++){
    if((n % i == 0) && (m % i == 0)){
        result = i;
    }
}
System.out.println(result);

使用该思路,每次都存储得到的公共约数,那么最后一个存储的就是两个数字的最大公约数。

第二种思路:从两个数字中最小的数字开始循环,每次减1,那么第一次得到的公共约数就是所求的最大公约数。

则实现的代码如下:                  

int n = 6;
int m = 9;
int result = n > m ?m : n;
    for(int i = result;i >= 1;i--){
        if((n % i == 0) && (m % i == 0)){
            result = i;
            break; //结束循环
        }
    }
System.out.println(result);

当然,解决这个问题,还有很多其它的方法,这里演示的这两种实现只是最自然的实现而已,采用类似的原理也可以求两个数字的最小公倍数的结构。

2. 百元百鸡问题

问题描述:每只母鸡3元,每只公鸡4元,每只小鸡0.5元,如果花100元钱买100只鸡,请问有哪些可能?说明:每种鸡的数量都可以为零。

其实这个问题是数学上的组合问题,只需要把所有的情况列举出来,然后来判断是否符合要求即可。这样的重复列举的问题,在程序上可以使用循环进行解决。

       第一种思路:当母鸡的数量为0时,公鸡的数量从0-100,当公鸡的数量每变化一次,小鸡的数量就从0变化到100,使用如下数值组合来描述这个思路:

                  母鸡数量                            公鸡数量                            小鸡数量

                      0                                               0                                   从0变化到100

                      0                                               1                                   从0变化到100

                      0                                               2                                   从0变化到100

                   ……

                      1                                               0 从0变化到100

                      1                                               1                                   从0变化到100

                   ……

                      100                                           100                               100

上面列举出了所有公鸡、母鸡和小鸡的数量都是0-100时的所有组合,总计是101的三次方种,这样的穷举结构直接存在嵌套,在程序实际实现时,通过循环之间的嵌套就可以实现,则实现的代码如下:                  

for(int i = 0;i <= 100;i++){ //母鸡数量
    for(int j = 0;j <= 100;j++){ //公鸡数量
        for(int k = 0;k <= 100;k++){ //小鸡数量
            //判断数量是否为100,以及金额是否为100
            if((i +j + k == 100) && (i * 3 + j * 4 + k * 0.5 == 100)){
                System.out.println(“母鸡数量:” + i + “ 公鸡数量:” + j + “ 小鸡数量” + k);
            }
        }
     }
}

按照for语句的执行流程,循环变量变化1,则内部的循环执行一次,而在循环嵌套时,循环体又是一个新的循环,则该循环执行完成的一组循环。这里通过循环的嵌套实现了所有数值的穷举。在循环的内部,只需要按照题目要求判断一下数量和金额是否符合要求即可。

但是这样的代码效率比较差,可以通过简单的优化来提高程序的执行效率。

第二种思路:由于母鸡每只的金额是3元,所以100元最多购买的母鸡数量是100/3=33只,同理100元最多购买的公鸡数量是25只,而按照100元100只的要求,小鸡的数量应该为100减去公鸡和母鸡的数量,这样代码就可以简化为如下的结构:

for(int i = 0;i <= 33;i++){ //母鸡数量
    for(int j = 0;j <= 25;j++){ //公鸡数量
        int k = 100 –i – j; //小鸡数量
        //判断金额是否为100
        if (i * 3 + j * 4 + k * 0.5 == 100){
            System.out.println(“母鸡数量:” + i + “ 公鸡数量:” + j + “ 小鸡数量” + k);
        }
    }
}

这样,就可以大幅提高程序的执行效率,从而提高程序的执行速度。当然该代码还可以继续进行优化,那样可以再次提高程序的执行效率。

3. 喝汽水问题

问题:共有1000瓶汽水,每喝完后一瓶得到的一个空瓶子,每3个空瓶子又能换1瓶汽水,喝掉以后又得到一个空瓶子,问总共能喝多少瓶汽水,最后还剩余多少个空瓶子?

这个问题其实是个比较典型的递推问题,每3个空瓶都可以再换1瓶新的汽水,这样一直递推下去,直到最后不能换到汽水为止。

第一种思路:每次喝一瓶,每有三个空瓶子就去换一瓶新的汽水,直到最后没有汽水可以喝为止。在程序中记忆汽水的数量和空瓶子的数量即可。

则实现的代码如下:                   

int num = 1000;       //汽水数量
int drinkNum = 0;     //喝掉的汽水数量
int emptyNum = 0;   //空瓶子的数量
while(num > 0){      //有汽水可以喝
    num--;         //喝掉一瓶
    emptyNum++; //空瓶子数量增加1
    drinkNum++;   //喝掉的汽水数量增加1
    if(emptyNum == 3){ //有3个空瓶子,则去换
        num++;   //汽水数量增加1
        emptyNum = 0;   //空瓶子数量清零
    }
}
System.out.println(“总共喝掉瓶数:” + drinkNum);
System.out.println(“剩余空瓶子数:” + emptyNum);

执行该程序,输出结果如下:

总共喝掉瓶数:1499

剩余空瓶子数:2

在该代码中,每次循环喝掉一瓶汽水,则汽水数量减少1,空瓶子数增加1,喝掉的总汽水瓶数增加1,每次判断空瓶子的数量是否达到3,如果达到3则换1瓶汽水,同时空瓶子的数量变为零。这种思路比较直观,但是循环的次数比较多,所以就有了下面的逻辑实现。

第二种思路:一次把所有的汽水喝完,获得所有的空瓶子,再全部换成汽水,然后再一次全部喝完,再获得所有的空瓶子,依次类推,直到没有汽水可喝为止。

则实现的代码如下:              

int num = 1000;       //汽水数量
int drinkNum = 0;     //喝掉的汽水数量
int emptyNum = 0;    //空瓶子的数量
while(num > 0){      //有汽水可以喝
    drinkNum += num; //喝掉所有的汽水
    emptyNum += num; //空瓶子数量等于上次剩余的加上这次喝掉的数量
    num = emptyNum / 3; //兑换的汽水数量
    emptyNum -= num * 3; //本次兑换剩余的空瓶子数量
}
System.out.println(“总共喝掉瓶数:” + drinkNum);
System.out.println(“剩余空瓶子数:” + emptyNum);

在该代码中,每次喝掉所有的汽水,也就是num瓶,则喝掉的总瓶数每次增加num,因为每次都可能剩余空瓶子(不足3个的),则总的空瓶子数量是上次空瓶子数量加上本次喝掉的num瓶。接着是兑换汽水,则每次可以兑换的汽水数量是空瓶子的数量的1/3,注意这里是整数除法,而本次兑换剩余的空瓶子数量是原来的空瓶子数量减去兑换得到汽水数量的3倍,这就是一次循环所完成的功能,依次类推即可解决该问题。

还有一种做法,3个空瓶子=1瓶饮料=>3个空瓶子=1瓶饮料(不带瓶)+1个空瓶子=>2个空瓶子=1瓶饮料(不带瓶),那么这样1000个空瓶可以兑换500瓶饮料(不带瓶),但是最后1瓶饮料你是喝不到的,因为你最后剩下2个空瓶,喝的饮料数=1000+500-1。

int num = 1000;       //汽水数量
int drinkNum = 0;     //喝掉的汽水数量
int emptyNum = 2;    //空瓶子的数量
drinkNum = num + num/2 - 1;
System.out.println(“总共喝掉瓶数:” + drinkNum);
System.out.println(“剩余空瓶子数:” + emptyNum);

这样做算不算做出这道题呢?

4. 水仙花数

问题:水仙花数指三位数中,每个数字的立方和和自身相等的数字,例如370,3 × 3 × 3 + 7 × 7 × 7 + 0 × 0 × 0 =370,请输出所有的水仙花数。

该问题中体现了一个基本的算法——数字拆分,需要把一个数中每位的数字拆分出来,然后才可以实现该逻辑。

实现思路:循环所有的三位数,拆分出三位数字的个位、十位和百位数字,判断3个数字的立方和是否等于自身。

则实现的代码如下所示:                   

for(int i = 100;i < 1000;i++){ //循环所有三位数
    int a = i % 10;         //个位数字
    int b = (i / 10) % 10; //十位数字
    int c = i / 100;       //百位数字
    //判断立方和等于自身
    if(a * a * a + b * b * b + c * c * c == i){
        System.out.println(i);
    }
}

在该代码中,拆分个位数字使用i和10取余即可,拆分十位数字时首先用i除以十,去掉个位数字,并使原来的十位数字变成个位,然后和10取余即可,因为i是一个三位数,所以i除以100即可得百位数字,因为这里都是整数除法,不存在小数的问题。然后只需要判断立方和是否等于自身即可。

注意:因为i是循环变量,这里不能改变i的值,不然可能造成死循环。

5. 求素数问题

       问题:求出1000以内的所有素数,素数即质数,只能被1和本身整除的数,最小的质数是2。

       实现思路:通过嵌套循环找出2到1000内所有的符合条件的数。

       则实现的代码如下所示:       

for (int i = 2; i <= 1000; i++) {
    boolean isPrime = true;
    for (int j = 2; j < i; j++) {
        if (i % j == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) {
        System.out.println(i);
    }
}           

       这样算是想到的最直接的方式,当然也是最笨的方式,因为每次判断的时候都会从2检查到i,聪明一点的方式是把i变成i/2,因为i/2以上的数肯定不会被i整除。

则实现的代码如下所示:       

for (int i = 2; i <= 1000; i++) {
    boolean isPrime = true;
    for (int j = 2; j < i / 2 + 1; j++) {
        if (i != j && i % j == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) {
        System.out.println(i);
    }
}

       那么再聪明的方式就是把i/2变成根号i,因为根号i以上的数肯定不会被i整除。

则实现的代码如下所示:

for (int i = 2; i <= 1000; i++) {
    boolean isPrime = true;
    // Math.sqrt(i):开平方方法
    for (int j = 2; j < Math.sqrt(i) + 1; j++) {
        if (i != j && i % j == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) {
        System.out.println(i);
    }
}

        当然还有效率更高的方式,筛选法,在本文基础算法中不作介绍。

6. 输出数列        要求:输出1 1 2 3 5 8 13……这样的数列,输出该数列的前20个数字。        该题是一个基本的数字逻辑,在实际解决该问题时,首先要发现该数字的规律,然后按照该规律来设计数组即可。        实现思路:数字的规律是除了数列里的前两个数字以外,其它的数字都满足该数字等于前两个数字的和,由于题目要求输出前20个数字,所以需要一个长度为20的数组,第一个和第二个数字直接赋值,后续的数字通过前两个数字元素得到。        则实现的代码如下:

int[] num = new int[20];
num[0] = 1;
num[1] = 1;
//循环初始化
for(int i = 2;i < num.length;i++){
    num[i] = num[i – 1] + num[i – 2];
}
//循环输出
for(int i = 0;i < num.length;i++){
    System.out.print(num[i] + " ");
}
System.out.println(); //换行

       在该代码中,初始化一个长度为20的数组,首先将数组中的前两个元素赋值成1,然后循环对后续的元素的赋值,如果当前元素的下标是i,则它前一个元素的下标是i-1,再前面一个元素的下标是i-2,只需要将这2个元素的值相加,然后赋值给当前元素即可。后面使用一个循环,输出数组中所有的元素,元素和元素之间有一个间隔的空格,在输出所有的元素以后换行。

7. 歌手打分        要求:在歌唱比赛中,共有10位评委进行打分,在计算歌手得分时,去掉一个最高分,去掉一个最低分,然后剩余的8位评委的分数进行平均,就是该选手的最终得分。如果已知每个评委的评分,求该选手的得分。        该题实际上涉及到求数组的最大值、最小值,以及求数组中所有元素的和,也是数组方便统计的用途体现。        实现思路:求出数组元素的最大值、最小值以及和,然后使用和减去最大值和最小值,然后除以8获得得分。        则实现的代码如下:

int[] score = {90,78,90,96,67,86,78,92,79,85}; //评委打分
int sum = score[0]; //存储和
int max = score[0]; //存储最大值
int min = score[0]; //存储最小值
for(int i = 1;i < score.length;i++) {
    sum += score[i]; //求和
    //获得最大值
    if(max < score[i]) {                                      
        max = score[i];
    }
    //获得最小值
    if(min > score[i]) {
        min = score[i];
    }
}
 //计算平均分
double avg = (sum – max – min) / 8.0;
System.out.println(avg);

       下一篇:基础算法(二)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SpiritLing

用Canvas生成随机验证码(后端前端都可以)

一 、使用前端生成验证码 <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> ...

2833
来自专栏开心的学习之路

Canvas绘图——2d表

初学JavaScript,用Canvas画一个表。主要用到昨天学的间歇调用(setInterval)。 方法和属性介绍 context.beginPath()、...

3407
来自专栏HTML5学堂

Canvas 基本绘制(下)

HTML5学堂:在前一篇文章《Canvas 基本绘制(上)》当中,我们为大家介绍了Canvas的基本知识——什么是Canvas、如何使用Canvas进行图像的绘...

3466
来自专栏葡萄城控件技术团队

三天学会HTML5——SVG和Canvas的使用

在第一天学习了HTML5的一些非常重要的基本知识,今天将进行更深层学习 首先来回顾第一天学习的内容,第一天学习了新标签,新控件,验证功能,应用缓存等内容。 第2...

3749
来自专栏十月梦想

canvas画布实现矩形的绘制

绘制一个实心矩形cv.fillRect(x,y,width,height)绘制之前声明绘制的实心矩形颜色使用fillStyle

1083
来自专栏听雨堂

关于vb中的容器

    最失败的事情莫过于,用了十来年的vb,忽然发现,原来自己还没有搞懂一些最简单的东西.昨天,第一次试用了一下vb的类的继承,感觉还不赖。今天,开始琢磨一下...

1827
来自专栏菩提树下的杨过

Flash/Flex学习笔记(46):正向运动学

所谓"正向运动学"通俗点讲就是把几个连接部件的一端固定起来,另一个端可以自由(向前/向外)运动。比如人的行走,单个下肢可以理解为脚连接小腿,小腿连接大腿,大腿连...

2026
来自专栏十月梦想

canvas扇形图、饼状图绘制

上一篇说过使用arc属性绘制一个完整的圆,这是绘制扇形是不是可以刷一下小聪明吧弧度修改一下,你会发现绘制的扇形想西瓜皮一样,只有初始弧度到结束弧度的一个简单连接...

901
来自专栏Golang语言社区

前端游戏编程基础-如何实现Canvas图像的拖拽、点击等操作

希望能对Canvas绘制出来的图像进行点击、拖拽等操作,因为Canvas绘制出的图像能很好的美化。好像是想做炉石什么的游戏,我也没玩过。 Canvas在我的理解...

4577
来自专栏HT

HT for Web 中Painter的介绍及用法

鉴于许多同学对Painter不熟悉,所以撰写此文介绍下。Painter的中文意思是画家、漆工,那放到HT里是什么意思呢?很简单,这是HT特有的一种接口,允许开发...

1706

扫码关注云+社区