第3章在线编程题参考答案
3．1第1章绪论
1． POJ1004——财务管理问题

时间限制： 1000ms； 空间限制： 10000KB。
问题描述： 拉里今年毕业，终于找到了工作。他赚了很多钱，但似乎还没有足够的钱，拉里决定抓住金融投资机会解决他的财务问题。拉里有自己的银行账户报表，他想看看自己有多少钱。请编写一个程序帮助拉里从过去12个月的每一月中取出他的期末账户余额并计算他的平均账户余额。
输入格式： 输入为12行，每行包含特定月份的银行账户的期末余额，每个数字都是正数并到便士为止，不包括美元符号。
输出格式： 输出一个数字，即12个月的期末账户余额的平均值(平均值)，它将四舍五入到最近的便士，紧接着是美元符号，然后是行尾。在输出中不会有其他空格或字符。
输入样例： 

100.00

489.12

12454.12

1234.10

823.05

109.20

5.27

1542.25

839.18

83.99

1295.01

1.75


输出样例： 

$1581.42


解： 读取每个月份的期末账户余额temp，累加到sum中，输出sum/12的结果。对应的AC程序如下： 

import java.util.Scanner; 

public class Main

{public static void main(String［］ args)

{Scanner fin=new Scanner(System.in);

double temp=0.00,sum=0.00;

int iMax=12;

while(iMax-->0)

{temp=fin.nextDouble();

sum += temp;

}

System.out.printf("$%.2f＼n",sum/12);

}

}

上述程序的执行时间为188ms，执行空间为3228KB。

第3章在线编程题参考答
案

数据结构教程（Java语言描述）学习与上机实验指导
2． HDU2012——素数判定问题
时间限制： 2000ms； 空间限制： 65536KB。
问题描述： 对于表达式n^2+n+41，当n在(x，y)范围内取整数值时(包括x、y，-39≤x<y≤50)判定该表达式的值是否都为素数。
输入格式： 输入数据有多组，每组占一行，由两个整数x、y组成，当x=0、y=0时表示输入结束，该行不做处理。
输出格式： 对于每个给定范围内的取值，如果表达式的值都为素数，输出“OK”，否则输出“Sorry”，每组输出占一行。
输入样例： 

0 1

0 0

输出样例： 

OK

解： 对于整数num，若它能够整除2~sqrt(num)中的任何整数，则不是素数，否则为素数。对应的AC程序如下： 

import java.util.Scanner;

public class Main

{public static void main(String［］ args)

{Scanner in = new Scanner(System.in);

while(in.hasNextInt())

{int x = in.nextInt();

int y = in.nextInt();

boolean flag = true;

int number = 0;

int num = 0;

if(x==0 && y= 0)

break;

else

{if(x>y)

{int temp = x;

x = y;

y = temp;

}

for(int i = x; i <= y; i++)

{num=i*i+i+41;

for(int j = 2; j <= Math.sqrt(num); j++)//素数判断

{if(num % j == 0)

flag = false;

}

}

if(flag == true)

System.out.println("OK");

else

System.out.println("Sorry");

flag = true;

}

}

}

}

上述程序的执行时间为296ms，执行空间为9312KB。
提示： 在本书所有在线编程题中，POJ题目的限制时间和空间是针对C/C++程序的，通常Java程序的时间和空间是其两倍，HDU题目的限制时间和空间就是针对Java程序的。
3．2第2章线性表
1． HDU2019——数列有序问题

时间限制： 2000ms； 空间限制： 65536KB。
问题描述： 有n(n≤100)个整数，已经按照从小到大的顺序排列好，现在另外给一个整数m，请将该数插入序列中，并使新的序列仍然有序。
输入格式： 输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0表示输入数据的结束，本行不做处理。
输出格式： 对于每个测试实例，输出插入新的元素后的数列。
输入样例： 

3 3

1 2 4

0 0

输出样例： 

1 2 3 4

解： 对于每个测试实例，n个有序整数采用顺序表存放，为了简单，这里顺序表直接用数组a表示。先查找插入m的位置i，将a［i．．n-1］的所有元素均后移一个位置，置a［i］=m。对应的AC程序如下： 

