算法基础

算法基础

算法基础部分

算法是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下5个属性：

• 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成
• 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口
• 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。
• 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。
• 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

所以对应的算法设计的要求：

• 正确性：算法应满足具体问题的需求；
• 可读性：算法应该好读，以有利于读者对程序的理解；
• 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。
• 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。

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只鸡，请问有哪些可能？说明：每种鸡的数量都可以为零。

参考代码：

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

3. 喝汽水问题

问题：共有1000瓶汽水，每喝完后一瓶得到的一个空瓶子，每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);  

4. 水仙花数

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

参考代码：

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

5. 求素数问题

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

参考代码：

for(int i = 2; i <= 1000; i++) {  
    boolean isPrime = true;  
    // Math.sqrt(i)：开平方方法  
    for(int j = 2; j < Math.sqrt(i); 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个数字。

参考代码：

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(); //换行 

7. 歌手打分

要求：在歌唱比赛中，共有10位评委进行打分，在计算歌手得分时，去掉一个最高分，去掉一个最低分，然后剩余的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; 

8. 寻找孤立数字

需求：给定一个数组，数组内的数两两相同，只有一个数是孤立的，用最快的方式找出这个数。

参考代码：

int[] array = {1, 2, 3, 2, 3, 1, 4};  
int single = 0;  
for(int i = 0; i < array.length; i++) {  
  boolean isSingle = true;  
  for(int j = 0; j < array.length; j++) {  
    if(j != i && array[i] == array[j]) {  
      isSingle = false;  
      break;  
    }  
  }  
  if(isSingle) {  
    single = array[i];  
    break;  
  }  
}
// 第二种方法
int[] array = {1, 2, 3, 2, 3, 1, 4};  
int single = array[0];  
for(int i = 1; i < array.length; i++) {  
        single ^= array[i];  
}  

9. 进制转换

将一个整型数据转换成二进制字符串。

参考代码：

public static String toBinary(int value) {  
    StringBuilder build = new StringBuilder();  
    if(value > 0) {  
        build.append(0);  
    } else {  
        build.append(1);  
        value = -value;  
    }  
    for(int i = 30; i >= 0; i--) {  
        build.append(value >> i & 1);
        // 和1做与操作之后，该位置之前的数全部干掉  
    }  
    return build.toString();      
}