算法设计与分析实验报告c++java实现(ACM面试题、字符串匹配算法、循环赛日程安排问题、分治法求解最大连续子序列和、动态规划法求解最大连续子序列和)

一、 实验目的

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

二、实验任务

1、【ACM、面试题】求解按“最多排序”到“最小排序”的顺序排列问题。一个序列中的“未排序”的度量是相对于彼此顺序不一致的条目对的数量，例如，在字母序列“DAABEC”中，该度量为5，因为D大于右边是4个字母，E大于其右边的1个字母。该度量称为该序列的逆序数。序列“AACEDGG”只有一个逆序对（E和D），它几乎被排序好了，而序列“ZWQM”有6个逆序对，它是未排序的，恰好是反序。
你需要对若干个DNA序列（仅包含4个字母A、C、G和T的字符串）分类，注意是分类而不是按字母顺序排序，而是按照“最多排序”到“最小排序”的顺序排列，所有DNA序列的长度都相同。
输入：第一行包含两个整数：n（0<n≤50）表示字符串长度，m（0<m≤100）表示字符串个数。后面是m行，每行包含一个长度为n的字符串。
输出：按“最多排序”到“最小排序”的顺序输出所有字符串。若两个字符串的逆序对个数相同，按原始顺序输出它们。
2、字符串匹配算法（BF,KMP）
给定一个文本，在该文本中查找并定位任意给定字符串。
3、循环赛日程安排问题
设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其他n-1个选手各赛一次；
（2）每个选手一天只能赛一次。
4、采用分治法求解最大连续子序列和问题
给定一个有n（n≥1）个整数的序列，要求求出其中最大连续子序列的和。
例如：
序列（-2，11，-4，13，-5，-2）的最大子序列和为20
序列（-6，2，4，-7，5，3，2，-1，6，-9，10，-2）的最大子序列和为16。
规定一个序列最大连续子序列和至少是0（长度为0的子序列），如果小于0，其结果为0。
5、 采用动态规划法求解最大连续子序列和问题

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

实验设备：Win10 电脑
开发工具：Visual Studio 2019
编程语言：C/JAVA

四、实验过程设计（算法设计过程）

（一）、DNA序列分类

1、算法分析：
输入字符的时候可以利用string对象来处理。在计算逆序对时要按照逆序对从小到大的顺序输出，这里有个小技巧，多定义一个数组来存放原始顺序的逆序对数，然后对求取到的逆序对进行从小到大的排序，最后将备用存放逆序对的数组数据跟排好序的进行比较，然后对应原始下标输出对应的字符串即可。

2、代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, m;
string a[55];
int t[110]={0},r[110];
 
int s(string  a)
{
	int sum = 0;
	for(int i = 0; i < a.length()-1; i++)
	  for(int j = i+1; j < a.length(); ++j)
	    if(a[i] > a[j])
	     sum++;
	return sum;
}
 
int main()
{
	
	int x = 0;
	
	cout << "请输入字符串长度和字符串个数：\n"; 
	scanf("%d%d",&n,&m);
	
	cout << "请输入所有的字符串：\n";
	for (int i = 0; i < m; ++i)
	{
		cin >> a[i];
		  
	}
	
	for(int i = 0; i < m; i++)
	{ 
	   t[i] = s(a[i]);
	   r[i] = t[i];
	}
	sort(t,t+m);
	
	cout << "=================\n";
	cout << "排序后的字符串顺序为：\n";
	for(int i = 0; i < m; i++)
	  for(int j = 0; j < m; j ++)
	  {
	  	if(t[i] == r[j])
	  	   cout << a[j] << endl;
	  }
	return 0;
	
}

DNA序列分类
1、实验结果

img

2、算法复杂度分析
时间复杂度：O(n^2)

二）、字符串匹配

1、算法分析：
首先，原字符串和子串左端对齐，比较第一个字符，发现不相等，子串向后移动，直到子串的第一个字符能和原字符串匹配。 当A匹配上之后，接着匹配后续的字符，直至原字符串和子串出现不相等的字符为止。参见kmp算法。

2、代码实现：

#include "vector"
#include "string"
#include <iostream>
#include "algorithm"
 
using namespace std;
 
