資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究蓄水池抽樣
蓄水池抽樣是一種隨機演算法。在這個演算法中，從包含 n 個不同專案的列表中選擇 k 個專案。
我們可以透過建立一個大小為 k 的陣列作為蓄水池來解決這個問題。然後從主列表中隨機選擇一個元素，並將該元素放入蓄水池列表中。當一個專案被選中一次後，它將不會被再次選中。但這種方法並不有效，我們可以透過這種方法增加複雜度。
在蓄水池列表中，從列表中複製前 k 個專案，現在從列表中的第 (k+1) 個數字開始，逐個進行，假設當前選擇的專案放在索引 i 處。從 0 到 i 中找到一個隨機索引，並將其儲存到 j 中，如果 j 在 0 到 k 的範圍內，則將 reservoir[j] 與 list[i] 交換。
輸入和輸出
Input:
The list of integers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, The value of k = 6
Output:
K-Selected items in the given array: 8 2 7 9 12 6演算法
chooseKItems(array, n, k)
輸入：陣列、陣列中的元素數量、要選擇的元素數量。
輸出：隨機選擇 k 個元素。
Begin define output array of size [k] copy k first items from array to output while i < n, do j := randomly choose one value from 0 to i if j < k, then output[j] := array[i] increase i by 1 done display output array End
示例
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void display(int array[], int n) {
for (int i = 0; i < n; i++)
cout << array[i] << " ";
}
void chooseKItems(int array[], int n, int k) { //it will choose k items from the array
int i;
int output[k];
for (i = 0; i < k; i++)
output[i] = array[i];
srand(time(NULL)); //use time function to get different seed value
while(i < n) {
int j = rand() % (i+1); //random index from 0 to i
if (j < k) //copy ith element to jth element in the output array
output[j] = array[i];
i++;
}
cout << "K-Selected items in the given array: ";
display(output, k);
}
int main() {
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = 12;
int k = 6;
chooseKItems(array, n, k);
}輸出
K-Selected items in the given array: 8 2 7 9 12 6
更新於： 2020年6月17日
948 次檢視
廣告