数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究用 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= 1
Explanation − 18+6+3 = 27 (is a perfect cube)
Except this no other triplet is a perfect cube.
Input − array[] = {1, 2, 3, 4, 5};
Output − Number of Triplets are= 2
Explanation − 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];
// Function to find the occurence of a number
// in the given range
void compute(int ar[], int num){
for (int i = 0; i < num; ++i) {
for (int j = 1; j <= 15000; ++j) {
// if i == 0
// assign 1 to present value
if (i == 0)
arrd[i][j] = (j == ar[i]);
// else add +1 to current state with
// previous state
else
arrd[i][j] = arrd[i - 1][j] + (ar[i] == j);
}
}
}
// Function to count the triplets whose sum
// is a perfect cube
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]);
// count all occurrence of third triplet
// in range from j+1 to n
if (rem > 0)
ans += arrd[num - 1][rem] - arrd[j][rem];
}
}
}
return ans;
}
// main function code
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
更新于：2020年5月15日
168 次浏览
广告