//计算模式P的部分匹配值，保存在next数组中  
void MakeNext(const string &P, vector<int> &next)
{
	int q,k;//k记录所有前缀的对称值  
	int m = P.size();//模式字符串的长度  
	next[0] = 0;//首字符的对称值肯定为0  
	for (q = 1, k = 0; q < m; ++q)//计算每一个位置的对称值  
	{
		//k总是用来记录上一个前缀的最大对称值  
		while (k > 0 && P[q] != P[k])
			k = next[k - 1];//k将循环递减，值得注意的是next[k]<k总是成立  
		if (P[q] == P[k])
			k++;//增加k的唯一方法  
		next[q] = k;//获取最终值  
	}
}
 
 
void KmpMatch(const string &T, const string &P, vector<int> &next)
{
	int n, m;
	n = T.size();
	m = P.size();
	MakeNext(P, next);
	for (int i = 0, q = 0; i < n; ++i)
	{
		while (q > 0 && P[q] != T[i])
			q = next[q - 1];
		if (P[q] == T[i])
			q++;
		if (q == m)
		{
			cout << "模式文本的偏移为：" << (i - m + 1) << endl;
			q = next[q - 1];//寻找下一个匹配
		}
	}
}
 
int main()
{
	system("color 0A");
	vector<int> next(20,0);//保存待搜索字符串的部分匹配表（所有前缀函数的对称值）
	string T = "abcdefgikjhgdjahfsdhgfusgr";//文本
	string P = "sdhg";//待搜索字符串
	cout <<"文本字符串："<< T << endl;
	cout <<"模式字符串："<< P << endl;
	KmpMatch(T, P, next);
	return 0;
}

字符串匹配
1、实验结果

img

2、算法复杂度分析
时间复杂度：O(m+n)

（三）、循环赛日程安排

1、算法分析：

按照要求，可以将比赛表设计成一个n行n-1列的二维表，其中第i行第j列的元素表示和第i个选手在第j天比赛的选手号。采用分治策略，可将所有参加比赛的选手分成两部分， n = 2 k n=2^k n=2k个选手的比赛日程表就可以通过 n = 2 （ k − 1 ） n=2^{（k-1）} n=2（k−1）个选手的的比赛日程表来决定。递归的执行这样的分割，直到只剩下两个选手，比赛日程表的就可以通过这样的分治策略逐步构建。

假设有 2 1 2^1 21个选手，其安排如下：

12
21

假设有 2 2 2^2 22个选手，其安排如下：

1234
2143
3412
4321

假设有 2 3 2^3 23个选手，其安排如下：

12345678
21446587
34127856
43218765
56781234
65872143
78563412
87654321

根据以上的规律，求解过程可以看作四个部分：

  1. 求左上角子表：左上角子表是前 2 ( k − 1 ) 2^{(k-1)} 2(k−1)个选手的比赛前半程的比赛日程。

  2. 求左下角子表：左下角子表是剩余的 2 ( k − 1 ) 2^{(k-1)} 2(k−1)个选手的比赛前半程比赛日程。这个子表和左上角子表的对应关系式，对应元素等于左上角子表对应元素加 2 ( k − 1 ) 2^{(k-1)} 2(k−1)。

  3. 求右上角子表：等于左下角子表的对应元素。

  4. 求右下角子表：等于左上角子表的对应元素。

2、代码实现：

#include<stdio.h>
#include<math.h>
#define N 50
void GameTable(int k,int array[][N]);
void print(int k,int array[][N]);         //输出二维数组 
main()
{
    int k;
    int array[N][N];
    printf("参赛选手的人数为n（n=2^k），请输入k 的值：");
    do
    {
         scanf("%d",&k);
        if(k>0)
        {
            GameTable(k,array);
            print(k,array);
        }
        else
          printf("您输入的数据有误,请重新输入"); 
    }while(k!=0);//排除输入错误k值

}
void GameTable(int k,int array[][N])//数组下标从1开始
{
    int i,j,s,t;
    int n=1;
    for(i=1;i<=k;i++)
        n*=2;                       //求总人数
    for(i=1;i<=n;i++)
        array[1][i]=i;                  //第一行排1-8
    int m=1;                          //用来控制每一次填表时i行j列的起始填充位置
    for(s=1;s<=k;s++)                 //s指对称赋值的总循环次数，即分成几大步进行制作日程表
    {
        n=n/2;
        for(t=1;t<=n;t++)              //t指明内部对称赋值的循环次数
            for(i=m+1;i<=2*m;i++)
                for(j=m+1;j<=2*m;j++)
                {
                    array[i][j+(t-1)*m*2]=array[i-m][j+(t-1)*m*2-m];       //右上角等于左上角的值
                    array[i][j+(t-1)*m*2-m]=array[i-m][j+(t-1)*m*2];       //左下角等于右上角的值
                }
        m*=2;
    }
    
}
void print(int k,int array[][N])
{
    int i,j;
    int num=pow(2,k);
    printf("%d人的循环赛日程表如下：\n",num);
    for(i=1;i<=num;i++)                           //输出二维数组 
    {
        for(j=1;j<=num;j++)
        {
            printf("%d\t",array[i][j]);
        }
         printf("\n");
    }
}