import java.util.*;

public class Main

{public static void main(String args［］)

{Scanner cin=new Scanner(System.in);

while(cin.hasNext())					　　//读取每个测试实例

{int n=cin.nextInt();				　　//读取n

int m=cin.nextInt();				　　//读取m

if(n==0 && m==0)				　　//结束

break;

else

{int a［］=new int［105］;			　　//最多100个整数

for(int i=0;i<n;i++)			　　//读取递增有序整数序列

a［i］=cin.nextInt();

if(m>a［n-1］)					　　//m最大，插入末尾

a［n］=m;

else

{for(int i=0;i<n;i++)		　　//查找第一个大于等于m的元素a［i］

{if(m<a［i］)

{int j=i;

for( i=n;i>j;i--)	　　//将a［i..n-1］后移一个位置

a［i］=a［i-1］;

a［i］=m;			　　//插入a［i］

break;			　　//退出查找

}

}

}

for(int i=0;i<=n;i++)			　　//输出新序列

if(i==0)

System.out.print(a［i］);

else

System.out.print(" "+a［i］);

}

System.out.println();

}

}

}

上述程序的执行时间为265ms，空间为9412KB。
2． HDU1443——Joseph(约瑟夫)问题
时间限制： 2000ms； 空间限制： 65536KB。
问题描述： Joseph问题是众所周知的。有n个人，编号为1，2，…，n，站在一个圆圈中，每隔m个人就杀一个人，最后仅剩下一个人。Joseph很聪明，可以选择最后一个人的位置，从而挽救他的生命。例如，当n=6且m=5时，按顺序出列的人员是5，4，6，2，3，1，那么1会活下来。
假设在圈子里前面恰好有k个好人，后面恰好有k个坏人，则必须确定所有坏人都在第一个好人前面被杀的最小m。
输入格式： 输入文件中包含若干行，每行一个k，最后一行为0，可以假设0<k<14。
输出格式： 输出文件中每行给出输入文件中的k对应的最小m。
输入样例： 

3

4

0

输出样例： 

5

30

解： 题目中有多个测试实例，每个测试实例的结果仅仅与k有关系，设计避免重复计算的数组a，a［k］记录k问题的m值，a数组的所有元素初始为0，当a［k］不为0时说明该k问题已经求出，直接返回a［k］即可。
对于每个k问题，假设2k个人的序号是0~2k-1，显然m从k+1开始枚举(因为每次从头开始，若m<k+1，则第一个被杀的一定是好人)。对于每个m： 
(1) cnt表示剩余人数，所以cnt从2k开始到k+1循环，p从0开始找被杀的人员的序号，每杀一个人，cnt减少1。
(2) 若被杀人员的序号p满足p<k(前k个好人的序号为0~k-1)，说明p对应的是好人，置cnt=0结束该m值的枚举。
(3) 若cnt==k，则说明剩下k个人，并且被杀的k个人都是坏人，则找到这样的m，置a［k］=m，返回m。
对应的AC程序如下： 

import java.util.*;

public class Main

{static int［］ ans=new int［15］;				　　//记录k问题的m值,初始时均为0

public static int Joseph(int k)			　　//求解Joseph问题

{int cnt,p;

if(ans［k］!=0) return ans［k］;			　　//若已经求出，直接返回

for(int m=k+1;;m++)					　　//m从k+1开始试探

{for(cnt=2*k,p=0;cnt>k;cnt--)		　　//检查是否满足要求

{p=(p+m-1) % cnt;			　　//被杀掉的人的位置

if(p<k) cnt=0;				　　//被杀掉的人是前k个(好人)

}

if(cnt==k)						　　//所有坏人都被杀了，满足要求

{ans［k］=m;

return m;

}

}

}

public static void main(String args［］)

{Scanner cin=new Scanner(System.in);

while(cin.hasNext())

{int k=cin.nextInt();

if(k==0) break;

System.out.println(Joseph(k));

}

}

}

