<>算法试验

<>试验一：统计求最大、最小元素的平均比较次数

import java.util.ArrayList; import java.util.Random; public class Experiment1 {
private ArrayList<Integer> list = new ArrayList(); private int length; private
int max; private int min; private int compareNum = 0; //寻找最大值与最小值并返回比较次数 private
int findMaxAndMin() { compareNum = 0; max = min = list.get(0); for (int i = 1; i
< list.size(); i++) { if (list.get(i) < min) { min = list.get(i); compareNum++;
continue; } else if (list.get(i) > max) { max = list.get(i); compareNum++;
continue; } else { compareNum += 2; } } return compareNum; }
//初始化改list，并执行寻找最大值最小值方法，并返回比较次数 public int initAListAndRunFind() { list = new
ArrayList<>(); Random random = new Random(); for (int i = 0; i < 10; i++) { int
temp= random.nextInt(20) + 1; list.add(temp); System.out.print(temp + " "); }
System.out.println(); length = list.size(); int number = findMaxAndMin(); System
.out.println("最大数为：" + max + "最小数为：" + min); System.out.println("比较次数为：" +
number); return number; } public static void main(String[] args) { Experiment1
experiment1= new Experiment1(); //执行十次并求出平均比较次数并输出 double avNumber = 0; for (int
i= 0; i < 10; i++) { avNumber += experiment1.initAListAndRunFind(); } System.
out.println("平均比较次数：" + avNumber / 10); } }

8 16 10 15 10 16 14 17 1 9

10 6 3 10 10 3 4 7 11 17

16 17 19 20 16 10 8 13 7 17

18 19 11 18 20 17 14 15 5 16

18 7 19 16 8 12 10 5 15 14

2 2 14 20 19 3 4 19 10 14

7 13 1 10 15 7 8 4 7 13

17 4 18 7 19 15 18 8 6 15

11 14 7 15 3 2 18 15 16 18

2 16 20 18 15 3 18 11 16 5

<>试验二：逆置单链表

out= "单链表： "; while (temp != null) { out = out + String.valueOf(temp.data) + " "
; temp = temp.next; } return out; } }

<>试验三：求解查找假币问题

public class Experiment { int[] coins; int coinNum; public Experiment() {
Random random = new Random(); coinNum = random.nextInt(17) + 4;
//假设硬币数量是4~20个；其中一个为假币； int fakeCoinIndex = random.nextInt(coinNum); System.out.
println("本次有硬币一共" + coinNum + "枚"); coins = new int[coinNum];
//真币的质量设置为3，假币的质量设置为2； Arrays.fill(coins, 3); coins[fakeCoinIndex] = 2; for (int
item: coins) { System.out.print(item + " "); } System.out.println(); } public
int balance(int begin, int end) { if (end - begin <= 3) { if (coins[begin] !=
coins[begin + 1]) { return coins[begin] < coins[begin + 1] ? begin : begin + 1;
} else { return end; } } else { int balanceNum = (end + 1 - begin) / 2; int
totalFront= 0; int totalRear = 0; for (int i = begin; i < begin + balanceNum; i
++) { totalFront += coins[i]; } for (int j = begin + balanceNum; j < begin +
balanceNum+ balanceNum; j++) { totalRear += coins[j]; } if (totalFront <
totalRear) { return balance(begin, begin + balanceNum - 1); } else if (
totalFront> totalRear) { return balance(begin + balanceNum, begin + balanceNum +
balanceNum- 1); } else { return end; } } } public static void main(String[]
args) { Experiment experiment = new Experiment(); int fateCoin = experiment.
balance(0, experiment.coinNum - 1); System.out.println(fateCoin); } }

<>试验四：

public class Experiment { public Integer compute(int n){ for(int i=1;i<n+2;i++)
{ if(i*i>n){ return i-1; } } return null; } public static void main(String[]
args) { Experiment experiment = new Experiment(); for (int i= 1;i<=20;i++){
System.out.println("根号"+i+"的下界为:"+experiment.compute(i)); } } }

<>试验五：

