计算所有三元组的总和等于C ++中的理想立方体
我们给定了一个由n个整数组成的数组，任务是计算总和等于理想立方的所有三元组的计数
什么是完美的立方体
一个完美的立方体是一个数字，它是任意数量的立方体，例如125是一个5的立方体，因此我们可以说125是一个完美的立方体。一些理想的立方整数是1、8、27、64、125…。
因此，根据数组中的问题，我们必须找到和计数总和等于理想立方数的三元组（3个值的集合）。此外，如果三元组的总和不超过15000，则条件只能是24个立方体。因此，我们将使用动态编程方法以较小的复杂度解决问题。
例如
Input− array[] = { 5, 2, 18, 6, 3 };Output − Number of Triplets are= 1Explanation − 18+6+3 = 27 (is a perfect cube)
Except this no other triplet是一个完美的立方体.Input − array[] = {1, 2, 3, 4, 5};Output − Number of Triplets are= 2Explanation − 1 + 2 + 5 = 8 (is a perfect cube)
1 + 3 + 4 = 8 (is a perfect cube)以下程序中使用的方法如下
输入正整数数组
计算其大小
使用动态编程，我们将发现数组中数字的出现。
初始化变量ans以存储三元组的数量。
遍历并找到三元组集合的第三次出现，并确定它是否是理想的立方体。如果三元组是理想的立方体，则将ans的值增加1。
返回ans。
示例
#include <bits/stdc++.h>
using namespace std;
int arrd[1001][15001];
//查找数字出现的功能
//在给定范围内
void compute(int ar[], int num){
for (int i = 0; i < num; ++i) {
for (int j = 1; j <= 15000; ++j) {
//如果我==0-
//给现值分配1-
if (i == 0)
arrd[i][j] = (j == ar[i]);
//将+1添加到当前状态
//先前状态
else
arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
}
}
}
//计算三元组的总和的功能
//是一个完美的立方体
int countTriplets(int ar[], int num){
compute(ar, num);
int ans = 0; // Initialize answer
for (int i = 0; i < num - 2; ++i) {
for (int j = i + 1; j < num - 1; ++j) {
for (int k = 1; k <= 24; ++k) {
int cube = k * k * k;
int rem = cube - (ar[i] + ar[j]);
//计算所有出现的第三个三元组
//范围从j+1到n-
if (rem > 0)
ans += arrd[num - 1][rem] - arrd[j][rem];
}
}
}
return ans;
}
//主要功能代码
int main(){
int ar[] = { 5, 2, 18, 6, 3 };
int num = sizeof(ar) / sizeof(ar[0]);
cout << “Number of Triplets are= ”<<countTriplets(ar, num);
return 0;
}输出结果
如果我们运行上面的代码，它将生成以下输出-
Number of Triplets are= 1