資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft 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日
952 次瀏覽
廣告