上述程序的执行时间为577ms，空间是10388KB。
3． POJ2389——公牛数学问题
时间限制： 1000ms； 空间限制： 65536KB。
问题描述： 公牛在数学上比奶牛好多了，它们可以将巨大的整数相乘，得到完全精确的答案。农夫约翰想知道它们的答案是否正确，请帮助他检查公牛队的答案。读入两个正整数(每个不超过40位)并计算其结果，以常规方式输出(没有额外的前导零)。约翰要求不使用特殊的库函数进行乘法。
输入格式： 输入两行，每行包含一个十进制数。
输出格式： 输出一行表示乘积。
输入样例： 

11111111111111

1111111111

输出样例： 

12345679011110987654321

解： 两个长度最多为40位的正整数采用String对象s1、s2表示。设置a、b两个整数数组(初始时所有元素为0)，将s1的各位存放在a中(s1的最后位存放在a［0］中)，将s2的各位存放在b中(s2的最后位存放在b［0］中)。
实现a与b相乘的过程是用c数组的c［i+j］元素存放a［i］和b［j］相乘的累加值，然后调整有进位的元素，反向输出得到最后结果。
对应的AC程序如下： 

import java.lang.*;

import java.util.*;

public class Main

{public static String mult(String s1,String s2)　　//两个数字字符串相乘

{int［］ a=new int［42］;

int［］ b=new int［42］;

int［］ c=new int［90］;

int i,j;

int m=s1.length();

int n=s2.length();

for(i=0;i<m; i++)					　　//a［0］存放s1的最低位

a［i］=s1.charAt(m-1-i)-'0';

for(i=0;i<n;i++)						　　//b［0］存放s2的最低位

b［i］=s2.charAt(n-1-i)-'0';

for(i=0;i<m;i++)

for(j=0; j<n; j++)

c［i+j］ += a［i］*b［j］;

for(i=0;i<80;i++)

if(c［i］ >= 10)					　　//有进位

{c［i+1］ += c［i］/10;

c［i］ %= 10;

}

String ans="";

for(i=c.length-1;i>=0; i--)			　　//删除前导零

if(c［i］!=0) break;

for(;i>=0; i--)

ans += c［i］;

return ans;

}

public static void main(String［］ args)

{Scanner cin = new Scanner(System.in);

String s1,s2;

s1=cin.nextLine();

s2=cin.nextLine();

String s3=mult(s1,s2);

System.out.println(s3);

}

}

上述程序的执行时间为1266ms，空间是2964KB。实际上，本题目可以直接使用Java的长整数类型来实现，对应的AC程序如下： 


import java.math.BigInteger;

import java.util.Scanner;

public class Main

{public static void main(String［］ args)

{Scanner cin = new Scanner(System.in);

BigInteger a = cin.nextBigInteger();

BigInteger b = cin.nextBigInteger();

a = a.multiply(b);

System.out.println(a);

}

}

上述程序的执行时间为1375ms，空间是3036KB。
说明： 尽管在线性表部分中讨论了多种存储结构，但在实际在线编程中，为了简单和提高效率往往直接采用数组代替顺序表，相反链表较少使用，其原因之一是在这类题目中都确定了数据量的大小，适合采用顺序结构，另外链表由于结点地址不连续，内存寻址空间较大，导致存取效率较低。
3．3第3章栈和队列
1． HDU1237——简单计算器

时间限制： 2000ms； 空间限制： 65536KB。
问题描述： 读入一个只包含+、-、*、/的非负整数计算的表达式，计算该表达式的值。
输入格式： 测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔； 没有非法表达式； 当一行中只有0时输入结束，相应的结果不要输出。
输出格式： 对每个测试用例输出一行，即该表达式的值，精确到小数点后两位。
输入样例： 

1 + 2

4 + 2 * 5 - 7 / 11

0

输出样例： 

3.00

13.36

