[刷题]算法竞赛入门经典(第2版) 4-5/UVa1590 - IP Networks

书上具体所有题目:http://pan.baidu.com/s/1hssH0KO

代码:(Accepted,0 ms)

//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位清零。于是用了这个方法

                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。

(应该没说错吧)

上一篇:Hashmat the brave warrior - UVa10055


下一篇:dotnet调用node.js写的socket服务(websocket/socket/socket.io)