Trong bài toán này, chúng ta được cung cấp một danh sách liên kết với một nút bao gồm hai giá trị và một con trỏ. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng các phần tử nhỏ hơn của một nút trong danh sách được liên kết.
Ở đây, trong danh sách liên kết chúng ta có hai phần tử là X và Y. Chương trình sẽ tìm điểm cực tiểu của x và y. Các phần tử tối thiểu từ tất cả các nút được thêm vào, đây là kết quả bắt buộc.
Đầu vào -
(5,2)->(7,9)->(6,3)->(36,24)->(19,26)->null
Đầu ra -
55
Giải thích -
Hãy lấy tối thiểu X và Y từ mỗi nút -
node1 - mini = 5 node2 - mini = 7 node3 - mini = 3 node4 - mini = 24 node5 - mini = 19 Sum = 55
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp tiếp cận phân tầng bằng cách truy cập từng nút và tìm điểm nhỏ nhất của X và Y. Sau đó thêm nó vào biến tổng và sau đó trả về tổng, khi nút kết thúc.
Thuật toán
Khởi tạo - sum =0
Bước 1 - Duyệt qua danh sách và thực hiện như sau:
Bước 1.1 - Tìm giá trị nhỏ nhất của phần đầu → X và phần đầu → Y.
Bước 1.2 - cộng tối thiểu thành tổng
Bước 2 - Trả lại Tổng,
Ví dụ
Chương trình minh họa hoạt động của thuật toán của chúng tôi -
#include <iostream>
using namespace std;
struct Node {
int X;
int Y;
Node* next;
};
void addNode(Node** head, int x, int y){
Node* ptr = *head;
Node* temp = new Node();
temp->X = x;
temp->Y = y;
temp->next = NULL;
if (*head == NULL)
*head = temp;
else {
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = temp;
}
}
int findMinSum(Node* head){
int sum = 0;
while (head != NULL) {
sum += min(head->X , head->Y);
head = head->next;
}
return sum;
}
int main(){
Node* head = NULL;
addNode(&head, 5, 2);
addNode(&head, 7, 9);
addNode(&head, 6, 3);
addNode(&head, 36, 24);
addNode(&head, 19, 26);
cout<<"The sum of smaller elements of nodes in Linked List is "<<findMinSum(head)<<endl;
return 0;
} Đầu ra
The sum of smaller elements of nodes in Linked List is 55