package unit5; import java.util.ArrayList; import java.util.Random; /** * 试验一：
* * 有12个硬币，分别用A到L表示，其中恰好有一个假币，假币的重量不同于真币，所有真币的重量 *

Experiment { ArrayList<Coin> coins = new ArrayList(); //设置硬币，并随机假币及重量 public
Experiment() { Random random = new Random(); int fakeCoin = random.nextInt(12);
for (int i = 0; i < 12; i++) { Coin coin = new Coin(); coin.name = String.
valueOf((char) (65 + i));// + String.valueOf(i); coins.add(i, coin); } int
newWeight= random.nextInt(2) == 0 ? -1 : 1; Coin c = coins.get(fakeCoin); c.
weight+= newWeight; coins.set(fakeCoin, c); for (Coin coin : coins) { System.out
.print(coin); } System.out.println(); } private Integer weight(int... index) {
int total = 0; for (int i : index) { total += coins.get(i).weight; } return
total; } /** * 用蛮力法及回溯法找出假币；把假币分成四份，能比较三次，只要第二次能确 *

() { //把硬币分成三份，先比较第一份和第二份； if (weight(0, 1, 2, 3) == weight(4, 5, 6, 7)) {
System.out.println("ABCD = EFGH"); if (weight(0, 1, 2, 8) > weight(4, 5, 9, 10))
{ System.out.println("ABCI > EFJK"); if (weight(0, 1, 8, 9) > weight(4, 5, 6, 7)
) { System.out.println("ABIJ > EFGH"); return coins.get(8); } else if (weight(0,
1, 8, 9) < weight(4, 5, 6, 7)) { System.out.println("ABIJ < EFGH"); return coins
.get(9); } else { System.out.println("ABIJ = EFGH"); return coins.get(10); } }
else if (weight(0, 1, 2, 8) < weight(4, 5, 9, 10)) { System.out.println("ABCI <
EFJK"); if (weight(8, 9) < weight(0, 1)) { System.out.println("IJ < AB"); return
coins.get(8); } else if (weight(8, 9) > weight(0, 1)) { System.out.println("IJ
> AB"); return coins.get(9); } else { System.out.println("IJ = AB"); return
coins.get(10); } } else { System.out.println("ABCI = EFJK"); return coins.get(11
); } } else if (weight(0, 1, 2, 3) > weight(4, 5, 6, 7)) { System.out.println(
"ABCD > EFGH"); if (weight(0, 1, 4) > weight(2, 3, 8)) { System.out.println(
"ABE > CDI"); if (weight(0) > weight(1)) { System.out.println("A > B"); return
coins.get(0); } else { System.out.println("A < B"); return coins.get(1); } }
else if (weight(0, 1, 4) < weight(2, 3, 8)) { System.out.println("ABE < CDI");
if (weight(2) < weight(3)) { System.out.println("C < D"); return coins.get(3); }
else { System.out.println("C > D"); return coins.get(2); } } else { System.out.
println("ABE = CDI"); if (weight(5) < weight(6)) { System.out.println("F < G");
return coins.get(5); } else if (weight(5) > weight(6)) { System.out.println("F
> G"); return coins.get(6); } else { System.out.println("F = G"); return coins.
get(7); } } } else { System.out.println("ABCD < EFGH"); if (weight(0, 1, 4) >
weight(2, 3, 8)) { System.out.println("ABE > CDI"); if (weight(2, 4) < weight(8,
9)) { System.out.println("CE < IJ"); return coins.get(2); } else if (weight(2, 4
) > weight(8, 9)) { System.out.println("CE > IJ"); return coins.get(4); } else {
System.out.println("CE = IJ"); return coins.get(3); } } else if (weight(0, 1, 4)
< weight(2, 3, 8)) { System.out.println("ABE < CDI"); if (weight(0) < weight(1))
{ System.out.println("A < B"); return coins.get(0); } else { System.out.println(
"A > B"); return coins.get(1); } } else { System.out.println("ABE = CDI"); if (
weight(5) < weight(6)) { System.out.println("F < G"); return coins.get(6); }
else if (weight(5) > weight(6)) { System.out.println("F > G"); return coins.get(
5); } else { System.out.println("F = G"); return coins.get(7); } } } } public
static void main(String[] args) { Experiment experiment = new Experiment();
System.out.println("假币为：" + experiment.FindFakeCoin()); } } class Coin { String
name; int weight = 2; @Override public String toString() { return '{' + name +
" , " + weight + '}'; } }

GitHub

Gitee