3、串、KMP、矩阵_答案

1、1、一个nxn的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n(n+1)/2。2、 一个串的任意连续字符组成的子序列称为串的子串，该串称为 主串。3、 串长度为0的串称为 空串，只包含空格的串称为 空格串。4、 若两个串的长度相等且对应位置上的字符也相等，则称两个串相等 。5、 寻找子串在主串中的位置，称为模式匹配 。其中，子串又称为模式串 。6求出二维数组An,n的两条对角线元素之和(程序题)。int sumOfDiagonal( int *a) int i, n = a0.length,sum1 = 0, sum2 = 0, sum;for (i

2、= 0; i Oand 珂max (Ci -11) If lfj Oand x.工 y.Ci,j= 1 /2、给定一个源串和目标串，能够对串进行如下操作：（2012.Baidu、google）在给定位置上插入一个字符串。替换任意字符删除任意字符使得源串等于目标串，源串和目标串的长度都小于2000。求出相似度=（操作次数+1）/2。注：距离=操作次数解：对第一个字符进行操作：删除A或B前增加一个字符，将变成 A2,lenA和B1,lenB。对第一个字符进行操作：删除B或A前增加一个字符，将变成 A1,lenA和B2,lenB。对第一个字符进行操作：修改A或修改B的字符，将变成A2,lenA和B2

3、,lenB。设 fi,j 表示 strAi,lenA 与 strBj,lenB的最小距离，则：|f/i + 1str/lUl = str/?|jrr； ；1 I min （/ti + 1,/ + 1 + 1+ 1 + 1 JtltL3、求数组的子数组之和的最大值。，子数组之和的最8,其对应的数组一个有N个整数元素的一维数组(A0, A1, . , An-2, An-1)大值是什么?(要求子数组的元素是连续的 )例子：有数组(-2, 5, 3, -6, 4,-8, 6)，则其子数组之和的最大值为为(5,3)AIIk+1=maxAk+1，Ak+1+Startk ，Allk.#define INTM

4、IN 0x80000000int getMaxSum(nt a, int len)int max=NTMINint sum=0;int i= 0;for (i= 0;ilen;i+)if (aimax)max=sum;return max;4、递归(全排列)template void Swap(Type &a,Type &b)Type t;t=a;a=b;b=t; template void Perm_CppType list, int k, int m) _/产生listk:m的所有全排列if (k=m)/只剩一个元素for (int i= 0;i=m;i+) coutlisti;coute

5、 ndl;else/ 还有多个元素待排列，递归产生排列for ( inti=k;ich);S-len = strlen(S- ch)/ sizeof ( char );i = 0;while (S- chi != 0&i len )k = 0;while (S- chi = S-chi+k)k+;if (*max chi != 0 & i len ) k = 0;while (S- chi = S-chi+k) k+;if (*max = k) ccount = S-chi;Locationcount = i; count+;i = i + k; ccount = 0 ;/ 输出字符平台及对应

6、的初始位置void PrintString( int *max, char c N, int Location N) int i, k; printf( 最大字符平台为： n );for (i = 0; ci != 0 ; i+) for (k = 0; k *max; k+) putchar(ci);printf( n 对应初始位置为： %3dn,Locationi+ void main()SString S;int max;int Location N;char c N;MaxStr(&S, &max, c, Location); PrintString(&max, c, Location

7、);6、 鞍点是指矩阵中的元素 aij 是第 i 行中值最小的元素，同时又是第 j 列中值 最大的元素。试设计一个算法求矩阵 A 的所有鞍点。#include int main()int n, m, i, j, k, l, minn, maxx, flag ;int a 256 256;while ( 1)printf( 请输入矩阵的行列数： n ); scanf( %d %d,&n,&m);printf( 请输入与行列数相符的矩阵： n );for (i= 0; in; i+)for (j= 0; jm; j+) scanf( %d,&aij);flag= 0;printf( 马鞍点输出 (

8、输出该点所在的行数与列数 ) ：n );for (i= 0; in; i+)for ( j = 0; j m; j+)minn = aij;for ( k = 0 ; k aik) break ; if ( k=m) maxx=aij; for (l= 0; ln; l+) if (maxxalj)break ;if (l=n)printf( %d %d %dn,i , j ,aij); flag = 1;if (flag= 0)printf( 此矩阵没有马鞍点 n );return 0;7、 字符串反序void reverse( char *str)if (*str= 0 ) return ;int len=strlen(str);char c=*str;*str=strlen- 1;strlen- 1= 0 ;reverse(str+ 1);strlen- 1=c;void reverse2( string &str)i