เราได้รับอาร์เรย์ของจำนวนเต็ม n และภารกิจคือการคำนวณการนับแฝดทั้งหมดที่มีผลรวมเท่ากับลูกบาศก์ที่สมบูรณ์แบบ
ลูกบาศก์ที่สมบูรณ์แบบคืออะไร
ลูกบาศก์สมบูรณ์คือตัวเลขที่เป็นลูกบาศก์ของจำนวนใดๆ เช่น 125 เท่ากับลูกบาศก์ของ 5 เราจึงกล่าวได้ว่า 125 เป็นลูกบาศก์สมบูรณ์ จำนวนเต็มลูกบาศก์ที่สมบูรณ์แบบบางจำนวนคือ 1, 8, 27, 64, 125….
ดังนั้น จากปัญหาในอาร์เรย์ เราต้องหาและนับแฝดสามเหล่านั้น (ชุดค่า 3 ค่า) ซึ่งผลรวมเท่ากับจำนวนลูกบาศก์สมบูรณ์ นอกจากนี้เงื่อนไขที่ให้ผลรวมของแฝดสามมากที่สุดคือ 15,000 ดังนั้นจึงมีได้เพียง 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) แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ใส่อาร์เรย์ของจำนวนเต็มบวก
-
คำนวณขนาด
-
การใช้โปรแกรมไดนามิกเราจะพบการเกิดขึ้นของตัวเลขในอาร์เรย์
-
กำหนดค่าเริ่มต้นของตัวแปรเพื่อเก็บจำนวน triplets
-
สำรวจและค้นหาเหตุการณ์ที่สามของชุดของแฝดสามและค้นหาว่าเป็นลูกบาศก์ที่สมบูรณ์แบบหรือไม่ หากแฝดสามเป็นลูกบาศก์สมบูรณ์ ให้เพิ่มค่าของ ans ขึ้น 1
-
ส่งคืนคำตอบ
ตัวอย่าง
#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
