資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中大小為 K 的所有子序列的乘積，除了最小和最大元素
給定一個數組 arr[n]，包含 n 個整數和一個整數 k 用於定義大小；任務是列印大小為 k 的所有子序列的乘積，除了最小和最大元素。
假設我們有一組 4 個元素 {1, 2, 3, 4} 和 k 為 2，那麼它的子集將是 - {1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 3}, {2, 4}
因此，排除最大元素 4 和最小元素 1，剩餘的元素將是 -
2, 3, 3, 3, 2，其乘積將是 -
2 * 3 * 3 * 3 * 2 = 108
同樣，我們必須解決這個問題
示例
Input: arr[] = {3, 4, 1, 7}, k = 3
Output: 144
Explanation: subset will be, {3, 4, 1}, {4, 1, 7}, {3, 1, 7}, {3, 4, 7}
Eliminating maximum value 7 and minimum 1 we will get:
{3, 4}, {4}, {3}, {3, 4}, so multiplying these will give us:
3 * 4 * 4 * 3 = 144
Input: arr[] = {1, 2, 3, 4}, k = 3
Output: 36**我們用來解決上述問題的方法** -
可以有多種方法來實現解決方案。有一種方法可以逐一生成所有可能的子序列，並對集合中的除最大值和最小值之外的所有元素進行乘積。雖然這種方法很容易實現，但複雜度非常高，並且這種方法效率低下。
我們也有一個有效的方法，在這種方法中，我們將首先對陣列進行排序，而不考慮要考慮或不考慮的子集或子序列。
然後，我們將逐一計算每個元素出現的次數。
一個數字可以在 C(k-1) (n-1) 個子序列中出現，其中 C(k-1) (i) 次它將作為最大元素出現，C(k-1) (n-i-1) 次它將作為該子序列的最小元素出現。
因此，我們可以說這是一種更有效的方法，因為第 i 個元素將出現 -
C(k-1) (n-1)- C(k-1) (i)- C(k-1) (n-i-1) 次。
現在，我們首先將為 arr[i] 中的每個元素求解 x，因此它的答案可能很難計算，因此我們可以使用費馬小定理。
**注意** - 由於答案可能非常大，因此我們將以 109+7 的模數列印答案。
演算法
Start
Step 1-> Declare function to calculate the pairs combination
void pairs(int a, int b)
Declare int i, j
Loop For i = 0 and i <= a and i++
Loop For j = 0 and j <= min(i, b) and j++
IF (j == 0 || j == i)
Set c[i][j] = 1
End
Else
Set c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val
End
End
End
Step 2-> declare function for power
LL power(LL x, unsigned LL y)
Declare unsigned LL temp = 1
Set x = x % val
Loop While (y > 0)
IF(y & 1)
Set temp = (temp * x) % val
End
Set y = y >> 1
Set x = (x * x) % val
End
return temp % val
Step 3-> Declare function to calculate product of all subsequences
unsigned LL product(LL arr[], int size, int k)
Declare and set unsigned LL temp = 1
Call function to sort an array as sort(arr, arr + size)
Declare and set as LL pow = c[size - 1][k - 1]
Loop For i = 0 and i < size and i++
Declare and set LL pow_l = c[i][k - 1]
Declare and set LL pow_f = c[size - i - 1][k - 1]
Declare and set LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val
Declare and set unsigned LL mul = power(arr[i], pow_e) % val
Set temp = ((temp % val) * (mul % val)) % val
End
return temp % val
Step 4-> In main()
Call pairs(100, 100)
Declare and set LL arr[] = { 3, 4, 1, 7 }
Calculate size as int size = sizeof(arr) / sizeof arr[0]
Declare and set int k = 3
Declare and set unsigned LL temp = product(arr, size, k)
Print temp
Stop示例
#include <bits/stdc++.h>
using namespace std;
#define val 1000000007
#define LL long long
#define max 101
LL c[max - 1][max - 1];
LL power(LL x, unsigned LL y) {
unsigned LL temp = 1;
x = x % val;
while (y > 0) {
if (y & 1) {
temp = (temp * x) % val;
}
y = y >> 1;
x = (x * x) % val;
}
return temp % val;
}
void pairs(int a, int b) {
int i, j;
for (i = 0; i <= a; i++) {
for (j = 0; j <= min(i, b); j++) {
if (j == 0 || j == i)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j - 1] % val + c[i - 1][j] % val) % val;
}
}
}
//function to calculate product of all subsequences
unsigned LL product(LL arr[], int size, int k) {
unsigned LL temp = 1;
//sorting array
sort(arr, arr + size);
LL pow = c[size - 1][k - 1];
for (int i = 0; i < size; i++) {
LL pow_l = c[i][k - 1];
LL pow_f = c[size - i - 1][k - 1];
LL pow_e = ((pow % val) - (pow_l + pow_f) % val + val) % val;
unsigned LL mul = power(arr[i], pow_e) % val;
temp = ((temp % val) * (mul % val)) % val;
}
return temp % val;
}
int main() {
// sum of all the pairs
pairs(100, 100);
LL arr[] = { 3, 4, 1, 7 };
int size = sizeof(arr) / sizeof arr[0];
int k = 3;
unsigned LL temp = product(arr, size, k);
cout<<"product of all subsequences of size k except minimum and maximum element is :"<<temp << endl;
return 0;
}輸出
product of all subsequences of size k except minimum and maximum element is :144
更新於: 2019-12-23
157 次檢視
廣告