C++ 程式設計題/簡單錯誤記錄,合唱團，馬戲團

問答題

題1：将網絡實體位址轉換為IP位址的協定是？

A： IP

B： ICMP

C： ARP

D： RARP

提示：題目中說的是将實體位址轉換為IP位址，而不是将 IP 位址轉換為實體位址，ARP 是将 IP 位址解析實體位址，RARP 是反向解析，也就是實體位址轉換 IP 位址；

ICMP 是屬于網絡層協定，主要用于在主機與路由器之間傳遞控制資訊，包括報告錯誤、交換受限控制和狀态資訊等。當遇到IP資料無法通路目标、IP路由器無法按目前的傳輸速率轉發資料包等情況時，會自動發送ICMP消息

題2：某IP位址 192.168.48.10，掩碼為255.255.255.128，其所在的子網為？廣播位址為？有效的主機IP位址範圍從 ？到？

提示：子網是掩碼和 IP 位址進行按位與(&)之後所得出的位址，廣播位址是主機位址全為 1 的時候；由于掩碼的後八位是 128 ，是以主機位址占 7 位，那麼全為 1 的時候是主機位址是 127，是以有效的主機位址為後七位是 0000001 - 1111110

程式設計題

題1：簡單錯誤記錄

開發一個簡單錯誤記錄功能小子產品，能夠記錄出錯的代碼所在的檔案名稱和行号處理：

1. 記錄最多 8 條錯誤記錄，循環記錄，對相同的錯誤記錄(淨檔案名稱和行号完全比對)隻記錄一條，錯誤計數增加
2. 超過 16 個字元的檔案名稱，隻記錄檔案的最後有效 16 個字元
3. 輸入的檔案可能帶路徑，記錄檔案名稱不能帶路徑

輸入描述：一行或多行字元串，每行包括帶路徑檔案名稱，行号，以空格隔開

輸出描述：将所有的記錄統計并将結果輸出，格式：檔案名 代碼行數 數目，一個空格隔開，如：

示例:

輸入

E:\V1R2\product\fpgadrive.c 1325

輸出

fpgadrive.c 1325 1

提示：通過一個結構體來儲存一個對象，一個對象中包含檔案名，錯誤行數，錯誤次數這三個成員

最多紀錄 8 次，循環紀錄指的是如果對象少于 8 個則都輸出，如果大于 8 個，輸出最後 8 個對象

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 擷取檔案名
string getFileName(string path) {
	int pos = path.rfind('\\');
	return path.substr(pos + 1);
}

// 截取檔案名後 16 位
string modifyName(string name) {
	if (name.size() > 16) {
		name = name.substr(name.size() - 16);
	}
	return name;
}

struct ErrRecord {
	string file;
	int lineNo;
	int count;
	// 構造函數
	ErrRecord(string file, int lineNo) {
		this->file = file;
		this->lineNo = lineNo;
		count = 1;
	}
	// 檔案名相等的規則
	bool operator==(const ErrRecord & a) {
		return (file == a.file) && (lineNo == a.lineNo);
	}
};

int main() {
	string file;
	int lineNo;
	vector<ErrRecord> myvec;
	while (cin >> file >> lineNo) {
		ErrRecord record(getFileName(file), lineNo);
		auto res = find(myvec.begin(), myvec.end(), record);
		// 如果相等代表沒有記錄
		if (res == myvec.end()) {
			myvec.push_back(record);
		}
		else {
			res->count++;
		}
	}
	int count = 0;
	for (auto item : myvec) {
		if (count + 8 >= myvec.size()) {
			cout << modifyName(item.file)<<" "\
				 << item.lineNo << " "\
				 << item.count << endl;
		}
		count++;
	}
	return 0;
}
           

題2：合唱團

有 n 個學生站成一排，每個學生有一個能力值，牛牛想從這 n 個學生中按照順序選取 k 名學生，要求相鄰兩個學生的位置編号的差不超過 d，使得這 k 個學生的能力值的乘積最大，你能傳回最大的乘積嗎？

