2021《算法分析与设计》练习8

目录

• 问题 A: 解密
• 问题 B: 最长公共子序列问题(LCS)之备忘录法
• 问题 C: 最长公共子序列问题(LCS)之动态规划法
• 问题 D: 最长公共子序列问题(LCS)-构造LCS
• 问题 E: 牛牛的字符串
• 问题 F: 最大子段和
• 问题 G: 绿地装饰（还不会）
• 问题 H: 百舸争流（还不会）

问题 A: 解密

题目描述
湖南中医药大学有含浦、东塘 2 个校区，学校办学历史悠久，前身为 1934 年的湖南国医专科学校，1953
年创办湖南中医进修学校，1960 年创建普通高等本科院校——湖南中医学院，1979 年成为全国首批取得
中医类研究生学历教育资格的院校，1990 年原湖南科技大学成建制并入湖南中医学院，2002 年与湖南省
中医药研究院合并，2006 年经教育部批准更名为湖南中医药大学，2012 年进入湖南省一本招生序列。
目前，学校与湖南省中医药研究院实行校院合一的管理体制。学校学科门类齐全、中医药特色鲜明。学校
设有 18 个学院、24 个本科专业，涵盖医、理、工、管、文等 5 大学科门类。中医诊断学在本学科研究领
域居国内领先水平。
小 F 居住在含浦校区，他想和东塘校区的同学小 L 聊天，为了保证沟通安全，他发明了一种加密方式，这
种加密方式是这样的：对于一个 01 串，小 F 会将其从左到右每 8 位分成一组，最后一组可能不足 8 位，
对每组进行逆序操作，即如果原来是 bLbL+1bL+2 · · · bR−1bR, 逆序之后变成 bRbR−1bR−2 · · · bL−1bL。现在
小 F 已经加密好了一个串，并且将其发给了小 L，你能帮助小 L 得到这串密文对应的原始信息吗？
输入
单组数据。
一行一个 01 串，代表加密后的字符串，串长度大于 0, 小于等于 100。
输出
一行字符串，代表加密后的字符串所对应的原始信。
样例输入

100010110011101

样例输出

110100011011100

注意字符串的边界就好了。

#include
using namespace std;string str;
int main()
{cin>>str;int len=str.length();int m=len%8;//不足8个字符的数量for(int i=0;i<=len-m-8;i+=8)//这里是将刚好是8个字符的串进行倒序输出{for(int j=i+7;j>=i;j--)printf("%c",str[j]);}for(int i=len-1;i>=len-m;i--)//处理不够8个的字符cout<<str[i];printf("\n");return 0;
}

问题 B: 最长公共子序列问题(LCS)之备忘录法

题目描述
使用备忘录法求解两个序列的最长公共子序列的长度。
输入
每组输入包括两行，每行包括一个字符串。
输出
两个序列的最长公共子序列的长度。
样例输入

ACBCDABD
ABDCABA

样例输出

5

模板题

#include
using namespace std;string s1,s2;
int a[1005][1005];
int fun(string s1,string s2,int i,int j)
{if(a[i][j]>-1)//判断处理过了没return a[i][j];if(i==0||j==0)//递归结束条件a[i][j]=0;else{if(s1[i-1]==s2[j-1])//找左上角a[i][j]=fun(s1,s2,i-1,j-1)+1;elsea[i][j]=max(fun(s1,s2,i-1,j),fun(s1,s2,i,j-1));//找左边或者上边}return a[i][j];
}int main()
{while(cin>>s1>>s2){memset(a,-1,sizeof(a));int len1=s1.length();int len2=s2.length();printf("%d\n",fun(s1,s2,len1,len2));}return 0;
}

问题 C: 最长公共子序列问题(LCS)之动态规划法

题目描述
使用动态规划算法求解两个序列的最长公共子序列的长度。
输入
每组输入包括两行，每行包括一个字符串。
输出
两个序列的最长公共子序列的长度。
样例输入

ACBCDABD
ABDCABA

样例输出 Copy

5

模板题

#include
using namespace std;string s1,s2;
int a[1005][1005];
int fun(string s1,string s2,int i,int j)
{if(i==0||j==0)//结束条件a[i][j]=0;else{if(s1[i-1]==s2[j-1])a[i][j]=fun(s1,s2,i-1,j-1)+1;elsea[i][j]=max(fun(s1,s2,i-1,j),fun(s1,s2,i,j-1));}return a[i][j];
}int main()
{while(cin>>s1>>s2){memset(a,-1,sizeof(a));int len1=s1.length();int len2=s2.length();printf("%d\n",fun(s1,s2,len1,len2));}return 0;
}

问题 D: 最长公共子序列问题(LCS)-构造LCS

题目描述
使用动态规划算法求两个序列的最长公共子序列，需构造一条最长公共子序列。
输入
每组输入包括两行，每行包括一个字符串。
输出
两个字符序列的一条最长公共子序列。（输入已确保最长公共子序列的唯一性）
样例输入

acdbxx
ccdxx

样例输出

cdxx

模板题 填表法

