计算所有三元组的总和等于C ++中的理想立方体

  • Z时代
  • 2024-01-10
  • 分类：综合

我们给定了一个由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

以上是 计算所有三元组的总和等于C ++中的理想立方体 的全部内容， 来源链接： utcz.com/z/353400.html

回到顶部