กำหนดรายการที่เชื่อมโยงแบบทวีคูณซึ่งมีค่าจำนวนเต็ม เป้าหมายคือการหาแฝดสามที่มีผลิตภัณฑ์เท่ากับค่าที่กำหนด x หากรายการเชื่อมโยงอินพุทคือ 3−4-1−2 และ x คือ 6 การนับจะเป็น 1 (ทริปเล็ต (3,1,2))
ตัวอย่าง
อินพุต
linked list: [ 200−4−16−5−10−10−2 ] x=200
ผลลัพธ์
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 3
คำอธิบาย
Triplets will be: (4,5,10), (4,5,10) and (10,10,2)
อินพุต
linked list: [ 4−3−1−5−2−4−2] x=12
ผลลัพธ์
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 3
คำอธิบาย
Triplets will be: (4,3,1), (3,1,4) and (3,2,2)
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้
-
เรากำลังรับโหนดรายการที่เชื่อมโยงเป็นโครงสร้างที่มีส่วนข้อมูล int และตัวชี้ถัดไปและก่อนหน้าที่อ้างอิงตนเอง
-
ฟังก์ชัน insert_node(struct block** head, int data) เพิ่มโหนดที่ส่วนหัวของรายการที่เชื่อมโยงกับข้อมูล
-
ฟังก์ชัน Product_x(struct block* head, int x) นำตัวชี้ไปที่ส่วนหัวของรายการที่เชื่อมโยงแบบทวีคูณและจำนวนเต็ม x และส่งคืนค่าจำนวน triplets ของโหนดที่มีผลิตภัณฑ์ของส่วนข้อมูลเป็น x
-
นับเริ่มต้นเป็น 0
-
ใช้ตัวชี้สามตัว temp_1, temp_2 และ temp_3 ของบล็อก struct ประเภท
-
เริ่มจาก temp_1 ที่ชี้ไปที่ส่วนหัวของรายการที่เชื่อมโยง temp_2 ชี้ไปที่ ถัดจาก temp_1 และ temp_3 ชี้ไปที่ temp_3 ถัดจาก temp_3 เรามีตัวชี้สามตัวที่ชี้ไปที่สามโหนดแรก
-
สำรวจโดยใช้พอยน์เตอร์เหล่านี้จนถึงโหนดสุดท้าย
-
หากส่วนข้อมูลปัจจุบันของพอยน์เตอร์ด้านบนทั้งหมดมีผลิตภัณฑ์เป็น x ((temp_1−>data * temp_2−>data * temp_3−>data) ==x) จากนั้นนับการเพิ่มขึ้น
-
ในตอนท้ายเรานับจำนวนแฝดและเก็บไว้ในการนับ
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#include <iostream>
using namespace std;
struct block{
int data;
struct block *next, *prev;
};
void insert_node(struct block** head, int data){
struct block* ptr = new block();
ptr−>data = data;
ptr−>next = NULL;
ptr−>prev = NULL;
if ((*head) == NULL){
(*head) = ptr;
} else {
ptr−>next = *head;
(*head)−>prev = ptr;
(*head) = ptr;
}
}
int Product_x(struct block* head, int x){
int count = 0;
struct block *temp_1, *temp_2, *temp_3;
for (temp_1 = head; temp_1!= NULL; temp_1 = temp_1−>next){
for (temp_2 = temp_1−>next; temp_2 != NULL; temp_2 = temp_2−>next){
for (temp_3 = temp_2−>next; temp_3!= NULL; temp_3 = temp_3−>next){
if ((temp_1−>data * temp_2−>data * temp_3−>data) == x){
count++;
}
}
}
}
return count;
}
int main(){
struct block* head = NULL;
insert_node(&head, 200);
insert_node(&head, 100);
insert_node(&head, 16);
insert_node(&head, 14);
insert_node(&head, 10);
insert_node(&head, 10);
insert_node(&head, 2);
int x = 200;
cout<<"Count of triplets in a sorted doubly linked list whose product is equal to a given value
x are: "<<Product_x(head, x);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are : 1
