Chúng ta được cung cấp với một mảng n số nguyên và nhiệm vụ là tính số tất cả các bộ ba có tổng bằng khối lập phương hoàn hảo
Khối lập phương hoàn hảo là gì
Một hình lập phương hoàn hảo là một số là một hình lập phương của bất kỳ số nào, chẳng hạn như 125 là một hình lập phương có 5 nên chúng ta có thể nói rằng 125 là một hình lập phương hoàn hảo. Một số số nguyên khối lập phương hoàn hảo là 1, 8, 27, 64, 125….
Vì vậy, theo bài toán trong mảng, chúng ta phải tìm và đếm những bộ ba (bộ 3 giá trị) có tổng bằng một số lập phương hoàn hảo. Hơn nữa, điều kiện đưa ra là tổng của bộ ba nhiều nhất là 15000 nên chỉ có thể có 24 khối. Vì vậy, chúng tôi sẽ sử dụng cách tiếp cận Lập trình động để giải quyết vấn đề một cách ít phức tạp hơn.
Ví dụ
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) Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập mảng các số nguyên dương
-
Tính toán kích thước của nó
-
Sử dụng lập trình động, chúng tôi sẽ tìm thấy sự xuất hiện của các chữ số trong mảng.
-
Khởi tạo biến ans để lưu trữ số lượng bộ ba.
-
Đi ngang và tìm lần xuất hiện thứ ba của bộ ba và tìm xem nó có phải là một khối hoàn hảo hay không. Nếu bộ ba là một khối hoàn hảo, hãy tăng giá trị của ans lên 1.
-
Trả lại ans.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Number of Triplets are= 1