算法设计与分析实验报告c++&java&python实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)
实验任务1、排序算法目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现5种）并分析算法的时间复杂度。比较各种算法的优劣。2、三壶谜题：有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。3、交替放置的碟子我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…现在要
一、实验目的
1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
1、排序算法
目前已知有几十种排序算法，请查找资料，并尽可能多地实现多种排序算法（至少实现5种）并分析算法的时间复杂度。比较各种算法的优劣。
2、三壶谜题：
有一个充满水的8品脱的水壶和两个空水壶（容积分别是5品脱和3品脱）。通过将水壶完全倒满水和将水壶的水完全倒空这两种方式，在其中的一个水壶中得到4品脱的水。
3、交替放置的碟子
我们有数量为2n的一排碟子，n黑n白交替放置：黑，白，黑，白…
现在要把黑碟子都放在右边，白碟子都放在左边，但只允许通过互换相邻碟子的位置来实现。为该谜题写个算法，并确定该算法需要执行的换位次数。
4、带锁的门：
在走廊上有n个带锁的门，从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次，每次都从1号门开始。在第i次经过时（i = 1,2，…, n)我们改变i的整数倍号锁的状态；如果门是关的，就打开它；如果门是打开的，就关上它。在最后一次经过后，哪些门是打开的，哪些门是关上的？有多少打开的门？
三、实验设备及编程开发工具
实验设备：惠普Win10电脑
开发工具：Java和python环境下，eclipse和pycharm编程工具
四、实验过程设计（算法思路及描述，代码设计）
一．排序算法
1.选择排序算法
基本原理和思路：从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。
代码实现如下：
public class SelectSort {
public static void main(String[] args) {
//定义一个数组
int [] arr = {49,38,65,97,76,13,27,49};
selectSort(arr,arr.length);
}
//定义一个static静态方法
public static void selectSort(int [] arr,int n){
for (int i = 0; i < n - 1; i++) {
int index = i;
int j;
// 找出最小值得元素下标
for (j = i + 1; j < n; j++) {
//找到最小的数
if (arr[j] < arr[index]) {
//将最小数的索引保存
index = j;
}
}
//交换
int tmp = arr[index];
arr[index] = arr[i];
arr[i] = tmp;
System.out.println(Arrays.toString(arr));
}
}
}
分析：选择排序算法，无论是最好情况、平均情况还是最差情况都是O(N^2)的时间复杂度，空间复杂度为O(1),是一种不稳定的算法。同时这也是蛮力法在排序问题中的应用。
选择排序算法，无论是最好情况、平均情况还是最差情况都是O(N^2)的时间复杂度，空间复杂度为O(1),是一种不稳定的算法。同时这也是蛮力法在排序问题中的应用。
2.冒泡排序算法
基本原理和思路：首先第一个元素和第二个元素比较，如果第一个大，则二者交换，否则不交换；然后第二个元素和第三个元素比较，如果第二个大，则二者交换，否则不交换……一直执行下去，最终最大的那个元素被交换到最后，一趟冒泡排序完成。
代码实现如下：
public class BubbleSort {
public static void main(String[] args) {
int [] arr = {49、38、65、97、76、13、27、49};
bubbleSort(arr,arr.length);
}
public static void bubbleSort(int[] arr, int n) {
for (int i=1,len=arr.length;i<len;i++){
//标识符，判断这趟排序是否发生位置变化，没有发生，则排序已经完成，无须执行剩下循环
Boolean flag=true;
for (int j=1;j<len;j++){
if (arr[j-1] > arr[j]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
flag=false;
}
}
//排序过程打印记录
System.out.println(Arrays.toString(arr));
if (flag){
return ;
}
}
}
}
分析：冒泡排序算法平均时间复杂度为O(N2)，最坏情况是排序是逆序的，复杂度是O(N2)，最好情况O(N)，空间复杂度为O(1)，是一种稳定的算法，同时也是蛮力法在排序问题中的应用。
冒泡排序算法平均时间复杂度为O(N2)，最坏情况是排序是逆序的，复杂度是O(N2)，最好情况O(N)，空间复杂度为O(1)，是一种稳定的算法，同时也是蛮力法在排序问题中的应用。
3.插入排序算法
基本原理和思路：利用插入法对无序数组排序时，我们其实是将数组R划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。
代码实现如下：
import java.util.Arrays;
public class InsertSort {
public static void insertionSort(int[] a) {
int tmp;
//外部for循环
for (int i = 1; i < a.length; i++) {
for (int j = i; j > 0; j--) {
//开始交换
if (a[j] < a[j - 1]) {
tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
//打印输出
System.out.println(Arrays.toString(a));
}
}
}
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
insertionSort(a);
for (int i : a)
System.out.print(i + " ");
}
}
分析：插入排序算法的平均时间复杂度是O(n2),最好的情况是O(n),也就是序列正好全是已经排好的情况。最坏的情况是O(n2);空间复杂度O(1);该算法是一种稳定的算法。
插入排序算法的平均时间复杂度是O(n2),最好的情况是O(n),也就是序列正好全是已经排好的情况。最坏的情况是O(n2);空间复杂度O(1);该算法是一种稳定的算法。
4.快速排序算法
基本原理和思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
代码实现如下：
import java.util.Arrays;
public class QuickSort {
private static int partition(int[] arr, int low, int high) {
//指定左指针i和右指针j
int i = low;
int j= high;
//将第一个数作为基准值。挖坑
int x = arr[low];
//使用循环实现分区操作
while(i<j){//5 8
//1.从右向左移动j，找到第一个小于基准值的值 arr[j]
while(arr[j]>=x && i<j){
j--;
}
//2.将右侧找到小于基准数的值加入到左边的（坑）位置， 左指针想中间移动一个位置i++
if(i<j){
arr[i] = arr[j];
i++;
}
//3.从左向右移动i，找到第一个大于等于基准值的值 arr[i]
while(arr[i]<x && i<j){
i++;
}
//4.将左侧找到的打印等于基准值的值加入到右边的坑中，右指针向中间移动一个位置 j--
if(i<j){
arr[j] = arr[i];
j--;
}
}
//使用基准值填坑，这就是基准值的最终位置
arr[i] = x;//arr[j] = y;
//返回基准值的位置索引
return i; //return j;
}
private static void quickSort(int[] arr, int low, int high) {//???递归何时结束
if(low < high){
//分区操作，将一个数组分成两个分区，返回分区界限索引
int index = partition(arr,low,high);
//对左分区进行快排
quickSort(arr,low,index-1);
//对右分区进行快排
quickSort(arr,index+1,high);
}
}
public static void quickSort(int[] arr) {
int low = 0;
int high = arr.length-1;
quickSort(arr,low,high);
}
public static void main(String[] args) {
//给出无序数组
int arr[] = {72,6,57,88,60,85};
//排序前
System.out.println(Arrays.toString(arr));
//快速排序
quickSort(arr);
//排序后
System.out.println(Arrays.toString(arr));
}
}
快速排序算法的最差时间复杂度和冒泡排序是一样的都是O ( n 2 ) O(n^2)O(n2)，它的平均时间复杂度为O(nlog2n)。
5.归并排序算法
基本原理和思路：①把 n 个记录看成 n 个长度为1的有序子表；
②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；
③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。
代码实现如下：
public class MergeSort02 {
static int number=0;
public static void main(String[] args) {
int[] a = {26, 5, 98, 108, 28, 99, 100, 56, 34, 1 };
printArray("排序前：",a);
MergeSort(a);
printArray("排序后：",a);
}
private static void printArray(String pre,int[] a) {
System.out.print(pre+"\n");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+"\t");
System.out.println();
}
private static void MergeSort(int[] a) {
// TODO Auto-generated method stub
System.out.println("开始排序");
Sort(a, 0, a.length - 1);
}
private static void Sort(int[] a, int left, int right) {
if(left>=right)
return;
int mid = (left + right) / 2;
//二路归并排序里面有两个Sort，多路归并排序里面写多个Sort就可以了
Sort(a, left, mid);
Sort(a, mid + 1, right);
merge(a, left, mid, right);
}
private static void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[a.length];
int r1 = mid + 1;
int tIndex = left;
int cIndex=left;
// 逐个归并
while(left <=mid && r1 <= right) {
if (a[left] <= a[r1])
tmp[tIndex++] = a[left++];
else
tmp[tIndex++] = a[r1++];
}
// 将左边剩余的归并
while (left <=mid) {
tmp[tIndex++] = a[left++];
}
// 将右边剩余的归并
while ( r1 <= right ) {
tmp[tIndex++] = a[r1++];
}
System.out.println("第"+(++number)+"趟排序:\t");
// TODO Auto-generated method stub
//从临时数组拷贝到原数组
while(cIndex<=right){
a[cIndex]=tmp[cIndex];
//输出中间归并排序结果
System.out.print(a[cIndex]+"\t");
cIndex++;
}
System.out.println();
}
}
分析：归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序
二．壶谜题
基本原理和思路：首先可以把每次三个水壶中水的量组成一个状态，比如初始状态为008，对应第一个水壶0品脱水，第二个水壶0品脱水，第三个水壶8品脱水。对题目的状态空间图进行广度优先遍历。当表示状态的数字中出现4时，即求出答案。
1、为了打印出倒水的过程，需要声明一个前置状态保存当前状态由哪个状态转换而来，然后就可以回溯到初始状态，打印出倒水过程。相当于树中的父结点。
2、可以声明一个map表，保存已有的状态，对已有的状态，就不再向下继续遍历，这样可以节省求解时间。
3、因为是广度优先遍历，所以第一次解得的答案所需的倒水的次数最少，解为最优解。
代码实现如下：
#include <iostream>
#include <vector>
#include <map>
#define MaxFirst 3
#define MaxSecond 5
#define MaxThird 8
using namespace std;
class State
{
public:
int second;
int num[3];
State* preState;
static map<int,int> mapping;
public:
State(int first,int second,int third)
{
num[0]=first;
num[1]=second;
num[2]=third;
}
void init()
{
mapping[0]=MaxFirst;
mapping[1]=MaxSecond;
mapping[2]=MaxThird;
}
bool canPour(int from,int to)//判断是否可以从from水壶中倒水到to水壶中
{
if(num[from]==0)
{
return false;
}
if(num[to]==mapping[to])
{
return false;
}
else
{
return true;
}
}
void pour(int from,int to)//倒水过程
{
if(num[from]+num[to]>mapping[to])
{
num[from]=num[from]-(mapping[to]-num[to]);
num[to]=mapping[to];
}
else
{
num[to]=num[to]+num[from];
num[from]=0;
}
}
};
map<int,int> State::mapping;
int main()
{
map<int,int> states;
State *start=new State(0,0,8);
start->init();
State *state=start;
State *endState=new State(8,8,8);//只有获得解endState才会改变，赋值全为8为了方便判断是否获得最终解
vector<State> action;//保存所有状态对象
action.push_back(*start);//把初始状态先加入队列中
int n=0;
do{
for(int i=0;i<3;i++)//双层循环为从i水壶中倒水入j水壶中
{
for(int j=0;j<3;j++)
{
if(i!=j)
{
if(state->canPour(i,j))
{
state->pour(i,j);
if(states[state->num[0]*100+state->num[1]*10+state->num[2]]==0)//如果该状态不在hash表中，即为第一次出现该状态
{
states[state->num[0]*100+state->num[1]*10+state->num[2]]++;
(state->preState)=new State(action[n]);
action.push_back(*state);
if(state->num[0]==4||state->num[1]==4||state->num[2]==4)//获得解
{
endState=state;
i=4;
break;
}
}
}
}
*state=action[n];
}
}
n++;
}while(endState->num[0]==8&&endState->num[1]==8&& n<action.size());
cout<<endState->num[0]<<" "<<endState->num[1]<<" "<<endState->num[2]<<endl;
state=endState;
do
{
state=state->preState;
cout<<state->num[0]<<" "<<state->num[1]<<" "<<state->num[2]<<endl;
}while(state->num[2]!=8);
return 0;
}
分析：三壶谜题程序的时间复杂度：O(1)
三．交替放置的碟子
基本原理和思路：用1表示黑碟子，0表示白碟子，那么目前的顺序是：1010…1010。结果要求1都放在右边，0都放在左边。这个题目看起来与冒泡排序相似。假设目前有6个碟子：101010。使用冒泡排序，第一次迭代，碟子序列变为：010101，交换3次。在进行第二次迭代之前，观察一下。现在，不仅第一个碟子就位，最后一个也是了，因此第二次迭代只需要对第2到第5个进行排序，巧合的是，碟子[2->5]仍然是10交替出现，不过比上一次少了两个，可以得到结论：对于2n个碟子，可以使用n次迭代完成，交换的次数分别是：n+(n-1)+…+2+1，即n(n+1)/2。
代码实现如下:
#include "stdafx.h"
#include
#include
#include
#include
using namespace std;
const int maxn = 20;
int plate[maxn] = { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
int main()
{
int n = maxn/2;
for (int i = 0; i
for (int j = 0; j < maxn - i - 1; j++){
if (plate[j] > plate[j + 1]){ //如果是黑色在白色左边，交换位置
int temp = plate[j];
plate[j] = plate[j + 1];
plate[j + 1] = temp;
}
}
}
for (int i = 0; i < maxn; i++)
cout << plate[i] << endl;
system("pause");
return 0;
}
分析：交替放置的碟子时间复杂度为O(n^2)
四．带锁的门
基本原理和思路：我们可以将这n个门看成数组A[n]，元素初始值为0，表示门为关，值为1表示门为开，每次遍历一次就改变它值（0->0/1->0），根据规则可以用一个两次for循环来改变数组的值（为了不用再次遍历我们可以用count计算每次后的门开数量）
代码实现如下：
#include <stdio.h>
#include <stdlib.h>
#define N 100000
int Lock(void)
{
int a[N+1];
int i, j;
int s;
for(i = 1; i <= N; i++)
a[i] = 0;
for(i = 1; i <= N; i++)
{
j = i;
while(j <= N)
{
if(a[j])
{
a[j] = 0;
}
else
{
a[j] = 1;
}
j +=i;
}
}
s = 0;
for(i = 1; i <= N; i++)
{
if(a[i])
{
//cout << "第 " << i << " 扇门是开着的." << endl;
}
else
{
s++;
//else cout << "第 " << i << " 扇门是关着的." << endl;
}
}
return s;
}
int main()
{
int i;
i=Lock();
printf("%d扇门中, %d扇门是关着的\n",N,i);
return 0;
}
带锁的门
分析：时间复杂度为O（n^2）
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
18
0- 0
已为社区贡献4条内容
所有评论(0)