算法分析与设计oj复习题

8594 有重复元素的排列问题(优先做)

时间限制:1000MS 代码长度限制:10KB
提交次数:1610 通过次数:656

题型: 编程题 语言: G++;GCC;VC;JAVA
Description
设集合R={r1,r2,…,rn}是要进行排列的n个元素,其中r1,r2,…,rn可能相同。
试着设计一个算法,列出R的所有不同排列。
即,给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。

输入格式

第1行是元素个数n,1<=n<=15。接下来的1行是待排列的n个元素,元素中间不要加空格。

输出格式

程序运行结束时,将计算输出n个元素的所有不同排列。最后1行中的数是排列总数。

(说明:
此题,所有计算出的排列原本是无所谓顺序的。但为了容易评判,输出结果必须唯一!
现做约定:所有排列的输出顺序如课本例2-4的程序段的输出顺序,区别仅是这道题是含
重复元素。)

输入样例

4
aacc

输出样例

aacc
acac
acca
caac
caca
ccaa
6

提示

课本上有“递归”实现无重复元素全排列的源程序。
稍加修改即可满足此题要求。

在递归产生全排列的那段程序开始之前,
加一个判断:判断第i个元素是否在list[k,i-1]中出现过。
PermExcludeSame(char list[], int k, int m)
{

for (int i=k; i<=m; i++)
{
if (Findsame(list,k,i))//判断第i个元素是否在list[k,i-1]中出现过
continue;
Swap (list[k], list[i]);
PermExcludeSame(list, k+1, m);
Swap (list[k], list[i]);
}
}

9718 整数因子分解(优先做)

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

大于1的正整数 n 都可以分解为 n = x1 * x2 * … * xm, 每个xi为大于1的因子,即1<xi<=n 。

例如:当n=12时,共有8种不同的分解式:
12 = 12
12 = 62
12 = 4
3
12 = 34
12 = 3
22
12 = 2
6
12 = 232
12 = 223

对于给定正整数n,计算n共有多少种不同的分解式。

输入格式

第一行一个正整数n (1<=n<=1000000)

输出格式

不同的分解式数目

输入样例

12

输出样例

8

提示

此题因子讲顺序的.第一个因子可能是2~n之间的数.
比如对12而言,第一个因子可能是2,3,4,6,12.

将第一个因子为2的分解个数,加上第一个因子为3的分解个数,…,直至加到第一个因子为12的分解个数.

而第一个因子为2的分解个数又是多少呢?是对6去做因子分解的个数(因为12/2=6),递归求解!

可用“递归”和“备忘录方法”两种方法分别求解,并测试一下效率。

递归实现整数因子分解的计数。假设对正整数n的因子分解计数为solve1(n)。
1)当n=1时,计数加1。
2)当n>1时,对n的每个因子i,计算solve1(n/i)。
void solve1 (int n)
{
if (n==1) total++; //total为全局变量,有初始化
else for (int i=2; i<=n; i++)
if (n%i ==0)
solve1(n/i);
}

或者另外一种实现方式:
递归算法同,但这样实现更容易理解:
int solve2(int n)
{
int num=0;

if(n==1) return 1;

for(int i=2; i<=n; i++)
    if(n%i == 0) num+=solve2(n/i);

return num;

}

17082 两个有序数序列中找第k小(优先做)

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n,
现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。

此题请勿采用将序列X和Y合并找第k小的O(m+n)的一般方法,要充分利用X和Y已经排好序的这一特性。

输入格式

第一行有三个数,分别是长度m、长度n和k,中间空格相连(1<=m,n<=100000; 1<=k<=m+n)。
第二行m个数分别是非减序的序列X。第三行n个数分别是非减序的序列Y。

输出格式

序列X和Y的第k小的数。

输入样例

5 6 7
1 8 12 12 21
4 12 20 22 26 31

输出样例

20

提示

假设:X序列为X[xBeg…xEnd],而Y序列为Y[yBeg…yEnd]。

