資料結構與演算法基礎實驗大合集
- 實驗一 線性表的創建、銷毀、插入、洗掉、遍歷等操作的實作：兩個有序鏈表序列的合并
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗二 佇列類的實作與測驗 ：銀行業務佇列簡單模擬
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗三 堆疊與佇列的應用 ：迷宮尋路
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗四 樹的存盤結構 ：樹的遍歷
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗五 哈夫曼編碼 ：哈夫曼編碼
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗六 圖的存盤 ：漢密爾頓回路
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗七 貪心演算法 ：月餅
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗八 圖的應用 ：列出連通集
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗九 動態規劃 ：湊零錢
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
- 實驗十 分治演算法 ：找第k小的數## 一、 題目
- 一、 題目
- 二、 解題思路
- 三、 程式設計
- 四、 程式詳解及運行結果
- 五、 問題及解決程序
實驗一 線性表的創建、銷毀、插入、洗掉、遍歷等操作的實作：兩個有序鏈表序列的合并
一、 題目
????已知兩個非降序鏈表序列S1與S2，設計函式構造出S1與S2合并后的新的非降序鏈表S3，
輸入格式:
????輸入分兩行，分別在每行給出由若干個正整數構成的非降序序列，用?1表示序列的結尾（?1不屬于這個序列），數字用空格間隔，
輸出格式:
????在一行中輸出合并后新的非降序鏈表，數字間用空格分開，結尾不能有多余空格；若新鏈表為空，輸出NULL，
二、 解題思路
????考察鏈表的基礎操作，鏈表為有序鏈表，需要定義一個結構體來實作鏈表資料結構，讀入鏈表后比較當前指標所指的兩個結點的值，將小的插入新的鏈表，指標指向下一個元素，重復上述操作即可，
三、 程式設計
宣告三個鏈表并開辟空間
定義指標p，指向第一個鏈表第一個結點
定義指標q，指向第二個鏈表第一個結點
while (p，q都不為NULL) {
if（p指向的值大于q指向的值）
將q指向的值插入第三個鏈表
q指向下一個結點
else
將p指向的值插入第三個鏈表
p指向下一個結點
}
輸出第三個鏈表
四、 程式詳解及運行結果
#include<iostream>
using namespace std;
struct LNode {
int val;
LNode* next = NULL;
};
int main() {
LNode* L1;
L1 = (LNode*)malloc(sizeof(LNode));
LNode* L2;
L2 = (LNode*)malloc(sizeof(LNode));
LNode* L3;
L3 = (LNode*)malloc(sizeof(LNode));
int temp;
cin >> temp;
LNode* l1 = L1;
while (temp != -1) {
l1->next = (LNode*)malloc(sizeof(LNode));//每次都要開辟空間
l1 = l1->next;
l1->val = temp;
l1->next = NULL;
cin >> temp;
}
cin >> temp;
LNode* l2 = L2;
while (temp != -1) {
l2->next = (LNode*)malloc(sizeof(LNode));
l2 = l2->next;
l2->val = temp;
l2->next = NULL;
cin >> temp;
}
LNode* l3 = L3;
L1 = L1->next;
L2 = L2->next;
while (L1 && L2)
{
if (L1->val <= L2->val) {
l3->next = (LNode*)malloc(sizeof(LNode));
l3 = l3->next;
l3->val=L1->val;
l3->next = NULL;
L1 = L1->next;
}
else {
l3->next = (LNode*)malloc(sizeof(LNode));
l3 = l3->next;
l3->val = L2->val;
l3->next = NULL;
L2 = L2->next;
}
}
if (L2==NULL) {
while (L1!=NULL) {
l3->next = (LNode*)malloc(sizeof(LNode));
l3 = l3->next;
l3->val = L1->val;
l3->next = NULL;
L1 = L1->next;
}
}
else {
while (L2!=NULL) {
l3->next = (LNode*)malloc(sizeof(LNode));
l3 = l3->next;
l3->val = L2->val;
l3->next = NULL;
L2 = L2->next;
}
}
if (L3==NULL) {
cout << "NULL" << endl;
}
else {
L3 = L3->next;
cout << L3->val;
L3 = L3->next;
while (L3!=NULL) {
cout << " " << L3->val;
L3 = L3->next;
}
cout << endl;
}
return 0;
}
五、 問題及解決程序
????指標每次指向下一個節點之前，都要先開辟空間再訪問，并且每次要將next成員賦值成NULL，以方便后續操作，
實驗二 佇列類的實作與測驗 ：銀行業務佇列簡單模擬
一、 題目
????設某銀行有A、B兩個業務視窗，且處理業務的速度不一樣，其中A視窗處理速度是B視窗的2倍 —— 即當A視窗每處理完2個顧客時，B視窗處理完1個顧客，給定到達銀行的顧客序列，請按業務完成的順序輸出顧客序列，假定不考慮顧客先后到達的時間間隔，并且當不同視窗同時處理完2個顧客時，A視窗顧客優先輸出，
輸入格式:
????輸入為一行正整數，其中第1個數字N(≤1000)為顧客總數，后面跟著N位顧客的編號，編號為奇數的顧客需要到A視窗辦理業務，為偶數的顧客則去B視窗，數字間以空格分隔，
輸出格式:
????按業務處理完成的順序輸出顧客的編號，數字間以空格分隔，但最后一個編號后不能有多余的空格，
二、 解題思路
????考察佇列的相關基礎操作，用線性表模擬佇列來實作佇列的相關操作即可，
三、 程式設計
宣告三個陣列
while(資料數量--){
if(為奇數)
放入第一個陣列
if(為偶數)
放入第二個陣列
}
while(第一個陣列和第二個陣列均不為空){
第一個陣列->第三個陣列
第一個陣列->第三個陣列
第二個陣列->第三個陣列
}
if(第一個陣列先空)
第二個陣列剩余元素->第三個陣列
else
第一個陣列剩余元素->第三個陣列
輸出第三個陣列
四、 程式詳解及運行結果
#include<iostream>
using namespace std;
int main() {
int ans[1001],ji[1001],ou[1001];
int n, tem, aa = 0, o = 0, p = 0, l = 0, u = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tem;
if (tem % 2) {
ji[o] = tem;
o++;
}
else {
ou[p] = tem;
p++;
}
}
while (n) {
if (u!=o && n) {
ans[aa] = ji[u];
aa++;
u++;
n--;
}
if (u != o && n) {
ans[aa] = ji[u];
aa++;
u++;
n--;
}
if (l != p && n) {
ans[aa] = ou[l];
aa++;
l++;
n--;
}
}
cout << ans[0];
for (int i = 1; i < aa; i++) {
cout << " " << ans[i];
}
cout << endl;
return 0;
}
五、 問題及解決程序
????每個線性表定義兩個下標表示隊首、隊尾，通過下標的移動來模擬出隊，入隊操作，
實驗三 堆疊與佇列的應用 ：迷宮尋路
一、 題目
????給定一個M行N列的迷宮圖，其中 "0"表示可通路，"1"表示障礙物，無法通行，在迷宮中只允許在水平或上下四個方向的通路上行走，走過的位置不能重復走，
????5行8列的迷宮如下：
- 0 1 1 1 0 0 0 0
- 0 0 0 1 0 0 0 0
- 0 1 0 0 0 1 0 0
- 0 1 1 1 0 1 1 0
- 1 0 0 0 0 0 0 0
????則從左上角（1，1）至右下角（5，8）的最短路徑為：
1,1--> 2,1--> 2,2--> 2,3--> 3,3 --> 3,4--> 3,5--> 4,5--> 5,5--> 5,6--> 5,7--> 5,8
????題目保證每個迷宮最多只有一條最短路徑，
????請輸出該條最短路徑，如果不存在任何通路，則輸出"NO FOUND".
輸入格式:
????第一行，輸入M和N值，表示迷宮行數和列數，接著輸入M行數值，其中，0表示通路，1表示障礙物，每列數值用空格符間隔，接下來可能輸入多組迷宮資料，當輸入M的值為-1時結束輸入，
輸出格式:
????按行順序輸出路徑的每個位置的行數和列數，如 x,y，如果不存在任何路徑，則輸出"NO FOUND".每組迷宮尋路結果用換行符間隔，
二、 解題思路
????考察運用佇列進行廣度優先搜索，（也可以用堆疊進行深度優先搜索求解）
三、 程式設計
定義一個佇列
將起點加入佇列
while(1)
將當前佇列中所有節點向四周的可達節點擴散
記錄每一個擴散節點和到達該頂點的步數
if(佇列為空)
回傳找不到
if(達到終點)
退出回圈
通過記錄的步數找出路徑
輸出路徑
回傳找到了
四、 程式詳解及運行結果
#include <iostream>
#include <queue>
#include <vector>
#include<stdio.h>
using namespace std;
struct Position{
int row;
int col;
};
Position fx[4];
bool findpath(vector<vector<int>>MG, int row, int col){
fx[0].row = 0; fx[0].col = 1;
fx[1].row = 1; fx[1].col = 0;
fx[2].row = 0; fx[2].col = -1;
fx[3].row = -1; fx[3].col = 0;
for (int i = 0; i < row + 2; i++){
MG[i][col + 1] = 1;
MG[i][0] = 1;
}//邊界標成 1
for (int i = 0; i < col + 2; i++){
MG[0][i] = 1;
MG[row + 1][i] = 1;
}//邊界標成 1
MG[1][1] = 2;
queue<Position> road;//用于廣搜的佇列
Position next;
Position here;
here.col = 1; here.row = 1;
while (1){
for (int i = 0; i < 4; i++){
next.row = here.row + fx[i].row;
next.col = here.col + fx[i].col;
if (MG[next.row][next.col] == 0){
MG[next.row][next.col] = MG[here.row][here.col] + 1;//記錄到每一個頂點的步數
if ((next.row == row) && (next.col == col))
break;
road.push(next);
}
}
if ((next.row == row) && (next.col == col))
break;
if (road.empty())
return false;
here = road.front();
road.pop();
}
int far = MG[row][col] - 2;
vector<Position>path(far);
here.row = row;
here.col = col;
for (int i = far - 1; i >= 0; i--){
path[i] = here;
for (int j = 0; j < 4; j++){
next.row = here.row + fx[j].row;
next.col = here.col + fx[j].col;
if (MG[next.row][next.col] == i + 2)
break;
}
here = next;
}
cout << "1,1" << endl;
for (int i = 0; i < far; i++)
cout << path[i].row << "," << path[i].col << endl;
return true;
}
int main(){
int a, b;
cin >> a >> b;
vector<vector<int>>mg(a + 2, vector<int>(b + 2));
while (a != -1 && b != -1){
for (int i = 1; i < a + 1; i++)
for (int j = 1; j < b + 1; j++)
cin >> mg[i][j];
if (findpath(mg, a, b))
cout << endl;
else
cout << "NO FOUND" << endl;
cin >> a >> b;
}
}
五、 問題及解決程序
????輸出路徑是該題難點，這里我通過標記到達每一個頂點的步數從終點一步步往回找前驅節點存盤到陣列中，再進行輸出，
實驗四 樹的存盤結構 ：樹的遍歷
一、 題目
????給定一棵二叉樹的后序遍歷和中序遍歷，請你輸出其層序遍歷的序列，這里假設鍵值都是互不相等的正整數，
輸入格式:
????輸入第一行給出一個正整數N（≤30），是二叉樹中結點的個數，第二行給出其后序遍歷序列，第三行給出其中序遍歷序列，數字間以空格分隔，
輸出格式:
????在一行中輸出該樹的層序遍歷的序列，數字間以1個空格分隔，行首尾不得有多余空格，
二、 解題思路
????主要考察樹的遍歷方法，先通過中序遍歷序列和后序遍歷序列將樹構造出來，然后再輸出層序遍歷結果，
三、 程式設計
宣告樹的結點結構體
先通過后序遍歷序列找到跟結點
再結合中序遍歷將樹構架出來
宣告三個變數標記中序遍歷序列與后序遍歷序列遍歷的當前位置
用遞回函式造樹
if (中序序列遍歷完畢)
回傳NULL
宣告一個結點
將后序序列最后一個值賦給當前結點
r->val = a[end_hou];
在中序序列中找到該結點的值所處位置
在該結點值所處位置左右分別遞回該構造樹的函式
最后利用廣度優先搜索將樹層序遍歷
四、 程式詳解及運行結果
#include <iostream>
#include<vector>
#include<queue>
using namespace std;
typedef struct node {
int val;
struct node* left;
struct node* right;
}node, * tree;
vector<int>ans;
vector<int>b(31);
vector<int>a(31);
queue<tree> c;
tree Du(int end_hou, int begin_zhong, int end_zhong) {
if (begin_zhong == end_zhong)
return NULL;
tree r = new node();
r->val = a[end_hou];
int i, t = a[end_hou];
for (i = begin_zhong; i < end_zhong; ++i)
if (t == b[i])
break;
r->left = Du(end_hou - (end_zhong - i), begin_zhong, i);
r->right = Du(end_hou - 1, i + 1, end_zhong);
return r;
}
int main() {
int n, x;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int tem;
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
tree root = Du(n, 1, n + 1);
if (root)
c.push(root);
while (!c.empty())
{
int n = c.size();
for (int i = 0; i < n; i++)
{
tree tem = c.front();
c.pop();
ans.push_back(tem->val);
if (tem->left)
c.push(tem->left);
if (tem->right)
c.push(tem->right);
}
}
cout << ans[0];
for (int i = 1; i < ans.size(); ++i) {
cout << " " << ans[i];
}
return 0;
}
五、 問題及解決程序
????該題最難的部分是利用中序后序序列對樹進行還原，需熟記樹的遍歷方法及其相應遍歷結果，找到方法后再進行還原，
實驗五 哈夫曼編碼 ：哈夫曼編碼
一、 題目
????給定一段文字，如果我們統計出字母出現的頻率，是可以根據哈夫曼演算法給出一套編碼，使得用此編碼壓縮原文可以得到最短的編碼總長，然而哈夫曼編碼并不是唯一的，例如對字串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出現頻率對應為 4、2、1、1，我們可以設計編碼 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，還可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套編碼都可以把原文壓縮到 14 個位元組，但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼編碼，因為用這套編碼壓縮得到 00001011001001 后，解碼的結果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以對應解碼的結果，本題就請你判斷任一套編碼是否哈夫曼編碼，
輸入格式:
????首先第一行給出一個正整數 N（2≤N≤63），隨后第二行給出 N 個不重復的字符及其出現頻率，格式如下：
c[1] f[1] c[2] f[2] ... c[N] f[N]
????其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出現頻率，為不超過 1000 的整數，再下一行給出一個正整數 M（≤1000），隨后是 M 套待檢的編碼，每套編碼占 N 行，格式為：
c[i] code[i]
????其中c[i]是第i個字符；code[i]是不超過63個’0’和’1’的非空字串，
輸出格式:
????對每套待檢編碼，如果是正確的哈夫曼編碼，就在一行中輸出"Yes"，否則輸出"No"，
????注意：最優編碼并不一定通過哈夫曼演算法得到，任何能壓縮到最優長度的前綴編碼都應被判為正確，
二、 解題思路
????考察哈夫曼編碼性質，哈夫曼編碼不唯一，但是長度肯定唯一，求出帶權路徑長度即可，
三、 程式設計
先將每個字符出現頻率看作權值存進陣列并進行升序排序
while(陣列不為空)
拿出陣列最小的兩個元素求和，并將結果插入陣列
陣列按升序排序
最后一個在陣列中的元素即為哈夫曼編碼長度
if(截取字串判斷輸入的編碼為其他結點的前綴)
回傳NO
if(輸入的編碼長度 = 哈夫曼編碼長度)
回傳NO
回傳YES
四、 程式詳解及運行結果
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
int main() {
int n, tem;
char t;
cin >> n;
map<char, int>a;
vector<int>b;
for (int i = 0; i < n; ++i) {
cin >> t >> tem;
a[t] = tem;
b.push_back(tem);
}
sort(b.begin(), b.end());
int sum = 0;
while (b.size() > 1) {
int temp = b[0] + b[1];
b.erase(b.begin() + 0);
b.erase(b.begin() + 0);
b.push_back(temp);
sum += temp;
sort(b.begin(), b.end());
}
int m;
cin >> m;
char s[1001];
string ss[1001];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> s[j];
cin >> ss[j];
}
int x = 0, flag = 0;
for (int j = 0; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
int p = min(ss[j].length(), ss[k].length());
if (ss[j].substr(0, p) == ss[k].substr(0, p)) {
flag = 1;
break;
}
}
if (!flag) {
auto it = a.find(s[j]);
x += (ss[j].length() * it->second);
}
else
break;
}
if (!flag && x == sum)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
五、 問題及解決程序
????宣告下標，利用線性表進行模擬實作優先級佇列，要注意每次插入新的權時都要重新給陣列排序，
實驗六 圖的存盤 ：漢密爾頓回路
一、 題目
????著名的“漢密爾頓（Hamilton）回路問題”是要找一個能遍歷圖中所有頂點的簡單回路（即每個頂點只訪問 1 次），本題就要求你判斷任一給定的回路是否漢密爾頓回路，
輸入格式:
????首先第一行給出兩個正整數：無向圖中頂點數 N（2<N≤200）和邊數 M，隨后 M 行，每行給出一條邊的兩個端點，格式為“頂點1 頂點2”，其中頂點從 1 到 N 編號，再下一行給出一個正整數 K，是待檢驗的回路的條數，隨后 K 行，每行給出一條待檢回路，格式為：n V1 V2 ? Vn其中 n 是回路中的頂點數，Vi是路徑上的頂點編號，
輸出格式:
????對每條待檢回路，如果是漢密爾頓回路，就在一行中輸出"YES"，否則輸出"NO"，
二、 解題思路
????考察圖的遍歷，遍歷同一個點兩次，兩點間沒有通路或者頂點沒有全部遍歷，便說明不是漢密爾頓回路，
三、 程式設計
讀入鄰接矩陣
if(回路頂點數!=d頂點總數)
不是漢密爾頓回路
if(回路第一個點與最后一個點不一樣)
不是漢密爾頓回路
宣告bool型別陣列
for(頂點 in 回路)
頂點為true
if(當前頂點與上一個頂點不連通)
不是漢密爾頓回路
if(bool陣列全為true)
是漢密爾頓回路
else
不是漢密爾頓回路
四、 程式詳解及運行結果
#include <iostream>
#include<vector>
using namespace std;
int main() {
int k, n, m, x, y;
cin >> n >> m;
int N = 2 * n;
vector<vector<int>>a(N, vector<int>(N, 0));
for (int i = 0; i < m; ++i) {
cin >> x >> y;
a[x][y] = 1;
a[y][x] = 1;
}
cin >> k;
while (k--) {
int h, t;
cin >> h;
if (h != n + 1) {
cout << "NO" << endl;
for (int i = 0; i < h; ++i) {
cin >> t;
}
continue;
}
vector<int>c(N);
vector<bool>b(N, false);
int flag = 1;
cin >> c[0];
b[c[0]] = true;
for (int j = 1; j < h; ++j) {
cin >> c[j];
if (!a[c[j]][c[j - 1]]) {
flag = 0;
}
b[c[j]] = true;
}
if (c[h - 1] != c[0])
flag = 0;
for (int j = 1; j <= n; ++j) {
if (!b[j]) {
flag = 0;
break;
}
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
五、 問題及解決程序
????如果經過的點數不為頂點數，或第一個點與最后一個點不同，便可以直接回傳不是漢密爾頓回路，要注意判斷經過一個點兩次的情況，
實驗七 貪心演算法 ：月餅
一、 題目
????月餅是中國人在中秋佳節時吃的一種傳統食品，不同地區有許多不同風味的月餅，現給定所有種類月餅的庫存量、總售價、以及市場的最大需求量，請你計算可以獲得的最大收益是多少，
????注意：銷售時允許取出一部分庫存，樣例給出的情形是這樣的：假如我們有 3 種月餅，其庫存量分別為 18、15、10 萬噸，總售價分別為 75、72、45 億元，如果市場的最大需求量只有 20 萬噸，那么我們最大收益策略應該是賣出全部 15 萬噸第 2 種月餅、以及 5 萬噸第 3 種月餅，獲得 72 + 45/2 = 94.5（億元），
輸入格式:
????每個輸入包含一個測驗用例，每個測驗用例先給出一個不超過 1000 的正整數 N 表示月餅的種類數、以及不超過 500（以萬噸為單位）的正整數 D 表示市場最大需求量，隨后一行給出 N 個正數表示每種月餅的庫存量（以萬噸為單位）；最后一行給出 N 個正數表示每種月餅的總售價（以億元為單位），數字間以空格分隔，
輸出格式:
????對每組測驗用例，在一行中輸出最大收益，以億元為單位并精確到小數點后 2 位，
二、 解題思路
????要想獲取最大收益，通過售價與庫存的比值降序排序，并按需求量輸出即可，
三、 程式設計
宣告一個含有庫存量和售價的結構體
撰寫用于排序比較售價與庫存比值的函式
然后讀入資料并進行排序即可
四、 程式詳解及運行結果
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct yb{
double kucun;
double shoujia;
};
bool cmp(yb a, yb b){
return (a.shoujia / a.kucun) > (b.shoujia / b.kucun);
}
int main(){
double n, m, ans = 0;
cin >> n >> m;
vector<yb> a(n);
for (int i = 0; i < n; i++)
cin >> a[i].kucun;
for (int i = 0; i < n; i++)
cin >> a[i].shoujia;
sort(a.begin(), a.end(), cmp);
for (int i = 0; i < n; i++){
if (m > a[i].kucun){
m -= a[i].kucun;
ans += a[i].shoujia;
}
else{
ans += (a[i].shoujia / a[i].kucun * m);
break;
}
}
printf("%.2f", ans);
return 0;
}
五、 問題及解決程序
????為避免宣告多個陣列來存盤資料，下標因排序變得混亂，定義結構體來更高效的存盤，排序，處理資料，
實驗八 圖的應用 ：列出連通集
一、 題目
????給定一個有N個頂點和E條邊的無向圖，請用DFS和BFS分別列出其所有的連通集，假設頂點從0到N?1編號，進行搜索時，假設我們總是從編號最小的頂點出發，按編號遞增的順序訪問鄰接點，
輸入格式:
????輸入第1行給出2個整數N(0<N≤10)和E，分別是圖的頂點數和邊數，隨后E行，每行給出一條邊的兩個端點，每行中的數字之間用1空格分隔，
輸出格式:
????按照"{ v1 v2 … vk }"的格式，每行輸出一個連通集，先輸出DFS的結果，再輸出BFS的結果，
二、 解題思路
????考察利用圖的遍歷，對圖的連通性進行判斷，并列出深搜與廣搜的連通集，
三、 程式設計
提前宣告一個陣列存盤要輸出的連通集
宣告一個用于深搜的堆疊和一個用于廣搜的佇列
讀入圖
對圖進行深度優先搜索與廣度優先搜索
每找到一個連通集便輸出
輸出后清空陣列
四、 程式詳解及運行結果
#include <vector>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
queue<int> bfss;
stack<int> dfss;
int h;
vector<int> ans;
void bfs(vector<vector<int>> b, vector<bool>& a, int n){
for (h = 0; h < n; h++){
if (a[h])
continue;
bfss.push(h);
ans.push_back(h);
a[h] = true;
while (!bfss.empty()){
int temp = bfss.front();
bfss.pop();
for (int k = 0; k < n; k++){
if ((b[temp][k] || b[k][temp]) && !a[k]){
a[k] = true;
ans.push_back(k);
bfss.push(k);
}
}
}
cout << "{ ";
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
cout << "}" << endl;
vector<int>::iterator it;
for (it = ans.begin(); it != ans.end();)
it = ans.erase(it);
}
}
void dfs(vector<vector<int>> b, vector<bool>& a, int n, int h){
a[h] = true;
ans.push_back(h);
for (int i = 0; i < n; i++)
if ((b[h][i] || b[i][h]) && !a[i])
dfs(b, a, n, i);
}
int main(){
int n, e, l, r;
cin >> n >> e;
vector<vector<int>> b(n, vector<int>(n, 0));
vector<bool> a(n, false);
for (int i = 0; i < e; ++i){
cin >> l >> r;
b[l][r] = 1;
b[r][l] = 1;
}
for (h = 0; h < n; h++){
if (a[h])
continue;
a[h] = true;
dfs(b, a, n, h);
cout << "{ ";
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
cout << "}" << endl;
vector<int>::iterator it;
for (it = ans.begin(); it != ans.end();)
it = ans.erase(it);
}
for (int i = 0; i < n; i++)
a[i] = false;
bfs(b, a, n);
return 0;
}
五、 問題及解決程序
????判斷連通性即可，要注意及時清空陣列，避免輸出時出現錯誤，
實驗九 動態規劃 ：湊零錢
一、 題目
????韓梅梅喜歡滿宇宙到處逛街，現在她逛到了一家火星店里，發現這家店有個特別的規矩：你可以用任何星球的硬幣付錢，但是絕不找零，當然也不能欠債，韓梅梅手邊有 104 枚來自各個星球的硬幣，需要請你幫她盤算一下，是否可能精確湊出要付的款額，
輸入格式:
????輸入第一行給出兩個正整數：N（≤104）是硬幣的總個數，M（≤102）是韓梅梅要付的款額，第二行給出 N 枚硬幣的正整數面值，數字間以空格分隔，
輸出格式:
????在一行中輸出硬幣的面值 V1≤V2≤?≤Vk，滿足條件 V1 +V2 +…+Vk=M，數字間以 1 個空格分隔，行首尾不得有多余空格，若解不唯一，則輸出最小序列，若無解，則輸出 No Solution，
????注：我們說序列{ A[1],A[2],? }比{ B[1],B[2],? }“小”，是指存在 k≥1 使得 A[i]=B[i] 對所有 i<k 成立，并且 A[k]<B[k]，
二、 解題思路
????考察動態規劃，求每種面值硬幣只有一個的情況下取最多硬幣湊出目標的情況，可以先利用深搜得到答案后，再用剪枝的方法簡化程式，列出所有情況及選擇到陣列中，就成了動態規劃，
三、 程式設計
定義bool型別二維陣列choice
和一維陣列a來存盤所有零錢面額
宣告一維陣列來儲存當前最小序列湊出的金額
choice[i][j]表示剩余j元的情況下是否選擇a[i]
因為要求最小序列，故將a陣列從大到小排序
for(面值 in a)
for(金額 in 目標金額 - 面值) 從大到小遍歷
if(當前金額 <= 更小序列湊出的金額)
當前金額 = 更小序列湊出的金額
choice該位置賦值為true
若目標金額 != 陣列對應位置最小序列湊出的金額
回傳無解
通過choice陣列標記輸出答案
四、 程式詳解及運行結果
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int sum = 0, m, n, tem;
cin >> n >> m;
vector<int>dp(m + 1, 0);
vector<int>a;
vector<vector<bool>>choice(n, vector<bool>(m + 1, false));
//choice[i][j]表示剩余j元的情況下是否選擇a[i]
for (int i = 0; i < n; ++i) {
cin >> tem;
sum += tem;
a.push_back(tem);
}
if (sum < m) {
cout << "No Solution" << endl;
return 0;
}
sort(a.begin(), a.end());
reverse(a.begin(), a.end());
for (int i = 0; i < a.size(); ++i) {
for (int j = m; j >= a[i]; --j) {
if (dp[j] <= dp[j - a[i]] + a[i]) {
choice[i][j] = true;
dp[j] = dp[j - a[i]] + a[i];
}
}
}
while (m != 0) {
int h = m;
cout <<"M 為"<< h << "時，對應解為 ：";
if (dp[h] != h) {
cout << "No Solution" << endl;
return 0;
}
int x = n - 1;
while (h) {
while (!choice[x][h]) --x;
cout << a[x];
h -= a[x];
x--;
if (h)
cout << ' ';
}
cout << endl;
m--;
}
return 0;
}
M從1~9對應樣例一的所有解為
五、 問題及解決程序
????先在草稿紙上演算，找到方法后再進行構思操作，應注意從大到小遍歷零錢面值，if中條件應為 <= ，這樣每一個符合要求的值都是一個更小的序列，
實驗十 分治演算法 ：找第k小的數## 一、 題目
一、 題目
????*設計一個平均時間為O(n)的演算法，在n(1<=n<=1000)個無序的整數中找出第k小的數，
????提示：函式int partition(int a[],int left,int right)的功能是根據a[left]a[right]中的某個元素x（如a[left])對a[left]a[right]進行劃分，劃分后的x所在位置的左段全小于等于x,右段全大于等于x,同時利用x所在的位置還可以計算出x是這批資料按升非降序排列的第幾個數，因此可以編制int find(int a[],int left,int right,int k)函式，通過呼叫partition函式獲得劃分點，判斷劃分點是否第k小，若不是，遞回呼叫find函式繼續在左段或右段查找，
*
輸入格式:
????輸入有兩行：第一行是n和k，0<k<=n<=10000，第二行是n個整數
輸出格式:
????輸出第k小的數
二、 解題思路
????考察分治演算法，找第k小的數的程序類似快速排序，通過改寫快速排序函式得出結果，
三、 程式設計
int partition(int a[],int left,int right)函式，其功能是根據a[left]a[right]進行劃分，
劃分后的x所在位置的左段全小于等于x,右段全大于等于x,
同時利用x所在的位置還可以計算出x是這批資料按升非降序排列的第幾個數
int find(int a[],int left,int right,int k)函式，通過呼叫partition函式獲得劃分點，
判斷劃分點是否第k小，若不是，遞回呼叫find函式繼續在左段或右段查找，
四、 程式詳解及運行結果
#include <iostream>
#include<vector>
using namespace std;
int partition(vector<int>&a, int left, int right) {
int temp = a[left];
int l = left, r = right;
left++;
while (left != right) {
while (left < right && a[right] > temp)
right--;
while (left < right && a[left] < temp)
left++;
if(left < right)
swap(a[left], a[right]);
}
a[l] = a[left];
a[left] = temp;
return left;
}
void find(vector<int>&a , int left, int right, int k) {
int p = partition(a, left, right);
if (p == k - 1)
cout << a[k - 1] << endl;
else if (p > k - 1)
find(a, left, p - 1, k);
else
find(a, p + 1, right, k);
}
int main() {
int n, k;
cin >> n >> k;
vector<int>a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
find(a, 0, n - 1, k);
return 0;
}
五、 問題及解決程序
????注意傳參時要加&符號，否則無法對陣列中元素順序進行修改，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243230.html
標籤：其他
上一篇：skynet原始碼分析之熱更新 lua代碼，兩個關鍵字搞定
下一篇：淺談 求各字串最長公共前綴