정수 값을 포함하는 정렬된 이중 연결 목록이 제공됩니다. 목표는 곱이 주어진 값 x와 같은 삼중항을 찾는 것입니다. 입력 연결 리스트가 3−4−1−2이고 x가 6이면 개수는 1이 됩니다(triplet (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의 헤드에 대한 포인터를 가져와서 데이터 부분의 곱을 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 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