輸入描述：每個輸入包含 1 個測試用例。每個測試資料的第一行包含一個整數 n [1,50] 表示學生的個數，接下來的一行，包含 n 個整數，按順序表示每個學生的能力值 ai [-50 , 50],接下來的一行包含兩個整數 k 和 d ，他們的範圍是，k [1,10] 和 d [1, 50]

輸出描述：輸出一行表示最大的乘積

示例:

輸入

3

7 4 7

2 50

輸出

49

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int n, k, d;
	cin >> n;
	vector<int> stud(n);
	for (int i = 0; i < n; i++) {
		cin >> stud[i];
	}
	cin >> k >> d;
	vector<vector<long long>> maxMul(n, vector<long long>(k + 1, 0));
	vector<vector<long long>> minMul(n, vector<long long>(k + 1, 0));

	for (int i = 0; i < n; i++) {
		maxMul[i][1] = stud[i];
		minMul[i][1] = stud[i];
	}

	for (int i = 2; i <= k; i++) {
		for (int j = 0; j < n; j++) {
			for (int m = 1; m <= d && j >= m; m++) {
				maxMul[j][i] = max(maxMul[j][i], max(maxMul[j - m][i - 1] * stud[j], minMul[j - m][i - 1] * stud[j]));
				minMul[j][i] = min(minMul[j][i], min(minMul[j - m][i - 1] * stud[j], maxMul[j - m][i - 1] * stud[j]));
			}
		}
	}

	long long maxMulResult = 0;
	for (int i = 0; i < n; i++) {
		maxMulResult = max(maxMulResult, maxMul[i][k]);
	}
	cout << maxMulResult;
	return 0;
}
           

題3：馬戲團

馬戲團要求疊羅漢過程中，站在某個人肩上的人應該既比自己矮又比自己瘦，或相等。團長想要本次節目中的羅漢塔疊的最高，于是統計了參與最高羅漢塔表演的所有團員的身高體重，并且很快找到疊最高羅漢塔的人員序列

現在你手上也拿到了這樣一份身高體重表，請找出可以疊出的最高羅漢塔的高度，這份表中馬戲團員依次編号為 1 到 N

輸入描述：

首先一個正整數 N，表示人員個數。之後 N 行，每行三個數，分别對應馬戲團員編号，體重和身高

輸出描述：

正整數 m，表示羅漢塔的高度

示例:

輸入

6

1 65 100

2 75 80

3 80 100

4 60 95

5 82 101

6 81 70

輸出

4

提示: 首先對體重進行升序排序，如果體重相等的，按照升高進行降序排序

然後根據升高序列求出最長上升子序列的值，就是我們要輸出的值

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct player{
    int h;
    int w;
};
bool com_w(player p1,player p2){
    if(p1.w == p2.w){
        return p1.h > p2.h;
    }else{
        return p1.w < p2.w;
    }
}


int main(){
    int n,h,w,index;
    vector<player>p;
    while(cin>>n){
        p.clear();
        for(int i = 0;i<n;++i){
            player pt;
            cin>>index>>w>>h;
            pt.h = h;
            pt.w = w;
            p.push_back(pt);
        }
        sort(p.begin(),p.end(),com_w);
        // 對容器進行最長上升子序列的算法
        vector<int>dp2(n+1);
        int max = 0;
        dp2[0] = 1;
        for(int i = 1;i<n;i++){
            dp2[i] = 1;
            for(int j = 0;j<i;j++){
                if(p[j].h <= p[i].h && dp2[j]+1 > dp2[i])
                    dp2[i] = dp2[j] + 1;
            }
        }
        for(int i = 0;i<n;i++){
            if(max < dp2[i])
                max = dp2[i];
        }
        cout<<max<<endl;
    }
    return 0;
}