算法设计与分析实验报告java实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)

2024-04-06 11:04
文章标签 java 算法 分析 实现 设计 放置 排序 谜题 实验报告 交替 三壶 带锁 碟子

本文主要是介绍算法设计与分析实验报告java实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、 实验目的

1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。

二、实验任务

1、排序算法
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现8种）并分析算法的时间复杂度。比较各种算法的优劣。
2、三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
3、交替放置的碟子
我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。
4、带锁的门：
在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？

三、实验设备及编程开发工具

实验设备：Win10电脑
开发工具：jdk1.8、IDEA

四、实验过程设计（算法思路及描述，代码设计）

1、排序算法

（1）冒泡排序

1）从第一个数开始，比较相邻的两个数，如果第一个数比第二个数大，则两数交换。
2）对后面的元素进行同样的操作，从开始到最后一个，这样进行一次排序后，数据的最后一位会是最大的。
3）重复上述步骤，直到在一次排序中无交换之后，排序完成。
代码：

public class Maopao {public static void main(String[] args) {int[] array1 = {1,10,5,8,6,4}; bubbleSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void bubbleSort(int[] array){int tmp;boolean flag = false;  //设置是否发生交换的标志for(int i = array.length-1;i >= 0;i--){for(int j=0;j<i;j++){          if(array[j]>array[j+1]){tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = true;   //发生了交换}}if(!flag)  break;   //没有发生交换，排序完成，退出循环}}
}

冒泡排序

最好的时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)。

结果：

img

（2）插入排序

1）第一次循环时，从第2个数开始处理。我们将第1个数作为已经排好序的数据：当第2个数 > 第1个数时，将第2个数放在第1个数后面一个位置；否则，将第2个数放在第1个数前面。此时，前两个数形成了一个有序的数据。
2）第二次循环时，我们处理第3个数。此时，前两个数形成了一个有序的数据：首先比较第3个数和第2个数，当第3个数 > 第2个数时，将第3个数放在第2个数后面一个位置并结束此次循环；否则，再和第1个数比较。如果第3个数 > 第1个数，则将第3个数插入第1个数和第2个数中间；否则，第3个数 < 第1个数，则将第3个数放在第1个数前面。此时，前三个数形成了一个有序的数据。
3）后续的数据同理处理，直至结束。
代码：

public class Charu {public static void main(String[] args) {int[] array1 = {1,10,35,8,6,44}; insertionSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void insertionSort(int[] array){int tmp;for(int i=0;i<array.length;i++){tmp = array[i];  //将当前位置的数给tmpint j = i;for(;j>0&&array[j-1]>tmp;j--){array[j] = array[j-1];}//将当前位置的数插入到合适的位置array[j] = tmp;}}
}

插入排序

最好的时间复杂度为O(n)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)。

结果：

img

（3）选择排序

首先在未排序的数列中找到最小元素，然后将其存放到数列的起始位置。接着，再从剩余未排序的元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
代码：

public class Xuanze {public static void main(String[] args) {int[] array1 = {1,10,35,8,6,44}; selectSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void selectSort(int[] array){for(int i = 0;i<array.length;i++){int min = array[i];int minindex = i;for(int j = i;j<array.length;j++){if(array[j]<min){  //选择当前最小的数min = array[j];minindex = j;}}if(i != minindex){ //若i不是当前元素最小的，则和找到的那个元素交换array[minindex] = array[i];array[i] = min;}}}
}

选择排序

最好的时间复杂度为O(n2)，最坏时间复杂度为O(n2)，平均时间复杂度为O(n^2)。

结果：

img

（4）希尔排序

1）比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，算法先将要排序的一组数按某个增量d分成若干组。
2）对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。
3）当增量减到1时，整个要排序的数被分成一组，排序完成。
4）一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
代码：

public class Xier{public static void main(String[] args) {int[] array1 = {22,10,55,87,66,44}; ShellSort(array1);for (int i = 0; i < array1.length; i++) {System.out.print(array1[i]+" ");}}public static int[] ShellSort(int[] array) {int len = array.length;int temp, gap = len / 2;while (gap > 0) {for (int i = gap; i < len; i++) {temp = array[i];int preIndex = i - gap;while (preIndex >= 0 && array[preIndex] > temp) {array[preIndex + gap] = array[preIndex];preIndex -= gap;}array[preIndex + gap] = temp;}gap /= 2;}return array;}
}

希尔排序

最好的时间复杂度为O(nlog2 n)，最坏时间复杂度为O(nlog2 n)，平均时间复杂度为O(nlog2n)

结果：

img

（5）快速排序

1）从数列中挑出一个元素，称为"基准"，重新排序数列。
2）所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。从而一趟排序过程，就可以锁定基准元素的最终位置。
3）对左右两个分块重复以上步骤直到所有元素都是有序的。
代码：

public class Kuaisu {public static void main(String[] args) {int[] array1 = {22,10,55,87,66,44}; quickSort(array1);for(int i=0;i<array1.length;i++){System.out.print(array1[i]+" ");}}public static void quickSort(int[] arr) {qsort(arr, 0, arr.length - 1);}private static void qsort(int[] arr, int low, int high) {if (low >= high)  return;int pivot = partition(arr, low, high);        //将数组分为两部分qsort(arr, low, pivot - 1);                   //递归排序左子数组qsort(arr, pivot + 1, high);                  //递归排序右子数组}private static int partition(int[] arr, int low, int high) {int pivot = arr[low];     //基准while (low < high) {while (low < high && arr[high] >= pivot) --high;arr[low] = arr[high];             //交换比基准大的记录到左端while (low < high && arr[low] <= pivot) ++low;arr[high] = arr[low];           //交换比基准小的记录到右端}//扫描完成，基准到位arr[low] = pivot;//返回的是基准的位置return low;}
}

（6）基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
代码：

import java.util.ArrayList;public class Paixu {public static void main(String[] args) {int[] array1 = {25,8,55,87,66,44}; RadixSort(array1);for (int i = 0; i < array1.length; i++) {System.out.print(array1[i]+" ");}}public static int[] RadixSort(int[] array) {if (array == null || array.length < 2)return array;// 1.先算出最大数的位数；int max = array[0];for (int i = 1; i < array.length; i++) {max = Math.max(max, array[i]);}int maxDigit = 0;while (max != 0) {max /= 10;maxDigit++;}int mod = 10, div = 1;ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();for (int i = 0; i < 10; i++)bucketList.add(new ArrayList<Integer>());for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {for (int j = 0; j < array.length; j++) {int num = (array[j] % mod) / div;bucketList.get(num).add(array[j]);}int index = 0;for (int j = 0; j < bucketList.size(); j++) {for (int k = 0; k < bucketList.get(j).size(); k++)array[index++] = bucketList.get(j).get(k);bucketList.get(j).clear();}}return array;}
}

基数排序

最好的时间复杂度为O(nk)，最坏时间复杂度为O(nk)，平均时间复杂度为O(n*k)

结果：

img

2、三壶谜题

1）本题使用广度优先遍历来进行计算。刚开始我们可以将三个瓶子的状态都标示为一个数。例如800

2）然后开始拓展这个数的所有可能的状态，第一步这个数可以变为（括号里的数是上一步的数字）：3 5 0（8 0 0） 、 5 0 3（8 0 0）。

3）然后继续拓展第二步所有可能的状态，并且不得和之前的状态出现重复，即进行剪枝：0 5 3（3 5 0）、3 2 3（3 5 0）、5 3 0（5 0 3）

4）继续进行同样操作，一直到第六步，出现1 4 3（1 5 2），这时候就应该停止了。因为出现了第一个数字4，满足了条件。所以最终的路径就是：143 <-- 152 <-- 602 <-- 620 <-- 323 <-- 350 <-- 800

代码:

import java.util.*;
public class Sanhu {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入三个值表示容器的初始状态,三个瓶子的容积目前是8，5，3：");int x1 = sc.nextInt();int x2 = sc.nextInt();int x3 = sc.nextInt();String string = x1+""+x2+""+x3;System.out.println(string);ContainerPot containerPot = new ContainerPot(8, 0, 0);List<String> list = new ArrayList<String>(); //保存状态list.add(string); //将第一个状态存入到状态数组中containerPot.init();//初始化这些瓶子可以装多少水String result = "";//保存最终带有4的结果int n = 0;//状态计数do {//遍历倒水for (int i = 0; i < 3 && containerPot.flag; i++) {for (int j = 0; j < 3 && containerPot.flag; j++) {if (i != j) { //不能让壶相同if (containerPot.canPour(i, j)) { //是否可以倒水String str = containerPot.getString();//保存初始状态//倒入水containerPot.pour(i, j);String strResult = containerPot.getString();if (!list.contains(strResult)) {list.add(strResult);containerPot.addList(str, strResult);}//如果出现容量为4的壶就停止if (containerPot.pot[0] == 4 || containerPot.pot[1] == 4 || containerPot.pot[2] == 4) {result = result + containerPot.pot[0] + containerPot.pot[1] + containerPot.pot[2];containerPot.flag = false;//已经找到break;}//初始化倒水到上一步containerPot.intPot(str);}}}}n++;containerPot.intPot(list.get(n));} while (containerPot.flag);System.out.println(list);System.out.println(containerPot.listMap);String key = result;System.out.print(key + "<--");do {for (Map.Entry<String, List<String>> entry : containerPot.listMap.entrySet()) {for (int i = 0; i < entry.getValue().size(); i++) {if (entry.getValue().get(i).equals(key)) {System.out.print(entry.getKey() + "<--");key = entry.getKey();break;}}}} while (containerPot.listMap.containsKey(key) && !key.equals(string));System.out.println();}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class ContainerPot {int[] pot = new int[3];//    List<String> list;//存放已经出现的结果Map<String, List<String>> listMap = new HashMap<>();int[] maxP = new int[3];boolean flag = true;public ContainerPot(int a, int b, int c) {pot[0] = a;pot[1] = b;pot[2] = c;}public void init() {maxP[0] = 8;maxP[1] = 5;maxP[2] = 3;}//将key值作为它的上一步public void addList(String key, String str) {if (listMap.isEmpty() || !listMap.containsKey(key)) {List<String> temp = new ArrayList<String>();temp.add(str);listMap.put(key, temp);} else {
//            System.out.println(listMap.containsKey(key));
//            System.out.println(listMap.get(key));listMap.get(key).add(str);}}//判读是否已经有这个key值在里面存放了public boolean isAdd(String str) {return listMap.containsKey(str);}//判读是否可以从from壶倒水到to壶public boolean canPour(int from, int to) {//如果没用水就不能倒了if (pot[from] == 0) {return false;}//如果里面已经有水了 就不能倒了if (pot[to] == maxP[to]) {return false;} else {return true;}}//倒水的过程public void pour(int from, int to) {//做一个判读看看是否能剩水if (pot[from] + pot[to] > maxP[to]) {pot[from] = pot[from] - (maxP[to] - pot[to]);pot[to] = maxP[to];} else {pot[to] = pot[to] + pot[from];pot[from] = 0;}}public String getString() {String str = "";for (int i = 0; i < pot.length; i++) {str = str + pot[i];}return str;}public void intPot(String str) {for (int i = 0; i < str.length(); i++) {pot[i] = Integer.parseInt(String.valueOf(str.charAt(i)));}}public void printDD() {for (List<String> value : listMap.values()) {System.out.println(value.toString());}}
}

三壶谜题
时间复杂度为O（n^2）
结果：

img

3、交替放置的碟子

将所有碟子存放在一个数组里，设白碟子为1，黑碟子为0，使其经过若干次冒泡排序的交换，将所有的黑碟子都放在右边，白碟子都放在左边。

代码：

import java.util.Scanner;
public class Jiaoti{public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入碟子的数量2n，其中黑白碟子各n个：");int num=sc.nextInt();//从控制台接受碟子数量int sum[]=new int[num];for(int i=0;i<=(sum.length-1)/2;i++) {sum[2*i]=0;sum[2*i+1]=1;}System.out.println("碟子的初始排序为：");for(int i=0;i<sum.length;i++) {System.out.print(sum[i]+" ");if(sum[i]==1) {System.out.print("白"+" ");}else {System.out.print("黑"+" ");}}System.out.println();//换行/** 进行排序 冒泡排序*/int k = 0;for(int i=0;i<sum.length-1;i++) {for(int j=0;j<sum.length-1-i;j++) {if(sum[j+1]>sum[j]) {int t=sum[j];sum[j]=sum[j+1];sum[j+1]=t;k++;}}}System.out.println("交换的次数为："+ k);System.out.println("排序后的顺序为：");for(int i=0;i<sum.length;i++) {System.out.print(sum[i]+" ");if(sum[i]==1) {System.out.print("白"+" ");}else {System.out.print("黑"+" ");}}}
}

交替放置的碟子

时间复杂度为O（n）

结果：

img

4、带锁的门

1）这道题需要统计从1到n每个数的因子个数（包括1和自身），每个数的因子个数决定了它代表的门被改变锁状态的次数，若i有奇数个因子，则第i号门最终是开着的，若i有偶数个因子，则第i号门最终仍然是关着的。

2）大多数情况下，每个数的因子是成对出现的，例如数15的因子有1和15，以及3和5，数12的因子有1和12，2和6，3和4，所以有偶数个因子。只有当这个数是完全平方数时，例如1,4,9,16,25,36等等，它的因子除成对出现的以外，还有它的整数平方根作为单独的因子，这些完全平方数的因子数为奇数。所以最终打开的门都会是完全平方数的门。

代码：

import java.util.ArrayList;
import java.util.Scanner;public class Daisuo {public static void main(String[] args){System.out.println("请输入带锁的门的个数：");int n = new Scanner(System.in).nextInt();	int sum = 0;ArrayList<Integer> open = new ArrayList<>();for(int i=1;i*i<=n;i++){open.add(i*i);sum++;}ArrayList<Integer> close=new ArrayList<>();for(int i=1;i<=n;i++){if(!open.contains(i)) //用于判断是否包含某个元素close.add(i);}System.out.println("打开的门的编号为：");for(Integer integer:open){System.out.print(integer +" ");}System.out.println("");System.out.println("关着的门的编号为：");for(Integer integer:close){System.out.print(integer +" ");}System.out.println("");System.out.println("打开的门的个数为："+ sum);}
}

带锁的门

时间复杂度为O（n）

结果：

img

这篇关于算法设计与分析实验报告java实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/879747。

相关文章

Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
Java中String字符串使用避坑指南

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下：1. 字符串的不可变性：每次修改都创建新对象2. 使用 == 比较字符串，陷阱满
阅读更多...
Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
IDEA编译报错“java: 常量字符串过长”的原因及解决方法

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①：StringBui
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
Java中ArrayList和LinkedList有什么区别举例详解

Java中ArrayList和LinkedList有什么区别举例详解

《Java中ArrayList和LinkedList有什么区别举例详解》：本文主要介绍Java中ArrayList和LinkedList区别的相关资料,包括数据结构特性、核心操作性能、内存与GC影... 目录一、底层数据结构二、核心操作性能对比三、内存与 GC 影响四、扩容机制五、线程安全与并发方案六、工程
阅读更多...
JavaScript中的reduce方法执行过程、使用场景及进阶用法

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》：本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
Java调用DeepSeek API的最佳实践及详细代码示例

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》：本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2