資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學計算具有 <= K 的乘積的所有子序列 - C++ 中的遞迴方法
本教程中，我們將討論一個程式，該程式用於查詢具有 <= k 乘積的子序列數。
為此，我們將得到一個數組和一個值 K。我們的任務是找到具有 K 的乘積的子序列數。
示例
#include <bits/stdc++.h>
#define ll long long
using namespace std;
//keeping count of discarded sub sequences
ll discard_count = 0;
ll power(ll a, ll n){
if (n == 0)
return 1;
ll p = power(a, n / 2);
p = p * p;
if (n & 1)
p = p * a;
return p;
}
//recursive approach to count
//discarded sub sequences
void solve(int i, int n, float sum, float k,
float* a, float* prefix){
if (sum > k) {
discard_count += power(2, n - i);
return;
}
if (i == n)
return;
float rem = prefix[n - 1] - prefix[i];
if (sum + a[i] + rem > k)
solve(i + 1, n, sum + a[i], k, a, prefix);
if (sum + rem > k)
solve(i + 1, n, sum, k, a, prefix);
}
int countSubsequences(const int* arr,
int n, ll K){
float sum = 0.0;
float k = log2(K);
float prefix[n], a[n];
for (int i = 0; i < n; i++) {
a[i] = log2(arr[i]);
sum += a[i];
}
prefix[0] = a[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
ll total = power(2, n) - 1;
if (sum <= k) {
return total;
}
solve(0, n, 0.0, k, a, prefix);
return total - discard_count;
}
int main() {
int arr[] = { 4, 8, 7, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
ll k = 50;
cout << countSubsequences(arr, n, k);
return 0;
}輸出
9
更新於： 17-Feb-2020
160 次觀看
廣告