เราได้รับอาร์เรย์ที่เรียงลำดับขององค์ประกอบประเภทจำนวนเต็มและตัวแปรจำนวนเต็ม x และงานคือการสร้างคู่จากอาร์เรย์ที่กำหนดและคำนวณผลคูณขององค์ประกอบในคู่และตรวจสอบว่าผลิตภัณฑ์ที่คำนวณได้น้อยกว่า k หรือไม่
ป้อนข้อมูล
int arr[] = {2, 7, 1, 0, 8}, int k = 10 ผลผลิต
Count of pairs in a sorted array whose product is less than k are: 7
คำอธิบาย
The pairs that can be formed from the given array are: (2, 7) = 14(greater than k), (2, 1) = 2(less than k), (2, 0) = 0(less than k), (2, 8) = 16(greater than k), (7, 1) = 7(less than k), (7, 0) = 0(less than k), (7, 8) = 56(greater than k), (1, 0) = 0(less than k), (1, 8) = 8(less than k), (0, 8) = 0(less than k). So, the count of pairs with sum less than k are 7.
ป้อนข้อมูล
int arr[] = {2, 4, 6, 8}, int k = 10 ผลผลิต
Count of pairs in a sorted array whose product is less than k are: 1
คำอธิบาย
The pairs that can be formed from the given array are: (2, 4) = 8(less than k), (2, 6) = 12(greater than k), (2, 8) = 16(greater than k), (4, 6) = 24(greater than x), (4, 8) = 32(greater than k), (6, 8) = 48(greater than k). So, the count of pairs with products less than k is 1.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
อาจมีหลายวิธีในการแก้ปัญหาที่กำหนด เช่น แนวทางไร้เดียงสาและแนวทางที่มีประสิทธิภาพ มาดูแนวทางไร้เดียงสากันก่อน .
-
ป้อนอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์แล้วส่งข้อมูลไปยังฟังก์ชัน
-
ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บจำนวนคู่ที่มีผลิตภัณฑ์น้อยกว่า k
-
เริ่มการวนซ้ำ FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์
-
ภายในลูป เริ่มวนใหม่ FOR จาก j ถึง i + 1 จนถึงขนาดอาร์เรย์
-
ภายในลูปคำนวณผลิตภัณฑ์เป็น arr[i] * arr[j] และตรวจสอบว่า IF product
-
คืนจำนวน
-
พิมพ์ผล
แนวทางที่มีประสิทธิภาพ
-
ป้อนอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์แล้วส่งข้อมูลไปยังฟังก์ชัน
-
ประกาศการนับตัวแปรชั่วคราวเพื่อเก็บจำนวนคู่ที่มีผลรวมน้อยกว่า x
-
ตั้งค่า arr_0 เป็น 0 และ arr_1 เป็น size-1
-
เริ่มวนซ้ำ FOR จาก arr_0 ถึง arr_1
-
ภายในลูป ให้ตรวจสอบ IF arr[arr_0] * arr[arr_1]
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง (แนวทางไร้เดียงสา)
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int count = 0;
int product = 1;
for(int i = 0 ; i<size ; i++){
for(int j = i+1; j<size; j++){
product = arr[i] * arr[j];
if(product < k){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {5, 8, 2, 1, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 10;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of pairs in a sorted array whose product is less than k are: 5
ตัวอย่าง (แนวทางที่มีประสิทธิภาพ)
#include <iostream>
using namespace std;
int pair_product(int arr[], int size, int k){
int arr_0 = 0;
int arr_1 = size-1;
int count = 0;
int product = 1;
while(arr_0 < arr_1){
product = arr[arr_0] * arr[arr_1];
if (product < k){
count = count + (arr_1 - arr_0);
arr_0++;
}
else{
arr_1--;
}
}
return count;
}
int main(){
int arr[] = {1, 3, 4, 2, 1};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 5;
cout<<"Count of pairs in a sorted array whose product is less than k are: "<<pair_product(arr, size, k);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of pairs in a sorted array whose product is less than k are: 10
