เราได้รับอาร์เรย์ที่เรียงแล้วขององค์ประกอบจำนวนเต็มและตัวแปรจำนวนเต็ม 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
คำอธิบาย
คู่ที่สามารถสร้างได้จากอาร์เรย์ที่กำหนดคือ: (2, 7) = 14(มากกว่า k), (2, 1) = 2(น้อยกว่า k), (2, 0) = 0(น้อยกว่า k), (2, 8) = 16(มากกว่า k), (7, 1) = 7(น้อยกว่า k), (7, 0) = 0(น้อยกว่า k), (7, 8) = 56(มากกว่า k), (1, 0) = 0(น้อยกว่า k), (1, 8) = 8(น้อยกว่า k), (0, 8) = 0(น้อยกว่า k) ดังนั้นจำนวนคู่ที่ผลรวมน้อยกว่า k คือ 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
คำอธิบาย
คู่ที่สามารถสร้างได้จากอาร์เรย์ที่กำหนดคือ: (2, 4) = 8(น้อยกว่า k), (2, 6) = 12(มากกว่า k), (2, 8) = 16(มากกว่า k), (4, 6) = 24(มากกว่า x), (4, 8) = 32(มากกว่า k), (6, 8) = 48(มากกว่า k) ดังนั้นจำนวนคู่ที่ผลคูณน้อยกว่า k คือ 1
วิธีการที่ใช้ในโปรแกรมด้านล่าง
สามารถมีหลายวิธีในการแก้ปัญหาที่กำหนด คือ วิธีเรียบง่ายและวิธีที่มีประสิทธิภาพ มาดู วิธีเรียบง่าย ก่อน
รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชัน
ประกาศตัวแปรชั่วคราว count เพื่อเก็บจำนวนคู่ที่ผลคูณน้อยกว่า k
เริ่มลูป FOR จาก i = 0 ถึงขนาดของอาร์เรย์
ภายในลูป เริ่มลูป FOR อีกอันจาก j = i + 1 ถึงขนาดของอาร์เรย์
ภายในลูป คำนวณผลคูณเป็น arr[i] * arr[j] และตรวจสอบ IF product < k แล้วเพิ่ม count ขึ้น 1
คืนค่า count
พิมพ์ผลลัพธ์
วิธีที่มีประสิทธิภาพ
รับอาร์เรย์ขององค์ประกอบจำนวนเต็มและคำนวณขนาดของอาร์เรย์และส่งข้อมูลไปยังฟังก์ชัน
ประกาศตัวแปรชั่วคราว count เพื่อเก็บจำนวนคู่ที่ผลรวมน้อยกว่า x
ตั้ง arr_0 เป็น 0 และ arr_1 เป็น size-1
เริ่มลูป FOR จาก arr_0 ถึง arr_1
ภายในลูป ตรวจสอบ IF arr[arr_0] * arr[arr_1] < x แล้วตั้ง count เป็น count + (arr_1 - arr_0) และเพิ่ม arr_0++ มิฉะนั้นลด arr_1 ลง 1
คืนค่า count
พิมพ์ผลลัพธ์
ตัวอย่าง (วิธีเรียบง่าย)
#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
