一、介绍
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
二、知识点介绍
1、水仙花数
2、闰年
3、排序（插入、冒泡、选择）
4、递归
三、上课对应视频的说明文档
1、水仙花数
分析：
（1）水仙花数是一个三位数100-999
（2）取出个位、十位、百位
（3）个位的立方+十位的立方+百位立方==原来这个数，这就是水仙花数
public class Test1{
public static void main(String args[]){
for(int n=100;n<=999;n++){
int a=n%10;//取个位
int b=n/10%10;//取十位
int c=n/100;//取百位
if(a*a*a+b*b*b+c*c*c==n){
System.out.println(n+ "为水仙花数！");
}
}
}
}
2、1949-2018年中的闰年
分析：
（1）找出 1949-2018年之间的闰年
（2）能被4整除且不能被100整除
（3）能被400整除
public class Test2{
public static void main(String args[]){
for(int year=1949;year<=2018;year++){
//当年份能被4并且不能被100整除，或者能被400整除时，为闫年
if(year%4==0&&year%100!=0||year%400==0){
System.out.println(year+"为闰年！");
}
}
}
}
3、排序
（1）选择排序
分析：
（1） 初始化我们的数组，
（2） 第1次执行循环，找出下标从0开始，后面数组中最小的值，与我们的下标为0的位置交换
（3） 第2次执行循环，找出下标从1开始，后面数组中最小的值，与我们的下标为1的位置交换
（4） 第3次执行循环，找出下标从2开始，后面数组中最小的值，与我们的下标为2的位置交换
（5） 以此内推，到循环结束
/*
选择排序
选出最小元素和第1个元素-N个元素交换。
*/
public class XzTest{
public static void main(String args[]){
int n[]={26,53,48,11,13,48,32,15};
for(int i=0;i<n.length;i++){
int min=n[i];//最小值
int k=i;//最小值的下标
for(int j=i;j<n.length;j++){
if(n[j]<min){//找出最小值，并记住下标
min=n[j];
k=j;
}
}
//交换值
n[k]=n[i];
n[i]=min;
}
//增强for，显示数组里面的值
for(int m:n){
System.out.print(m+" ");
}
}
}
（2）插入排序
分析：
（1）初始化我们的数组，
（2）第1次执行循环，找出下标为1开始，保存这个数，保存好的数与他前面的数进行比较 ，如果前面的数比他大，那么前面的数后移，保存好的数放在后移的数的位置，如果不比他大，位置不变
（3）第2次执行循环，找出下标为2开始，保存这个数，保存好的数与他前面的数进行比较 ，如果前面的数比他大，那么前面的数后移，继续比较前面的数，如果不比他大，就将保存好的数放在后移这个数位置，如果比他大，就后移，将保存的数放在第一个位置
（4）以此内推，到循环结束
/*
插入排序
右移，插入
*/
public class CrTest{
public static void main(String args[]){
int n[]={26,53,48,11,13,48,32,15};
int i=1;
while(i<n.length){
int k=n[i];//要插入的值
int j=i; //下标
while(j>0&&k<n[j-1]){
n[j]=n[j-1]; //满足条件的数，右移
j--;
}
n[j]=k;//插入数据到指定位置
i++;
}
for(int m:n){
System.out.print(m+" ");
}
}
}
（3）冒泡排序
分析：
（1）初始化我们的数组，
（2）第1次执行循环，如果第一个数比第二个数大，交换位置，继续和第三个数比较，如果还大，继续交换，如果第四个数比，第三个数大，那么位置不变，以第四个数继续和后面的数比较 ，至到最大的数跑到最后。
（3）以此内推，到循环结束
/*
冒泡排序：
遇到小的就交换，将最大的数放到最后
*/
public class MpTest{
public static void main(String args[]){
int n[]={26,53,48,11,13,48,32,15};
for(int j=n.length-1;j>=0;j--){
for(int i=0,t=0;i<j;i++){
if(n[i]>n[i+1]){//满足条件交换数据
t=n[i];n[i]=n[i+1];n[i+1]=t;
}
}
}
for(int m:n){
System.out.print(m+" ");
}
}
}
4、递归算法
递归：是指在定义自身的同时又出现了对自身的引用。如果一个算法直接或间接的调用了自己，则称之为递归算法。
public class Factorail {
/**
* 求5的阶乘? 5*4*3*2*1 = ?
*/
public static int test(int number){
if(number == 1){//当条件满足时，返回1，否则，反复调用自身
return 1;
}else{
return number * test(number - 1);//反复调用自身
}
}
public static void main(String[] args) {
System.out.println(test(5));
}
}
如案例：当我们的number不为1的时候，我们反复的去调用test(number),当为1时，返回1；
5、题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21....
具体分析如下：
f(1) = 1(第1个月有一对兔子）
f(2) = 1(第2个月还是一对兔子）
f(3) = 2(原来有一对兔子，第3个开始，每个月生一对兔子）
f(4) = 3(原来有两对兔子，有一对可以生育）
f(5) = 5(原来有3对兔子，第3个月出生的那对兔子也可以生育了，那么现在有两对兔子可以生育）
f(6) = 8(原来有5对兔子，第4个月出生的那对兔子也可以生育了，那么现在有3对兔子可以生育）
..............
由以上可以看出，第n个月兔子的对数为
f(n) = f(n - 1) + f(n - 2);
f(n-1)是上个月的兔子数量，是原来有的。
f(n-2)是可以生育的兔子数，即多出来的数量。第n-2个月开始后的第3个月是第n个月，此时第n-2个月时的兔子都可以生育了。
public class Demo01 {
public static void main(String args[]) {
for (int i = 1; i <= 20; i++)
System.out.println(f(i));
}
//递归的调用的方式
public static int f(int x) {
if (x == 1||x == 2)
return 1;
else
return f(x - 1) + f(x - 2);
}
}
或
public class Demo01 {
public static void main(String args[]) {
math mymath = new math();
for (int i = 1; i <= 20; i++)
System.out.println(mymath.f(i));
}
}
//封装成类
class math {
public int f(int x) {
if (x == 1||x == 2)
return 1;
else
return f(x - 1) + f(x - 2);
}
}
6、 题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
1.程序分析：对n进行分解质因数，应先找到一个最小的质数i，然后按下述步骤完成：
(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
(2)如果n > i，但n能被i整除，则应打印出i的值，并用n除以i的商,作为新的正整数你,重复执行第一步。
(3)如果n不能被i整除，则用i+1作为i的值,重复执行第一步。
import java.util.Scanner;
public class Demo04 {
public Demo04() {
super();
}
public void fenjie(int n) {
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
System.out.print(i);
if(n!=i){//分解完后打印*
System.out.print("*");
}
fenjie(n/i);//改变值后，调用本身
}
}
System.exit(0); //退出程序
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("请输入N的值：");
int N = in.nextInt();
System.out.print( "分解质因数：" + N +"=");
new Demo04().fenjie(N);
}
}
7、 题目：输入两个正整数m和n，求其最大公约数和最小公倍数。
1.程序分析：利用辗除法。
import java.util.Scanner;
public class Demo06 {
public static void main(String[] args){
int a,b,m,n;
Scanner in=new Scanner(System.in);
System.out.println("请输入一个正整数：");
a=in.nextInt();
System.out.println("再输入一个正整数：");
b=in.nextInt();
commonDivisor use=new commonDivisor();
m=use.commonDivisor(a,b);
n=a*b/m;
System.out.println("最大公约数："+m);
System.out.println("最小公倍数："+n);
}
}
class commonDivisor{
public int commonDivisor(int x,int y){
if(x<y){//x小于y，交换二个值
int t=x;
x=y;
y=t;
}
while(y!=0){
if(x==y){
return x;
}else{//x不等于y,取x与y的余数
int k=x%y;
x=y;//y赋值给x
y=k;//k赋值给y
}
}
return x;
}
}
8、二分查找（扩展）
对于二分查找算法要求, 查找前的数据必须是已经排好序的, 然后得到数组的开始位置start和结束位置end, 取中间位置mid的数据a[mid]跟待查找数据key进行比较, 若 a[mid] > key, 则取end = mid - 1; 若 a[mid] < key, 则取start = mid + 1; 若 a[mid] = key 则直接返回当前mid为查找到的位置. 依次遍历直到找到数据或者最终没有该条数据. 啰嗦这么多, 上代码!!!
//已经排好序的数组public static int binarySearch(int[] nums, int key) {
int start = 0;
int end = nums.length - 1;
int mid = -1;
while (start <= end) {
mid = (start + end) / 2;
if (nums[mid] == key) {
return mid;//已经查到返回！
} else if (nums[mid] > key) {
end = mid - 1;
} else if (nums[mid] < key) {
start = mid + 1;
}
}
return -1;
}
