編程題（共2題，第一題40分，第二題60分，共100分。請(qǐng)上機(jī)編寫程序，按題目要求提交文件。[詳見考試說明]

本試題采用自動(dòng)測(cè)試用例進(jìn)行評(píng)分，測(cè)試用例不對(duì)考生公開，凡不滿足提交要求導(dǎo)致不能運(yùn)行或用例不通過，不予評(píng)分）。

?

1. 識(shí)別字符串中的整數(shù)并轉(zhuǎn)換為數(shù)字形式（40分）

問題描述：?
識(shí)別輸入字符串中所有的整數(shù)，統(tǒng)計(jì)整數(shù)個(gè)數(shù)并將這些字符串形式的整數(shù)轉(zhuǎn)換為數(shù)字形式整數(shù)。

要求實(shí)現(xiàn)函數(shù)：?
void take_num(const char *strIn, int *n, unsigned int *outArray)

【輸入】 strIn：?? 輸入的字符串

【輸出】 n：?????? 統(tǒng)計(jì)識(shí)別出來的整數(shù)個(gè)數(shù)

?????? outArray：識(shí)別出來的整數(shù)值，其中outArray[0]是輸入字符串中從左到右第一個(gè)整數(shù)，

?outArray[1]是第二個(gè)整數(shù)，以此類推。數(shù)組地址已經(jīng)分配，可以直接使用

【返回】 無

注：

I、???? 不考慮字符串中出現(xiàn)的正負(fù)號(hào)(+, -)，即所有轉(zhuǎn)換結(jié)果為非負(fù)整數(shù)（包括0和正整數(shù)）

II、??? 不考慮轉(zhuǎn)換后整數(shù)超出范圍情況，即測(cè)試用例中可能出現(xiàn)的最大整數(shù)不會(huì)超過unsigned int可處理的范圍

III、?? 需要考慮 '0' 開始的數(shù)字字符串情況，比如 "00035" ，應(yīng)轉(zhuǎn)換為整數(shù)35；

??????? "000" 應(yīng)轉(zhuǎn)換為整數(shù)0；"00.0035" 應(yīng)轉(zhuǎn)換為整數(shù)0和35（忽略小數(shù)點(diǎn)：mmm.nnn當(dāng)成兩個(gè)數(shù)mmm和nnn來識(shí)別）

IV、?? 輸入字符串不會(huì)超過100 Bytes，請(qǐng)不用考慮超長(zhǎng)字符串的情況。

示例?
輸入：strIn = "ab00cd+123fght456-25? 3.005fgh"

輸出：n = 6

outArray = {0, 123, 456, 25, 3, 5}

?

2. IP地址匹配（60分）

問題描述：?
在路由器中，一般來說轉(zhuǎn)發(fā)模塊采用最大前綴匹配原則進(jìn)行目的端口查找，具體如下：

IP地址和子網(wǎng)地址匹配：

IP地址和子網(wǎng)地址所帶掩碼做AND運(yùn)算后，得到的值與子網(wǎng)地址相同，則該IP地址與該子網(wǎng)匹配。

?

比如：

IP地址：192.168.1.100

子網(wǎng)：192.168.1.0/255.255.255.0，其中192.168.1.0是子網(wǎng)地址，255.255.255.0是子網(wǎng)掩碼。

192.168.1.100&255.255.255.0 = 192.168.1.0，則該IP和子網(wǎng)192.168.1.0匹配

?

IP地址：192.168.1.100

子網(wǎng)：192.168.1.128/255.255.255.192

192.168.1.100&255.255.255.192 = 192.168.1.64，則該IP和子網(wǎng)192.168.1.128不匹配

?

最大前綴匹配：

任何一個(gè)IPv4地址都可以看作一個(gè)32bit的二進(jìn)制數(shù)，比如192.168.1.100可以表示為：11000000.10101000.00000001.01100100，

192.168.1.0可以表示為11000000.10101000.00000001.00000000

最大前綴匹配要求IP地址同子網(wǎng)地址匹配的基礎(chǔ)上，二進(jìn)制位從左到右完全匹配的位數(shù)盡量多（從左到右子網(wǎng)地址最長(zhǎng)）。比如：

IP地址192.168.1.100，同時(shí)匹配子網(wǎng)192.168.1.0/255.255.255.0和子網(wǎng)192.168.1.64/255.255.255.192，

