[整理]ACM详解(9)——其他

蓝飞 蓝飞 | 时间:2012-02-17, Fri | 4,458 views
编程算法 
有时候会考一些锻炼基本能力的题目,下面使用几个例子进行简单分析。
1IP Address
Description
Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1s' and '0s' (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are:
27 26 25 24 23 22 21 20
128  64 32 16 8   4   2   1
Input
The input will have a number N (1<=N<=9) in its first line representing the number of streams to convert. N lines will follow.
Output
The output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation.
Sample Input
4
00000000000000000000000000000000
00000011100000001111111111111111
11001011100001001110010110000000
01010000000100000000000000000001
Sample Output
0.0.0.0
3.128.255.255
203.132.229.128
80.16.0.1
翻译:23位的0/1序列表示可以用来表示一个IP地址,题目要求把给定的32位序列转换为IP地址。例如序列00000011100000001111111111111111可以转换为3.128.255.255。
解题思路:把序列分成8个一组,然后把二进制序列转换为十进制的数,然后把4个数用“.”连接即可。题目比较简单,不再给出参考代码。
2Elevator
描述
The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.
For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.
输入
There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.
输出
Print the total time on a single line for each test case.
样例输入
1 2
3 2 3 1
0
样例输出
17
41
翻译:大楼中只有一个电梯,请求序列有N个正整数组成,数字表示电梯将在哪里停,按照顺序。电梯向上一层需要6秒,向下一层需要4秒,每层停5秒。题目要求根据给定的请求序列求出电梯完成所有任务需要的时间。电梯刚开始在0层。
解题思路:使用sum表示总时间,初始值为0。对于每个请求序列,取出每个请求的楼层,如果是请求序列中第一个,计算上楼需要的时间(n*6),然后再加上电梯停留的时间(5),sum=sum+n*6+5。如果不是第一个请求,看上次请求的位置m,如果小于当前位置,计算上楼的时间(n-m)*6,电梯停留时间5,sum=sum+(n-m)*6+5,如果大于当前位置,计算下楼时间(m-n)*4,电梯停留时间5,sum=sum+(m-n)*4+5。
参考代码如下:
/*
 * 电梯运行时间
 */
public static void test4(int[] datas){
	// 表示原来的楼层
	int m = 0;
	// 表示总时间
	int sum = 0;
	for(int i=1;i<=datas[0];i++){
		int n = datas[i];
		if(n>m){
			sum = sum+(n-m)*6+5;
		}else{
			sum = sum+(m-n)*4+5;
		}
		m = n;
	}
	System.out.println(sum);
}
3、集合的减法运算
Problem Description
集合的减法运算。(当然,大家都知道集合的定义,就是同一个集合中不会有两个相同的元素,这里还是提醒大家一下)。
Input
每组输入数据占1行,每行数据的开始是2个整数n(0<n<=100)和m(0<m<=100),分别表示集合A和集合B的元素个数,然后紧跟着n+m个元素,前面n个元素属于集合A,其余的属于集合B. 每个元素为不超出int范围的整数,元素之间有一个空格隔开.
如果n=0并且m=0表示输入的结束,不做处理。
Output
针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合,则输出“NULL”,否则从小到大输出结果,为了简化问题,每个元素后面跟一个空格.
Sample Input
3 3 1 2 3 1 4 7
3 7 2 5 8 2 3 4 5 6 7 8
0 0
Sample Output
2 3
NULL
集体思路:没有难度,就是锻炼基本功。从每个测试用例中分别得到A集合和B集合,遍历A集合中的所有元素,如果不在B集合中,则输出该元素。不再给出参考代码。

整理自:李绪成 CSDN Blog:http://blog.csdn.net/javaeeteacher

如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »