Đưa ra một danh sách được liên kết kép được sắp xếp có chứa các giá trị số nguyên. Mục đích là tìm các bộ ba có tích bằng giá trị x đã cho. Nếu danh sách liên kết đầu vào là 3−4−1−2 và x là 6 thì số lượng sẽ là 1 (bộ ba (3,1,2))
Ví dụ
Đầu vào
linked list: [ 200−4−16−5−10−10−2 ] x=200
Đầu ra
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 3
Giải thích
Triplets will be: (4,5,10), (4,5,10) and (10,10,2)
Đầu vào
linked list: [ 4−3−1−5−2−4−2] x=12
Đầu ra
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are: 3
Giải thích
Triplets will be: (4,3,1), (3,1,4) and (3,2,2)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Theo cách tiếp cận này.
-
Chúng tôi đang sử dụng một nút danh sách được liên kết dưới dạng cấu trúc chứa phần dữ liệu int và các con trỏ tiếp theo và trước đó tự tham chiếu
-
Hàm insert_node (struct block ** head, int data) thêm nút ở đầu danh sách được liên kết với dữ liệu.
-
Hàm Product_x (khối struct * head, int x) đưa con trỏ đến phần đầu của danh sách được liên kết kép và số nguyên x và trả về số lượng bộ ba nút có tích của phần dữ liệu là x.
-
Lấy số lượng ban đầu là 0.
-
Lấy ba con trỏ temp_1, temp_2 và temp_3 của loại khối cấu trúc.
-
Bắt đầu từ temp_1 trỏ đến đầu danh sách được liên kết, temp_2 trỏ đến bên cạnh temp_1 và temp_3 trỏ đến tiếp theo temp_3, chúng tôi có ba con trỏ trỏ đến ba nút đầu tiên.
-
Di chuyển bằng cách sử dụng các con trỏ này cho đến nút cuối cùng.
-
Nếu các phần dữ liệu hiện tại của tất cả các con trỏ ở trên có sản phẩm là x. ((temp_1−> data * temp_2−> data * temp_3−> data) ==x) sau đó đếm gia số.
-
Cuối cùng, chúng tôi đếm số lượng sinh ba và lưu vào số đếm.
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of triplets in a sorted doubly linked list whose product is equal to a given value x are : 1