循坏日程赛安排
1、实验结果

img

2、算法复杂度分析
时间复杂度：O(2^k * 2^k)。

（四）、（分治）最大连续子序列和

1、算法分析：
1.将一个长度为n的序列，一分为二变为两个长度为n/2的子序列，继续将子序列们一分为二，直到每个子序列只含有1个整数。
2.此时问题已经足够小，“最大子序列和”有以下三种情况：左边序列的最大子序列和、右边序列的最大子序列和和处在中间位置上的最大子序列和，我们通过比较，得到三者中的最大值。
3.再将这些“小问题”合并，使用同样的比较方法逐步向上合并这些“左右序列”，直到得到整个序列的最大子序列和，解决问题。

2、代码实现：

#include<stdio.h>
#define MAXSIZE 100
 
int max3(int a,int b,int c)
{
	if(a>b) return a>c?a:c;
	else return b>c?b:c;
}
 
int MaxSubseqSum(int a[],int left,int right)
{
	int maxLeftSum,maxRightSum,maxMidSum;
	int maxLeftBorderSum,LeftBorderSum;
	int maxRightBorderSum,RightBorderSum;
	int mid;
	int i;
	if(left==right)	//递归出口，子序列只有一个元素时
		return a[left];
	mid=(left+right)/2;	//求中间位置
	maxLeftSum=MaxSubseqSum(a,left,mid);	//求左边序列的最大子序列和
	maxRightSum=MaxSubseqSum(a,mid+1,right);	//求右边序列的最大子序列和
	maxLeftBorderSum=0;
	LeftBorderSum=0;
	for(i=mid;i>=left;i--)	//从中间位置向左找靠边界的最大子序列
	{
		LeftBorderSum+=a[i];
		if(LeftBorderSum>maxLeftBorderSum)
			maxLeftBorderSum=LeftBorderSum;
	}
	maxRightBorderSum=0;
	RightBorderSum=0;
	for(i=mid+1;i<=right;i++)	//从中间位置向右找靠边界的最大子序列
	{
		RightBorderSum+=a[i];
		if(RightBorderSum>maxRightBorderSum)
			maxRightBorderSum=RightBorderSum;
	}
	maxMidSum=maxLeftBorderSum+maxRightBorderSum;	//得到处在中间位置上的最大子序列和
	return max3(maxLeftSum,maxRightSum,maxMidSum);
}
 
int MaxNum(int a[],int left,int right)
{
	int maxLeft,maxRight;
	int mid;
	if(left==right)
		return a[left];
	mid=(left+right)/2;
	maxLeft=MaxNum(a,left,mid);
	maxRight=MaxNum(a,mid+1,right);
	return maxLeft>maxRight?maxLeft:maxRight;
}
 
int main()
{
	int a[MAXSIZE];
	int count=0;
	int i,n;
	printf("序列长度:");
	scanf("%d",&n);
	printf("输入整数序列:");
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]<=0)
			count++;
	}
	if(count==n)	//判断是否含有正整数
		printf("最大子序列和:%d\n",MaxNum(a,0,n-1));
	else
		printf("最大子序列和:%d\n",MaxSubseqSum(a,0,n-1));
 
}

（分治）最大连续子序列和
1、实验结果

img

2、算法复杂度分析
时间复杂度：O(nlog(n))

（五）、（动态规划）最大连续子序列和

1、算法分析：

  1. 动态规划算法：求最大连续子序列
    1） k[j] 表示最大连续子序列最后一个元素，dk[j]表示最大连续子序列和
    2）最大连续子序列和为从 dk[i] ~ dk[j]
  2. 分两种情况：
    1)最大和为k[j]。它之前的序列和都小于k[j]
    2)最大和为dk[j-1]+k[j]。
    3.得到状态转移方程：
    dk[j] = max{dk[j-1]+k[j], k[j]} 边界为 dk[0] = j[0]
  3. 动态规划算法计算特点（步骤）：
    从后往前算，每步计算结果都记录进表。
    计算结束后，再遍历记录表。

2、代码实现：

import java.util.Scanner;

public class MaxSubSequence {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("请输入子序列长度：");
        int N = sc.nextInt();
        System.out.println("请输入子序列：");
        int[] A = new int[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = sc.nextInt();
        }

        int ThisSum, MaxSum, j;
        ThisSum = MaxSum = 0;
        for (j = 0; j < N; j++) {
            ThisSum += A[j];

            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
            else if (ThisSum < 0)
                ThisSum = 0;
        }

