算法类问题
木棒三角形
（枚舉）
#include <iostream> #include<stdlib.h> using namespace std; int main()//木棒三角形 有n根木棍 挑出其中三根構(gòu)成直角三角形 輸出面積最大的三角形面積 輸入n再輸入每根三角形長(zhǎng)度,n<100 {int n;//輸入n根木棍 再分別輸入每根木棍的長(zhǎng)度 限制了n數(shù)量小于100int len[110];//每個(gè)數(shù)組元素儲(chǔ)存木棍長(zhǎng)度 且要求長(zhǎng)度由小到大給出while (scanf("%d", &n) != EOF) {for (int i = 0; i < n; i++)cin >> len[i];double ans = -1;for (int i = 0; i < n ; i++)//枚舉最短木棍for (int j = i + 1; j < n ; j++)for (int z = j + 1; j < n ; j++){//讓i < j < k,這樣棍子就不會(huì)被重復(fù)選中了if(len[i]*len[i] + len[j]*len[j]==len[z]*len[z]){if ((len[i] * len[i] + len[j] * len[j] + len[z] * len[z]) > ans)ans = 0.5 * len[i] * len[j];}}if (ans == -1)cout << "no !";elsecout << ans;} }順序查找
/順序查找 從第一個(gè)開始查找 關(guān)鍵字與給定值相比較 如果相等則退出int order(int array[], int n, int key){int i;array[n] = key;//監(jiān)視哨for (i = 0; array[i] != key; i++);//分號(hào)不可少return (i < n ? i : -1);}折半查找
也叫二分查找 可以在最壞的情況下用O(logn)完成任務(wù)
int binarysearch(int array[], int key, int n) {int left = 0;int right = n - 1;while (left <= right){int middle = (left + right) / 2;if (array[middle] == key)return middle;if (left > array[middle])left = middle + 1;if (right < array[middle])right = middle - 1;}return -1; }二分查找:
二分搜索算法每次將候選區(qū)間減小至大約原來的一半。因此，要判斷長(zhǎng)度為"的有序數(shù)組A中是否 包含x,只要反復(fù)執(zhí)行約log?”次就完成了。二分查找的復(fù)雜度是O(log”)時(shí)間的，我們稱這種階的 運(yùn)行時(shí)間為對(duì)數(shù)時(shí)間。即便n變得很大時(shí)，對(duì)數(shù)時(shí)間的算法依然非?？焖?。
int n,x,k; int k[100]; bool binary(int x){ int l = 0,r = n; while(r - l>=1) { int i = (r+l)/2; if(k[i] == x)return true; else if(k[i] < x) l = i+1; else r = i;.} return true; }/字符串統(tǒng)計(jì)
每組測(cè)試輸出兩個(gè)正整數(shù) 第一個(gè)是表示重復(fù)的次數(shù)，第二次是在該重復(fù)次數(shù)下有幾種不同的字符串
using namespace std; struct abc {char str[20];///int num; }que[20000]; int cmp(const void* a, const void* b) {abc* f1 = (abc*)a;abc* f2 = (abc*)b;return strcmp(f1->str, f2->str);//排序函數(shù)用于在qsort函數(shù)中將字符串從小到大排序 可以根據(jù)cmp的寫法來確定從大到小還是從小到大 } //qsort函數(shù)的基本用法：qsort(que,n,sizeof(que[0]),cmp)que為需要排序的序列首地址 //n為序列的元素 sizeof為序列中單個(gè)元素所占空間的大小 cmp為排序過程中用到的比較函數(shù) 有-1、0、1三種返回值 int main() {int count[20000];//存放種類數(shù) 其中[]中的數(shù)值是重復(fù)的次數(shù)int n;int number = 1;while (cin >> n){for (int i = 0; i < n; i++){cin >>que[i].str;count[i] = 0;}qsort(que, n, sizeof(que[0]), cmp);如果后一個(gè)元素等于前一個(gè)元素則出現(xiàn)次數(shù)加一int i = 1;//while(i < n)for (int i = 0; i < n - 1; i++){if (strcmp(que[i].str, que[i+1].str) == 0)//比較兩個(gè)字符串是否相等 不要用=={number++;continue;}count[number]++;//如果不相等了 再加上最后這一位本身number = 1;//恢復(fù)number}count[number]++;//for (int i = 1; i < n; i++){cout << i << " :" << count[i] << "";cout << endl;}}}遞歸:
//求解組合問題 1~n中任取r個(gè)數(shù) 求所有組合 //輸出一個(gè)組合 int r;//全局變量 void display(int a[]) {for (int i = 0; i < r; i++)cout << a[i]<<" ";cout << endl; } void mm(int a[], int n, int r) {for (int i = n; i >= r; i--){a[r - 1] = i;if (r > 1)mm(a, i - 1, r - 1);elsedisplay(a);} }int main() {int n;int a[8];cin >> n >> r;mm(a, n, r);}n皇后問題
using namespace std; //n皇后問題 //每個(gè)皇后不能同行不能同列且不能同對(duì)角線 const int N = 20;//最多的皇后數(shù) int q[N];//存放皇后的列好 i是行數(shù)q[i]是列數(shù)即第i個(gè)皇后所在的列號(hào)place(k,n)是指【已經(jīng)在1~k-1行上 //放好了k-1個(gè)皇后，現(xiàn)要在k~n上放n-k+1個(gè)皇后，則place（k+1,n）指已經(jīng)在1~k行上放了k個(gè)皇后，要在k+1~n行 //放n-k個(gè)皇后 即place(k+1,n)比place(k,n)少放一個(gè)皇后，前者是小問題，后者是大問題 //當(dāng)同對(duì)角線時(shí) 即等腰直角三角形 行的絕對(duì)值之差=列的絕對(duì)值之差 //本代碼i從1開始取，最大下標(biāo)是n int ccount = 0;//解的個(gè)數(shù) void display(int n) {ccount++;cout << "第" << ccount << "個(gè)解：";for (int i = 1; i <= n; i++)cout << i << " " << q[i]<<".";cout << endl;} //已經(jīng)放好了k-1個(gè)皇后 考慮第k個(gè)皇后 它只能放第k行 j是傳進(jìn)來的值 bool iff(int k, int j)//判斷（k,j)能否放皇后 已經(jīng)放好的皇后是（i,q[i]) i為1~k-1 {int i = 1;while (i < k)//前面k-1行已經(jīng)放了皇后{if (q[i] == j ||fabs(j - q[i]) == fabs(k - i))return false;i++;}return true; } void place(int k, int n) {if (k > n)display(n);//此時(shí)所有皇后放置結(jié)束elsefor (int j = 1; j <= n; j++)//在K行上窮舉每一個(gè)位置{if (iff(k, j))//找到了合適的位置（k,j)時(shí){q[k] = j;place(k + 1, n);}} } int main() {int n;//實(shí)際的皇后數(shù)cin >> n;place(1, n); }[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-zna7DOv7-1604131085348)(C:\Users\14172\OneDrive\圖片\屏幕快照\(chéng)2020-10-23 (3)].png)
數(shù)組。
設(shè)計(jì)算法高效將數(shù)組的奇數(shù)元素移到偶數(shù)元素后面
//設(shè)計(jì)算法盡可能高效地將所有奇數(shù)元素移動(dòng)到偶數(shù)元素前面 //設(shè)置兩個(gè)指針 ij i=0,j = n-1,當(dāng)ij不相等時(shí)循環(huán) a[i]找偶數(shù)元素 a[j]找奇數(shù)元素 當(dāng)i!=j時(shí)發(fā)生交換void swapp(int a[], int n) {int i = 0, j = n - 1;int temp;while (i != j){j--;if (a[j] % 2 == 1){for (; i != j; i++){if (a[i] % 2 == 0 && a[j] % 2 == 1 && i != j){temp = a[i];a[i] = a[j];a[j] = temp;i++;break;}}}} } int main() {m1 = 3;int m[] = { 1,2,3,4,4,5,6 };swapp(m, 7);for (int i = 0; i < 7; i++)cout << m[i];}以第一個(gè)元素為基準(zhǔn) 大于該基準(zhǔn)的移到后面
//以a[0]為基準(zhǔn)將所有大于a[0]的元素移到該基準(zhǔn)后面 小于等于的元素移到該基準(zhǔn)前面 得到一個(gè)新的數(shù)組 void swapp(int a[], int n) {int temp;int num = a[0];int j = n - 1;//a[j]掃描小于a[0]的 a[i]掃描大于a[0]的 兩者發(fā)生交換int i = 0;while (i != j) {j--;if(a[j] < num)for (; i != j; i++){if (a[i] >= num){temp = a[i];a[i] = a[j];a[j] = temp;i++;break;}}} }//刪除一個(gè)已排序好的整數(shù)數(shù)組的重復(fù)元素 返回a
//刪除一個(gè)已排序好的整數(shù)數(shù)組的重復(fù)元素 返回a[](算法效率問題) //重建法 int* delee(int a[], int n) {int k = 0;for (int i = 0; i < n; i++){if (a[i] != a[i + 1//如果a[i]不是重復(fù)的元素則將a[i]重新插入到a中{a[k] = a[i];k++;//保留的元素增一}}return a; }//刪除給定的有序整數(shù)數(shù)組 兩個(gè)或兩個(gè)以上的 重復(fù)元素僅僅保留兩個(gè)
#include<iostream> using namespace std; int* delee(int a[], int& n) {//刪除給定的有序整數(shù)數(shù)組 兩個(gè)或兩個(gè)以上的 重復(fù)元素僅僅保留兩個(gè)int k = 0;int b[30] = { 0 };for (int i = 0; i < n-1; i++){if (a[i] != a[i + 1]){a[k] = a[i];k++;//保留的元素增一}if (a[i] == a[i + 1] && a[i] != a[i + 2] ){a[k] = a[i];a[k+1] = a[i + 1];k += 2;i += 1;}}n = k;//更新數(shù)組的個(gè)數(shù) 用引用傳遞 這樣在主函數(shù)中可以獲得新數(shù)組的大小return a; } int main() {int a[20] = { 2,2,2,2,3,3,3,4,5,6,7,7,8,8,8 };int k = 16;int* b= delee(a,k);for (int i = 0; i < k; i++)cout << b[i] << " "; }//假設(shè)數(shù)組a中有m+n個(gè)元素空間其中0~m-1存放m個(gè)升序 數(shù)組b存放n個(gè)降序整數(shù) 不借助其他數(shù)組將這些元素升序存放到a中
//采用二路歸并產(chǎn)生升序數(shù)組，用i從a[m-1]的元素開始向前掃描 j從前向后掃描 k=m+n-1指向最后一個(gè)位置 void shengxu(int a[], int m,int b[], int n) {int l = 0;int r = m - 1;int k = m+n-1;while (r >= 0 && l < n){if (b[l] > a[r])//如果b更大{a[k] = b[l];k--;l++;}else{a[k] = a[r];r--;k--;}while (r >= 0)//此時(shí)a的前半部分沒有掃完{a[k] = a[r];k--;r--;}while (l < n)//b的后部分沒有掃完{a[k] = b[l];l++;k--;} }} //上述算法時(shí)間復(fù)雜度為m+n空間復(fù)雜度為o(1) int main() {int a[31] = { -2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20,21 };int b[10] = { 8,7,6,5,4,3,2,1,-3,-4};shengxu(a, 20, b, 10);for (int i = 0; i < 30; i++)cout << a[i] << " "; }高效判斷兩個(gè)數(shù)組是否存在相同元素
//采用二路歸并產(chǎn)生升序數(shù)組，用i從a[m-1]的元素開始向前掃描 j從前向后掃描 k=m+n-1指向最后一個(gè)位置 bool shengxu(int a[], int m,int b[], int n) {int i = 0, j = 0;while (i < m && j < n){if (a[i] == b[j])return true;else if (a[i] > b[j])j++;elsei++;}return false; }深度優(yōu)先搜索算法
油田問題
//油田問題 一個(gè)油田是由m*n個(gè)單元組成的矩形，有些里面有石油，一個(gè)采油機(jī)可以把與該單元油田相連的油田采完，問至少 //需要多少臺(tái)采油機(jī) //@表示有石油 //采用深度優(yōu)先搜索算法 設(shè)變量many表示采油機(jī) 把整個(gè)地圖搜索完畢 當(dāng)遇到?jīng)]有標(biāo)號(hào)的油田時(shí)用深度優(yōu)先搜索把與這塊油田相連 //的其他油田全部進(jìn)行標(biāo)號(hào) #include <iostream>using namespace std; int dfs(int i, int j); int mmap[55][55] = { 0 }; char s[50][50] = { '0' }; int main() {int m, n;cin >> m >> n;for(int i = 0;i < m;i++)for (int j = 0; j < n; j++){cin >> s[i][j];}int many = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){if (mmap[i][j] == 0 && s[i][j] == '@')many += dfs(i, j);}cout << many; } int dfs(int i, int j) {mmap[i][j] = 1;//搜索過的地方置為1if (mmap[i + 1][j] == 0 && s[i + 1][j] == '@')dfs(i + 1, j);if (mmap[i][j + 1] == 0 && s[i][j + 1] == '@')dfs(i, j + 1);if (mmap[i - 1][j] == 0 && s[i - 1][j] == '@')dfs(i - 1, j);if (mmap[i][j - 1] == 0 && s[i][j - 1] == '@')dfs(i, j - 1);//將該點(diǎn)周圍上下左右四個(gè)點(diǎn)全部搜索并且標(biāo)記為1return 1;//搜到一個(gè)符合條件的點(diǎn)時(shí)加一}螺旋矩陣 子矩陣之和（遞歸和非遞歸算法）
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-ippBV9Ih-1604131085354)(C:\Users\14172\Pictures\數(shù)組.jpg)]
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-lYFDRNjU-1604131085357)(C:\Users\14172\Pictures\數(shù)組2.jpg)]
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-m0Tdomap-1604131085360)(C:\Users\14172\Pictures\子矩陣.jpg)]
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-m8YyYCcW-1604131085364)(C:\Users\14172\Pictures\子矩陣解答.jpg)]
求一個(gè)a矩陣以（i,j)和(m,n)為對(duì)角線的子矩陣元素之和
//求一個(gè)a矩陣以（i,j)和(m,n)為對(duì)角線的子矩陣元素之和 int a[][100]; void sum(int a[][100], int b[][100], int m, int n) {b[0][0] = a[0][0];for (int i = 1; i < m; i++)b[0][i] = b[0][i - 1] + a[0][i];for (int i = 1; i < m; i++)b[i][0] = b[i - 1][0] + a[i][0];for (int i = 1; i < m; i++)for (int j = 1; j < n; i++)b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];//引入數(shù)組b b(i,j)存儲(chǔ)的是以a[0][0] a[i][j]//為對(duì)角線的矩陣元素之和 } int ziju(int b[][100], int s, int t, int m, int n){if(m == 0 && n == 0)return b[m][n];int sum = b[m][n] - b[m][t - 1] - b[s - 1][n] + b[s - 1][t - 1];return sum; }遞歸和非遞歸創(chuàng)建螺旋矩陣
//創(chuàng)建一個(gè)n階螺旋矩陣并輸出 //對(duì)于左上角（ix,iy)右下角(ex,ey)起始元素為start的那一圈，通過調(diào)用函數(shù)1產(chǎn)生 函數(shù)2用于創(chuàng)建整個(gè)螺旋矩陣 //設(shè)f(x,y,start,n)用于創(chuàng)建左上角為(x,y)起始元素為start的n階螺旋矩陣，是大問題，則f(x+1,y+1,start,n-2)是小問題 //（去掉最外面一大圈后剩下的部分） //有遞歸算法和非遞歸算法 int a[15][15] = { 0 }; void create(int& start,int ix,int iy,int ex,int ey)//最外面的大圈 {if (ix == ex)a[ix][iy] = start++;//當(dāng)該圈只有一個(gè)元素時(shí)else{int curl = iy;while (curl != ey)a[ix][curl++] = start ++;curl = ix;while (curl != ex)a[curl++][ey] = start++;curl = ey;while (curl != iy)a[ex][curl--] = start++;curl = ex;while (curl != ix)a[curl--][iy] = start++;}} void spira(int x,int y,int n,int start)//遞歸調(diào)用螺旋矩陣 {if (n <= 0)//退出遞歸條件return;if (n == 1){a[x][y] = start;//矩陣大小為1時(shí)return;}else{for (int i = y; i < y+n-1; i++)//上一行a[x][i] = start++;for (int i = x; i < x+n-1; i++)//右一列a[i][x +n-1] = start++;for (int i = x +n-1;i > y; i--)//下一行a[x + n-1][i] = start++;for (int i =x+ n-1; i > x; i--)//左一列a[i][y] = start++;spira(x+1,y + 1, n-2,start);//遞歸調(diào)用自身}} void spira2(int n)//非遞歸調(diào)用螺旋矩陣 {int start = 1;int i = 0, j = 0, ex = n - 1, ey = n - 1;while (i <= ex)create(start, i++, j++, ex--, ey--);// 不斷循環(huán)調(diào)用創(chuàng)建最外圈元素的函數(shù)} void display(int n) {for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++)cout << a[i][j] << " ";cout << endl;//輸出} }[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-a8ZB6NYe-1604131085367)(C:\Users\14172\Pictures\屏幕截圖 2020-10-28 210335.png)]
//有兩個(gè)有序數(shù)組ab 元素個(gè)數(shù)m,n 設(shè)計(jì)一個(gè)高效算法求a和b的差集
//設(shè)a-b的元素?cái)?shù)組為c int a[5], b[5]; int c[8] = { 0 }; void chaji(int m,int n,int a[],int b[]) {int i = 0, k = 0, j = 0;//k來維護(hù)c中元素個(gè)數(shù)while (i < m && j < n)//注意這個(gè)while循環(huán)很重要不能遺漏否則無法得到正確結(jié)果{if (a[i] < b[j]){c[k] = a[i];i++;k++;//只將a中較小的元素放入c中}else if (a[i] > b[j])//如果b中元素更小則跳過{j++;}else//如果元素相等 不能放入C中 下標(biāo)加一{i++;j++;}}while (i < n)//注意要將如果a沒有遍歷完則全部放入C中{c[k] = a[i];i++;k++;}} int main() {int a[5] = { 3,4,9,10,77};int b[5] = { 2,3,5,6,4 };chaji(5, 5, a, b);for (int i = 0; i < 8; i++)cout << c[i]<<" "; }基于鏈表的算法設(shè)計(jì)
-
通常單鏈表是帶頭結(jié)點(diǎn)的結(jié)構(gòu)，單鏈表如果有頭結(jié)點(diǎn)，通常用頭結(jié)點(diǎn)的地址即頭指針來標(biāo)識(shí)整個(gè)單鏈表，第一個(gè)數(shù)據(jù)結(jié)點(diǎn)稱為首結(jié)點(diǎn)，指向首結(jié)點(diǎn)的指針稱為首指針，
-
頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息，它不計(jì)入表長(zhǎng)度。
首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a０的結(jié)點(diǎn)。
其中頭指針只是指針，它指向頭結(jié)點(diǎn)或首元結(jié)點(diǎn)所對(duì)應(yīng)的地址，在程序中，并沒有給它分配固定的內(nèi)存；而頭結(jié)點(diǎn)和首元結(jié)點(diǎn)卻對(duì)應(yīng)著固定的內(nèi)存。頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別在于數(shù)據(jù)域中是否存放了數(shù)據(jù)元素，頭結(jié)點(diǎn)中的數(shù)據(jù)域?yàn)榭?#xff0c;或存放表長(zhǎng)信息，引入它是為了方便鏈表的插入和刪除操作；而首元結(jié)點(diǎn)的數(shù)據(jù)域中會(huì)存儲(chǔ)第一個(gè)數(shù)據(jù)元素的值。 -
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-zTAyLxHh-1604131085370)(C:\Users\14172\Pictures==.png)]
-
Head指針為單鏈表的頭指針，單鏈表L：L既是單鏈表的名字，也是其頭指針。鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域定義為空指針(NULL)。那么什么是頭指針呢？我們把指向第一個(gè)結(jié)點(diǎn)的指針稱為頭指針，那么每次訪問鏈表時(shí)都可以從這個(gè)頭指針依次遍歷鏈表中的每個(gè)元素，例如：
-
struct node first;
struct node *head = &first;這個(gè)head指針就是頭指針。
示例如下：#include <stdio.h> struct node { int data; struct node *next; }; int main(void) { struct node *head, first, second; head = &first; first.data = 1; first.next = &second; second.data = 2; second.next = NULL; while (head) { printf("%d\n", head->data); head = head->next; } return 0; }
這個(gè)頭指針的意義在于，在訪問鏈表時(shí)，總要知道鏈表存儲(chǔ)在什么位置（從何處開始訪問），由于鏈表的特性（next指針），知道了頭指針，那么整個(gè)鏈表的元素都能夠被訪問，也就是說頭指針是必須存在的。示例如下需要著重注意的是while那部分（通過頭指針遍歷完整個(gè)鏈表）。
單鏈表有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)之分。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-GD3ESMcw-1604131085373)(C:\Users\14172\Pictures\111.jpg)]
那么什么又是頭結(jié)點(diǎn)呢？很多時(shí)候，會(huì)在鏈表的頭部附加一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，這個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，
頭結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)，例如：
struct node head, first;
head.next = &first;
那么這里的頭指針又是誰呢，不再是指向第一個(gè)結(jié)點(diǎn)的指針，而是指向頭結(jié)點(diǎn)的指針，例如：
struct node *root = &head;即root指針才是頭指針。示例如下：
1.刪除非空鏈表中值最大的結(jié)點(diǎn)
struct linklist {int data;linklist* next; }; void shanchu(linklist* p) {linklist* head = new linklist;p = head->next; linklist* L = head;//p的前驅(qū)結(jié)點(diǎn)int max = p->data;while (p != NULL)//查找最大的結(jié)點(diǎn){p = p->next;if (p->data > max)max = p->data;}p = head->next;while (p != NULL){if (p->data == max){L->next = p->next;delete p;p = L->next;//讓p繼續(xù)指向L結(jié)點(diǎn)的后繼結(jié)點(diǎn)}else{L = p;p = p->next;//L和p都同時(shí)前移}} }2.將兩個(gè)遞增有序單鏈表合并為一個(gè)遞減有序單鏈表
空間復(fù)雜度為o(1)的頭插法:
struct linknode {int data;linknode* next; }; void guibing(linknode* &L1, linknode* &L2, linknode*& L3) {linknode* p1 = L1->next,*p2 = L2->next,*p3;delete L1;//釋放L1頭結(jié)點(diǎn)并置為NULLdelete L2;L1 = NULL;L2 = NULL;L3 = new linknode;L3->next = NULL;while (p1 != nullptr && p2 != nullptr){if (p1->data > p2->data){p3 = p1->next;//臨時(shí)保存p1結(jié)點(diǎn)的后繼結(jié)點(diǎn)p1->next = L3->next;//采用頭插法將p1插入到L3中L3->next = p1;p1 = p3;//p1指向下一個(gè)結(jié)點(diǎn)}else{p3 = p2->next;p2->next = L3->next;L3->next = p2;p2 = p3;}}if (p2 != nullptr){p1 = p2;//如果p2沒有掃完 讓p1指向p2結(jié)點(diǎn)}while (p1 != nullptr){p3 = p1->next;//臨時(shí)保存p1結(jié)點(diǎn)的后繼結(jié)點(diǎn)p1->next = L3->next;//采用頭插法將p1插入到L3中L3->next = p1;p1 = p3;//p1指向下一個(gè)結(jié)點(diǎn)} }[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-gduDJdnF-1604131085375)(C:\Users\14172\Pictures\22.jpg)]
將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m的單鏈表之后，時(shí)間復(fù)雜度為m.（先通過遍歷找到尾結(jié)點(diǎn)p 再讓p結(jié)點(diǎn)的指針域指向長(zhǎng)度為n的單鏈表首結(jié)點(diǎn)。）
3.遞歸算法逆置非空單鏈表
struct linknode {int data;linknode* next; }; //注意下面這個(gè)函數(shù)參數(shù)是值參數(shù)(對(duì)應(yīng)的實(shí)參不變）而不是引用參數(shù)。如果改為引用是錯(cuò)誤的 linknode* nizhi(linknode* first)//first為不帶頭結(jié)點(diǎn)的 {linknode* p;if (first == nullptr || first->next == nullptr)return first;p = nizhi(first->next);first->next->next = first;//first結(jié)點(diǎn)連接到first->next結(jié)點(diǎn)的后面 注意二者順序first->next = NULL;//first結(jié)點(diǎn)作為逆置后的尾結(jié)點(diǎn)return p; } //引用作為參數(shù) void nizhi1(linknode* &L)//L為帶頭結(jié)點(diǎn)的單鏈表 {L->next = nizhi(L->next);//L->next為不帶頭結(jié)點(diǎn)的單鏈表 調(diào)用第一個(gè)函數(shù) }4.逆置單鏈表中序號(hào)為i到j(luò)的結(jié)點(diǎn)
注意ij參數(shù)可能錯(cuò)誤
struct linknode {int data;linknode* next; }; //逆置非空單鏈表中序號(hào)從i到j(luò)的結(jié)點(diǎn) //為了防止i與j超過范圍要先求出長(zhǎng)度 且第二個(gè)函數(shù)為bool型 int length(linknode* m) {int k = 0;linknode* p = m;while (p != nullptr){p = p->next;k++;}return k;//先求出單鏈表長(zhǎng)度 } bool nizhiij(linknode* &L,int i,int j) {linknode* r;int len = length(L);if (i < 0 || i > len || j < 0 || j> len)return false;else{int n = 0;linknode* p = L,*q;while (n < i - 1 && p != NULL){n++;p = p->next;}//p為第i-1個(gè)結(jié)點(diǎn)linknode* m = p;linknode*r = p->next;p1 = r;//用p1保存逆置的第一個(gè)結(jié)點(diǎn)p->next = NULL;//斷開第i和第i-1個(gè)結(jié)點(diǎn)while (n < j && r != NULL){n++;q = r->next;//不斷將r結(jié)點(diǎn)到第j個(gè)結(jié)點(diǎn)采用頭插法插入到m結(jié)點(diǎn)之后r->next = m->next;m->next = r;r = q;}p1->next = q;//將第j個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)接到p1結(jié)點(diǎn)之后return true;} }5.對(duì)于一個(gè)帶頭結(jié)點(diǎn)的單鏈表以第一個(gè)結(jié)點(diǎn)為基準(zhǔn) 將所有小于其值的結(jié)點(diǎn)移動(dòng)到它前面 將所有大于等于其值的結(jié)點(diǎn)移動(dòng)到它后面
void yidong(linknode* a) {linknode* p = a->next;//p指向首結(jié)點(diǎn)int data1 = p->data;//cache指向其后繼結(jié)點(diǎn) 如果cache值小于p值 通過p將cache刪除linknode* cache = p->next;if (a != nullptr || a->next == nullptr)return;while (cache != nullptr){int da2 = cache->data;//da2存放基準(zhǔn)值if (da2 >= data1)//此時(shí)p和cache同步后移{p = cache;cache = p->next;}else{p->next = cache->next;//如果cache結(jié)點(diǎn)的值小于基準(zhǔn)值 刪除cache結(jié)點(diǎn) 頭插法查到表a中cache->next = a->next;a->next = cache;cache = p->next;//cache繼續(xù)指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn)}} }6.設(shè)計(jì)一個(gè)算法求非空單鏈表中間位置結(jié)點(diǎn)
(1,2,3,4)的中間位置是結(jié)點(diǎn)2 （1，2，3，4，5）中間位置是5
//方法：用快慢兩個(gè)指針 快指針一次移動(dòng)兩個(gè)結(jié)點(diǎn) 循環(huán)結(jié)束后slow指向的結(jié)點(diǎn)即目標(biāo)結(jié)點(diǎn) linknode* middle(linknode* L) {if (L == nullptr)return NULL;if (L->next == nullptr)return L;linknode* fast = L->next,*slow = L->next;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;}return slow;}尾插法
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-bnZG9Yhq-1604131085377)(C:\Users\14172\Pictures\untitled.png)]
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-cj2lzHkD-1604131085380)()]
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-07qYDuBg-1604131085386)(C:\Users\14172\Pictures\21.png)]
注意是r->next = L1->next;(注意這兩個(gè)鏈表都有頭結(jié)點(diǎn))
7.將一個(gè)非空單鏈表（a1,a2,…an,b1,b2…bn)重新排列為(a1,b1,a2,b2…,an,bn)
//空間復(fù)雜度為O(1) //采用尾插法 建立新表L r作為尾指針 利用上一題求中間結(jié)點(diǎn)的函數(shù)找到中間結(jié)點(diǎn) void rearrange(linknode* &L) {if (L == NULL)return;linknode* mid = middle(L);//此題結(jié)點(diǎn)個(gè)數(shù)是偶數(shù)linknode* r = L;//新鏈表的尾結(jié)點(diǎn)linknode* p = r->next;//p指向結(jié)點(diǎn)a1linknode* q = mid->next;//q指向結(jié)點(diǎn)b1while (p != nullptr && q != nullptr){r->next = p;//p結(jié)點(diǎn)鏈接到新鏈表的表尾r = p;r->next = q;r = q;p = p->next;q = q->next;}r->next = NULL;//尾結(jié)點(diǎn)的指針域置空（盡管這里不需要，但這是一個(gè)好習(xí)慣）}8.設(shè)計(jì)一個(gè)算法判斷一個(gè)非空單鏈表是否為回文
//非遞歸算法 找到中間結(jié)點(diǎn) 后半部分構(gòu)成帶頭結(jié)點(diǎn)的單鏈表p 將p逆置 然后依次按照結(jié)點(diǎn)順序判斷數(shù)據(jù)是否相等bool ispal(linknode* L) {if (L->next == nullptr || L->next->next == nullptr)return true;linknode *q,*q2,* p = new linknode;linknode* mid = middle(L);//中間結(jié)點(diǎn)p->next = mid->next;//將后半部分結(jié)點(diǎn)構(gòu)成帶頭結(jié)點(diǎn)的單鏈表reverse(p);//逆置帶頭結(jié)點(diǎn)的單鏈表mid->next = p->next;//重新連接q = p->next;q2 = L->next;while (q != nullptr && q2 != mid->next){if (q->data !=q2->data)return false;q = q->next;q2 = q2->next;}return true; }9.判斷序列B是否是A序列的子序列
//先在A中找到與B結(jié)點(diǎn)值相等的結(jié)點(diǎn)pa,pb指向B的首結(jié)點(diǎn)然后比較值是否相等 相等則同步后移 bool subseq(linknode* A, linknode* B) {linknode* pa = A->next;while (pa != nullptr){linknode* pb = B->next;//每次循環(huán)開始pb都是指向B的首結(jié)點(diǎn)while(pa->next != nullptr && pa->data != pb->data)//只用來求出與B第一個(gè)結(jié)點(diǎn)相等的A中結(jié)點(diǎn)pa {pa = pa->next;}linknode* q = pa;//用q來保存pa ,以便pa進(jìn)行下一輪循環(huán)（如果進(jìn)入下一輪循環(huán)仍要匹配A中與B第一個(gè)結(jié)點(diǎn)相等的其他結(jié)點(diǎn)）while (q != nullptr && pb != nullptr && q->data == pb->data){q = q->next;//如果值相等同步移動(dòng)pb = pb->next;}if (pb == nullptr)return true;else if(pa->next != nullptr)//如果A序列沒有遍歷完 ，則從下一個(gè)結(jié)點(diǎn)開始重復(fù)進(jìn)行{pa = pa->next;}}return false; }不同顏色排列（數(shù)量未知） 【有無頭結(jié)點(diǎn)的寫法】
L有頭結(jié)點(diǎn) L1,L2無
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-GqV607iS-1604131085390)(C:\Users\14172\Pictures\untitled.png)]
= nullptr)
return true;
linknode q,q2, p = new linknode;
linknode mid = middle(L);//中間結(jié)點(diǎn)
p->next = mid->next;//將后半部分結(jié)點(diǎn)構(gòu)成帶頭結(jié)點(diǎn)的單鏈表
}
## 9.判斷序列B是否是A序列的子序列```c++ //先在A中找到與B結(jié)點(diǎn)值相等的結(jié)點(diǎn)pa,pb指向B的首結(jié)點(diǎn)然后比較值是否相等 相等則同步后移 bool subseq(linknode* A, linknode* B) {linknode* pa = A->next;while (pa != nullptr){linknode* pb = B->next;//每次循環(huán)開始pb都是指向B的首結(jié)點(diǎn)while(pa->next != nullptr && pa->data != pb->data)//只用來求出與B第一個(gè)結(jié)點(diǎn)相等的A中結(jié)點(diǎn)pa {pa = pa->next;}linknode* q = pa;//用q來保存pa ,以便pa進(jìn)行下一輪循環(huán)（如果進(jìn)入下一輪循環(huán)仍要匹配A中與B第一個(gè)結(jié)點(diǎn)相等的其他結(jié)點(diǎn)）while (q != nullptr && pb != nullptr && q->data == pb->data){q = q->next;//如果值相等同步移動(dòng)pb = pb->next;}if (pb == nullptr)return true;else if(pa->next != nullptr)//如果A序列沒有遍歷完 ，則從下一個(gè)結(jié)點(diǎn)開始重復(fù)進(jìn)行{pa = pa->next;}}return false; }不同顏色排列（數(shù)量未知） 【有無頭結(jié)點(diǎn)的寫法】
L有頭結(jié)點(diǎn) L1,L2無
[外鏈圖片轉(zhuǎn)存中…(img-GqV607iS-1604131085390)]
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-zNQL42cZ-1604131085393)(C:\Users\14172\Pictures\00.png)]
二叉樹
求以二叉鏈存儲(chǔ)的二叉樹兩個(gè)結(jié)點(diǎn)的最大距離
三種情況：
代碼實(shí)現(xiàn)：
從根結(jié)點(diǎn)到葉結(jié)點(diǎn)所有結(jié)點(diǎn)值之和為sum的路徑
//每個(gè)結(jié)點(diǎn)儲(chǔ)存一個(gè)整數(shù)，求從根結(jié)點(diǎn)到葉結(jié)點(diǎn)路徑上所有結(jié)點(diǎn)之和等于sum的路徑 void disppath(vector<int> path) {vector<int>:: iterator ite;for( ite = path.begin(); ite != path.end(); ite++){cout<<*ite<<" ";} } void allpathsum(btnode *b, int sum, vector<int> path) {if(b == NULL) return;path.push_back(b->data);if(b -> lchild == NULL && b -> rchild == NULL){if(b -> data == sum)disppath(path);}//如果左子樹右子樹并非都空allpathsum(b->lchild,sum - b->data, path);//左右子樹中查找 allpathsum(b->rchild, sum- b->data, path) ;}對(duì)于一個(gè)給定的的結(jié)點(diǎn)值x,輸出所有從x到根結(jié)點(diǎn)的逆路徑
//每個(gè)結(jié)點(diǎn)儲(chǔ)存一個(gè)整數(shù)，對(duì)于一個(gè)給定的的結(jié)點(diǎn)值x,輸出所有從x到根結(jié)點(diǎn)的逆路徑 //逆路徑用棧保存 void display(stack<int>path)//輸出一條逆路徑 {while(!path.empty()){cout<<path.top()<<" ";path.pop();}} void allpath(btnode *b, int x,stack<int>path){if(b == NULL) return;path.push(b->data);//注意要先將b的值推入棧中再進(jìn)行判斷 因?yàn)橹禐閤的結(jié)點(diǎn)也要輸出 if(b->data == x)//當(dāng)找到一個(gè)為x的結(jié)點(diǎn)，逆向輸出 display(path);allpath(b->lchild,x,path);allpath(b->rchild,x,path);//在左右子樹中查找 }求二叉樹最大路徑和（即路徑上所有結(jié)點(diǎn)之和的最大值）
如圖，藍(lán)色的一條路徑為最大值：
路徑和為某一個(gè)值的所有路徑 這里的路徑是從根結(jié)點(diǎn)出發(fā)
//給定二叉樹 二叉樹中尋找路徑和為某一個(gè)值的所有路徑 路徑從根結(jié)點(diǎn)出發(fā) temsum存放臨時(shí)和（初始為0） vector<btnode *>path; void display(vector<btnode *> path) {for(int i = 0;i < path.size(); i++)cout<<path[i]->data<<" ";cout << endl; } void findpath(btnode *b, int sum, int temsum, vector<btnode *>path) {if(b == NULL) return;path.push_back( b );if(temsum + b->data == sum) display(path);findpath(b->lchild,sum , temsum + b->data,path);findpath(b->rchild,sum, temsum + b->data, path);}btnode *pa, *pb, *pc, *pd, *pe, *pg, *pf, *ph;btnode* creat(){pa = new btnode;pa->data = 2;pb = new btnode;pb->data = 3;pc = new btnode;pc->data = 1;pd = new btnode;pd->data = -1;pe = new btnode;pe->data = 4;pg = new btnode;pg->data = -6;pf = new btnode;pf->data = 6;ph = new btnode;ph->data = 20;pa->lchild = pb; pa->rchild = pc;pb->lchild = pd; pb->rchild = pe;pc->lchild = pg; pc->rchild = pf;pd->lchild = NULL; pd->rchild = NULL;pe->lchild = NULL; pe->rchild = NULL;pf->lchild = NULL; pf->rchild = NULL;pg->lchild = NULL; pg->rchild = ph;ph->lchild = NULL;ph->rchild = NULL;//這句話一定要寫 經(jīng)過調(diào)試如果這句話沒有則無輸出 所以一定要設(shè)置ph左右子樹為空 return pa; }void clear(){//銷毀二叉樹delete pa;delete pb;delete pc;delete pe;delete pd;delete pf;delete pg;} int main() {btnode*m = creat(); int tmp = 0; findpath(m, 9, tmp, path);}3.21在每個(gè)結(jié)點(diǎn)中增加一個(gè)next指針，用于指向同一層的右兄弟或者堂兄弟， 設(shè)計(jì)算法實(shí)現(xiàn)
//先序和層次遍歷兩種方法 #include<queue> using namespace std; #define maxn 100 typedef struct node {char data;struct node* lchild;struct node* rchild;node* next; }btnode; //假設(shè)一顆二叉樹 在每個(gè)結(jié)點(diǎn)中增加一個(gè)next指針，用于指向同一層的右兄弟或者堂兄弟，如圖所示，設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)這種 轉(zhuǎn)化 void trans(btnode* b, btnode* sibling) {//先序遍歷，用sibling指向當(dāng)前結(jié)點(diǎn)b的兄弟 若b不空，修改其next指針指向siblingif (b == nullptr) return;elseb->next = sibling;//如果b不空，修改b的next trans(b->lchild, b->rchild);//遞歸處理左子樹，b左子樹的兄弟為b右子樹if (sibling != nullptr){trans(b->rchild, sibling);//當(dāng)前結(jié)點(diǎn)b的兄弟不為空時(shí) 右孩子的next改為兄弟的左孩子}elsetrans(b->rchild, nullptr);//如果當(dāng)前結(jié)點(diǎn)b的兄弟為空，右孩子的next為空 } //層次遍歷方式，按照h = 1,2,3...處理，將每一層的k個(gè)結(jié)點(diǎn)放到lnode數(shù)組中，當(dāng)一層遍歷完畢后，將lnode數(shù)組中的結(jié)點(diǎn)用next指針鏈接 typedef struct {int lno;//結(jié)點(diǎn)的層次btnode* p;//結(jié)點(diǎn)指針 }qytype;//隊(duì)列元素類型 void process(btnode* lnode[], int k) {for (int i = 0; i < k - 1; i++)lnode[i]->next = lnode[i + 1];lnode[k - 1]->next = NULL; } void trans2(btnode* b) {btnode* lnode[maxn];//用于存放一層的所有結(jié)點(diǎn) 其中下標(biāo)表示的是層 lnode[i]是第i層的結(jié)點(diǎn)個(gè)數(shù)queue<qytype>qu;btnode* tem;int k=0;//k記錄lnode中結(jié)點(diǎn)個(gè)數(shù)if (b == nullptr) return;qytype m;m.p = b;m.lno = 1;qu.push(m);int h = 1;//從第一層開始while (!qu.empty()){qytype tt = qu.front();qu.pop();tem = tt.p;if (tt.lno == h){lnode[k] = tem;//如果該結(jié)點(diǎn)是第h層，則將該結(jié)點(diǎn)存入lnode中k++;//結(jié)點(diǎn)個(gè)數(shù)加一}else{//如果該結(jié)點(diǎn)不屬于第h層 則輸出上一層的所有結(jié)點(diǎn)process(lnode, k);k = 0; h++;//結(jié)點(diǎn)個(gè)數(shù)清空 層數(shù)加一lnode[k] = tem;//該層第一個(gè)結(jié)點(diǎn)是temk++;//結(jié)點(diǎn)個(gè)數(shù)加一}if (tt.p->lchild != nullptr)//p結(jié)點(diǎn)有左孩子 將其進(jìn)隊(duì){tem = tt.p->lchild;tt.lno = tt.lno + 1;qu.push(tt);}if (tt.p->rchild != nullptr)//有右孩子 進(jìn)隊(duì){tem = tt.p->rchild;tt.lno = tt.lno + 1;qu.push(tt);}}process(lnode, k);;//處理最后一層的所有結(jié)點(diǎn)的next指針 注意實(shí)在while循環(huán)的外面}3.22給定一個(gè)二叉樹及其兩其中的兩個(gè)node求公共父節(jié)點(diǎn)到兩節(jié)點(diǎn)距離之和最小
//給定一個(gè)二叉樹及其兩其中的兩個(gè)node(地址均非空） 給出這兩個(gè)node的一個(gè)公共父節(jié)點(diǎn)，使得這個(gè)父節(jié)點(diǎn) //與兩個(gè)結(jié)點(diǎn)的路徑之和最小struct treenode {treenode* left;//指向左右子樹treenode* right;treenode* father;//指向父節(jié)點(diǎn) };//二叉樹采用三叉鏈存儲(chǔ)結(jié)構(gòu)，根結(jié)點(diǎn)的father為NULL,求兩個(gè)非空結(jié)點(diǎn)first second的層次，比較兩個(gè)層次大小//通過Father指針將它們的指針移到相同層次，然后查找公共祖先結(jié)點(diǎn) #define max(x,y) ((x) > (y)?(x):(y))int level(treenode* p){int l = 1;if (p->father != nullptr){p = p->father;l++;}return l;}treenode* lowestcommom(treenode* first, treenode* second){int i;if (first == nullptr || second == nullptr) return nullptr;int l1 = level(first);int l2 = level(second);if (l1 < l2){for (int i = l1; i < l2; i++)second = second->father;//如果Second層次更大 則second在first下面部分}else if (l1 > l2){for (int i = 0; i < l1 - l2; i++)first = first->father;}while (first != second){first = first->father;second = second->father;}return first;}3.23樹中每一個(gè)結(jié)點(diǎn)放一個(gè)整數(shù) 函數(shù)返回這棵二叉樹中相差最大的兩個(gè)結(jié)點(diǎn)間差的絕對(duì)值
//編寫函數(shù) 樹中每一個(gè)結(jié)點(diǎn)放一個(gè)整數(shù) 函數(shù)返回這棵二叉樹中相差最大的兩個(gè)結(jié)點(diǎn)間差的絕對(duì)值//通過一次先序遍歷求出最大結(jié)點(diǎn)指max和最小結(jié)點(diǎn)指min 返回abs(max - min)void maxmin(btnode* p, int& max, int& min){//求最大最小值的函數(shù)if (p == nullptr) return;if (p->data > max)max = p->data;if (p->data < min)min = p->data;maxmin(p->lchild, max, min);maxmin(p->rchild, max, min);//遞歸處理左右子樹}int fun(btnode* b){if (b == nullptr) return 0;int max, min;max = min = b->data;//初始化最大最小值maxmin(b, max, min);return abs(max - min);}3.24 設(shè)計(jì)算法用遞歸實(shí)現(xiàn)輸出二叉樹的層次遍歷
//以二叉鏈存儲(chǔ)的二叉樹 設(shè)計(jì)算法用遞歸實(shí)現(xiàn)輸出二叉樹的層次遍歷 //采用一個(gè)全局兩層向量result存放先序遍歷結(jié)果 只是按結(jié)點(diǎn)b的層次h將其存放在result[h-1]向量元素中，然后 //一層一層輸出result即構(gòu)成層次遍歷序列vector<vector<int>>result; void travel(btnode* b, int h) {if (b == NULL) return;if (h > result.size()){result.push_back(vector<int>());}result[h - 1].push_back(b->data);travel(b->lchild, h + 1);travel(b->rchild, h + 1);} void levelorder(btnode* b) {travel(b, 1);for (int i = 0; i < result.size(); i++)for (int j = 0; j < result[i].size(); j++)cout << result[i][j]<<" ";//輸出結(jié)果}3.25//設(shè)計(jì)算法釋放二叉樹
//設(shè)計(jì)算法釋放二叉樹 //只能用后序遍歷，不能前序或者中序，因?yàn)橹挥袑⒆訕淇臻g釋放后才能釋放根結(jié)點(diǎn)的空間，否則會(huì)丟失子樹 void deletetree(btnode* b) {if (b != nullptr){deletetree(b->lchild);deletetree(b->rchild);delete b;} }枚舉
你的朋友提議玩一個(gè)游戲：將寫有數(shù)字的"個(gè)紙片放入口袋中，你可以從口袋中抽取4次紙 片，每次記下紙片上的數(shù)字后都將其放回口袋中。如果這4個(gè)數(shù)字的和是機(jī)，就是你贏，否 則就是你的朋友贏。你挑戰(zhàn)了好幾回，結(jié)果一次也沒贏過，于是怒而撕破口袋，取出所有紙 片，檢查自己是否真的有贏的可能性。請(qǐng)你編寫一個(gè)程序，判斷當(dāng)紙片上所寫的數(shù)字是k2, —,kn時(shí)，是否存在抽取4次和為m的方案。如果存在，輸yes;否則，輸出no
n = 3
m = 10
k = (1, 3, 5)
輸出
Yes （例如4次抽取的結(jié)果是1、1、3、5,和就是10 ）
(挑戰(zhàn)程序設(shè)計(jì)競(jìng)賽）
請(qǐng)計(jì)算所有螞蟻落下竿子所需 的最短時(shí)間和最長(zhǎng)時(shí)間。
當(dāng)螞蟻爬到竿子的端點(diǎn)時(shí)就會(huì)掉落。 由于竿子太細(xì)，兩只螞蟻相遇時(shí)，它們不能交錯(cuò)通過，只能各自反向爬回去。對(duì)于每只螞蟻, 我們知道它距離竿子左端的距離的，但不知道它當(dāng)前的朝向。
輸入
L = 10
n = 3
x = {2, 6, 7)
輸出
min = 4 （左、右、右）
max = 8 （右、右、右）
首先對(duì)于最短時(shí)間，看起來所有螞蟻都朝向較 近的端點(diǎn)走會(huì)比較好。事實(shí)上，這種情況下不會(huì)發(fā)生兩只螞蟻相遇的情況，而且也不可能在比此 更短的時(shí)間內(nèi)走到竿子的端點(diǎn)。事實(shí)上，可以知道兩只螞蟻相遇后，當(dāng)它們保持原樣交錯(cuò)而過繼續(xù)前進(jìn)也不會(huì)有任何問題。這樣不論最長(zhǎng)時(shí)間還是最短時(shí)間，都只要對(duì)每只螞蟻檢查一次就好了，
總結(jié)
- 上一篇： 职工管理系统
- 下一篇： 结构体数组实现的简易学生信息管理系统