将序列X和Y都均分2段,即取X序列中间位置为 xMid (xMid = xBeg+(xEnd-xBeg)/2),也同理取序列Y中间位置为yMid。
比较X[xMid]和Y[yMid]的大小,此时记录X左段和Y左段元素个数合计为halfLen,即halfLen = xMid-xBeg+yMid-yBeg+2。

  1. 当X[xMid] < Y[yMid]时,在合并的数组中,原X[xBeg…xMid]所有元素一定在Y[yMid]的左侧,
    (1) 若k < halfLen,则此时第k大的元素一定不会大于Y[yMid]这个元素,
    故以后没有必要搜索 Y[yMid…yEnd]这些元素,可弃Y后半段数据。
    此时只需递归的对X序列+Y序列的前半段,去搜索第k小的数。

    (2) 若k >= halfLen,则此时第k大的元素一定不会小于X[xMid]这个元素,
    故以后没有必要搜索 X[xBeg…xMid]这些元素,可弃X前半段数据。
    此时只需递归的对X序列的后半段+Y序列,去搜索第 k-(xMid-xBeg+1)小的数。

  2. 当X[xMid] >= Y[yMid]时,在合并的数组中,原Y[yBeg…yMid]的所有元素一定在X[xMid]的左侧,
    (1) 若k < halfLen,则此时第k大的元素一定不会大于X[xMid]这个元素,
    故以后没有必要搜索 X[xMid…xEnd]这些元素,可弃X后半段数据。
    此时只需递归的对X序列的前半段+Y序列,去搜索第k小的数。

    (2) 若k >= halfLen,则此时第k大的元素一定不会小于Y[yMid]这个元素,
    故以后没有必要搜索 Y[yBeg…yMid]这些元素,可弃Y前半段数据。
    此时只需递归的对X序列+Y序列的后半段,去搜索第 k-(yMid-yBeg+1)小的数。

递归的边界,如何来写?

  1. if (xBeg > xEnd) return Y[yBeg + k - 1]; //X序列为空时,直接返回Y序列的第k小元素。
  2. if (yBeg > yEnd) return X[xBeg + k - 1]; //Y序列为空时,直接返回X序列的第k小元素。

效率分析:

T(m,n)表示对长度为m的有序的X序列和长度为n的有序的Y序列,搜索第k小元素的复杂度。
T(m,n)=1 m=0或n=0
T(m,n) <= max{T(m/2,n), T(m,n/2)} + O(1)

则T(m,n) = O(max{logm, logn})

10303 数字三角(优先做)

时间限制:1000MS 代码长度限制:10KB
提交次数:117 通过次数:56

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

问题描述:给定一个由n行数字组成的数字三角形,如下图所示。试用动态规划算法,计算出从三角
顶部至底部的一条路径,使得该路径经过的数字总和最大。

注意每个数字只能走向下一行左边或右边的数字,而不能跳跃的走。

     7
  3   8
8   1   0

2 7 4 4
4 5 2 6 5

输入格式

第一行是数字三角的行数n,1<=n<=100。接下来n行是数字三角各行中的数字,所有数字在0~99之间。

输出格式

输出两行,第一行是计算出的最大路径的和值,第二行是该路径上的数字。若有多条路径,靠右的路径
优先(即仅仅输出靠右的路径即可,无需多条路径都输出)。

如:
Input:
5
7
3 8
8 1 6
2 7 4 4
4 5 2 4 5
有两条路径:7-3-8-7-5和7-8-6-4-5都为30,由于后者靠右,因此仅输出后者。
Output:
30
7 8 6 4 5

输入样例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例

30
7 3 8 7 5

提示

上课讲了,听课或看课件。

最长上升子序列

。。。。。

最大长方体问题

。。。。

11077 最长公共子字符串(优先做)

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

求两个输入序列的最长的公共子字符串的长度。子字符串中的所有字符在源字符串中必须相邻。

如字符串:21232523311324和字符串312123223445,他们的最长公共子字符串为21232,长度为5。

输入格式

两行,第一行为第一个字符串X,第二行为第二个字符串Y,字符串不含空格并以回车标示结束。X和Y的串长都
不超过10000。

输出格式

两行,第一行为最长的公共子字符串的长度,第二行输出一个最长的公共子字符串。

说明:
(1)若最长的公共子字符串有多个,请输出在源字符串X中靠左的那个。
(2)若最长公共子字符串的长度为0,请输出空串(一个换行符)。

如输入:
21232523311324
152341231
由于523和123都是最长的公共子字符串,但123在源串X中更靠左,因此输出:
3
123

输入样例

21232523311324
312123223445

