devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：Cpp五条 | 2024-04-10 17:10:17

赞

踩

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

一、实验目的

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));
        }
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

分析：选择排序算法，无论是最好情况、平均情况还是最差情况都是O(N^2)的时间复杂度，空间复杂度为O(1),是一种不稳定的算法。同时这也是蛮力法在排序问题中的应用。

选择排序算法，无论是最好情况、平均情况还是最差情况都是O(N^2)的时间复杂度，空间复杂度为O(1),是一种不稳定的算法。同时这也是蛮力法在排序问题中的应用。

img

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 ;
            }   
        }
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

分析：冒泡排序算法平均时间复杂度为O(N2)，最坏情况是排序是逆序的，复杂度是O(N2)，最好情况O(N)，空间复杂度为O(1)，是一种稳定的算法，同时也是蛮力法在排序问题中的应用。

冒泡排序算法平均时间复杂度为O(N2)，最坏情况是排序是逆序的，复杂度是O(N2)，最好情况O(N)，空间复杂度为O(1)，是一种稳定的算法，同时也是蛮力法在排序问题中的应用。

img

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 + " ");
    }
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

分析：插入排序算法的平均时间复杂度是O(n2),最好的情况是O(n),也就是序列正好全是已经排好的情况。最坏的情况是O(n2);空间复杂度O(1);该算法是一种稳定的算法。

插入排序算法的平均时间复杂度是O(n2),最好的情况是O(n),也就是序列正好全是已经排好的情况。最坏的情况是O(n2);空间复杂度O(1);该算法是一种稳定的算法。

img

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));
}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

快速排序算法的最差时间复杂度和冒泡排序是一样的都是O ( n 2 ) O(n^2)O(n2)，它的平均时间复杂度为O(nlog2n)。

img

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();
	        }
	    

	    }




  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77

分析：归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。

归并排序是一种稳定的排序，可用顺序存储结构。也易于在链表上实现。对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序

img

二．壶谜题

基本原理和思路：首先可以把每次三个水壶中水的量组成一个状态，比如初始状态为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;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112

分析：三壶谜题程序的时间复杂度：O(1)

img

三．交替放置的碟子

基本原理和思路：用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;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

分析：交替放置的碟子时间复杂度为O(n^2)

img

四．带锁的门

基本原理和思路：我们可以将这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;
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

带锁的门

分析：时间复杂度为O（n^2）

img

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号