水壺問題要求我們把紅藍(lán)水壺進(jìn)行配對(duì)。如何才能讓紅藍(lán)水壺一一對(duì)應(yīng)，那就是分別對(duì)它們進(jìn)行排序。所以這里借助快排的思想來進(jìn)行排序，紅水壺?cái)?shù)組使用藍(lán)水壺中的pivot來排序，藍(lán)水壺使用紅水壺中的pivot來排序。由于前提條件紅水壺有一個(gè)對(duì)應(yīng)的藍(lán)水壺，反之亦然，且紅水壺內(nèi)部各不相同，所以排序就很簡(jiǎn)單，稍微修改一下快排就可以得到結(jié)果。

a. 遍歷所有的紅水壺，每個(gè)紅水壺與所有的藍(lán)水壺進(jìn)行比較，比較次數(shù)為Θ(n²)。

b. 使用決策樹模型，但這里每個(gè)分支有三個(gè)，對(duì)應(yīng)小于大于和相等。由于每種配對(duì)都至少有一個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)，所以比較次數(shù)下界Ω(nlgn)。這里配對(duì)次數(shù)可以看做把n個(gè)不同的小球放到n個(gè)不同的桶里有多少種方法（每個(gè)桶只能有一個(gè)小球）。

c. 隨機(jī)算法類似于隨機(jī)版快排，不同的就是每次partition二次，所以期望運(yùn)行時(shí)間不變。最壞情況是O(n²)。

#include <iostream> #include <algorithm> using namespace std;int Jug_Partition(int *a, int p, int r, int key); void Jug_Sort(int *R, int *B, int p,int r){ if (p >= r) return; int pivot = p + rand() % (r - p + 1); swap(R[pivot], R[r]); int q=Jug_Partition(B, p, r, R[r]); Jug_Partition(R, p, r, B[q]); Jug_Sort(R, B, p, q - 1); Jug_Sort(R, B, q + 1, r); } int Jug_Partition(int *a, int p, int r, int key){ int i = p - 1; int j = p; for (; j <= r; ++j){ if (a[j] < key){ ++i; swap(a[j], a[i]); } } for (j = i + 1; j <= r; ++j) if (a[j] == key){ ++i; swap(a[j], a[i]); break; } return i; } int main(){ int R[10] = { 1, 2, 3, 4, 5, 99, 7, 8, 9, 10 }; int B[10] = { 10, 9, 8, 7, 99, 5, 4, 3, 2, 1 }; Jug_Sort(R, B, 0, 9); for (auto r : B) cout << r << " "; cout << endl; for (auto r : R) cout << r << " "; }

轉(zhuǎn)載于:https://www.cnblogs.com/Nastukashii/p/4413867.html

總結(jié)

以上是生活随笔為你收集整理的水壶问题 算法导论8.4的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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