但對(duì)于子網(wǎng)192.168.1.64/255.255.255.192，匹配位數(shù)達(dá)到26位，多于子網(wǎng)192.168.1.0/255.255.255.0的24位，

因此192.168.1.100最大前綴匹配子網(wǎng)是192.168.1.64/255.255.255.192。

?

請(qǐng)編程實(shí)現(xiàn)上述最大前綴匹配算法。

要求實(shí)現(xiàn)函數(shù)：?
void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n)

【輸入】ip_addr：IP地址字符串，嚴(yán)格保證是合法IPv4地址形式的字符串

??????? net_addr_array：子網(wǎng)地址列表，每一個(gè)字符串代表一個(gè)子網(wǎng)，包括子網(wǎng)地址和掩碼，

??????????????????????? 表現(xiàn)形式如上述，子網(wǎng)地址和子網(wǎng)掩碼用’/’分開，嚴(yán)格保證是

??????????????????????? 合法形式的字符串；如果讀到空字符串，表示子網(wǎng)地址列表結(jié)束

【輸出】n：最大前綴匹配子網(wǎng)在*net_addr_array[]數(shù)組中對(duì)應(yīng)的下標(biāo)值。如果沒有匹配返回-1

示例?
輸入：

ip_addr = "192.168.1.100"

net_addr_array[] =

{

"192.168.1.128/255.255.255.192",

"192.168.1.0/255.255.255.0",

"192.168.1.64/255.255.255.192",

"0.0.0.0/0.0.0.0",

""

}

輸出：n = 2

?

參考程序（歡迎討論）轉(zhuǎn)載請(qǐng)注明來源http://www.cnblogs.com/jerry19880126/