        System.out.println("最大子序列和位：" + MaxSum);
    }
}

（动态规划）最大连续子序列和
1、实验结果

img

2、算法复杂度分析
时间复杂度：0（n）

五、实验小结（包括问题和解决方法、心得体会等）

分治法，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。本次实验增加了动手编码能力，对算法设计有了更进一步的认识，但是技术上的缺陷，编码能力上存在的短板，在今后的实验中还需要加大练习力度。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/520273.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

jmeter下载与使用

jmeter下载与使用

下载 官网下载地址&#xff1a;Apache JMeter - Apache JMeter™ 由于jmeter是由java语言编写的&#xff0c;所以要先安装jdk1.8或者以上的版本 配置环境变量 配置classpath环境变量 %JMETER_HOME%\lib\ext\ApacheJMeter_core.jar;%JMETER_HOME%\lib\jorphan.jar;%JMETER_HO…
阅读更多...
深入理解 SQL 中的数据集合和数据关联

深入理解 SQL 中的数据集合和数据关联

引言 在数据库管理系统中&#xff0c;数据集合和数据关联是 SQL 查询中常见的概念。它们是构建复杂查询和分析数据的基石。本文将深入探讨 SQL 中的数据集合和数据关联&#xff0c;包括它们的概念、常见用途以及实际示例。 首先引入一下数学中的集合 集合的基本概念&#x…
阅读更多...
【Kafka】聊聊如何做Kafka集群部署方案

【Kafka】聊聊如何做Kafka集群部署方案

实际业务问题 在实际的业务中&#xff0c;因业务方要求&#xff0c;每天从三方拉取一定100W用户的三方数据&#xff0c;具体就是 提供uid&#xff0c;然后每天进行离线跑批。前期是部署多个jar实例&#xff0c;然后将名单拆分成多分&#xff0c;然后python脚本读取uid&#xf…
阅读更多...
基于spark分析以springboot为后段vue为前端的大学生就业管理系统

基于spark分析以springboot为后段vue为前端的大学生就业管理系统

基于spark分析以springboot为后段vue为前端的大学生就业管理系统 大学生就业管理系统是一个针对高校毕业生就业信息管理的有效工具，它能够帮助学校和学生更好地管理就业数据，提供数据驱动的决策支持。本文将介绍如何通过爬虫采集数据，利用Spark进行数据分析处理，再结合Spr…
阅读更多...
【cpp】快速排序优化

【cpp】快速排序优化

标题&#xff1a;【cpp】快速排序 水墨不写bug 正文开始&#xff1a; 快速排序的局限性&#xff1a; 虽然快速排序是一种高效的排序算法&#xff0c;但也存在一些局限性&#xff1a; 最坏情况下的时间复杂度&#xff1a;如果选择的基准元素不合适&#xff0c;或者数组中存在大…
阅读更多...
【C++】c++11新特性(一)

【C++】c++11新特性(一)

目录 { }列表初始化 内置类型---对单值变量及数组的初始化 列表初始化时进行的类型转换 自定义类型---对类对象或结构的初始化 initializer_list 1. 定义接受 initializer_list 参数的构造函数 2. 在函数中使用 initializer_list 参数 3. 使用 initializer_list 与 vect…
阅读更多...
教你网络安全

教你网络安全

如今&#xff0c;组织的信息系统和数据面临着许多威胁。而人们了解网络安全的所有基本要素是应对这些威胁的第一步。 网络安全是确保信息完整性、机密性和可用性(ICA)的做法。它代表了应对硬盘故障、断电事故&#xff0c;以及来自黑客或竞争对手攻击等防御和恢复能力。而后者包…
阅读更多...
Android14应用启动流程（源码+Trace）

Android14应用启动流程（源码+Trace）

1.简介 应用启动过程快的都不需要一秒钟&#xff0c;但这整个过程的执行是比较复杂的&#xff0c;无论是对手机厂商、应用开发来说启动速度也是核心用户体验指标之一&#xff0c;本文采用Android14源码与perfetto工具进行解析。 源码参考地址&#xff1a;Search trace分析工…
阅读更多...
基于单片机多功能MP3播放器系统设计

基于单片机多功能MP3播放器系统设计

**单片机设计介绍&#xff0c;基于单片机多功能MP3播放器系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机多功能MP3播放器系统设计是一个结合了硬件和软件设计的复杂项目。以下是对该系统设计的概要描述&#…
阅读更多...
初识二叉树和二叉树的基本操作

初识二叉树和二叉树的基本操作

