4 5_ip_network_uva1590 - nuaazdh/acm GitHub Wiki

###习题 4-5 IP Network UVa1590 ##问题 给定一组IP,求IP集合的最小子网和对应的子网掩码。

样例输入

3
194.85.160.177
194.85.160.183
194.85.160.178

样例输出

194.85.160.176
255.255.255.248

###分析 两种方法,一个IP分四个段,一是从 n 个IP地址的第 1 段开始比较,如果都相同,则掩码第一个段为255,一直比较下去直到第一个不是255的段出现,比较结束。 而是第一个与第二个求最小子网IP地址,然后再与第三个比较,这样每次比较两个。

###code in C

#define MAX_SIZE 1010

int all[MAX_SIZE][4];
int min_net[4];
int mask[4];
int bits = 0;

int remove_last_bit(int m)
{
    int k = 255;
    while ((m&k) == m) {
        k<<=1;
    }
    return m&k;
}

void get_min_2(int m)
{
    int i,j;
    for (i=0; i<4; ++i) {
        if((min_net[i]&mask[i]) == (all[m][i]&mask[i]))
           continue;
        while ((min_net[i]&mask[i]) != (all[m][i] & mask[i])) {
            mask[i] = remove_last_bit(mask[i]);
        }
        min_net[i] &= mask[i];
        for (j=i+1; j<4; ++j) {
            mask[j]=0;
            min_net[j] = 0;
        }
        break;
    }
}

void get_min(int m, int n)
{
    int i;
    for (i=0; i<4; ++i) {
        mask[i] = 255;
        min_net[i] = mask[i] & all[m][i];
    }
    while (n--) {
        get_min_2(n+m);
    }
}

void str2IP(char *s, int k)
{
    int i=0,num,j=0;
    while (1) {
        num = 0;
        while (s[i]!='.' && s[i] != '\0') {
            num = num*10+(s[i++]-'0');
        }
        ++i;
        all[k][j++] = num;
        if(j>4) break;
    }
}


int main()
{
    int m,n, i=0,j,k;
    char buff[50];
    memset(buff,0,sizeof(buff));
    memset(all, 0, sizeof(all));
    while (scanf("%d",&n)==1 && scanf("%s",buff)!=EOF) {
        m = n, i=0;
        do{
            j = 0, k = 0;
            str2IP(buff,i);
            ++i;
        }while ((--m) && scanf("%s",buff)!=EOF);
        get_min(0,n);
        printf("%d.%d.%d.%d\n",min_net[0],min_net[1],min_net[2],min_net[3]);
        printf("%d.%d.%d.%d\n",mask[0],mask[1],mask[2],mask[3]);
    }
}

###点评 使用了第二个方法实现的,提交了三次才AC

  1. 注意题目input的内容描述,不能只处理一组输入;
  2. 使用四个int 来存储IP有点浪费空间

###改进 使用 int 存 IP地址

###code in C

#define MAX_SIZE 1010

unsigned int ip_list[MAX_SIZE];
unsigned int min_net;
unsigned int mask;

void min_ip(int n)
{
    mask=~0;
    min_net = ip_list[0];
    while (n--) {
        while ((mask & min_net) != (ip_list[n] & mask)) {
            mask=mask<<1;
            min_net &= mask;
        }
    }
}

unsigned str2IP(char *s)
{
    unsigned ip=0,j=0;
    while (*s!='\0') {
        unsigned char num=0;
        do{
            num = num*10 + *(s++)-'0';
        }while(*s != '.' && *s != '\0');
        ip<<=8;ip^=num;
        ++s,++j;
        if(j>4) break;
    }
    return ip;
}

void print_ip(unsigned ip)
{
    printf("%d.%d.%d.%d\n",(ip>>24)%256,(ip>>16)%256, (ip>>8)%256, ip%256);
}

int main()
{
    int m,n, i=0;
    char buff[50];
    memset(ip_list, 0, sizeof(ip_list));
    
    while (scanf("%d",&n)==1) {
        m = n, i=0;
        while(n--){
            memset(buff,0,sizeof(buff));
            scanf("%s",buff);
            ip_list[i++] =  str2IP(buff);
        }
        min_ip(m);
        print_ip(min_net);
        print_ip(mask);
    }
    return 0;
}