XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 4-5UVa1590 - IP Networks

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2k 阅读时长 ≈ 2 分钟

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO 代码：（Accepted，0 ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//UVa1590 - IP Networks
#include<iostream>
unsigned i, m, num, ip[4], ipmax[4], ipmin[4], mask[4];
int cmp(unsigned *a, unsigned *b) {//compare
	for (int i = 0;i < 4;++i) {
		if (a[i] < b[i]) return -1;
		if (a[i] > b[i]) return 1;
	}
	return 0;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	while (scanf("%d", &m) != -1) {
		scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]);
		for (i = 0;i < 4;++i) ipmax[i] = ipmin[i] = ip[i];
		while (--m) {
			scanf("%d.%d.%d.%d", &ip[0], &ip[1], &ip[2], &ip[3]);
			if (cmp(ip, ipmax) == 1)
				for (i = 0;i < 4;++i) ipmax[i] = ip[i];
			else if (cmp(ip, ipmin) == -1)
				for (i = 0;i < 4;++i) ipmin[i] = ip[i];
		}
		for (i = 0;i < 4;++i) {
			if (i == 0 || mask[i - 1] == 255) {
				mask[i] = 255 ^ (ipmax[i] ^ ipmin[i]);
				for (int j = 0;j <= 8;++j)
					if ((mask[i] >> j) == (255 >> j)) {
						mask[i] = ((mask[i] >> j) << j);
						break;
					}
			}
			else mask[i] = 0;
		}
		printf("%u.%u.%u.%u\n", mask[0] & ipmax[0], mask[1] & ipmax[1], mask[2] & ipmax[2], mask[3] & ipmax[3]);
		printf("%u.%u.%u.%u\n", mask[0], mask[1], mask[2], mask[3]);
	}
	return 0;
}

分析：网上他们说这是水题ToT。。。他们说只要知道点IP地址的知识就行了。。。然而我并不知道。。。于是看那英文的题目也没细说ip地址与子网掩码的规则，就自己查了好久子网掩码和ip地址的转化规则，其实到现在也仅仅是“好像懂了”，却竟然做出来了，不知道是开心还是不开心。而且之前我也没学过按位运算，这次竟然自己摸索着运用的还可以。 IP地址与子网掩码转化规则如下：（假设ip地址为a，a 的子网掩码为b，图个打字方便） a与b（每一段分别）按位与，就得到它的smallest possible IP network 如果a1、a2、a3……分别与b“按位与”运算均得到一个答案，那么说明这些电脑全在一个子网里。 而现在要求已知很多地址，且知道他们在一个子网里，让你求smallest possible IP network和子网掩码。那么其实只要知道最大最小两个ip就行。于是找出最大最小，ipmax和ipmin。然后看ipmax和ipmin从哪一位（二进制）开始不同，从不同的那一位开始，那些电脑就是在同一个子网里了，于是可以求得子网掩码。我的算法是，最大最小两个ip进行异或运算，目的是找出第一个开始不一样的地方，然后再与1111 1111（二进制，即255）异或运算，相当于取反，但是这里不能直接使用取反运算“~”，因为一个unsigned有32位，会使得比1111 1111高位的0也取反。于是得到子网掩码的雏形。而子网掩码前n位连续为1，后32-n位连续为0，这个雏形仅仅办到了前n位为1，所以得想办法把后32-n位清零。于是用了这个方法 

1
2
3
4
5
for (int j = 0;j <= 8;++j)
    if ((mask[i] >> j) == (255 >> j)) {
        mask[i] = ((mask[i] >> j) << j);
        break;
    }
再根据子网掩码和随意一个ip按位与，就得到smallest possible IP network。 （应该没说错吧）