home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

นับแฝดสามในรายการที่เชื่อมโยงแบบทวีคูณซึ่งผลรวมเท่ากับค่าที่กำหนด x ใน C++

กำหนดรายการที่เชื่อมโยงแบบทวีคูณซึ่งมีค่าจำนวนเต็ม เป้าหมายคือการหาแฝดสามที่มีผลิตภัณฑ์เท่ากับค่าที่กำหนด x หากรายการเชื่อมโยงที่ป้อนคือ 3-4-1-2 และ x คือ 6 การนับจะเท่ากับ 1 (แฝดสาม (3,1,2) )

นับแฝดสามในรายการที่เชื่อมโยงแบบทวีคูณซึ่งผลรวมเท่ากับค่าที่กำหนด x ใน C++

ตัวอย่าง

อินพุต

linked list: [ 3−4−13−5−10−10−0 ] x=20

ผลลัพธ์

Count of triplets in a sorted doubly linked list whose product is equal to a given
value x are: 2

คำอธิบาย

Triplets will be:
( 3,4,13 ) and ( 10,10,0 )

อินพุต

linked list: [ 4−3−1−5−2−4−2 ] x=8

ผลลัพธ์

Count of triplets in a sorted doubly linked list whose product is equal to a given
value x are: 6

คำอธิบาย

Triplets will be:
( 4,3,1), (1,5,2), (3,1,4), (1,5,2), (4,2,2) and (2,4,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 ถัดไป เรามีตัวชี้สามตัวที่ชี้ไปที่สามโหนดแรก

  • สำรวจโดยใช้พอยน์เตอร์เหล่านี้จนถึงโหนดสุดท้าย

  • หากส่วนข้อมูลปัจจุบันของพอยน์เตอร์ด้านบนทั้งหมดมีผลิตภัณฑ์เป็น 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 sum_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 = 22;
   cout<<"Count of triplets in a sorted doubly linked list whose sum is equal to a given value x
   are: "<<sum_x(head, x);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of triplets in a sorted doubly linked list whose sum is equal to a given value x are: 1