解： 与《教程》中3．1．7节“用栈求解简单表达式求值问题”的原理相同，由于这里不包括括号，所以更简单一些，将求表达式值的两个步骤合并起来。
设计运算数栈为opand，运算符栈为oper。先将输入行str拆分为strs字符串数组，用i遍历strs： 
(1) 若strs［i］为“*”或者“/”，为最高优先级，将oper栈顶为“*”或者“/”的运算符先计算，再将strs［i］进oper栈。
(2) 若strs［i］为“+”或者“-”，为最低优先级，将oper栈中所有的运算符先计算，再将strs［i］进oper栈。
(3) 其他为运算数，将其进opand栈。
最后输出opand的栈顶数值。
对应的AC程序如下： 

import java.util.*;

import java.util.Scanner;

public class Main

{static Stack<Double> opand=new Stack<Double>();	　　//运算数栈

static Stack<String> oper=new Stack<String>();		　　//运算符栈

public static boolean Same(String s1,String s2)		　　//比较两个字符串值是否相同

{

return s1.compareTo(s2)==0;

}

public static void comp(String op)					　　//用于一个运算符的计算

{double a=opand.pop();							　　//从opand中出栈两个数a和b

double b=opand.pop();

double c=0.0;

if(Same(op,"+"))								　　//op为“+”

c=b+a;

else if(Same(op,"-"))							　　//op为“-”

c=b-a;

else if(Same(op,"*"))							　　//op为“*”

c=b*a;

else if(Same(op,"/"))								　　//op为“/”

c=b/a;

opand.push(c);									　　//结果进opand栈

}

public static void main(String［］ args)

{Scanner fin = new Scanner(System.in);

while(fin.hasNext())

{String str=fin.nextLine();						　　//接收输入的字符串

if(str.compareTo("0")==0) 					　　//若是只输入0，则结束

break;

opand.clear();

oper.clear();

String［］ strs=str.split(" ");						　　//根据题目要求分割字符串

String op;

double a,b,c;

int i=0;

while(i<strs.length)							　　//遍历strs

{if(Same(strs［i］,"*") || Same(strs［i］,"/"))	　　//遇到*或者/

{while(!oper.empty())

{op=oper.peek();

if(Same(op,"*") || Same(op,"/")) 	　　//栈顶为*或者/,先计算

{comp(op);

oper.pop();

}

else break;						　　//其他+或者-

}

oper.push(strs［i］);					　　//将strs［i］进oper栈

}

else if(Same(strs［i］,"+") || Same(strs［i］,"-"))　　//遇到+或者-

{while(!oper.empty())					　　//计算oper栈中所有的运算符

{op=oper.pop();

comp(op);

}

oper.push(strs［i］);					　　//将strs［i］进oper栈

}

else										　　//其他运算数进opand栈

opand.push(Double.parseDouble(strs［i］)); 

i++;

}

while(!oper.empty())							　　//计算oper栈中所有的运算符

{op=oper.pop();

comp(op);

}

System.out.printf("%.2f", opand.peek());

System.out.println();

}

}

}

上述程序的执行时间为452ms，空间为13620KB。
说明： 类似的题目有POJ3295。
2． POJ1363——铁轨问题
时间限制： 1000ms； 空间限制： 65536KB。
问题描述： A市有一个著名的火车站，那里的山非常多。该站建于20世纪，不幸的是该火车站是一个死胡同，并且只有一条铁轨，如图3．1所示。
当地的传统是从A方向到达的每列火车都继续沿B方向行驶，需要以某种方式进行车厢重组。假设从A方向到达的火车有n(n≤1000)个车厢，按照递增的顺序1、2、…、n编号。火车站负责人必须知道是否可以通过重组得到B方向的车厢序列。


图3．1铁轨问题示意图


输入格式： 输入由若干行块组成； 除了最后一个之外，每个块描述了一个列车以及可能更多的车厢重组要求； 在每个块的第一行中为上述的整数n，下一行是1、2、…、n的车厢重组序列； 每个块的最后一行仅包含0； 最后一个块只包含一行0。
输出格式： 输出包含与输入中具有车厢重组序列对应的行。如果可以得到车厢对应的重组序列，输出一行“Yes”，否则输出一行“No”。此外，在输入的每个块之后有一个空行。
输入样例： 

5

1 2 3 4 5

5 4 1 2 3

0

6

6 5 4 3 2 1

0

0

输出样例： 

Yes

No



Yes