第3章〓基本算法设计方法
3．1单项选择题及其参考答案
1． 穷举法的适用范围是。
A． 一切问题
B. 解的个数极多的问题
C. 解的个数有限且可一一列举
D. 不适合设计算法
答： 穷举法作为一种算法设计基本方法并非万能的，主要适合于解个数有限且可一一列举的问题的求解。答案为C。
2． 如果一个4位数恰好等于它的各位数字的4次方和，则这个4位数称为玫瑰花数。例如1634=14+64+34+44，则1634是一个玫瑰花数。若想求出4位数中所有的玫瑰花数，可以采用的问题解决方法是。
A. 递归法
B. 穷举法
C. 归纳法
D. 都不适合
答： 4位数的范围是1000~9999，可以一一枚举。答案为B。
3． 有一个数列，递推关系是a1=12，an+1=anan+1，则求出的通项公式是。
A. an=1n+1
B. an=1n
C. an=12n
D. an=n2
答： 采用不完全归纳法，a1=12，a2=13，a3=14，a4=15 ，…，an=1n+1，可以采用数学归纳法证明这个结论的正确性。答案为A。
4． 猜想1=1，1-4=-(1+2)，1-4+9=1+2+3，…的第5个式子是。
A. 12+22-32-42+52=1+2+3+4+5
B． 12+22-32+42-52=-(1+2+3+4+5)
C. 12-22+32-42+52=-(1+2+3+4+5)
D. 12-22+32-42+52=1+2+3+4+5
答： 推导如下。
n=1，12=1
n=2，1-4=1-22=-(1+2)
n=3，1-4+9=12-22+32=1+2+3
n=4，12-22+32-42=-(1+2+3+4)
n=5，12-22+32-42+52=1+2+3+4+5
答案为D。
5． 对于迭代法，下面的说法不正确的是。
A. 需要确定迭代模型
B. 需要建立迭代关系式
C. 需要对迭代过程进行控制，要考虑什么时候结束迭代过程
D. 不需要对迭代过程进行控制
答： 迭代法先确定迭代变量，再对迭代过程进行控制。答案为D。
6． 设计递归算法的关键是。
A. 划分子问题
B. 提取递归模型
C. 合并子问题
D. 求解递归出口
答： 递归模型是递归算法的核心，反映递归算法的本质。答案为B。
7． 若一个问题的求解既可以用递归算法，也可以用迭代算法，则往往用①算法，因为②。
① A．先递归后迭代
B. 先迭代后递归
C. 递归
D. 迭代
② A．迭代的效率比递归高
B. 递归宜于问题分解
C. 递归的效率比迭代高
D. 迭代宜于问题分解
答： 一般情况下求解同一个问题的迭代算法比递归算法的效率高。答案是①D，②A。
8． 递归函数f(n)=f(n-1)+n(n>1)的递归出口是。
A. f(-1)=0
B. f(1)=1
C. f(0)=1
D. f(n)=n
答： f(n)=f(n-1)+n(n>1)是递归体，递归出口对应n=1的情况。答案为B。
9． 递归函数f(n)=f(n-1)+n(n>1)的递归体是。
A. f(-1)=0
B. f(1)=1
C. f(n)=n
D. f(n)=f(n-1)+n
答： f(n)=f(n-1)+n(n>1)本身就是递归体。答案为D。
10． 有以下递归算法，f(123)的输出结果是。
void f(int n)
{if(n>0)
{printf("%d",n%10);
f(n/10);
}
}
A. 321
B. 123
C. 6
D. 以上都不对
答： 该算法属于先合后递的递归算法。在执行f(123)时先输出123%10=3，再调用f(12)输出2，最后调用f(1)输出1。答案为A。
11． 有以下递归算法，f(123)的输出结果是。
void f(int n)
{if(n>0)
{f(n/10);
printf("%d",n%10);
}
}
A. 321
B. 123
C. 6
D. 以上都不对
答： 该算法属于先递后合的递归算法。执行过程是f(123)→f(12)→f(1)，返回时依次输出1，2和3。答案为B。
12． 整数单链表h是不带头结点的，结点类型ListNode为(val，next)，则以下递归算法中隐含的递归出口是。
void f(ListNode* h)
{if(h!=NULL)
{printf("%d ",h->val);
f(h->next);
}
}
A. if(h!=NULL) return;
B. if(h==NULL) return 0;
C. if(h==NULL) return;
D. 没有递归出口
答： 任何递归算法都包含递归出口，该递归算法是正向输出单链表h中的结点值，递归出口是h为空的情况。答案为C。
13． T(n)表示输入规模为n时的算法效率，以下算法中性能最优的是。
A. T(n)= T(n-1)+1，T(1)=1
B. T(n)=2n2
C. T(n)= T(n/2)+1，T(1)=1
D. T(n)=3nlog2n
答： 对于选项A，采用直接展开法求出T(n)=Θ(n)。对于选项B，T(n)=Θ(n2)。对于选项C，采用主方法，a=1，b=2，f(n)=O(1)，nlogba=1与f(n)的阶相同，则T(n)=Θ(log2n)。对于选项D，T(n)=Θ(nlog2n)。答案为C。
3.2问答题及其参考答案
1． 采用穷举法解题时的常用列举方法有顺序列举、排列列举和组合列举，问求解以下问题应该采用哪一种列举方法？
(1) 求m~n的所有素数。
(2) 在数组a中选择出若干元素，它们的和恰好等于k。
(3) 有n个人合作完成一个任务，他们采用不同的排列顺序，则完成该任务的时间不同，求最优完成时间。
答： (1) 采用顺序列举。
(2) 采用组合列举。
(3) 采用排列列举。
2． 许多系统用户登录时需要输入密码，为什么还需要输入已知的验证码？
答： 一般密码长度有限，密码由数字和字母等组成，可以采用穷举法枚举所有可能的密码，对每个密码进行试探。如果加入验证码，就会延迟每次试探的时间，从而使得这样破解密码变成几乎不可能。
3． 什么是递归算法？递归模型由哪两个部分组成？
答： 递归算法是指直接或间接地调用自身的算法。递归模型由递归出口和递归体两个部分组成。
4． 比较迭代算法与递归算法的异同。
答： 迭代算法与递归算法的相同点是都是解决“重复操作”的机制，不同点是递归算法往往比迭代算法耗费更多的时间(调用和返回均需要额外的时间)与存储空间(用来保存不同次调用情况下变量的当前值的栈空间)，每个迭代算法原则上总可以转换成与它等价的递归算法，反之不然。
5． 有一个含n(n>1)个整数的数组a，写出求其中最小元素的递归定义。
答： 设f(a，i)表示a［0．．i］(共i+1个元素)中的最小元素，为大问题，则f(a，i-1)表示a［0．．i-1］(共i个元素)中的最小元素，为小问题。对应的递归定义如下：
f(a，i)=a［0］当i=0时
f(a，i)=min(f(a，i-1)，a［i］)其他
则f(a，n-1)求数组a中n个元素的最小元素。
6． 有一个含n(n>1)个整数的数组a，写出求所有元素和的递归定义。
答： 设f(a，i)表示a［0．．i］(共i+1个元素)中所有元素的和，为大问题，则f(a，i-1)表示a［0．．i-1］(共i个元素)中所有元素的和，为小问题。对应的递归定义如下：
f(a，i)=a［0］当i=0时
f(a，i)=f(a，i-1)+a［i］其他
则f(a，n-1)求数组a中n个元素的和。
7． 利用整数的后继函数succ写出x+y(x和y都是正整数)的递归定义。
答： 设f(x，y)=x+y，对应的递归定义如下。
f(x，y)=y当x=0时
f(x，y)=x当y=0时
f(x，y)=f(succ(x)，succ(y))+2其他
8． 有以下递归算法，则f(f(7))的结果是多少？
int f(int n)
{if(n<=3)
return 1;
else
return f(n-2)+f(n-4)+1;
}
答： 先求f(7)，如图3．1(a)所示，求出f(7)=5后，再求f(5)，如图3．1(b)所示，求出f(5)=3后，所以f(f(7))的结果是3。
9． 有以下递归算法，则f(3，5)的结果是多少？
int f(int x,int y)
{if(x<=0 || y<=0)
return 1;
else
return 3*f(x-1,y/2);
}
答： 求f(3,5)的过程如图3．2所示，求出f(3，5)=27。
图3．1求f(f(7))的过程
图3．2求f(3,5)的过程
10． 采用直接展开法求以下递推式：
T(1)=1
T(n)=T(n-1)+n当n>1时
答： 求T(n)的过程如下。
T(n)=T(n-1)+n=［T(n-2)+(n-1)］+n=T(n-2)+n+(n-1)
=T(n-3)+n+(n-1)+(n-2)
=…
=T(1)+n+(n-1)+…+2
=n+(n-1)+…+2+1=n(n+1)/2=Θ(n2)
11． 采用递归树方法求解以下递推式：
T(1)=1
T(n)=4T(n/2)+n当n>1时
解： 构造的递归树如图3．3所示，第1层的问题规模为n，第2层的子问题的问题规模为n/2，以此类推，当展开到第k+1层时，其规模为n/2k=1，所以递归树的高度为log2n+1。
第1层有一个结点，其时间为n，第2层有4个结点，其时间为4(n/2)=2n，以此类推，第k层有4k-1个结点，每个子问题的规模为n/2k-1，其时间为4k-1(n/2k-1)=2k-1n。叶子结点的个数为n个，其时间为n。将递归树每一层的时间加起来，可得：
T(n)=n+2n+…+2k-1n+…+n≈n×2log2n=Θ(n2)。
图3．3一棵递归树
12． 采用主方法求解以下递推式：
(1) T(n)=4T(n/2)+n
(2) T(n)=4T(n/2)+n2
(3) T(n)=4T(n/2)+n3
答： (1) 这里a=4，b=2，f(n)=n。nlogba=nlog24=n2，显然f(n)的阶小于nlogba，满足主方法中的情况①，所以T(n)=Θ(nlogba)=Θ(n2)。
(2) 这里a=4，b=2，f(n)=n2。nlogba=nlog24=n2，显然f(n)与nlogba同阶，满足主方法中的情况②，T(n)=Θ(nlogbalog2n)=Θ(n2log2n)。
(3) 这里a=4，b=2，f(n)=n3。nlogba=nlog24=n2，显然f(n)的阶大于nlogba。另外，对于足够大的n，af(n/b)=4×n3/8=n3/2≤cf(n)，这里c=1/2，满足正规性条件，则有T(n)=Θ(f(n))=Θ(n3)。
13． 有以下算法，分析其时间复杂度。
void f(int n)
{for(int i=1;i<=n;i++)
{for(int j=1;j<=i;j++)
printf("%d %d %d＼n",i,j,n);
}
if(n>0)
{for(int i=1;i<=4;i++)
f(n/2);
}
}
答： 算法中两重for的执行次数=∑ni=1∑ij=11=∑ni=1i=n(n+1)2=Θ(n2)。对应的时间递推式如下：
T(n)=1当n=0时
T(n)=4T(n/2)+n2其他
采用主方法，a=4，b=2，f(n)=n2，nlogba=n2，与f(n)的阶相同，则T(n)=Θ(n2log2n)。
14． 分析《教程》3．4．3节中求1~n的全排列的递归算法perm21(n，n)的时间复杂度。
答： perm21(n，n)用于求1~n的全排列Pn，设其执行时间为T(n)，它首先调用perm2(n，n-1)求出1~n-1的全排列Pn-1，该小问题的执行时间为T(n-1)，再对于Pn-1中每个集合元素(共(n-1)!个集合元素)的每个位置(共n个位置)插入n，合并结果得到Pn，执行次数为n(n-1)!=n!。所以递推式如下：
T(1)=1求P1为常量
T(n)=T(n-1)+n!当n>1时
令T(n)=n!g(n)(因为1~n全排列中的排列个数为n!)，则
T(n-1)=(n-1)!g(n-1)
代入T(n)=T(n-1)+n!中得到：
n!g(n)= (n-1)!g(n-1)+n!
两边乘以n：
nn!g(n)=n(n-1)!g(n-1)+nn!=n!g(n-1)+nn!
两边除以n!：
ng(n)=g(n-1)+n
得到如下递推式：
g(1)=1
g(n)=g(n-1)/n+1当n>1时
采用直接展开法，g(n)=g(n-1)/n+1=g(n-2)/(n(n-1))+1/n+1=…≤2。
T(n)=n!g(n)≤2n!
因此有T(n)=O(n!)。
15*． 有以下多项式：
f(x，n)=x-x33!+x55!-x77!+…+(-1)nx2n+1(2n+1)!
给出求f(x，n)值的递推式，分析其求解的时间复杂度。
答： 为了简单，省略x参数。
f(1)=x，g(1)=x
f(2)=x-x33!=f(1)+(-1)×g(1)×x23×2，g(2)=(-1)×g(1)×x22×3
f(3)=x-x33!+x55!=f(2)+(-1)×g(2)×x24×5，g(3)=(-1)×g(2)×x24×5
可以推出求f(n)的递推式如下：
f(1)=x，g(1)=x
g(n)=(-1)×g(n-1)×x2(2n-2)(2n-1)
f(n)=f(n-1)+g(n)
设求f(n)的执行时间为T(n)，求f(n)需要求出g(n)，但它们是同时计算的，也就是说T(n)表示的是求f(n)和g(n)的时间，对应的执行时间递推式如下：
T(1)=O(1)
T(n)=T(n-1)+O(1)当n>1时
可以推出T(n)=O(n)。
3.3算法设计题及其参考答案
1． 有3种硬币若干个，面值分别是1分、2分、5分，如果要凑够1毛5，设计一个算法求有哪些组合方式，共多少种组合方式。
解： 采用穷举法，设所需1分、2分和5分硬币的个数分别为i、j和k，显然有0≤i≤15，0≤j≤7，0≤k≤3，约束条件为i+2j+5k=15，用cnt表示组合方式数。对应的算法如下：
int solve()
{int cnt=0;
for(int i=0;i<=15;i++)
{for(int j=0;j<=7;j++)
{for(int k=0;k<=3;k++)
{if (i+(2*j)+(5*k)==15)
{printf("一分硬币%d个，两分硬币%d个，五分硬币%d个＼n",i,j,k);
cnt++;
}
}
}
}
return cnt;
}
2． 有一个整数序列是0，5，6，12，19，32，52，…，其中第1项为0，第2项为5，第3项为6，以此类推，采用迭代算法和递归算法求该数列的第n(n≥1)项。
解： 设f(n)为数列的第n项，则
f(1)=0
f(2)=5
f(3)=6=f(1)+f(2)+1
f(4)=12=f(2)+f(3)+1
…
可以归纳出当n>2时有f(n)=f(n-2)+f(n-1)+1。对应的迭代算法如下：
int sequence1(int n)//迭代算法
{int a=0,b=5,c;
if(n==1)
return a;
else if(n==2)
return b;
else
{for(int i=3;i<=n;i++)
{c=a+b+1;
a=b;
b=c;
}
return c;
}
}
对应的递归算法如下：
int sequence2(int n)//递归算法
{if(n==1)
return 0;
else if(n==2)
return 5;
else
return sequence2(n-2)+sequence2(n-1)+1;
}
3． 给定一个正整数n(1≤n≤100)，采用迭代算法和递归算法求s=1+(1+2)+(1+2+3)+…+(1+2+…+n)。
解： 设curs=1+2+…+(i-1)，则curs+i便是1+2+…+i，用ans累加所有的curs(初始为0)。对应的迭代算法如下：
int Sum1(int n) //迭代算法
{int ans=0;
int curs=0;
for(int i=1;i<=n;i++)
{curs+=i;
ans+=curs;
}
return ans;
}
设f(n)=1+(1+2)+(1+2+3)+…+(1+2+…+n)，则f(n-1)=1+(1+2)+(1+2+3)+…+(1+2+…+n-1)，两式相减得到f(n)-f(n-1)=(1+2+…+n)=n(n+1)/2，则递归模型如下：
f(1)=1
f(n)=f(n-1)+n(n+1)/2当n>1时
对应的递归算法如下：
int Sum2(int n) //递归算法
{if(n==1)
return 1;
else
return Sum2(n-1)+n*(n+1)/2;
}
4． 一个数列的首项a1=0，后续奇数项和偶数项的计算公式分别为a2n=a2n-1+2，a2n+1=a2n-1+a2n-1，设计一个递归算法求数列的第n项。
解： 设f(m)计算数列的第m项。当m为偶数时，不妨设m=2n，则2n-1=m-1，所以有f(m)=f(m-1)+2； 当m为奇数时，不妨设m=2n+1，则2n-1=m-2，2n=m-1，所以有f(m)=f(m-2)+f(m-1)-1。对应的递归算法如下：
int sequence(int m) //递归算法
{if (m==1)
return 0;
else if (m%2==0)
return sequence(m-1)+2;
else
return sequence(m-2)+sequence(m-1)-1;
}
5． 设计一个递归算法用于翻转一个非空字符串s。
解： 设f(str，i)返回s［i．．n-1］(共n-i个字符)的翻转字符串，为大问题，f(str，i+1)返回s［i．．n-1］(共n-i-1个字符)的翻转字符串，为小问题，i≥n时空串的翻转结果是空串。对应的递归模型如下：
f(s，i)=""当i≥n时
f(s，i)=f(s，i+1)+s［i］其他情况
对应的递归算法如下：
string reverse1(string s,int i)//被reverse算法调用
{if (i>=s.size())
return "";
else
return reverse1(s,i+1)+s［i］;
}
string reverse(string s) //递归算法
{
return reverse1(s,0);
}
6． 对于不带头结点的非空整数单链表h，设计一个递归算法求其中值为x的结点的个数。
解： 设f(h，x)返回单链表h中值为x的结点的个数，为大问题，f(h->next，x)返回子单链表h->next中值为x的结点的个数，为小问题，空单链表的结点个数为0。对应的递归模型如下：
f(h，x)=0当h=NULL时
f(h，x)=f(h->next，x)+1当h->val=x时
f(h，x)=f(h->next，x)其他
对应的递归算法如下：
int Count(ListNode* h,int x)
{if(h==NULL)
return 0;
else if(h->val==x)
return Count(h->next,x)+1;
else
return Count(h->next,x);
}
7． 对于不带头结点的非空单链表h，设计一个递归算法删除其中第一个值为x的结点。
解： 设f(h，x)删除单链表h中第一个值为x的结点，为大问题，f(h->next，x)删除子单链表h->next中第一个值为x的结点，为小问题。对应的递归模型如下：
f(h，x) ≡ 不做任何事情当h=NULL时
f(h，x) ≡ 删除h结点，h=h->next当h->val=x时
f(h，x) ≡ f(h->next，x)其他
对应的递归算法如下：
void Delfirstx(ListNode* &h,int x)//递归算法:删除单链表h中第一个值为x的结点
{if (h==NULL) return;
if (h->val==x)
{ListNode *p=h;
h=h->next;
free(p);
}
else
Delfirstx(h->next,x);
}
8． 对于不带头结点的非空单链表h，设计一个递归算法删除其中所有值为x的结点。
解： 设f(h，x)删除单链表h中所有值为x的结点，为大问题，f(h->next，x)删除子单链表h->next中所有值为x的结点，为小问题。对应的递归模型如下：
f(h，x) ≡ 不做任何事情当h=NULL时
f(h，x) ≡ 删除h结点，h=h->next; f(h，x)当h->val=x时
f(h，x) ≡ f(h->next，x)其他
对应的递归算法如下：
void Delallx(ListNode* &h,int x)//递归算法:删除单链表h中所有值为x的结点
{if (h==NULL) return;
if (h->val==x)
{ListNode *p=h;
h=h->next;
free(p);
Delallx(h,x);
}
else
Delallx(h->next,x);
}
9． 假设二叉树采用二叉链存储结构存放，结点值为整数，设计一个递归算法求二叉树b中所有叶子结点值的和。
解： 设f(b)返回二叉树b中所有叶子结点值的和，为大问题，f(b->left)和f(b->right)分别返回二叉树b左、右子树中所有叶子结点值的和，为两个小问题。对应的递归模型如下：
f(b)=0当b=NULL时
f(b)=b->val当b结点为叶子结点时
f(b)=f(b->left)+f(b->right)其他
对应的递归算法如下：
int LeafSum(TreeNode*b) //递归算法：求二叉树b中所有叶子结点值的和
{if (b==NULL) return 0;
if (b->left==NULL && b->right==NULL)
return b->val;
int lsum=LeafSum(b->left);
int rsum=LeafSum(b->right);
return lsum+rsum;
}
10． 假设二叉树采用二叉链存储结构存放，结点值为整数，设计一个递归算法求二叉树b中第k(1≤k≤二叉树b的高度)层所有结点值的和(根结点层次为1)。
解： 设f(b，h，k)返回二叉树b中第k层所有结点值的和(初始时b指向根结点，h置为1表示结点b的层次)。其递归模型如下：
f(b，h，k)=0当b=NULL时
f(b，h，k)=b->val当h=k时
f(b，h，k)=f(b->left，h+1，k)+f(b->right，h+1，k)当h<k时
f(b，h，k)=0其他
对应的递归算法如下：
int LevelkSum1(TreeNode*b,int h,int k) //被LevelkSum算法调用
{if(b==NULL)
return 0;
if(h==k)
return b->val;
if(h<k)
{int lsum=LevelkSum1(b->left,h+1,k);
int rsum=LevelkSum1(b->right,h+1,k);
return lsum+rsum;
}
else
return 0;
}
int LevelkSum(TreeNode*b,int k) //递归算法：求二叉树b中第k层所有结点值的和
{
return LevelkSum1(b,1,k);
}
11． 设计将十进制正整数n转换为二进制数的迭代算法和递归算法。
解： 设f(n)为n的二进制数。求出n%2和n/2，n%2作为结果二进制数的最高位，f(n/2)作为小问题。假设f(n/2)已经求出，将n%2作为其最高位得到f(n)的结果。对应的递归模型如下：
f(n) = 空当n≤0时
f(n) = n%2f(n/2)当n>0时
其中xy表示x作为y的最高位。
采用数组存放转换的二进制数，每个元素表示一个二进制位，由于需要将n%2的二进制位插入最前面，所以改为用deque<int>容器存放转换的二进制数。对应的迭代法算法如下：
deque<int> trans1(int n) //迭代算法
{deque<int> ans;
while(n>0)
{int d=n%2; //求出二进制位d
ans.push_front(d); //将d作为高位的元素
n/=2; //新值取代旧值
}
return ans;
}
对应的递归算法如下：
deque<int> trans2(int n) //递归算法
{if(n<=0) return {};
deque<int> ans=trans2(n/2); //先递后合
int d=n%2;
ans.push_back(d);
return ans;
}
12． 在《教程》3．2．2节中采用迭代算法实现直接插入排序，请设计等效的递归算法。
解： 直接插入排序递归算法的设计思路参考《教程》3．2．2节和3．4．2节。采用先递后合和先合后递两种递归算法如下：
void Insert(vector<int>&R,int i) //将R［i］有序插入R［0..i-1］中
{int tmp=R［i］;
int j=i-1;
do //找R［i］的插入位置
{R［j+1］=R［j］; //将大于R［i］的元素后移
j--;
} while(j>=0 && R［j］>tmp); //直到R［j］<=tmp为止
R［j+1］=tmp; //在j+1处插入R［i］
}
/***先递后合算法*****************************/
void InsertSort21(vector<int> &R,int i) //递归的直接插入排序
{if(i==0) return;
InsertSort21(R,i-1);
if (R［i］<R［i-1］) //反序时
Insert(R,i);
}
void InsertSort2(vector<int> &R) //递归算法：直接插入排序
{int n=R.size();
InsertSort21(R,n-1);
}
/***先合后递算法*****************************/
void InsertSort31(vector<int> &R,int i) //递归的直接插入排序
{int n=R.size();
if(i<1 || i>n-1) return;
if (R［i］<R［i-1］) //反序时
Insert(R,i);
InsertSort31(R,i+1);
}
void InsertSort3(vector<int> &R) //递归算法：直接插入排序
{
InsertSort31(R,1);
}
13． 在《教程》3．3．2节中采用迭代算法实现简单选择排序，请设计等效的递归算法。
解： 简单选择排序递归算法的设计思路参考《教程》3．3．2节和3．4．2节。采用先递后合和先合后递两种递归算法如下：
void Select(vector<int>& R,int i) //在R［i..n-1］中选择最小元素交换到R［i］位置
{int minj=i; //minj表示R［i..n-1］中最小元素的下标
for (int j=i+1;j<R.size();j++) //在R［i..n-1］中找最小元素
{if (R［j］<R［minj］)
minj=j;
}
if (minj!=i) //若最小元素不是R［i］
swap(R［minj］,R［i］); //交换
}
/***先递后合算法*****************************/
void SelectSort21(vector<int>& R,int i) //递归的简单选择排序
{if (i==-1) return; //满足递归出口条件
SelectSort21(R,i-1);
Select(R,i);
}
void SelectSort2(vector<int>& R) //递归的简单选择排序
{
SelectSort21(R,R.size()-2);
}
/***先合后递算法*****************************/
void SelectSort31(vector<int>& R,int i) //递归的简单选择排序
{int n=R.size();
if (i==n-1) return; //满足递归出口条件
Select(R,i);
SelectSort31(R,i+1);
}
void SelectSort3(vector<int>& R) //递归的简单选择排序
{
SelectSort31(R,0);
}
14． 在《教程》3．4．2节中采用递归算法实现冒泡排序，请设计等效的迭代算法。
解： 冒泡排序迭代算法的设计思路参考《教程》3．4．2节和3．3．2节。对应的算法如下：
void Bubble(vector<int>& R,int i,bool& exchange)//在R［i..n-1］中冒泡最小元素到R［i］位置
{int n=R.size();
for (int j=n-1;j>i;j--)//无序区元素比较,找出最小元素
{if (R［j-1］>R［j］) //当相邻元素反序时
{swap(R［j］,R［j-1］); //R［j］与R［j-1］进行交换
exchange=true; //本趟排序发生交换置exchange为true
}
}
}
void BubbleSort1(vector<int>& R) //迭代算法：冒泡排序
{int n=R.size();
bool exchange;
for (int i=0;i<n-1;i++) //进行n-1趟排序
{exchange=false; //本趟排序前置exchange为false
Bubble(R,i,exchange);
if (exchange==false) //本趟未发生交换时结束算法
return;
}
}
15． 在《教程》3．3．4节中采用迭代算法求1~n的幂集，请设计等效的递归算法。
解： 用Mi表示1~i的幂集。对应的递归模型如下：
M1={{}，{1}}
Mi=Mi-1∪Ai当i>1时
其中Ai=appendi(Mi-1，i)。幂集用vector<vector<int>>容器存放，其中每个vector<int>类型的元素表示幂集中的一个集合。大问题是求{1~i}的幂集，小问题是求{1~i-1}的幂集。采用先递后合和先合后递两种递归算法如下：
vector<vector<int>> appendi(vector<vector<int>> Mi_1,int i)
//向Mi_1中每个集合元素的末尾添加i
{vector<vector<int>> Ai=Mi_1;
for(int j=0;j<Ai.size();j++)
Ai［j］.push_back(i);
return Ai;
}
/***先递后合算法*****************************/
vector<vector<int>> pset(int n,int i) //递归算法
{if(i==1)
return {{},{1}};
else
{vector<vector<int>> Mi_1=pset(n,i-1); //递归求出Mi_1
vector<vector<int>> Mi=Mi_1; //Mi置为Mi_1
vector<vector<int>> Ai=appendi(Mi_1,i);
for(int j=0;j<Ai.size();j++) //将Ai中的所有集合元素添加到Mi中
Mi.push_back(Ai［j］);
return Mi; //返回Mi
}
}
vector<vector<int>> subsets2(int n) //递归算法
{
return pset(n,n);
}
/***先合后递算法*****************************/
vector<vector<int>> pset(vector<vector<int>> M,int n,int i) //递归算法
{vector<vector<int>> A=appendi(M,i); //求A
for(int j=0;j<A.size();j++) //将A中的所有集合元素添加到M中
M.push_back(A［j］);
if(i==n) //已经求出结果时返回M
return M;
else //否则递归调用
return pset(M,n,i+1);
}
vector<vector<int>> subsets3(int n) //递归算法
{vector<vector<int>> M={{},{1}}; //M存放{1-n}的幂集,初始时置为M1
if(n==1)
return M;
else
return pset(M,n,2);
}
16． 在《教程》3．4．3节中采用递归算法求1~n的全排列，请设计等效的迭代算法。
解： 全排列是一个两层集合，采用vector<vector<int>>容器存放。首先置Pi=P1={{1}}，i从2到n循环： 置Pi-1=Pi，清空Pi，在Pi-1中每个集合元素的每个位置插入i，将结果添加到Pi中，最后返回Pi。对应的迭代法算法如下：
vector<int> Insert(vector<int> s,int i,int j) //在s的位置j插入i
{vector<int>::iterator it=s.begin()+j; //求出插入位置
s.insert(it,i); //插入整数i
return s;
}
vector<vector<int>> CreatePi(vector<int> s,int i) //在s集合中i-1到0的位置插入i
{vector<vector<int>> tmp;
for (int j=s.size();j>=0;j--) //在s的每个位置插入i
{vector<int> s1=Insert(s,i,j);
tmp.push_back(s1); //添加到Pi中
}
return tmp;
}
vector<vector<int>> Perm1(int n) //用迭代法求1~n的全排列
{vector<vector<int>> Pi; //存放1~i的全排列
Pi.push_back({1});
vector<vector<int>> Pi_1; //存放1~i-1的全排列
for (int i=2;i<=n;i++) //迭代循环：添加2~n
{Pi_1=Pi; //新值取代旧值
Pi.clear();
for (auto it=Pi_1.begin();it!=Pi_1.end();it++)
{vector<vector<int>> tmp=CreatePi(*it,i); //在it集合中插入i得到tmp
for(int k=0;k<tmp.size();k++)
Pi.push_back(tmp［k］); //将tmp的全部元素添加到Pi中
}
}
return Pi;
}
17． 在《教程》3．4．3节中求1~n的全排列的递归算法采用的是先递后合，请设计等效的先合后递的递归算法。
解： 在先合后递的递归算法中，P首先置为P1={{1}}，再依次产生P2，…，Pn。也就是说当i<=n时，将P看成Pi-1，在Pi-1中每个集合元素的每个位置插入i得到Pi，再递归添加i+1； 若i>n，说明已经生成1~n的全排列P，返回P即可。对应的递归算法如下：
vector<vector<int>> perm31(vector<vector<int>> P,int n,int i)//先合后递的递归算法
{if(i<=n)
{vector<vector<int>> Pi;
for (auto it=P.begin();it!=P.end();it++) //由P产生Pi
{vector<vector<int>> tmp=CreatePi(*it,i);//在it集合中插入i得到tmp
for(int k=0;k<tmp.size();k++)
Pi.push_back(tmp［k］); //将tmp的全部元素添加到Pi中
}
return perm31(Pi,n,i+1);
}
else return P;
}
vector<vector<int>> Perm3(int n) //用递归法求1-n的全排列
{vector<vector<int>> P={{1}}; //P存放{1-n}的全排列,初始时置为P1
if(n==1)
return P;
else
return perm31(P,n,2);
}
18． 给定一个整数数组a，打印一个和三角形，其中第一层包含数组元素，以后每一层的元素数比上一层少一个，该层的元素是上一层中连续两个元素的和，设计一个算法求最高层的整数。例如，a={1，2，3，4，5}，对应的和三角形如下：
48
2028
81216
3579
12345
求出的最高层的整数为48。
解法1： 设f(a)为数组a的和三角形中最高层的整数，为大问题。假设a中含n个整数，分为两种情况：
① 当n=1时，a［0］就是a的和三角形中最高层的整数，直接返回a［0］。
② 当n>1时，由a中两两元素相加得到数组b，b中的元素个数为n-1，求f(b)是对应的小问题，此时返回f(b)即可。
对应的递归算法如下：
int solve1(vector<int>&a) //解法1：递归算法
{int n=a.size();
if (n==1)
return a［0］;
else
{vector<int> b(n-1);
for (int i=0;i<n-1;i++)
b［i］=a［i］+a［i+1］;
return solve1(b);
}
}
解法2： 采用迭代法。定义一个队列qu，先将a中的所有元素进队，当队中元素个数大于1时循环： 对于队中的n个元素，出队n次，每次求出相邻元素和后进队，共进队n-1次。当队中只有一个元素时返回该元素。对应的迭代算法如下：
int solve2(vector<int>&a) //解法2：迭代算法
{int n=a.size();
if (n==1)
return a［0］;
else
{queue<int> qu;
for(int i=0;i<n;i++)
qu.push(a［i］); //a中的所有元素进队
while(qu.size()>1) //循环到队列中只有一个元素时为止
{n=qu.size();
int x=qu.front(); qu.pop(); //出队首元素
for(int i=1;i<n;i++) //循环n-1次
{int y=qu.front(); qu.pop(); //出队元素y
qu.push(x+y); //x+y和进队
x=y; //替换
}
}
return qu.front(); //返回结果
}
}
19． 给定一个含n个元素的整数序列a，设计一个算法求其中两个不同元素相加的绝对值的最小值。
解法1： 采用穷举法，任意两个不同元素求相加的绝对值，比较求最小值ans，算法的时间复杂度为O(n2)。对应的算法如下：
int minabs1(vector<int>&a) //解法1
{int n=a.size();
int ans=0x3f3f3f3f; //初始置为∞
for(int i=0;i<n-1;i++)
{for(int j=i+1;j<n;j++)
{ans=min(ans,abs(a［i］+a［j］));
if(ans==0) return ans; //当结果为0时不必继续
}
}
return ans;
}
解法2： 改进穷举法算法，如果a中元素全部是正数，只需要找到其中两个不同的最小元素，答案就是它们相加的结果，对应的时间复杂度为O(n)。但这里a中可能有负数，那么在这种情况下就变成了求差的绝对值，而差的绝对值最小的两个整数一定是大小最相近的，为此先对数组a递增排序，用low和high前后遍历，求sum=a［low］+a［high］，将最小绝对值保存在ans中，如果sum>0除去a［high］，如果sum<0除去a［low］。算法的时间主要花费在排序上，时间复杂度为O(nlog2n)。对应的算法如下：
int minabs2(vector<int>&a) //解法2
{int n=a.size();
int ans=0x3f3f3f3f; //初始置为∞
sort(a.begin(),a.end()); //递增排序
int low=0,high=n-1;
while(low<high)
{int sum=a［low］+a［high］;
ans=min(ans,abs(sum));
if(ans==0) return ans; //当结果为0时不必继续
if(sum>0) high--;
if(sum<0) low++;
}
return ans;
}
3．4上机实验题及其参考答案
3．4．1求最长重复子串
编写一个实验程序exp31，采用穷举法求字符串s中最长的可重叠重复的子串。例如，s="aaa"，结果是"aa"。
解： 采用穷举法，用maxlen表示s中最长的可重叠重复子串的长度(初始为0)，maxi表示其起始下标。用i遍历字符串s，j从i+1开始找到s［i，curlen］=s［j，curlen］的重复子串(s［i，curlen］表示s中从i下标开始长度为curlen的子串)，若curlen>maxlen，则置maxlen=curlen，maxi=i。最后将s［maxi，maxlen］存放在ans中，并且返回ans。对应的程序如下：
#include <iostream>
#include<vector>
#include <string>
using namespace std;
string longestsubstr(string s)
{int n=s.size();
int i=0,j;
int maxlen=0,maxi,curlen;
while(i<n)
{j=i+1;
while(j<n)
{curlen=0;
while(j<n && s［i+curlen］==s［j+curlen］)
curlen++;
if(curlen>maxlen)
{maxi=i;
maxlen=curlen;
}
j++;
}
i++;
}
string ans="";
int cnt=0;
for(int i=maxi;cnt<maxlen;i++,cnt++)
ans+=s［i］;
return ans;
}
int main()
{vector<string> ss{"aababcabcd","aaaaaaaaa","aaaaabaaaabac"};
cout << "实验结果" << endl;
for(int i=0;i<ss.size();i++)
{cout << "串" << ss［i］ << "的结果: ＼t";
cout << longestsubstr(ss［i］) << endl;
}
return 0;
}
上述实验程序的输出结果如图3．4所示。
图3．4exp31．cpp的执行结果
思考题： 如何求字符串s中最长的不重叠的子串。
3．4．2求子矩阵元素和
编写一个实验程序exp32，给定一个m行n列的二维矩阵a(2≤m，n≤100)，其中所有元素为整数。其大量的运算是求左上角为a［i，j］、右下角为a［s，t］(i<s，j<t)的子矩阵的所有元素之和。请设计高效的算法求给定子矩阵的所有元素之和，并用相关数据进行测试。
解： 建立一个m行n列的二维数组b，b［i，j］为a中左上角为a［0，0］、右下角为a［i，j］的子矩阵的所有元素之和，设计算法Sum由数组a求出数组b，时间复杂度为O(m×n)。在求出b数组后，设计算法submat求数组a中左上角为a［i，j］、右下角为a［s，t］(i≤s，j≤t)的子矩阵(用(i，j)-(s，t)表示这样的子矩阵)的所有元素的和，它可以利用数组b来实现，如图3．5所示，(i，j)-(s，t)子矩阵的所有元素之和为b［s］［t］-b［s］［j-1］-b［i-1］［t］+b［i-1］［j-1］，另外考虑两种特殊情况，i=0时如图3．6所示，j=0时如图3．7所示，显然该算法的时间复杂度为O(1)。
这样尽管sum算法的时间复杂度为O(m×n)，但只需要执行一次(除非数组a发生改变)，而submat算法需要大量应用，所以这种设计是十分经济的。
图3．5子矩阵和=b［s］［t］-b［s］［j-1］-b［i-1］［t］+b［i-1］［j-1］
图3．6i=0时子矩阵和=b［s］［t］-b［s］［j-1］
图3．7j=0时子矩阵和=b［s］［t］-b［i-1］［t］
对应的程序如下：
#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> Sum(vector<vector<int>> &a) //由矩阵a求矩阵b
{int m=a.size();
int n=a［0］.size();
vector<vector<int>> b(m,vector<int>(n));
b［0］［0］=a［0］［0］;
for (int i=1;i<m;i++) //求b的第0列
b［i］［0］=b［i-1］［0］+a［i］［0］;
for (int j=1;j<n;j++) //求b的第0行
b［0］［j］=b［0］［j-1］+a［0］［j］;
for (int i=1;i<m;i++) //求b［i］［j］
for (int j=1;j<n;j++)
b［i］［j］=a［i］［j］+b［i-1］［j］+b［i］［j-1］-b［i-1］［j-1］;
return b;
}
int submat(vector<vector<int>> &b,int i,int j,int s,int t) //求［i,j］-［s,t］子矩阵元素和
{int sum;
if (i==0 && j==0)
return b［s］［t］;
else if(i==0)
sum=b［s］［t］-b［s］［j-1］;
else if(j==0)
sum=b［s］［t］-b［i-1］［t］;
else
sum=b［s］［t］-b［s］［j-1］-b［i-1］［t］+b［i-1］［j-1］;
return sum;
}
int main()
{vector<vector<int>> a={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
vector<vector<int>> q={{0,0,1,1},{0,0,2,1},{1,1,2,3},{0,0,2,3},{0,1,2,3}};
int m=a.size();
int n=a［0］.size();
printf("a:＼n");
for(int i=0;i<m;i++)
{for(int j=0;j<n;j++)
printf("%4d",a［i］［j］);
printf("＼n");
}
vector<vector<int>> b=Sum(a);
cout << "实验结果" << endl;
for(int i=0;i<q.size();i++)
{printf("［%d,%d］-［%d,%d］子矩阵元素和=",q［i］［0］,q［i］［1］,q［i］［2］,q［i］［3］);
printf("%d＼n",submat(b,q［i］［0］,q［i］［1］,q［i］［2］,q［i］［3］));
}
return 0;
}
上述实验程序的输出结果如图3．8所示。
图3．8exp32．cpp的执行结果
思考题： 当数组a中的元素a［i］［j］发生改变时，如何设计高效的算法修改对应的b数组(注意仅影响b［i．．m-1．．j．．n-1］的部分)。
3．4．3求n阶螺旋矩阵
编写一个实验程序exp33，采用非递归和递归算法创建一个n(1≤n≤10)阶螺旋矩阵并输出。例如，n=4时的螺旋矩阵如下：
1234
1213145
1116156
10987
解： 采用递归求解时，设f(x，y，start，n)用于创建左上角为(x，y)、起始元素值为start的n阶螺旋矩阵，共n行n列，它是大问题； 则f(x+1，y+1，start，n-2)用于创建左上角为(x+1，y+1)、起始元素值为start的n-2阶螺旋矩阵，共n-2行n-2列，它是小问题，如图3．9所示为n=4时的大问题和小问题。对应的递归模型如下：
f(x，y，start，n)≡不做任何事情当n≤0时
f(x，y，start，n)≡产生只有一个元素的螺旋矩阵当n=1时
f(x，y，start，n)≡产生(x，y)的那一圈； 当n>1时
f(x+1，y+1，start，n-2)
图3．9n=4时的大问题和小问题
非递归算法则是采用循环语句代替递归调用。对应的程序如下：
#include<iostream>
using namespace std;
#define N 15
int s［N］［N］;
int n;
void CreateaLevel(int &start,int ix,int iy,int ex,int ey) //产生一圈的螺旋矩阵元素
{if (ix==ex) //该圈只有一个元素时
s［ix］［iy］=start++;
else
{int curx=ix;
int cury=iy;
while (curx!=ex) //上一行
{s［iy］［curx］=start++;
curx++;
}
while (cury!=ey) //右一列
{s［cury］［ex］=start++;
cury++;
}
while (curx!=ix) //下一行
{s［ey］［curx］=start++;
curx--;
}
while (cury!=iy) //左一列
{s［cury］［ix］=start++;
cury--;
}
}
}
void Spiral1(int n) //非递归创建螺旋矩阵
{int start=1;
int ix=0,iy=0;
int ex=n-1,ey=n-1;
while (ix<=ex && iy<=ey)
CreateaLevel(start,ix++,iy++,ex--,ey--);
}
void Spiral2(int x,int y,int start,int n) //递归创建螺旋矩阵
{if (n<=0) //递归结束条件
return;
if (n==1) //矩阵大小为1时
{s［x］［y］ = start;
return;
}
for (int i=x; i<x+n-1; i++) //上一行
s［y］［i］=start++;
for (int j=y; j<y+n-1; j++) //右一列
s［j］［x+n-1］= start++;
for (int i=x+n-1; i>x; i--) //下一行
s［y+n-1］［i］= start++;
for (int j=y+n-1; j>y; j--) //左一列
s［j］［x］=start++;
Spiral2(x+1,y+1,start,n-2); //递归调用
}
void Display() //输出螺旋矩阵
{for (int i=0; i<n; i++)
{for (int j=0; j<n; j++)
printf("%4d", s［i］［j］);
printf("＼n");
}
}
int main()
{n=5;
printf("非递归方法建立的%d阶螺旋矩阵:＼n",n);
Spiral1(n);
Display();
n=5;
printf("递归方法建立的%d阶螺旋矩阵:＼n",n);
Spiral2(0,0,1,n);
Display();
return 0;
}
上述程序的执行结果如图3．10所示。
图3．10exp33．cpp的执行结果
3．4．4验证汉诺塔问题
《教程》的例38中给出了求解汉诺塔问题的递归算法，请针对该算法推导出移动n盘片时搬动盘片总次数的公式，再用递归算法求出搬动盘片的总次数，前者称为公式求解结果，后者称为递归算法求解结果，判断两者是否相同。编写一个实验程序exp34完成上述功能，并用相关数据进行测试。
解： 设Hanoi(n，x，y，z)中的搬动盘片总次数为C(n)。根据递归算法有以下递归式：
C(n)=1当n=1时
C(n)=2C(n-1)+1当n>1时
则：
C(n)=2［2C(n-2)+1］+1=22C(n-2)+1+21
=23C(n-3)+1+21+22
=…
=2n-1C(1)+1+21+22+…+2n-2
=2n-1
所以移动n盘片时搬动盘片的总次数为2n-1。对应的验证程序如下：
#include<iostream>
#include<cmath>
using namespace std;
int Hanoi(int n,char x,char y,char z)
{if (n==1)
return 1; //搬一次盘片：将盘片n从x搬到z
else
{int cnt=Hanoi(n-1,x,z,y);
cnt++; //搬一次盘片：将盘片n从x搬到z
cnt+=Hanoi(n-1,y,x,z);
return cnt;
}
}
int main()
{printf("实验结果＼n");
for(int n=2;n<=10;n++)
{int cnt1=(int)pow(2,n)-1;
int cnt2=Hanoi(n,'x','y','z');
printf("公式求解结果=%4d 递归算法求解结果=%4d 两者%s＼n",
cnt1,cnt2,(cnt1==cnt2？ "相等":"不相等"));
}
return 0;
}
上述程序的执行结果如图3．11所示。
图3．11exp34．cpp的执行结果
3．5在线编程题及其参考答案
3．5．1LeetCode344——反转字符串
问题描述： 将输入的字符串反转过来。不要给另外的数组分配额外的空间。要求设计如下函数：
class Solution {
public:
void reverseString(vector<char>& s) {}
};
解法1： 采用迭代算法。将s的两端字符交换，直到未交换区间为空或者只有一个字符时为止。对应的程序如下：
class Solution {
public:
void reverseString(vector<char>& s) //迭代算法
{int i=0,j=s.size()-1;
while(i<j)
{swap(s［i］,s［j］);
i++; j--;
}
}
};
上述程序提交时通过，执行时间为20ms，内存消耗为22．7MB。
解法2： 采用递归算法。设f(s，i，j)用于反转s［i．．j］，先交换s［i］和s［j］，子问题为f(s，i+1，j-1)。对应的程序如下：
class Solution {
public:
void reverseString(vector<char>& s) //递归算法
{int n=s.size();
if(n==0 || n==1)
return;
rev(s,0,n-1);
}
void rev(vector<char>&s,int i,int j)
{if(i>j || i==j) return;
swap(s［i］,s［j］);
rev(s,i+1,j-1);
}
};
上述程序提交时通过，执行时间为24ms，内存消耗为22．7MB。
3．5．2LeetCode206——反转链表
问题描述： 反转一个不带头结点的单链表head。例如head为［1，2，3，4，5］，反转后为［5，4，3，2，1］。要求设计如下函数：
class Solution {
public:
ListNode*reverseList(ListNode*head) {}
};
解法1： 采用迭代算法。先建立一个反转单链表的头结点rh，用p遍历单链表head，将结点p采用头插法插入rh的表头。最后返回rh->next。对应的程序如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) //迭代算法
{ListNode* rh=new ListNode; //建立一个头结点
ListNode* p=head;
while(p!=NULL)
{ListNode* q=p->next; //临时保存结点p的后继结点
p->next=rh->next;
rh->next=p;
p=q;
}
return rh->next;
}
};
上述程序提交时通过，执行时间为8ms，内存消耗为8MB。
解法2： 采用递归算法。设f(head)的功能是反转单链表head并且返回反转单链表的首结点rh，其过程如图3．12所示。对应的程序如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) //递归算法
{if (head==NULL || head->next==NULL)
return head;
ListNode* rh=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return rh;
}
};
图3．12递归反转单链表head的过程
上述程序提交时通过，执行时间为8ms，内存消耗为8．4MB。
3．5．3LeetCode24——两两交换链表中的结点
问题描述： 给定一个不带头结点的单链表head，两两交换其中相邻的结点，并返回交换后的链表。注意，不能只单纯地改变结点内部的值，而是需要实际地进行结点交换。例如head为［1，2，3，4，5］，两两交换后变为［2，1，4，3，5］。要求设计如下函数：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {}
};
解法1： 采用迭代算法。先将前面的两个结点交换，交换后head指向a1的结点，last指向a0的结点，然后让p、q、r分别指向其后的3个相邻结点，如图3．13所示，若p或者q为空则结束，否则交换结点p、q。
图3．13两两结点交换的过程
对应的程序如下：
class Solution {
public:
ListNode* swapPairs(ListNode* head) //迭代算法
{if (head==NULL || head->next==NULL)
return head; //head为空或者只有一个结点的情况
ListNode *p,*q,*r,*last;
p=head; //p指向a0
q=head->next; //q指向a1
r=q->next; //r指向a2
head=q; p->next=r; //交换p和q结点，head指向新的首结点
head->next=p;
last=p;
while(true)
{p=r;
if (p==NULL || p->next==NULL)
break; //单链表p为空或者只有一个结点的情况
q=p->next;
r=q->next;
last->next=q; p->next=r; //交换p和q结点
q->next=p; p->next=r;
last=p; //重新设置last
}
return head; //返回交换后的单链表
}
};
上述程序提交时通过，执行时间为4ms，内存消耗为7．3MB。
解法2： 采用递归算法。设f(head)是大问题，用于两两交换链表head中的结点。
① 若单链表head为空或者只有一个结点(head=NULL或者head->next=NULL)，交换后的结果单链表没有变化，返回head。
② 否则，让last和p分别指向a1和a2结点，如图3．14所示，显然f(p)为小问题，用于两两交换链表p中的结点。f(head)的执行过程是先交换last和head结点(让head指向a1结点，last指向a0结点)，再置last->next=f(p)，最后返回head。
图3．14有两个或者两个以上结点时f(head)的执行过程
对应的程序如下：
class Solution {
public:
ListNode* swapPairs(ListNode* head)//递归算法
{if (head==NULL || head->next==NULL)
return head; //head为空或者只有一个结点的情况
ListNode* last=head->next; //last指向a1
ListNode* p=last->next; //p指向a2
last->next=head; //交换head和last结点
head=last;
last=head->next;
last->next=swapPairs(p);
return head;
}
};
上述程序提交时通过，执行时间为4ms，内存消耗为7．2MB。
3．5．4LeetCode62——不同路径
问题描述： 一个机器人位于一个m×n(1≤m，n≤100)网格的左上角(起始点标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图到达网格的右下角(标记为“Finish”)。问总共有多少条不同的路径？要求设计如下函数：
class Solution {
public:
int uniquePaths(int m,int n) {}
};
图3．153×3的网格
例如，m=3，n=3，对应的网格如图3．15所示，结果为6。
解： 在从左上角到右下角的任意路径中，一定是向下走m-1步向右走n-1步，不妨置x=m-1，y=n-1，路径长度为x+y。例如对于图3．15，这里x=2，y=2，所有路径长度为4，6条不同的路径如下：
右右下下
右下右下
右下下右
下右右下
下右下右
下下右右
归纳起来，不同路径条数等于从x+y个选择中挑选x个“上”或者“右”的组合数，即Cxx+y或者Cyx+y(实际上从数学上推导也有Cxx+y=Cyx+y)，为了方便，假设x≤y，结果取Cxx+y。
Cxx+y=(x+y)!x!y!=(x+y)(x+y-1)…(y-1)y!x!y!=(x+y)×…×(y-1)x×(x-1)×…×2×1
上式中的分子、分母均为x个连乘，可以进一步转换为：
x+yx×x+y-1x-1×…×y-11
由于除法的结果是实数，而不同的路径数一定是整数，所以最后需要将计算的结果向上取整得到整数结果。对应的程序如下：
class Solution {
public:
int uniquePaths(int m, int n)
{
return comp(m-1,n-1);
}
int comp(int x,int y)
{int a=x+y,b=min(x,y);
double ans=1.0;
while(b>0)
ans*=(double)(a--)/(double)(b--);
ans+=0.5;
return (int)ans;
}
};
上述程序提交时通过，执行时间为0ms，内存消耗为5．8MB。
3．5．5HDU1003——最大子序列和
问题描述： 给定一个整数序列a，请计算一个最大子序列和。例如，给定(6，-1，5，4，-7)，该序列中的最大子序列和为 6+(-1)+5+4=14。
输入格式： 输入的第一行包含一个整数t(1≤t≤20)，表示测试用例的数量，接下来是t行，每行以一个数字n(1≤n≤100000)开始，然后是n个整数(整数的取值范围为-1000~1000)。
输出格式： 对于每个测试用例，输出两行，第一行是"Case #:"，其中#表示测试用例的编号(从1开始)，第二行包含3个整数，依次为序列中的最大子序列和、对应子序列的开始位置和结束位置。如果有多个结果，则输出第一个。每两个测试用例的输出之间输出一个空行，最后一个测试用例的输出的后面没有空行。
输入样例：
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
输出样例：
Case 1:
14 1 4
Case 2:
7 1 6
解： 算法原理参见《教程》3．1．2节求最大连续子序列和问题的解法3，但有以下两点不同。
① 这里的最大连续子序列至少包含一个元素，也就是说最大连续子序列和可能为负数。
② 需要求第一个最大连续子序列，由于最大连续子序列和相同的子序列可能有多个，这里是求第一个，也就是说起始位置最小的子序列。
第一个最大连续子序列表示为a［start．．end］，首先置maxsum(最大连续子序列和)和cursum(当前连续子序列a［prestart．．i］和)为0，prestart=0。用i遍历a，累计a［i］到cursum中，分为两种情况：
① 若cursum≥maxsum，说明cursum是一个更大的连续子序列和，将其存放在maxsum中，即置maxsum=cursum，［start，end］=［prestart，i］。
② 若cursum<0，说明cursum不可能是一个更大的连续子序列和，从下一个i开始继续遍历，所以置cursum=0，prestart置为i+1。
最后输出maxsum，start和end。对应的程序如下：
#include<stdio.h>
#define INF 0x3f3f3f3f //∞
#define MAXN 100010
int a［MAXN］;
int n;
int maxSubSum(int& start,int &end)//求最大子序列和
{int cursum=0;
int maxsum=-INF;
int prestart;
start=end=prestart=0;
for(int i=0;i<n;i++)
{cursum+=a［i］;
if(cursum>maxsum)
{start=prestart;
end=i;
maxsum=cursum;
}
if(cursum<0)
{prestart=i+1;
cursum=0;
}
}
return maxsum;
}
int main()
{int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++)
{scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a［i］);
int start,end;
int ans=maxSubSum(start,end);
printf("Case %d:＼n",cas);
printf("%d %d %d＼n",ans,start+1,end+1);
if(cas!=t) printf("＼n");
}
return 0;
}
上述程序提交时通过，执行时间为46ms，内存消耗为2116KB。
3．5．6HDU1143——三平铺问题
问题描述： 可以用多少种方式用2×1的多米诺骨牌平铺一个3×n的矩形？如图3．16所示为一个3×12矩形的平铺示例。
图3．16一个3×12矩形的平铺示例
输入格式： 输入由几个测试用例组成，以包含-1的行结束。每个测试用例是一行，其中包含一个整数0≤n≤30。
输出格式： 对于每个测试用例，输出一个整数，给出可能的平铺方案数。
输入样例：
2
8
12
-1
输出样例：
3
153
2131
解： 设f(n)表示用2×1的多米诺骨牌平铺一个3×n矩形的方案数，假设平铺所用的2×1的多米诺骨牌个数为k，则2k=3n，当n为奇数时该式右边为奇数，而左边为偶数，所以不成立，也就是说当n为奇数时不能平铺，返回0。下面仅考虑n为偶数的情况。
当n=2时，所有的平铺方案如图3．17所示，即f(2)=3，不妨设f(0)=1。
图3．17一个3×2矩形的3种平铺方案
当n>2时，将3×n矩形看成高度为3、长度为n的矩形，按分割线分割为(2，n-2)，(4，n-4)，(6，n-6)，…，(n，0)。
① 当分割为(2，n-2)时，平铺方案数为f(2)×f(n-2)，即3f(n-2)。
② 当分割为(4，n-4)时，前面长度为4的部分只能有两种(考虑第一列，第一种是一个横的在上面，然后一个竖的在左下方； 第二种是一个横的在下面，然后一个竖的在左上方，两种情况是对称的)，其他情况与(2，n-2)重复，如图3．18所示，所以平铺方案数为2f(n-4)。
图3．18分割为(4，n-4)的情况
③ 当分割为(6，n-6)时，前面长度为6的部分也只能有两种，其他情况是重复的，如图3．19所示，所以平铺方案数为2f(n-6)。
图3．19分割为(6，n-6)的情况
以此类推，利用加法原理得到f(n)=3f(n-2)+2f(n-4)+2f(n-6)+…+2f(0)。
用n-2代入得到f(n-2)=3f(n-4)+2f(n-6)+2f(n-8)+…+2f(0)。
两式相减： f(n)=4f(n-2)-f(n-4)。
所以递推关系如下：
f(0)=1
f(2)=3
f(n)=4f(n-2)-f(n-4)当n≥4(偶数)时
对应的程序如下：
#include<iostream>
using namespace std;
int main()
{int n;
int a［35］; //a［i］存放f(i)
a［0］=1,a［2］=3;
for(int i=4;i<=30;i+=2) //求出a数组
a［i］=4*a［i-2］-a［i-4］;
while(~scanf("%d",&n))
{if(n==-1) break;
if(n%2==1) //n为奇数时
printf("0＼n");
else //n为偶数时
printf("%d＼n",a［n］);
}
return 0;
}
上述程序提交时通过，执行时间为15ms，内存消耗为1732KB。
3．5．7POJ2231——奶牛的总音量
问题描述： John 收到邻居Bob的噪声投诉，称他的奶牛噪声太大。John的n头奶牛(1≤n≤10000)都在一个长长的一维牧场的不同位置吃草。每对奶牛之间可以同时对话，也就是说每头奶牛可以同时向其他n-1头奶牛发出哞哞声。当奶牛i对奶牛j发出哞哞声时，这个音量必须等于它们之间的距离才能让奶牛j完全听到哞哞声。请帮助John计算所有n×(n-1)个同时发出的哞哞声的总音量。
输入格式： 第一行为n，第二行到第n+1行表示每只奶牛的位置(范围是0~1000000000)。
输出格式： 输出一行表示总音量。
输入样例：
5
1
5
3
2
4
输出样例：
40
解： 题目大意是数轴上共有n头奶牛，每头奶牛有一个位置，每头奶牛都要向其他所有奶牛发出一个哞哞声，因此一共有n×(n-1)个哞哞声，每个哞哞声的大小等于两头奶牛之间坐标差的绝对值，求所有哞哞声大小的和。
用一个数组a存放所有奶牛的位置，题目就是求a中任意两个元素差的绝对值之和。采用穷举法的程序如下：
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a［10005］;
int main()
{int n;
while(~scanf("%d",&n))
{for(int k=0;k<n;k++)
scanf("%lld",&a［k］);
LL sum=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{if(i!=j)
sum+=abs(a［i］-a［j］);
}
printf("%lld＼n",sum);
}
return 0;
}
上述程序提交时出现超时。假设b［i］［j］=|a［i］-a［j］|，显然b数组是对称的并且主对角线均为0，只需要求出下三角部分元素和(或者上三角部分元素和)sum，输出2sum即可。对应的程序如下：
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a［10005］;
int main()
{int n;
while(~scanf("%d",&n))
{for(int k=0;k<n;k++)
scanf("%lld",&a［k］);
LL sum=0;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
sum+=abs(a［i］-a［j］);
printf("%lld＼n",2*sum);
}
return 0;
}
上述程序提交时通过，执行时间为593ms，内存消耗为212KB。
3．5．8POJ1050——最大子矩形
问题描述： 给定一个由正整数或者负整数组成的二维数组，子矩形是位于整个数组内的大小为1×1或更大的任何连续子数组。矩形的总和是该矩形中所有元素的总和。在这个问题中，总和最大的子矩形称为最大子矩形。例如有以下数组：
0-2-70
9 2 -62
-41 -41
-180 02
其最大子矩形是左下角：
92
-41
-18
最大子矩形和是15。
输入格式： 输入由一个n×n的整数数组组成。输入以单独一行的单个正整数n开头，表示二维数组的大小。后面是由空格(空格和换行符)分隔的n2个整数，这些是数组的n2个整数元素，以行优先顺序显示，即先从左到右为第一行中的所有整数，然后是第二行中的所有整数，以此类推。n可能大到100，数组中的整数在 ［-127,127］ 范围内。
输出格式： 输出最大子矩形的总和。
输入样例：
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
输出样例：
15
解： 利用《教程》3.2.2节中求子矩阵元素和的思路，在获取n和a数组后，先执行b=Sum(a)求出数组b，采用i从0到n-1，j从0到n-1，s从i到n-1，t从j到n-1的四重循环，执行curmax=submat(b,i,j,s,t)求出每个矩阵(i，j)-(s，t)的元素和，比较求出最大值ans，最后输出ans。调用的程序如下：
#include<iostream>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f //存放∞
vector<vector<int>> Sum(vector<vector<int>> &a) //由矩阵a求矩阵b
{int n=a.size();
vector<vector<int>> b(n,vector<int>(n));
b［0］［0］=a［0］［0］;
for (int i=1;i<n;i++) //求b的第0列
b［i］［0］=b［i-1］［0］+a［i］［0］;
for (int j=1;j<n;j++) //求b的第0行
b［0］［j］=b［0］［j-1］+a［0］［j］;
for (int i=1;i<n;i++) //求b［i］［j］
for (int j=1;j<n;j++)
b［i］［j］=a［i］［j］+b［i-1］［j］+b［i］［j-1］-b［i-1］［j-1］;
return b;
}
int submat(vector<vector<int>> &b,int i,int j,int s,int t) //求［i,j］-［s,t］子矩阵元素和
{int sum;
if (i==0 && j==0)
return b［s］［t］;
else if(i==0)
sum=b［s］［t］-b［s］［j-1］;
else if(j==0)
sum=b［s］［t］-b［i-1］［t］;
else
sum=b［s］［t］-b［s］［j-1］-b［i-1］［t］+b［i-1］［j-1］;
return sum;
}
int main()
{int n;
cin >> n;
vector<vector<int>> a(n,vector<int>(n));
for(int i=0;i<n;i++) //获取a数组
for(int j=0;j<n;j++)
cin >> a［i］［j］;
vector<vector<int>> b=Sum(a);
int ans=-INF; //存放结果，初始为-∞
for(int i=0;i<n;i++) //4重循环
{for(int j=0;j<n;j++)
{for(int s=i;s<n;s++)
{for(int t=j;t<n;t++)
{int curmax=submat(b,i,j,s,t);
ans=max(ans,curmax);
}
}
}
}
cout << ans << endl; //输出结果
return 0;
}
上述程序提交时通过，执行时间为309ms，内存消耗为308KB。