算法设计与分析（第二版）
主编：吕国英
习题答案
第四章
1.
#include
int main(void)
{
int buf[100];
int n;
int i,j,k;
scanf("%d",&n);
for(i=0;i
buf[i]=2;
for(i=0;i
{
for(j=0;j
{
buf[j]+=2;
}
}
for(j=0;j
{
if(buf[j]>=10)
{
buf[j+1]+=buf[j]/10;
buf[j]=buf[j]%10;
}
}
for(i=n-1;i>=0;i--)
printf("%d",buf[i]);
printf("\n");
return 0;
}
2.
#include
int main(void)
{
int n=2;
int i; for(i=1;i<=9;i++)
{
n=(n+2)*2;
}
printf("%d\n",n);
return 0;
}
3.
#include
int main(void)
{
int a=54;
int n;
int m;
printf("计算机先拿3张牌\n");
a=a-3;
while(a>=0)
{
printf("还剩%d张牌\n",a);
printf("你拿几张？请输入：");
scanf("%d",&n);
if(n>4||n<1||n>a)
{
printf("错误！重新拿牌\n");
continue;
}
a=a-n;
printf("还剩%d张牌\n",a);
if(a==0)
break;
m=5-n;
printf("计算机拿%d\n",m);
a=a-m;
}
return 0;
}
4.
#include
int d;
int a1,a2;
int fun(int n);
int main(void)
{
int n; printf("n=?,d=?,a1=?,a2=?");
曲阜师范大学课堂作业
作业四
4.1.2 Alternating glasses
a. There are 2n glasses standing next to each other in a row, the first n of them filled with a soda
drink and the remaining n glasses empty. Make the glasses alternate in a filled-empty-filled-empty pattern in the minimum number of glass moves. [Gar78]
b. Solve the same problem if 2n glasses—n with a drink and n empty—are initially in a random
order
答：
图1 杯子分组
a. 两个为一组，在前n个杯子中判断偶数的杯子是否为空，不为空与同组的进行交换，共需要交换n/2次，考虑n为奇数对n/2进行向下取整即可。
b. 由于最终偶数位置为空杯，奇数位置为满杯，从第一项开始遍历，如果在奇数位置出现空杯与后面偶数位置出现的第一个满杯进行交换，如果偶数位置出现满杯则与后面奇数出现的第一个空杯进行交换，每次交换使得两个位置满足条件，最坏情况是2n位置均为乱序，则需要交换n次，最好的情况为2n位置均满足条件，则交换次数为[0,n]
4.1.7 Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order.
答：
import numpy as np
data = np.array(['E', 'X', 'A', 'M', 'P', 'L', 'E'])
L = len(data)
for i in range(L):
算法设计与分析（第二版）
主编：吕国英
习题答案
第四章
1.
#include
int main(void)
{
int buf[100];
int n;
int i,j,k;
scanf("%d",&n);
for(i=0;i
buf[i]=2;
for(i=0;i
{
for(j=0;j
{
buf[j]+=2;
}
}
for(j=0;j
{
if(buf[j]>=10)
{
buf[j+1]+=buf[j]/10;
buf[j]=buf[j]%10;
}
}
for(i=n-1;i>=0;i--)
printf("%d",buf[i]);
printf("\n");
return 0;
}
2.
#include
int main(void)
{
int n=2;
int i; for(i=1;i<=9;i++)
{
n=(n+2)*2;
}
printf("%d\n",n);
return 0;
}
3.
#include
int main(void)
{
int a=54;
int n;
int m;
printf("计算机先拿3张牌\n");
a=a-3;
while(a>=0)
{
printf("还剩%d张牌\n",a);
printf("你拿几张？请输入：");
scanf("%d",&n);
if(n>4||n<1||n>a)
{
printf("错误！重新拿牌\n");
continue;
}
a=a-n;
printf("还剩%d张牌\n",a);
if(a==0)
break;
m=5-n;
printf("计算机拿%d\n",m);
a=a-m;
}
return 0;
}
4.
#include
int d;
int a1,a2;
int fun(int n);
int main(void)
{
int n; printf("n=?,d=?,a1=?,a2=?");
第 1 页 共 1 页 习题答案第四章 算法设计与分析 吕国英
main(void)
{ int buf[100]; int n; int i,j,k; scanf("%d",&n);
for(i=0;i
buf[i]=2; for(i=0;i
{ for(j=0;j
{ buf[j]+=2; } } for(j=0;j
{ if(buf[j]>=10)
{ buf[j+1]+=buf[j]/10; buf[j]=buf[j]%10; } } for(i=n-1;i>=0;i--)
printf("%d",buf[i]); printf("\n"); return 0; }2、#includeint main(void){int n=2;int
i;for(i=1;i<=9;i++){n=(n+2)*2;}printf("%d\n",n);return
0;}3、#includeint main(void){int a=54;int n;int
m;printf("计算机先拿3张牌\n");a=a-3;while(a>=0){printf("还剩%d张牌\n",a);printf("你拿几张？请输入：");scanf("%d",&n);if(n>4||n<1||n>a){printf("错误！重新拿牌\n");continue;}a=a-n;printf("还剩%d张牌\n",a);if(a==0)break;m=5-n;printf("计算机拿%d\n",m);a=a-m;}return 0;}4、#includeint d;int a1,a2;int
fun(int n);int main(void){int
第 1 页 共 1 页 n;printf("n=?,d=?,a1=?,a2=?");scanf("%d%d%d%d\n",&n,&d,&a1,&a2);printf("%d\n",fun(n));return 0;}int fun(int