目录 一、树 1.什么是树 2. 与树相关的概念 二、二叉树 1.什么是二叉树 2.二叉树特点 3.满二叉树与完全二叉树 4.二叉树性质 相关题目&#xff1a; 5.二叉树的存储 6.二叉树的遍历和基本操作 二叉树的遍历 二叉树的基本操作 一、树 1.什么是树 子树是不相交的;…
阅读更多...
Github 2024-04-06Rust开源项目日报Top10

Github 2024-04-06Rust开源项目日报Top10

根据Github Trendings的统计，今日(2024-04-06统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量Rust项目10HTML项目1Dart项目1RustDesk: 用Rust编写的开源远程桌面软件 创建周期：1218 天开发语言：Rust, Dart协议类型：GNU Affero General …
阅读更多...
docker + miniconda + python 环境安装与迁移（详细版）

docker + miniconda + python 环境安装与迁移（详细版）

本文主要列出从安装dockerpython环境到迁移环境的整体步骤。windows与linux之间进行测试。 简化版可以参考&#xff1a;docker miniconda python 环境安装与迁移&#xff08;简化版&#xff09;-CSDN博客 目录 一、docker 安装和测试 二、docker中拉取miniconda&#xff…
阅读更多...
C语言--指针终章

C语言--指针终章

目录 1. sizeof和strlen的对⽐ 1.1 sizeof 1.2 strlen 1.3 sizeof 和 strlen的对⽐ 2. 数组和指针的理解——题目理解 2.1.sizeof 代码1&#xff1a; 代码2&#xff1a; 代码3&#xff1a; 代码4&#xff1a; 代码5&#xff08;二维数组&#xff09;&#xff1a; 2.2…
阅读更多...
【蓝桥杯-单链表-网络寻路】

【蓝桥杯-单链表-网络寻路】

蓝桥杯-单链表-网络寻路 单链表基本操作操作一&#xff1a;向链表头插入一个数操作二:在第 k个插入的数后插入一个数操作三&#xff1a;删除第 k个插入的数后面的一个数&#xff1b; P8605 [蓝桥杯 2013 国 AC] 网络寻路 单链表基本操作 初始化有关操作 // head 表示头结点的…
阅读更多...
Debian12 使用 nginx 与 php8.2 使用 Nextcloud

Debian12 使用 nginx 与 php8.2 使用 Nextcloud

最近将小服务器升级了下系统&#xff0c;使用了 debian12 的版本&#xff0c;正好试试 nginx 和 php-fpm 这种方式运行 Nextcloud 这个私有云的配置。 一、基本系统及应用安装 系统&#xff1a;debian12 x86_64 位版本最小安装&#xff0c;安装后可根据自己需求安装一些工具&…
阅读更多...
如何优化TCP？TCP的可靠传输机制是什么？

如何优化TCP？TCP的可靠传输机制是什么？

在网络世界中&#xff0c;传输层协议扮演着至关重要的角色&#xff0c;特别是TCP协议&#xff0c;以其可靠的数据传输特性而广受青睐。然而&#xff0c;随着网络的发展和数据量的激增&#xff0c;传统的TCP协议在效率方面遭遇了挑战。小编将深入分析TCP的可靠性传输机制&#x…
阅读更多...
【C++初阶】 vector 在OJ中的使用

【C++初阶】 vector 在OJ中的使用

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;只出现一次的数字 和 杨辉三角 OJ 目录 一、只出现一次的数字 题目描述&#xff1a; 二、杨辉三角OJ 题目描述&#xff1a; 一、只…
阅读更多...
vue快速入门（七）内联语句

vue快速入门（七）内联语句

注释很详细&#xff0c;直接上代码 上一篇 新增内容 button点击事件绑定内联语句写法与要求 源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wid…
阅读更多...
phpstorm设置头部注释和自定义注释内容

phpstorm设置头部注释和自定义注释内容

先说设置位置&#xff1a; PhpStorm中文件、类、函数等注释的设置在&#xff1a;setting-》Editor-》FIle and Code Template-》Includes-》PHP Function Doc Comment下设置即可&#xff0c;其中方法的默认是这样的&#xff1a; /** ${PARAM_DOC} #if (${TYPE_HINT} ! "…
阅读更多...
【第九篇】使用BurpSuite进行编码与解码

【第九篇】使用BurpSuite进行编码与解码

Burp存在一个功能&#xff0c;可以识别包含不透明数据&#xff08;例如会话令牌&#xff09;的消息。 如图&#xff1a;如果 Burp 识别所选内容的编码格式&#xff0c;它会自动解码数据。解码后的文本显示在 Inspector面板中。 在编码工具模块中&#xff0c;可对数据进行重复解…
阅读更多...
最新文章

Copyright @ 2022~2023