UVA1590题解

sunyizhe · 2023-09-10 20:27:20 · 题解

一、题面简洁翻译

有 n 个 IP 地址，现给出 n 和 n 个 IP，求最小网络的网络地址和子网掩码。

二、思路

2.1 前置知识和基本思路

下文均以样例举例。

2.1.1 化成 32 位二进制数

首先，我们要知道什么是网络地址和子网掩码（子网掩码和翻译中的网络掩码是一个东西）（选读）。那么已经知道 n 个 IP 地址，如何算出最小网络的网络地址和子网掩码呢？很简单。首先，我们将所有的 IP 地址化成 32 位二进制数。化的方法很简单：只需要把用点号隔开的四个数分别化成二进制数，再按序拼起来即可。

样例化完以后是这样的（为了方便阅读，我把每个字节中间用空格隔开，实际操作不需要）：

  194  .   85  .  160   . 177
11000010 01010101 10100000 10110001

  194  .   85  .  160   . 183
11000010 01010101 10101010 10110111

  194  .   85  .  160   . 178
11000010 01010101 10101010 10110010

2.1.2 计算子网掩码

接着开始算子网掩码。计算方法是这样的：看这 n 个二进制数，如果所有数的这一位都相同，那么这一位就是 1，否则当前位和后面位全都是 0。比如样例：

  194  .   85  .  160   . 177
11000010 01010101 10100000 10110001

  194  .   85  .  160   . 183
11000010 01010101 10101010 10110111

  194  .   85  .  160   . 178
11000010 01010101 10101010 10110010

11111111 11111111 11111111 11111000 => 255.255.255.248

其中，由于这三个数的倒数第三位并不完全相同，所以后面都是 0。

2.1.2 计算网络地址

网络地址理解起来就更简单了：在 n 个 IP 中任挑一个与子网掩码进行按位与运算，得到的就是网络地址。依旧放样例：

  194  .   85  .  160   . 177
11000010 01010101 10100000 10110001

  255  .  255   . 255   . 248
11111111 11111111 11111111 11111000

11000010 01010101 10100000 10110000 => 网络地址：194.85.160.176

2.2 代码实现

我们用字符串模拟实现。我们需要如下函数：

整数转 8 位二进制数：

string IntTo8Bin(int x)
{
    string s="";
    if(x==0)s="0";
    while(x)
    {
        char ch=x%2+'0';
        s=ch+s;
        x/=2;
    }

    while(s.size()<8)s='0'+s;//补前导0变成8位数

    return s;
}

二进制数转整数：

string BinToInt(string s)//不要手残，循环里ans不要打成s
{
    string ans="";
    int x=(s[0]-'0')*128+(s[1]-'0')*64+(s[2]-'0')*32+(s[3]-'0')*16+(s[4]-'0')*8+(s[5]-'0')*4+(s[6]-'0')*2+(s[7]-'0');//暴力拼接
    if(x==0)return "0";
    while(x)
    {
        char ch=x%10+'0';
        ans=ch+ans;
        x/=10;
    }
    return ans;
}

IP 地址转 32 位二进制数：

string IpToBin(int a,int b,int c,int d)//a.b.c.d -> 32位二进制数
{
    string s=""+IntTo8Bin(a)+IntTo8Bin(b)+IntTo8Bin(c)+IntTo8Bin(d);
    return s;
}