Gợi ý thuật toán cho bài tập nhánh

Chào mọi người, em đang gặp một bài toán liên quan tới nhánh mà nó có nhiều nhánh quá :frowning: em chưa thể tưởng tượng ra cách dùng thuật toán cho bài này thế nào :frowning:
Em nghĩ nếu đây là nhánh thẳng thì em sẽ dùng Backtracking nhưng vì trong nhánh lại có thêm nhánh nên em nghĩ là không thể dùng Backtracking được
Mọi người có thể xem qua rồi gợi ý thuật toán cho em được không ạ? :point_right: :point_left:

Đây là bài toán em cần giải:

Tìm số lớn nhất trong các phần tử a, b, c, d…, biết chúng là các số nguyên và được nhập sẵn. Biết rằng đây luôn là mạch hở, nhánh sẽ được nhập vào từ bàn phím dưới dạng (<điểm đầu> <điểm cuối> <giá trị phần tử>)
Ví dụ:
INPUT
1 2 3
2 3 9
3 4 7
3 5 2
2 6 6
OUTPUT: 9

Hình vẽ cho ví dụ

Đây là mô phỏng hình vẽ của cái cây phức tạp hơn và cũng là bài toán em muốn giải:

Cảm ơn mọi người ạ!

Update: em vừa edit lại ví dụ ạ

Giá trị lớn nhất của cái gì? Là trong đám a, b c???
Theo ví dụ thì đáp án là gì

5 Likes

Dạ là giá trị lớn nhất trong đám a, b, c á anh.
Ví dụ a, b, c, d nhập vào là 3, 9, 7, 2 thì đáp án là 9 á anh

Bài này nghe giống như là tìm đoạn đường có độ dài lớn nhất trong một đồ thị (graph) được biểu diễn theo danh sách các cạnh kề (adjacency list).

Bạn có thể search với từ khoá: c++ graph dfs adjacency list
Trong đó, DFS (Depth first search) là thuật toán duyệt đồ thị có sử dụng kỹ thuật Backtracking.

Nhưng mà mình chưa hiểu lắm, nếu chỉ là tìm độ dài lớn nhất trong danh sách cạnh a, b, c, d, … thì có thể biết ngay tại thời điểm input rồi, cần gì phải duyệt đồ thị nữa nhỉ?

5 Likes

với cái ví dụ, thì bạn chỉ việc nhập vào rồi lấy lớn nhất thôi, không quan tâm 2 số đầu tiên nữa là được

max = 1 // gán max = -1, đây sẽ là biến chưa giá trị max
lặp:
   nhập a, b, c 
   max = maxOf(max, c) // nếu c lớn hơn max thì gán max = c
in kết quả biến max
6 Likes

Ôi cảm ơn 2 anh @nguyenchiemminhvu@kisuluoibieng rất nhiều vì đã giải ngố cho em. Em bị mấy cái <điểm đầu> <điểm cuối> làm rối nên mới phức tạp hóa cái bài toán :frowning:

Dù gì cũng cảm ơn anh @nguyenchiemminhvu nhiều vì từ khóa nhé, đây là lần đầu tiên em biết đến thuật toán này nên em sẽ xem qua để học thêm kiến thức ạ :kissing_closed_eyes: :kissing_closed_eyes:

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?