Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 주어진 값 x와 합이 같은 정렬된 이중 연결 목록에서 세 쌍을 셉니다.

<시간/>

정수 값을 포함하는 정렬된 이중 연결 목록이 제공됩니다. 목표는 곱이 주어진 값 x와 같은 트리플렛을 찾는 것입니다. 입력 연결 목록이 3−4−1−2이고 x가 6이면 개수는 1이 됩니다(triplet (3,1,2) )

C++에서 주어진 값 x와 합이 같은 정렬된 이중 연결 목록에서 세 쌍을 셉니다.

예를 들어

입력

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의 헤드에 대한 포인터를 가져와서 데이터 부분의 곱을 x로 갖는 노드의 트리플렛 개수를 반환합니다.

  • 초기 카운트를 0으로 합니다.

  • 구조체 블록 유형의 세 포인터 temp_1, temp_2 및 temp_3을 가져옵니다.

  • 연결 목록의 헤드를 가리키는 temp_1, temp_1 옆을 가리키는 temp_2, temp_3 다음을 가리키는 temp_3부터 시작하여 처음 세 노드를 가리키는 세 개의 포인터가 있습니다.

  • 이 포인터를 사용하여 마지막 노드까지 트래버스합니다.

  • 위의 모든 포인터의 현재 데이터 부분의 곱이 x인 경우. ((temp_1−>data + temp_2−>data + temp_3−>data) ==x) 그런 다음 카운트를 증가시킵니다.

  • 결국 우리는 세 쌍의 수를 세고 count에 저장했습니다.

  • 결과로 카운트를 반환합니다.

예시

#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