算法设计与分析实验报告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。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2