输出样例

5
21232

提示

一,对输入字符串的处理
大家在接受数据的时候,不要用(c=getchar())!=’\n’诸如此类一个字符一个字符接受,然后判断是否是回车
符号来结束一行的输入,这样的方式在你本机运行不会有问题,但OJ系统中会有错误,无法输出结果,因为
测试平台行末并非’\n’字符。这里接受数据用scanf的%s,或cin等,会自动判别结束字符的,你就不要在你
程序里专门去判别或吸收回车字符。

二,递推公式
此题和书上3.3节"最长公共子序列"描述是不同的,子序列可由不连续字符组成,但子字符串是连续的。
此题更加简单!

假设求字符串str1,str2的最长公共子串的长度.
定义f(m,n): 分别以str1[m],str2[n]结尾的最长连续公共子串的长度,
其中字符串末尾的str1[m]和str2[n]包含在最长公共子串中,即为最长公共子串的最末元素。

(这里大家思考一下,为何要这样假设子问题和子问题最优解f(m,n)?
因为子串是连续的,更大规模问题和下一级更小规模的子问题要能联系起来,而且这种联系还要越简单越好,
只有规定原先两个串的最末元素包含在最长公共子串中,这样就能联系上两个串的前缀部分(都去掉末个元
素)的最长公共子串问题。)

而对于f(m+1,n+1) 有:

  1. f(m+1,n+1) = 0, if str1[m+1] != str2[n+1]
  2. f(m+1,n+1) = f(m,n) + 1, if str1[m+1] == str2[n+1]
  3. 另外边界情况,f(0,j)=0(j>=0), f(j,0)=0(j>=0)

而此题所求的最长公共字符串的长度即为f(m,n)整个二维数组中的最大值,注意不是填充的最后一个元素。
也不是最后一行元素的最大值,而是整个二位数组的最大值。思考一下为什么呢?

至于如何优先输出在源串X靠左的公共子串,大家自行思考。
这也容易,在你比较产生数组最大值maxlen时,就同步记录下那时在x数组中的下标位置,比如此位置叫endindex_x。
最后用这个位置在X序列中输出从X[endindex_x - maxlen + 1]元素一直到X[endindex_x]元素即可。

8595 钱币组合的问题(优先做)

时间限制:300MS 代码长度限制:10KB
提交次数:897 通过次数:398

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

设有n种不同的钱币各若干,可用这n种钱币产生许多不同的面值。
如给定面值7分,有1分3张,2分3张,5分1张,能组成给定面值7分的方法有如下4种:
3个1分+2个2分; 5个;
1个1分+3个2分; 4个;
2个1分+1个5分; 3个;
1个2分+1个5分; 2个。

上面4种方案的最少张数为2个。

你的编程任务:给定面值m,和n种不同面值钱币及其张数,
(1) 求给定面值m能有多少种不同的构成方法数。
(2) 求给定面值m最少要多少张。

输入格式

第1行有1个正整数n(1<=n<=50),表示有n种不同的钱币。
第2行有n个数,分别表示每种钱币的面值v[1]…vn
第3行有n个数,分别表示每种钱币的张数k[1]…kn
第4行有1个数,表示给定的面值m (1<=m<=20000)。

输出格式

两行:
第一行:计算出给定面值的不同的方法种数。若无法给出找钱方案,返回0数值。
第二行:计算出给定面值所需的最少张数。若无法给出找钱方案,返回“no possible”(无大写,无标点)。

输入样例

3
1 2 5
3 3 1
7

输出样例

4
2

提示

(1)给定面值m的不同方法种数

给定的总面值m,n种钱币,每种钱币面值v[1…n],每种钱币的张数k[1…n],
用一个二维数组d[i][1…m]记录用前i种钱币组成1…m面值产生的方法数。1<=i<=n。
初始,该数组全清零,然后逐个加入第i种面值的钱币(1<=i<=n),并修改影响到数组d的方法数。

设d[i,j]:表示前i种钱币组成面值j分的方法数,1<=i<=n,0<=j<=m。(j>=0才有意义,若j<0,可视为d[i,j]=0)
d[i,0] = 1, if 1<=i<=n
d[1,j] = 1, if j%v[1]=0 && j/v[1]<=k[1];
d[1,j] = 0, if j%v[1]!=0 || j/v[1]>k[1] || j<0;

