2021-05-30

<>算法试验

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

编写一个程序，随机产生10个1~20的整数，设计一个高效算法找其中的最大元素和最小
元素，并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数。
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
最大数为：17最小数为：1
比较次数为：15
10 6 3 10 10 3 4 7 11 17
最大数为：17最小数为：3
比较次数为：14
16 17 19 20 16 10 8 13 7 17
最大数为：20最小数为：7
比较次数为：12
18 19 11 18 20 17 14 15 5 16
最大数为：20最小数为：5
比较次数为：14
18 7 19 16 8 12 10 5 15 14
最大数为：19最小数为：5
比较次数为：15
2 2 14 20 19 3 4 19 10 14
最大数为：20最小数为：2
比较次数为：16
7 13 1 10 15 7 8 4 7 13
最大数为：15最小数为：1
比较次数为：15
17 4 18 7 19 15 18 8 6 15
最大数为：19最小数为：4
比较次数为：15
11 14 7 15 3 2 18 15 16 18
最大数为：18最小数为：2
比较次数为：12
2 16 20 18 15 3 18 11 16 5
最大数为：20最小数为：2
比较次数为：16
平均比较次数：14.4

<>试验二：逆置单链表

对于不带头结点的单链表L,设计一个递归算法逆置所有节点。编写完整的实验程序，并采用相应数据进行测试。
public class Experiment { Link link; int linkLength = 1; Link preLink=null;
Link nextLink = null; public Experiment() { link = new Link(); link.data = 1;
Link tempLink = link; for (int i = 0; i < 10; i++) { Link inLink = new Link();
inLink.data = i + 2; tempLink.next = inLink; tempLink = inLink; linkLength++; }
} public Link reverseLink(Link link){ if(link.next==null){ link.next = preLink;
return link; } nextLink = link.next; link.next = preLink; preLink = link; return
reverseLink(nextLink); } public static void main(String[] args) { Experiment
experiment= new Experiment(); System.out.println(new Link().print(experiment.
link)); System.out.println(experiment.linkLength); System.out.println(new Link()
.print(experiment.reverseLink(experiment.link))); } } class Link { Link next =
null; int data = 0; public String print(Link link) { Link temp = link; String
out= "单链表： "; while (temp != null) { out = out + String.valueOf(temp.data) + " "
; temp = temp.next; } return out; } }
试验结果：

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

编写一个程序查找假币问题。有n（n>3)个硬币，其中有一个假币，且假币较轻，采用天平称重的方式找到这个假币，并给出操作步骤。
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); } }
试验结果：

<>试验四：

编写一个程序计算根号n的向下取整（根号n的下界，如2.8的下界是2），其中n是任意正整数，要求除了赋值和比较运算，该算法只能用到基本四则运算，并输出1~20的求解结果。
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)); } } }
根号1的下界为:1
根号2的下界为:1
根号3的下界为:1
根号4的下界为:2
根号5的下界为:2
根号6的下界为:2
根号7的下界为:2
根号8的下界为:2
根号9的下界为:3
根号10的下界为:3
根号11的下界为:3
根号12的下界为:3
根号13的下界为:3
根号14的下界为:3
根号15的下界为:3
根号16的下界为:4
根号17的下界为:4
根号18的下界为:4
根号19的下界为:4
根号20的下界为:4

<>试验五：

有12个硬币，分别用A到L表示，其中恰好有一个假币，假币的重量不同于真币，所有真币的重量相同。现在采用天平称重的方式找到这个假币，某人已经给了一种3次称重的方案。编写一个程序找到这个假币。
package unit5; import java.util.ArrayList; import java.util.Random; /** * 试验一：
* * 有12个硬币，分别用A到L表示，其中恰好有一个假币，假币的重量不同于真币，所有真币的重量 *
相同。现在采用天平称重的方式找到这个假币，某人已经给了一种3次称重的方案。编写一个程序 * 找到这个假币。 * */ public class
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; } /** * 用蛮力法及回溯法找出假币；把假币分成四份，能比较三次，只要第二次能确 *
定某三个或三个以下的硬币中有假币，最后一次必定能找到假币 * * @return Coin (假币对象) */ public Coin FindFakeCoin
() { //把硬币分成三份，先比较第一份和第二份； 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 + '}'; } }
试验结果：

• « 上一篇：springboot项目配置项目名 端口号
• » 下一篇：html在状态栏中显示时间,html网页时间显示代码和倒计时代码大全