1 #include <iostream> 2 using namespace std; 3 4 5 // 編程題第一題 6 // 識(shí)別輸入字符串中所有的整數(shù)，統(tǒng)計(jì)整數(shù)個(gè)數(shù)并將這些字符串形式的整數(shù)轉(zhuǎn)換為數(shù)字形式整數(shù) 7 void take_num(const char *strIn, int *n, unsigned int *outArray) 8 { 9 unsigned int len = strlen(strIn); 10 unsigned int outArrayIndex = 0; 11 bool hasNumber = false; // temp 中已經(jīng)存在有效數(shù)字 12 unsigned int temp = 0; 13 *n = 0; 14 for(unsigned int i = 0; i < len; ++i) 15 { 16 if(strIn[i] >= '0' && strIn[i] <= '9') 17 { 18 if(hasNumber == false) 19 { 20 // 間隔后第一次出現(xiàn)的數(shù)字 21 ++*n; 22 } 23 else 24 { 25 // 連續(xù)出現(xiàn)的數(shù)字 26 } 27 hasNumber = true; 28 temp = temp * 10 + (strIn[i] - '0'); 29 } 30 else 31 { 32 if(hasNumber) 33 { 34 outArray[outArrayIndex++] = temp; 35 temp = 0; 36 hasNumber = false; 37 } 38 } 39 } 40 if(hasNumber) 41 { 42 outArray[outArrayIndex++] = temp; 43 } 44 } 45 46 47 // 編程題第二題 48 // IP地址最長(zhǎng)匹配問題，要求不僅是匹配，而且是最長(zhǎng)匹配 49 void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n) 50 { 51 int arrayIndex = 0; 52 *n = -1; 53 const char* p = net_addr_array[arrayIndex]; 54 int maxLength = -1; //記錄最長(zhǎng)匹配串最遠(yuǎn)的1的位置 55 int number = 0;// 用于轉(zhuǎn)換字符串形式的點(diǎn)分十進(jìn)制數(shù)至整數(shù) 56 //先把IP址址轉(zhuǎn)換成int型元素的數(shù)組 57 int ipAddress[4]; 58 int netIndex = 0; 59 int ipLen = strlen(ip_addr); 60 for(int i = 0; i <= ipLen; ++i) 61 { 62 if(ip_addr[i] >= '0' && ip_addr[i] <= '9') 63 { 64 number = number * 10 + (ip_addr[i] - '0'); 65 } 66 else 67 { 68 ipAddress[netIndex++] = number; 69 number = 0; 70 } 71 } 72 while(*p != '\0') 73 { 74 75 int netAddress[4];//子網(wǎng)地址 76 int maskAddress[4];//子網(wǎng)掩碼 77 netIndex = 0; 78 //將點(diǎn)分十進(jìn)制轉(zhuǎn)成4個(gè)int元素 79 int len = strlen(p); // 本次 IP地址/子網(wǎng)掩碼 字符串的長(zhǎng)度 80 number = 0; 81 int i; 82 //先轉(zhuǎn)換給定的子網(wǎng)地址 83 for(i = 0; ; ++i) 84 { 85 if(p[i] >= '0' && p[i] <= '9') 86 { 87 number = number * 10 + (p[i] - '0'); 88 } 89 else 90 { 91 netAddress[netIndex++] = number; 92 number = 0; 93 if(p[i] == '/') 94 { 95 netIndex = 0; 96 break; 97 } 98 } 99 } 100 101 //再轉(zhuǎn)換子網(wǎng)掩碼 102 for(++i; i <= len; ++i) 103 { 104 if(p[i] >= '0' && p[i] <= '9') 105 { 106 number = number * 10 + (p[i] - '0'); 107 } 108 else 109 { 110 maskAddress[netIndex++] = number; 111 number = 0; 112 } 113 } 114 netIndex = 0; 115 116 //判斷IP地址和子網(wǎng)掩網(wǎng)的與 是否 和 子網(wǎng)地址相同 117 int j = 0; 118 for(;j < 4; ++j) 119 { 120 if((ipAddress[j] & maskAddress[j]) != netAddress[j]) 121 { 122 break; 123 } 124 } 125 if(j >= 4) 126 { 127 //匹配 128 //再比較長(zhǎng)度，從最后往前數(shù)，記錄下第一個(gè)出現(xiàn)1的位置 129 int currentLength = 0; 130 for(int k = 3; k >= 0; --k) 131 { 132 if(netAddress[k] != 0) 133 { 134 currentLength = k * 8; 135 // 將十進(jìn)制轉(zhuǎn)成二進(jìn)制 136 char binaryArray[8]; 137 int temp = netAddress[k]; 138 int index = 0; 139 while(temp > 0) 140 { 141 if(temp % 2 == 0) 142 { 143 binaryArray[index++] = '0'; 144 } 145 else 146 { 147 binaryArray[index++] = '1'; 148 } 149 temp /= 2; 150 } 151 while(index <= 7) 152 { 153 binaryArray[index++] = '0'; 154 } 155 for(int k = 0; k < 8; ++k) 156 { 157 if(binaryArray[k] == '1') 158 { 159 currentLength += (8 - k); 160 break; 161 } 162 } 163 break; 164 } 165 } 166 if(currentLength > maxLength) 167 { 168 maxLength = currentLength; 169 *n = arrayIndex; 170 } 171 } 172 //輸入下一個(gè)數(shù)組 173 ++arrayIndex; 174 p = net_addr_array[arrayIndex]; 175 } 176 } 177 178 179 // 輸出 180 void output(unsigned int* a, unsigned int len) 181 { 182 for(unsigned int i = 0; i < len; ++i) 183 { 184 cout << a[i] << " "; 185 } 186 cout << endl; 187 } 188 189 int main() 190 { 191 cout << "第一題測(cè)試樣例：" << endl; 192 char *strIn = "ab00cd+123fght456-25 3.005fgh"; 193 unsigned int outArray[100]; 194 int n; 195 take_num(strIn, &n, outArray); 196 output(outArray, n); 197 198 cout << endl << "第二題測(cè)試樣例：" << endl; 199 const char* ip_addr = "192.168.1.100"; 200 const char *net_addr_array[] = 201 { 202 "192.168.1.128/255.255.255.192", 203 "192.168.1.0/255.255.255.0", 204 "192.168.1.64/255.255.255.192", 205 "0.0.0.0/0.0.0.0", 206 "" 207 }; 208 max_prefix_match(ip_addr, net_addr_array, &n); 209 cout << n << endl; 210 }

轉(zhuǎn)載于:https://www.cnblogs.com/jerry19880126/archive/2012/08/06/2625854.html

總結(jié)

以上是生活随笔為你收集整理的华为2011上机笔试题2+参考程序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。