if i>1 && j1 && v[i]<=j<2*v[i]
d[i,j] = d[i-1,j] + d[i-1,j-v[i]]

if i>1 && 2v[i]<=j<3v[i]
d[i,j] = d[i-1,j] + d[i-1,j-v[i]] + d[i-1,j-2*v[i]]

if i>1 && k[i]v[i]<=j<=m
d[i,j] = d[i-1,j] + d[i-1,j-1
v[i]] + d[i-1,j-2*v[i]] + … + d[i-1,j-k[i]*v[i]]
//这里要注意,要保证 j-k[i]*v[i]>=0 才有意义,对可能的越界(无论是左边越界还是右边越界),都要仔细审查。

最后d[n,m]为原问题所求。

当然由于这里的d数组d[i,j]只与d[i-1,…]有关,也完全可以用一维数组d[1…m]来实现。

(2)求给定面值m最少要多少张

假设c[i][j]表示:选择前i种面值的钱,凑成面值j的最少张数,这里1<=i<=n, 0<=j<=m。
c[i][j]的递归关系如下:

令:t = min{ (int)(j/v[i]), k[i] },表示第i种钱币最多加入的张数。
c[i][j] = min{ p+c[i-1][j-pv[i]] | p from 0 to t },这里p表示第i种币值选入的张数,
t表示第i种币值最多选入的张数。
//这里要注意,要保证 j-p
v[i]>=0 才有意义,对可能的越界(无论是左边越界还是右边越界),都要仔细审查。

初始条件:
c[i][0]=0, 1<=i<=n
c[1][j]=int(j/v[1]), if j%v[1]==0 && j/v[1]<=k[1]
c[1][j]=MAXINT, if j%v[1]!=0 || j/v[1]>k[1]
//此处MAXINT为自定义的无穷大的数,表示没法放。

最后返回c[n][m],若c[n][m]为MAXINT,则无法找到找钱的方案。

11079 可以移动的石子合并(优先做)

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),现要将石子合并成一堆,规定每次可
选择至少2堆最多k堆移出然后合并,每次合并的分值为新堆的石子数。

若干次合并后,石子最后肯定被合并为一堆,得分为每次合并的分值之和。

现在求解将这n堆石子合并成一堆的最低得分和最高得分。

输入格式

两行。第一行n和k。
第二行a1 a2 … an,每个ai(1<=i<=n)表示第i堆石子的个数,n<=200,2<=k<=n。

输出格式

仅一行,为石子合并的最低得分和最高得分,中间空格相连。

输入样例

7 3
45 13 12 16 9 5 22

输出样例

199 593

提示

此题贪心算法求解.
给这题标记标签"dp"方法是同学所为,并非老师标注.动规不是不可以,但有更好更快的贪心解法的.

如7堆石头,每次可选择最少2堆最多3堆合并,可以如下这样合并:
第1次合并:45+22=67
第2次合并:67+16=83
第3次合并:83+13=96
第4次合并:96+12=108
第5次合并:108+9=117
第6次合并:117+5=122
合并的总分值:67+83+96+108+117+122=593,593已是最大分值。

也可以这样合并:
第1次合并:5+9+12=26
第2次合并:13+16+22=51
第3次合并:45+51+26=122
合并的总分值:26+51+122=199,199已是最小分值。

因此此题贪心的方法如下:

(1)保证每次选两堆最多的,合并直至只剩一堆为止,能获得最大得分;
这个和huffman树构造是相同的,不再详述!

(2)保证每次选k堆最少的,合并直至只剩一堆为止,能获得最小得分。
这个是多元huffman树的构造。要注意的是:在合并之前,若n%(k-1)!=1,说明合并到最后一轮时,
剩下不是k堆(而是比k堆少),这样算的并不是最小得分,而必须在合并之前添加若干个为0的虚拟
堆,目的为凑成的堆数保证每次都能有k堆合并(包括最后一次)最后合并为1堆。

因此,在合并前作如下处理:

//假设石头每堆个数放于stone[1]~stone[n],且stone[n]之后最多k-1个数组单元为可写;
while (n % (k - 1) != 1)
{
n++;
stone[n]=0;
}

上一篇:SWUST OJ 964: 数细胞


下一篇:链表OJ题(一)