算法设计与分析
第二章实验1.逆置单链表实验2.判断两棵二叉树是否同构实验5.求两个数最大公约数第三章实验1.求解查找假币问题实验2.求解众数问题实验3.求解逆序数的问题第四章实验1.求解根号n向下取整实验2.求解钱币兑换问题实验3.求解环绕的区域的问题第五章第一次更新时间：4.21
第二次更新时间：5.18——增加了第二章第二题
第二章
实验1.逆置单链表
我这里创建了一个头节点为空的单链表
package DataStructure.LinkedList;public class SingleList {public static void main(String[] args) {//创建节点Node a = new Node(1, "陈");Node b = new Node(2, "范");Node c = new Node(3, "卢");Node d = new Node(4, "胡");list List = new list();//创建一个链表//把节点也就是数据添加到链表里面List.addbyorder(c);List.addbyorder(a);List.addbyorder(d);List.addbyorder(b);List.listview();//显示链表内的数据Node e = new Node(5, "卢*");List.update(e);//更改List.listview();List.delete(3);//删除List.listview();System.out.println("逆置单链表：");InvertList(List.getHead());List.listview();}//逆置链表public static void InvertList(Node head) {if (head.next == null || head.next.next == null) {//如果头节点下一个为空或者下一个的下一个为空，即只有一个数据，即不用逆置，直接输出即可return;}Node temp = head.next;//建立一个辅助引用，也可以说是辅助变量Node Assist = null;Node InverList = new Node(0, " ");while (temp != null) {Assist = temp.next;temp.next = InverList.next;InverList.next = temp;temp = Assist;}head.next = InverList.next;}}class Node {public int number;public String name;public Node next;public Node(int number, String name) {this.name = name;this.number = number;}@Overridepublic String toString() {return "学号：" + number + ",姓名：" + name;}}class list {private Node head = new Node(0, "");public Node getHead() {return head;}//添加到链表public void add(Node node) {Node temp = head;while (true) {if (temp.next == null) {break;}temp = temp.next;}temp.next = node;}//按照值顺序添加到链表public void addbyorder(Node node) {//按照number序号添加Node temp = head;boolean flag = false;while (true) {if (temp.next == null) {break;}if (temp.next.number > node.number) {break;} else if (temp.next.number == node.number) {flag = true;break;}temp = temp.next;}if (flag) {System.out.println("当前学号为" + node.number + "的学生已存在！");} else {node.next = temp.next;temp.next = node;}}//更新节点public void update(Node node) {Node temp = head;boolean flag = false;while (true) {if (temp.next == null) {break;} else if (temp.next.number == node.number) {flag = true;break;}temp = temp.next;}if (flag) {temp.next.name = node.name;} else {System.out.println("没有找到该学号学生！");}}//删除节点public void delete(int number) {Node temp = head;boolean flag = false;while (true) {if (temp.next == null) {break;} else if (temp.next.number == number) {flag = true;break;}temp = temp.next;}if (flag) {temp.next = temp.next.next;System.out.println("修改成功");} else {System.out.println("没有找到要删除的学生学号！");}}//展示链表public void listview() {if (head.next == null) {System.out.println("链表为空");return;}Node temp = head.next;while (true) {if (temp == null) {break;}System.out.println(temp);temp = temp.next;}}}
实验2.判断两棵二叉树是否同构
递归求解
class TwoSolution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;} else if (p == null || q == null) {return false;} else if (p.val != q.val) {return false;} else {return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}}}
实验5.求两个数最大公约数
import java.util.Scanner;public class CommonDivisor {public static void main(String[] args) {go One = new go();Scanner scanner = new Scanner(System.in);//输入数据int n = scanner.nextInt();int m = scanner.nextInt();One.run1(n, m);One.run2(n,m);}}class go {public void run1(int a, int b) {//第一种方法if (a % b == 0) {System.out.println(b);} else {run1(b, a % b);}}public void run2(int a, int b) {//第二种方法if(a==b){System.out.println(a);}else if (a>b){run2(b,a-b);}else {run2(a,b-a);}}}
第一种方法：用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。
第二种方法：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
这里想知道原理可以参看最大公约数
第三章
实验1.求解查找假币问题
package Third;import java.util.Random;import java.util.Scanner;public class first {public static int a[];//存放硬币public static void main(String[] args) {//输入硬币数量Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();//随机产生假币并标注下标为mRandom random = new Random();int m=random.nextInt(n-1);//查看m是多少System.out.println(m);//给数组创建大小a=new int[n];//给数组赋值为1，1为真硬币，0为假硬币，因题目要求假硬币要轻一点for (int i = 0; i < n; i++) {a[i]=1;}//创造假币a[m]=0;//查看数组for (int i = 0; i < n; i++) {System.out.print(a[i]+" ");}System.out.println("");Balance(0,n);}//二分递归public static void Balance(int m,int n){int add1=0,add2=0;//定义两个变量来计算二分后两边的质量if ((n-m)%2==0){//判断是否为偶数个int j=0;for (int i = m; i < (n+m)/2; i++) {//从中间分开，计算两边的和add1=add1+a[i];add2=add2+a[n-j-1];j++;}if(add1>add2){//判断左边是否大于右边//偶数只剩两个时候，结束递归if(n-m-1==1){//判断你是否只剩两个数，如果是则输出小的那个是假币System.out.println(n-1);return;}Balance((m+n)/2,n);//右边进入的递归}else {//同理上面if(n-m-1==1){System.out.println(m);return;}Balance(m,(m+n)/2);}}else {//为奇数个时int j=0;for (int i = m; i < (n+m)/2; i++) {add1=add1+a[i];add2=add2+a[n-j-1];j++;}//奇数不一样，平均分两边，中间剩下一个数，然后判断两边是否相等，相等则输出中间的那个数字，之后同理//奇数剩下三个，结束递归if (add1>add2){if((n-m)/3==1){//如果只剩下三个的时候，左边大于右边直接输出右边，下面同理System.out.println(n-1);return;}Balance((m+n)/2+1,n);}else if (add1<add2){if(n-m==3){System.out.println(m);return;}Balance(m,(m+n)/2);}else if(add1==add2){System.out.println((m+n/2));return;}}}}
实验2.求解众数问题
package Third;import java.util.Arrays;import java.util.Random;import java.util.Scanner;public class second {public static void main(String[] args) {Random random=new Random();Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();int m=scanner.nextInt();int a[]=new int[n];int b[]=new int[m];int c[]=new int[m];for (int i = 0; i < n; i++) {a[i]=random.nextInt(m);System.out.print(a[i]+" ");b[a[i]]++;c[a[i]]++;}System.out.println();for (int i = 0; i < m; i++) {System.out.print(b[i]+" ");}System.out.println();Arrays.sort(c);for (int i = 0; i < m; i++) {if(b[i]==c[m-1]){System.out.println("众数："+i+" 重数："+c[m-1]);}}}}
实验3.求解逆序数的问题
package Third;import java.util.Random;import java.util.Scanner;public class Third {public static void main(String[] args) {Random random = new Random();Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int a[] = new int[n];for (int i = 0; i < n; i++) {a[i] = random.nextInt(100);System.out.print(a[i]+" ");}System.out.println(" ");int temp=0;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n - i; j++) {if(a[i]>a[j]){System.out.println("<"+a[i]+","+a[j]+">");temp++;}}}System.out.println(temp);}}
第四章
实验1.求解根号n向下取整
package Forth;public class first {public static void main(String[] args) {int count=0;int num=101;int i=1;boolean falg=true;while (falg){if (num==i*i){count=i;falg=false;}else if(num<i*i){count=i-1;falg=false;}else {i++;}}System.out.println(count);}}
实验2.求解钱币兑换问题
package Forth;public class Two {public static void main(String[] args) {TwoSolution temp=new TwoSolution();temp.DuiHuan(14);}}class TwoSolution{int one=1,two=2,five=5;public void DuiHuan(int num){for (int i = 0; i <= num/five; i++) {for (int j = 0; j <= num/two; j++) {for (int k = 0; k <= num; k++) {if (num==i*five+j*two+k){System.out.println("需要五分："+i+"个,需要二分："+j+"个,需要一分："+k);}}}}}}
实验3.求解环绕的区域的问题
主要采用了深度优先搜素算法。
package Forth;public class Third {public static void main(String[] args) {ThirdSolution a = new ThirdSolution();char[][] temp = {{'O', 'X', 'X', 'O', 'X'}, {'X', 'O', 'O', 'X', 'O'}, {'X', 'O', 'X', 'O', 'X'}, {'O', 'X', 'O', 'O', 'O'}, {'X', 'X', 'O', 'X', 'O'}};for (int i = 0; i < temp.length; i++) {for (int j = 0; j < temp[0].length; j++) {System.out.print(temp[i][j] + ",");}System.out.println();}System.out.println("转换后：");a.solve(temp);for (int i = 0; i < temp.length; i++) {for (int j = 0; j < temp[0].length; j++) {System.out.print(temp[i][j] + ",");}System.out.println();}}}class ThirdSolution {int x, y;public void solve(char[][] area) {x = area.length;if (x == 0) {return;}y = area[0].length;for (int i = 0; i < x; i++) {dfs(area, i, 0);dfs(area, i, y - 1);}for (int i = 1; i < y - 1; i++) {dfs(area, 0, i);dfs(area, x - 1, i);}for (int i = 0; i < x; i++) {for (int j = 0; j < y; j++) {if (area[i][j] == 'o') {area[i][j] = 'O';} else if (area[i][j] == 'O') {area[i][j] = 'X';}}}}public void dfs(char[][] area, int n, int m) {if (n < 0 || n >= x || m < 0 || m >= y || area[n][m] != 'O') {return;}area[n][m] = 'o';dfs(area, n + 1, m);dfs(area, n - 1, m);dfs(area, n, m + 1);dfs(area, n, m - 1);}}
