（1） 基本语句2*i

基本语句y = y + i * j执行了2/n次 一共执行次数=n/2+n/2=O（n）

（2） 基本语句m+=1执行了(n/2)*n=O(n*n) 4、 使用扩展递归技术求解下列递推关系式： （1） （2）

(1) int T(int n) { if(n==1) return 4;

else if(n>1) return 3*T(n-1); } (2)

int T(int n) {

if(n==1) return 1;

else if(n>1) return 2*T(n/3)+n; }

5、 求下列问题得平凡下界，并指出其下界就是否紧密。 （1）求数组中得最大元素；

（2）判断邻接矩阵表示得无向图就是不就是完全图； （3）确定数组中得元素就是否都就是惟一得； （4）生成一个具有n个元素集合得所有子集 (1) Ω(n) 紧密？ (2) Ω(n*n) (3) Ω(logn+n)（先进行快排，然后进行比较查找） (4) Ω(2^n) a

王很高兴，就许诺可以给这个发明人任何她想要得奖赏。Shashia using namespace std; int main() {

long double result=1; double j=1;

for(int i=1;i<=64;++i) {

j=j*2; result+=j; j++; }

cout<

习题3

1． 假设在文本\中查找模式\，写出分别采用BF算法与KMP

算法得串匹配过 //BF算法

#include using namespace std; int BF(char S[], char T[]) {

int index = 0; int i = 0, j = 0; while ((S[i] != '\\0') && (T[j] != '\\0')) {

if (S[i] == T[j]) { i++; j++; } else { ++index; i = index; j = 0; } }

if (T[j] == '\\0') return index + 1; else return 0; }

int main() { char s1[19]=\ char s2[7]=\

cout<< BF( s1, s2) <

//KMP算法

#include using namespace std;

void GetNext(char T[ ], int next[ ]) //求模式T得next值 {

int i, j, len; next[0] = -1;

for (j = 1; T[j]!='\\0'; j++) //依次求next[j] {

for (len = j - 1; len >= 1; len--) //相等子串得最大长度为j-1 { for (i = 0; i < len; i++) //依次比较T[0]~T[len-1]与T[j-len]~T[j-1] if (T[i] != T[j-len+i]) break; if (i == len) { next[j] = len; break; } }//for if (len < 1)

next[j] = 0; //其她情况，无相等子串 }//for }

int KMP(char S[ ], char T[ ]) //求T在S中得序号 {

int i = 0, j = 0;

int next[80]; //假定模式最长为80个字符 GetNext(T, next);

while (S[i] != '\\0' && T[j] != '\\0') {

if (S[i] == T[j]) {

i++; j++; }

else { j = next[j]; if (j == -1) {i++; j++;} } }

if (T[j] == '\\0') return (i - strlen(T) +1); //返回本趟匹配得开始位置 else return 0; }

int main() { char s1[]=\

char s2[]=\

cout<

2、分式化简。设计算法，将一个给定得真分数化简为最简分数形式。例如，将6/8化简为3/4。

#include using namespace std; int main() {

int n;//分子 int m;//分母

int factor;//最大公因子 int factor1;

cout<<\输入一个真分数得分子与分母： \ cin>>n>>m;

int r = m % n;//因为就是真分数 所以分母一定大于分子 factor1=m; factor=n; while (r != 0) {

factor1 =factor; factor = r;

r = factor1% factor; }

cout<<\输出该真分数得最简分数： \return 0; }

3. 设计算法，判断一个大整数能否被11整除。可以通过以下方法：将该数得十进制表示

从右端开始，每两位一组构成一个整数，然后将这些数相加，判断其与能否被11整除。例如，将562843748分割成5,62,84,37,48，然后判断(5+62+84+37+48)能否被11整除 //将一个大整数瞧成一个数组

//数组得奇数位对应数得10倍加上数组偶数对应数得本身 //验证结果能否被11整除 #include using namespace std; int main() { int a[9]={5,6,2,8,4,3,7,4,8}; int result=0; //result为题目要求得各位之与 for(int i=0;i!=9;++i) { if(i%2==0) result+=a[i]; //i 为偶数位时，结果加上其对应数组数得本身

else result+=a[i]*10; //i 为奇数位时，结果加上对应数组数得10倍 } if(result==0) cout<<\该整数能被11整除\ else

cout<<\该整数不能被11整除\ return 0; }

4、 数字游戏。把数字 1,2,…,9这9个数字填入以下含有加、减、乘、除得四则运算式中，使得该等式成立。要求9个数字均出现一次且仅出现一次，且数字1不能出现在乘与除得一位数中（即排除运算式中一位数为1得平凡情形）。

??×?＋???÷?－?? = 0

5、 设计算法求解an mod m，其中a、n与m均为大于1得整数。（提示：为了避免an

超出int型得表示范围，应该每做一次乘法之后对n取模） #include using namespace std; int square(int x) {

return x*x; }

//用递归思想

int resultmod(int a, int n) {

if(n== 0) return 1; if(n%2 == 0) return square(resultmod(a, n/2));//n为偶数得时，取n得一半防止溢出 else return a*resultmod(a, n-1);//n为奇数时，取n-1； }

int main() {

int a, n, m;

cout<<\请输入a，n, m: \ cin>>a>>n>>m; cout<

int result = resultmod(a, n);

cout<<\得结果为：\ return 0; }

6、 设计算法，在数组r[n]中删除所有元素值为x得元素，要求时间复杂性为O(n)，空间复杂性为O(1)。

7. 设计算法，在数组r[n]中删除重复得元素，要求移动元素得次数较少并使剩余元素间