資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告