#include
using namespace std;string s1,s2;
int b[1005][1005];//记录方向
int a[1005][1005];
int fun(string s1,string s2)//记录方法的函数
{int len1=s1.length();int len2=s2.length();for(int i=1;i<=len1;i++){a[i][0]=0;for(int j=1;j<=len2;j++){a[0][j]=0;if(s1[i]==s2[j]){a[i][j]=a[i-1][j-1]+1;b[i][j]=1;}else{if(a[i-1][j]>=a[i][j-1]){a[i][j]=a[i-1][j];b[i][j]=2;}else{a[i][j]=a[i][j-1];b[i][j]=3;}}}}
}
void lcs(int i,int j,string c)//构造最优解
{if(i==0||j==0)return ;if(b[i][j]==1){lcs(i-1,j-1,c);cout<<c[i];}elseif(b[i][j]==2)lcs(i-1,j,c);elselcs(i,j-1,c);
}
int main()
{while(cin>>s1>>s2){fun(s1,s2);int len1=s1.length()-1;int len2=s2.length()-1;lcs(len1,len2,s1);printf("\n");}return 0;
}

问题 E: 牛牛的字符串

题目描述
牛牛有两个字符串(可能包含空格)，他想找出其中最长的公共连续子串的长度，希望你能帮助他。例如：两个字符串分别为"abede"和"abgde"，结果为2。
输入
每组数据包括两行，每行为一个字符串。
输出
输出最长的公共连续子串的长度。
样例输入

abede
abgde

样例输出

2

方法：动态规划

#include
using namespace std;string s1,s2;
int dp[1005][1005];
int main()
{while(getline(cin,s1)){//getchar();getline(cin,s2);int max1=-1;for(int i=0;i<s1.length();i++){for(int j=0;j<s2.length();j++){if(s1[i]==s2[j]){if(i>0&&j>0)dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=1;if(dp[i][j]>max1)max1=dp[i][j];}}}printf("%d\n",max1);}return 0;
}

问题 F: 最大子段和

题目描述
给定n个整数（可能是负数）组成的序列a[1], a[2], a[3], …, a[n]，求该序列的子段和如a[i]+a[i+1]+…+a[j]的最大值。
输入
每组输入包括两行，第一行为序列长度n，第二行为序列。
输出
输出字段和的最大值。
样例输入 Copy

5
-1 0 1 2 3

样例输出 Copy

6

#include
using namespace std;int a[1005];
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++)scanf("%d",&a[i]);int sum=0,max1=0;for(int i=0;i<n;i++){if(sum>0)sum+=a[i];elsesum=a[i];if(sum>max1)max1=sum;}printf("%d\n",max1);}return 0;
}

问题 G: 绿地装饰（还不会）

题目描述
湖南中医药大学坐落于中国历史文化名城长沙，是湖南省重点建设本科院校，是全国首批设立国家级重
点学科的高校，也是首批招收博士研究生、留学生及港澳台学生的中医药院校。学校现有 2 个校区，占
地面积 1393 亩，建筑面积 52 万平方米，主校区依岳麓南坡，临湘江西岸，环境幽雅，风光秀丽，是求
学成才的理想之地。
校园景观设计师小 W 的主要工作就是植被环境的设计维护，他有一个 N×N 的模板图，他创作景观的步
骤如下：
1、将当前的绿地分成 N×N 小块，再按照模板图添加装饰（黑色表示有装饰，白色表示没有）；
2、对于每个白色（未被装饰）的地块，递归操作 1，应用模板图，即分成更小的 N×N 块，继续进行装
饰，而黑色（已装饰）的地块则不必操作。
下图是某次装饰过程的示意图。

现在你的任务是求出 K 次递归后的绿地状态。

输入
单组数据。
第一行两个数 N,K，如题意中的描述。
接下来是一个 N×N 的模板图，’ . ’ 表示白色，’ * ’ 表示黑色。
2 ≤ n ≤ 3
1 ≤ k ≤ 5

输出
输出一个 N K×N K 的矩阵表示答案，不允许有多余的空行或空格。
样例输入

2 3

.*

…

样例输出

.*******

…******

.*.*****

…****

.***.***

……

....

…

问题 H: 百舸争流（还不会）

题目描述
橘子洲风景区位于湖南省长沙市市区对面的湘江江心，是湘江中最大的名洲，由南至北，横贯江心，西望
岳麓山，东临长沙城，四面环水，绵延数十里，狭处横约 40 米，宽处横约 140 米，形状是一个长岛，是
国家重点风景名胜区。
一天，N 名选手参加了一年一度的橘洲竞渡大赛，现在只剩下最后一场决赛了！
赛制为积分制，N 名选手的积分分别为 A1 到 AN。决赛的积分规则如下：第一名得 B1 分，第二名得 B2
分，……，第 m 名得 Bm 分，第 m+1 名至第 n 名不得分。最后第 i 名选手的总得分为 Ai 加上他在决
赛中的得分。
我们按总分为第一关键字、名字的字典序为第二关键字对选手进行排序。现告诉你一名选手的名字，希望
你告诉他，他最终的排名最前可能是多少，最后可能是多少。

输入
单组数据。
第一行为一个数 n，表示有 n 名选手 (1 ≤ n ≤ 105)。
接下来有 n 行，每行由一个字符串 S 和一个非负整数 Ai 表示，代表该人的名字和决赛之前的总分。

(名字仅由英文字母和数字表示，长度不超过 20，没有相同名字的两个人，0 ≤ Ai ≤ 106)。

接下来一个数 m(0 ≤ m ≤ n)。
接下来一行 m 个数字依次表示 B1, B2, B3, · · · , Bm (0 ≤ Bi ≤ 106)。
最后一个字符串表示询问的选手的名字。
输出
输出两个数，第一个表示最终排名最前可能多少，第二个表示最后可能多少。
样例输入

3
CH1 10
CH2 20
CH3 40
2
20 10
CH1

样例输出

2 3

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！