資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 統計中位數也在子集中出現的子集數量
給定一個包含正數的陣列 arr[]。目標是找到 arr[] 元素的子集，使得子集的值的中位數也存在於該集合中。
例如
輸入
arr[] = { 1,2,3 }輸出
Count of number of subsets whose median is also present in the same subset are: 4
解釋
The sets with their medians in that same set are: [ 1 ], median is 1 [ 2 ], median is 2 [ 3 ], median is 3 [ 1,2,3 ], median is 2
輸入
arr[] = { 4,6,5 }輸出
Count of number of subsets whose median is also present in the same subset are: 4
解釋
The sets with their medians in that same set are: [ 4 ], [ 6 ], [ 5 ], [ 4,6,5 ],
下面程式中使用的方案如下−
在這個方案中，我們將檢查偶數和奇數大小的元素。然後，我們可以根據奇數項的中位數存在於與中間元素相同的集合中的事實來找到中位數。因此，我們將 2n-1 加到計數中。對於偶數長度的子集，我們將檢查是否存在兩個相同的元素，因此對於具有兩個中間元素的偶數長度子集進行計數。
取包含正數的陣列 arr[]。
函式 median_subset(arr, size) 獲取 arr 並返回中位數也在同一子集中出現的子集數量。
函式 check(int temp) 獲取一個整數並使用從 i=2 到 i<=temp 的 for 迴圈返回該數字的階乘。
計算 count=count*i，並在迴圈結束時將其作為階乘返回。
函式 com(int n, int r) 獲取 n 和 r 並返回組合 nCr 的值。在其中，取 temp = check(r) * check(n − r) 和 temp_2=check(n) / temp。返回計算出的值 tem_2。
函式 power(int n, int r) 獲取 n 和 r 並返回 nr 的值。
如果 r 為 0，則答案將為 1，因此返回 1。
取 total = power(n, r / 2)。( nr/2)
使用 total2 % mod 更新 total。其中 mod=1000000007。
如果 r 為偶數，則返回 temp 為 (total * n) % mod，否則返回 total。
在函式 median_subset() 內，取 count 為 count = power(2, size − 1)，它是奇數長度子集的數量。
使用 sort(arr, arr + size) 對陣列 arr[] 進行排序。
使用 while 迴圈，我們將檢查每個元素的最左側中間元素，直到它們相等。
取 temp_2 = size − 1 − temp 作為最右側中間元素右側元素的數量。
取 temp_3 = i 作為最左側中間元素左側元素的數量。
將選定的偶數長度子集新增到 count 中，如 count = (count + com(temp_3 + temp_2, temp_3)) % mod。
在 while 迴圈結束時，我們將擁有 count。
返回 count 作為結果。
示例
#include <algorithm>
#include <iostream>
using namespace std;
#define mod 1000000007;
int check(int temp){
int count = 1;
for (int i = 2; i <= temp; i++){
count = count * i;
}
return count;
}
int com(int n, int r){
int temp = check(r) * check(n − r);
int temp_2 = check(n) / temp;
return temp_2;
}
int power(int n, int r){
if (r == 0){
return 1;
}
int total = power(n, r / 2);
total = (total * total) % mod;
if (r % 2){
int temp = (total * n) % mod;
return temp;
} else {
return total;
}
}
int median_subset(int* arr, int size){
int count = power(2, size − 1);
sort(arr, arr + size);
for (int i = 0; i < size; ++i){
int temp = i + 1;
while (temp < size && arr[temp] == arr[i]){
int temp_2 = size − 1 − temp;
int temp_3 = i;
count = (count + com(temp_3 + temp_2, temp_3)) % mod;
temp++;
}
}
return count;
}
int main(){
int arr[] = { 4, 5, 4, 6 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of subsets whose median is also present in the same subset are: "<<median_subset(arr, size);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出 -
Count of number of subsets whose median is also present in the same subset are: 9
171 次檢視
