Bác nào giỏi về Cấu trúc dữ liệu vào giúp em với [Archive]

mustexist

30-12-2009, 22:07

Chuẩn bị thi môn này mà tỷ lệ trượt rất cao, các bác giải giúp em bài này với:

Cho cây nhị phân:
typedef struct
{
truong info;
left child;
right child;
}

Viết hàm (bằng C hoặc C++) trả về đường kính của cây (tức độ dài lớn nhất có thể có giữa 2 nút của cây)

Cảm ơn các bác nhiều :beauty:

pipokute

30-12-2009, 22:26

Em hôk thik làm người giỏi nên mạn phép hôk trả lời :) !

mustexist

30-12-2009, 22:45

Help me :((

dangminh2708

30-12-2009, 22:46

he he , mình cũng sắp thi đây ,11/1 là thi , cũng môn này luôn

mustexist

30-12-2009, 23:10

Không ai giúp em sao :((

dangminh2708

30-12-2009, 23:13

up, mình cũng thi phần cây nhị phân

Alias_X

30-12-2009, 23:18

Cũng đang chết cây cối đây :((

phutri2005

30-12-2009, 23:31

Chuẩn bị thi môn này mà tỷ lệ trượt rất cao, các bác giải giúp em bài này với:

Cho cây nhị phân:
typedef struct
{
truong info;
left child;
right child;
}

Viết hàm (bằng C hoặc C++) trả về đường kính của cây (tức độ dài lớn nhất có thể có giữa 2 nút của cây)

Cảm ơn các bác nhiều :beauty:

Sao mà mà bác dốt thế ? Có cái tư tưởng mà nghĩ ko ra !Tư tưởng ở đây là :tính khoảng cách giữa root với nốt xa nhất rồi cộng với khoảng cách cũng từ root đến nốt xa nhì.Mà bác này rõ vcl, đường kính của cây là gì bác cũng dek định nghĩa ra thì bố thằng nào trả lời đc với lại chưa gì kêu ng ta viết code rồi,sao ko nói là cho xin ý tưởng hay thuật giải đi,có fải dễ nghe hơn ko ?Tính khỏang cách từ root đến nốt bất kì mà ko biết nữa thì nghỉ học đi cho rồi.PS:Mình là ITer của trường Đại Học Quốc Gia: ĐH Khoa Học Tự Nhiên:misdoubt:

2 bác chắc ae 1 nhà thoai...đừng như thế :pudency: Cũng sắp chết môn này nè :sosad:

hitman88

30-12-2009, 23:33

bữa mới thi lại môn này, mới coi điểm được 6 đ, mừng :D

mustexist

30-12-2009, 23:38

Sao mà mà bác dốt thế ? Có cái tư tưởng mà nghĩ ko ra !Tư tưởng ở đây là :tính khoảng cách giữa root với nốt xa nhất rồi cộng với khoảng cách cũng từ root đến nốt xa nhì.Mà bác này rõ vcl, đường kính của cây là gì bác cũng dek định nghĩa ra thì bố thằng nào trả lời đc với lại chưa gì kêu ng ta viết code rồi,sao ko nói là cho xin ý tưởng hay thuật giải đi,có fải dễ nghe hơn ko ?Tính khỏang cách từ root đến nốt bất kì mà ko biết nữa thì nghỉ học đi cho rồi.PS:Mình là ITer của trường Đại Học Quốc Gia: ĐH Khoa Học Tự Nhiên:misdoubt:

Mình muốn nhờ người viết code lại cho chắc ăn. Còn ý tưởng thì đã có rồi, khỏi cần bạn chỉ :hell_boy:

ITer KHTN là đây :lol:

mình trường khác :pudency:

herokt44

31-12-2009, 00:02

Sao mà mà bác dốt thế ? Có cái tư tưởng mà nghĩ ko ra !Tư tưởng ở đây là :tính khoảng cách giữa root với nốt xa nhất rồi cộng với khoảng cách cũng từ root đến nốt xa nhì.Mà bác này rõ vcl, đường kính của cây là gì bác cũng dek định nghĩa ra thì bố thằng nào trả lời đc với lại chưa gì kêu ng ta viết code rồi,sao ko nói là cho xin ý tưởng hay thuật giải đi,có fải dễ nghe hơn ko ?Tính khỏang cách từ root đến nốt bất kì mà ko biết nữa thì nghỉ học đi cho rồi.PS:Mình là ITer của trường Đại Học Quốc Gia: ĐH Khoa Học Tự Nhiên:misdoubt:

Thưa ITer ĐH QG: ĐH KHTN rằng cái tư tưởng này sai bố nó rồi. Ngồi đó mà chửi người khác ngu.:hell_boy:
Độ dài lớn nhất có thể có giữa 2 nút của cây không nhất thiết phải qua nút gốc.
Bài này ko khó nhưng cũng ko dễ đâu.
Ở đây có cách giải và code bằng Java. Bạn xem thử:
http://www.coderanch.com/t/467812/Java-General/java/Algorithm-find-Nodes-having-largest
Xem các post của Embla Tingeling . Đầu tiên là tư tưởng giải, sau đó là code.

dinhduongxd4

31-12-2009, 00:16

thi có khó bằng phương pháp tính trường xây dựng không nhỉ? lớp em qua được 5 chú lần 1, 4 con 5 và một con lớn hơn 5

LiberiFatali

31-12-2009, 00:27

nút ko có dữ liệu về cha của nó ah :D

Kumori

31-12-2009, 00:30

Sao mà mà bác dốt thế ? Có cái tư tưởng mà nghĩ ko ra !Tư tưởng ở đây là :tính khoảng cách giữa root với nốt xa nhất rồi cộng với khoảng cách cũng từ root đến nốt xa nhì.Mà bác này rõ vcl, đường kính của cây là gì bác cũng dek định nghĩa ra thì bố thằng nào trả lời đc với lại chưa gì kêu ng ta viết code rồi,sao ko nói là cho xin ý tưởng hay thuật giải đi,có fải dễ nghe hơn ko ?Tính khỏang cách từ root đến nốt bất kì mà ko biết nữa thì nghỉ học đi cho rồi.PS:Mình là ITer của trường Đại Học Quốc Gia: ĐH Khoa Học Tự Nhiên:misdoubt:

Vừa thi bài này xong, và nhắm éo đủ thời gian để nghĩ, pass luôn :lmao:

mustexist

31-12-2009, 00:35

Vừa thi bài này xong, và nhắm éo đủ thời gian để nghĩ, pass luôn :lmao:

Bạn này Việt Nhật K53 phải không nhỉ :D

Đọc bài tiếng anh của bác Embla Tingeling không hiểu lắm :baffle:
java thì không biết rồi. Bác nào tóm tắt lại cho em ý tưởng không :*

anhtrue

31-12-2009, 00:55

Vác quyển sách ra mà chép vào thế thôi, còn muốn hiểu kĩ thì phải đọc code mà theo...Chứ tự nhiên nghĩ ra thì pó tay chấm cơm

DarkPhoenix

31-12-2009, 00:57

Chuẩn bị thi môn này mà tỷ lệ trượt rất cao, các bác giải giúp em bài này với:

Cho cây nhị phân:
typedef struct
{
truong info;
left child;
right child;
}

Viết hàm (bằng C hoặc C++) trả về đường kính của cây (tức độ dài lớn nhất có thể có giữa 2 nút của cây)

Cảm ơn các bác nhiều :beauty:

xuất phát từ 1 node lá A, tìm đường đi dài nhất từ A

Gọi B là node đường đi ấy kết thúc, tìm đường đi dài nhất từ B, đây chính là đường kính cây

DarkPhoenix

31-12-2009, 00:58

Mình muốn nhờ người viết code lại cho chắc ăn. Còn ý tưởng thì đã có rồi, khỏi cần bạn chỉ :hell_boy:

ITer KHTN là đây :lol:

mình trường khác :pudency:

lol, cái ý tưởng ấy sai bét nhè mà bảo là có rùi

ăn sẵn thế này thì chả thèm giúp =))

// cái bạn moder ITers gì đó KHTN đừng lên mặt nữa, ko mình mất mặt theo bạn luôn :baffle:

anhtrue

31-12-2009, 01:01

Thế mấy bác học không có sách, sách tiếng anh đầy ra, code đầy đủ, không chỉ C mà C++ lẫn Java đều có. Ngoài ra, một số sách nó còn viết cả UML. Đọc đi đã rồi hãy hỏi, hỏi giờ cũng chẳng ăn được cái gì đâu.

Ngoài ra, các thuật toán này đều có công thức tính độ sau, số nút lá, nút root và tính hiệu quả hết rồi, chỉ cần lắp công thức là ra.

Chứng tỏ , bác này chưa dở quyển sách ra đọc thì phải, nghi ngờ quá

mustexist

31-12-2009, 01:02

lol, cái ý tưởng ấy sai bét nhè mà bảo là có rùi

ăn sẵn thế này thì chả thèm giúp =))

// cái bạn moder ITers gì đó KHTN đừng lên mặt nữa, ko mình mất mặt theo bạn luôn :baffle:

Bác có giải thích giúp em được bài tiếng anh kia không? ông ấy tính khoảng cách đến nút cha chung bằng nhị phân gì mà em đọc có thấy nhưng không hiểu tại sao, hic. Vẫn chưa hiểu ý tưởng lắm :pudency:

DarkPhoenix

31-12-2009, 01:03

Thế mấy bác học không có sách, sách tiếng anh đầy ra, code đầy đủ, không chỉ C mà C++ lẫn Java đều có. Ngoài ra, một số sách nó còn viết cả UML. Đọc đi đã rồi hãy hỏi, hỏi giờ cũng chẳng ăn được cái gì đâu.

Ngoài ra, các thuật toán này đều có công thức tính độ sau, số nút lá, nút root và tính hiệu quả hết rồi, chỉ cần lắp công thức là ra.

Chứng tỏ , bác này chưa dở quyển sách ra đọc thì phải, nghi ngờ quá

=)) chỉ mình quyển sách nào có bài này với =))

mình biết làm mà mình chẳng biết cuốn sách nào mà bạn nói cả =))

DarkPhoenix

31-12-2009, 01:04

Bác có giải thích giúp em được bài tiếng anh kia không? ông ấy tính khoảng cách đến nút cha chung bằng nhị phân gì mà em đọc có thấy nhưng không hiểu tại sao, hic. Vẫn chưa hiểu ý tưởng lắm :pudency:

cha chung làm wái gì cho nó phiền

cách mình đã chỉ rùi đó, đúng cho cây tổng quát luôn, khỏi cần là cây nhị phân

xuất phát từ 1 node lá A, tìm đường đi dài nhất từ A

Gọi B là node đường đi ấy kết thúc, tìm đường đi dài nhất từ B, đây chính là đường kính cây

mustexist

31-12-2009, 01:06

Lúc đầu có ý tưởng là dành cho cây cân bằng. Thế thì dễ mà bác. Chứ em có nói là giống ý tưởng với cha ITer kia đâu :sad:

DarkPhoenix

31-12-2009, 01:07

Lúc đầu có ý tưởng là dành cho cây cân bằng. Thế thì dễ mà bác. Chứ em có nói là giống ý tưởng với cha kia đâu :sad:

Maintain 1 balance tree khó hơn cái bài mà bạn cần làm đấy :))

mình chỉ bạn cách chuẩn rùi, thi OLP toàn code cách này

còn bạn code đc hay ko thì còn tuỳ bạn :)

còn giờ giải thích cái node cha chung cho bạn, thì mình giải thích cũng mệt, mình chỉ thích đi chém gió thôi :D

anhtrue

31-12-2009, 01:14

http://www.flazx.com/tags/algorithms+in+c

Bạn vào đây để tham khảo nhé, còn quyển sách của mình hình như không có ở việt nam thì phải , hơn nữa mình photo lại của một bạn cùng lớp nên không rõ. Quyển này khá dầy , gồm 4 quyển
1. Object in C/C++
2. Algorithm and Block
3. Data struct
4. .... (quên rồi)

Chịu khó vào xem nhá...

DarkPhoenix

31-12-2009, 01:18

http://www.flazx.com/tags/algorithms+in+c (http://vozforums.com/redirect/?link=http%3A%2F%2Fwww.flazx.com%2Ftags%2Falgorithms%2Bin%2Bc)

Bạn vào đây để tham khảo nhé, còn quyển sách của mình hình như không có ở việt nam thì phải , hơn nữa mình photo lại của một bạn cùng lớp nên không rõ. Quyển này khá dầy , gồm 4 quyển
1. Object in C/C++
2. Algorithm and Block
3. Data struct
4. .... (quên rồi)

Chịu khó vào xem nhá...

mấy cái cuốn sách của bạn đưa ra đều có rất nhiều thuật toán cơ bản

Tuy nhiên bài này là 1 bài cần phải suy luận từ những bài cơ bản

vd: bài cơ bản là: tìm đường đi của 2 node trên cây --> mở rộng ra bài chủ thớt hỏi

Nếu bạn ko chỉ rõ được ở cuốn sách nào, mà cứ nói chung chung thế, thì nội thời gian lục hết đống sách kia cũng khiến bạn ấy wa ngày thi luôn :)

anhtrue

31-12-2009, 01:28

Mình lâu không đụng rồi, tài liệu thì toàn photo sách thôi, không chơi ebook nhiều lắm.
ebook thì có 1 quyển tâm đắc lắm lắm nhưng đã mất sau lần format ổ từ lâu rồi ...

Theo kinh nghiệm thì trong đống sách kia , bạn tìm quyển của bọn Addison-Wesley nhá, quyển của mình đang cầm cũng có ghi nhà xuất bản Addison-Wesley, còn tên sách thì ko có

Có rồi đây :
Data Structures and Problem Solving with C++ [2nd Ed] [M. A. Weiss] [Addison Wesley]

http://www.flazx.com/ebook6337.php

Quyển này đòi hỏi bạn phải học qua, và tiếng anh phải khá, nếu vẫn chưa thấm thì mình pó tay rồi

herokt44

31-12-2009, 10:37

xuất phát từ 1 node lá A, tìm đường đi dài nhất từ A

Gọi B là node đường đi ấy kết thúc, tìm đường đi dài nhất từ B, đây chính là đường kính cây

Cách này nghe được nè. Làm theo cách này cũng ok.

-------------

Giải thích cách làm theo cách đánh số nhị phân cho các nút trên cây nhị phân:

Nút gốc đánh số 1. Từ nút gốc
+ Nhánh trái thêm 0 vào -> 10.
+ Nhánh phải thêm 1 vài -> 11.

Tương tự cứ làm như thế:
+ Nút trái = nút cha thêm 1.
+ Nút phải = nút cha thêm 0.

Sau khi điền đủ cây nhị phân thì khi xét khoảng cách giữa 2 nút rất đơn giản. Xác định phần giống nhau ở đầu. Và đếm số chữ số ở phần còn lại

Ví dụ 1: Nút 100 và nút 101. Có phần đầu là 10 giống nhau. Mỗi số trừ phần giống nhau ra thì còn lại 1 số.
10|0
10|1
-> Khoảng cách = 1+1 = 2;

Ví dụ 2: Nút 100 và nút 110. Có phần đầu là 1 giống nhau. Mỗi số trừ phần giống nhau ra thì còn lại 2 số.
1|00
1|10
-> Khoảng cách = 2+2 = 2;

Ví dụ 3: Nút 10 và nút 110. Có phần đầu là 1 giống nhau. Số đầu trừ phần giống nhau ra còn 1 số, số sau trừ phần giống nhau còn 2 số
1|0
1|10
-> Khoảng cách = 1+2 = 3;

katurato

31-12-2009, 12:39

dù mình cũng dốt CTDL và mới thi là biết roqts xiềng nhưng mình vẫn ko ngửi đc cái lối bố đời của bạn moder. bạn đừng có đi đâu cũng khoe cái mác tự nhiên ra mà nhục lây cả mình :stick: lớp nào đấy??

mustexist

31-12-2009, 14:25

có thêm 1 hướng này, các bác thử coi xem có sai ở đâu không?

Vì luôn tồn tại 1 node là gốc của 1 cây con nào đó sao cho đường nối 2 nút có độ dài lớn nhất đi qua.
==> dùng 1 hàm đệ quy tính chiều cao cây con trái, cây con phải.
thì đường kính cây chính bằng max(chiều cao cây con trái + chiều cao cây con phải)
Không biết có sai không các bác :D

akiross

31-12-2009, 14:32

Thưa ITer ĐH QG: ĐH KHTN rằng cái tư tưởng này sai bố nó rồi. Ngồi đó mà chửi người khác ngu.:hell_boy:
Độ dài lớn nhất có thể có giữa 2 nút của cây không nhất thiết phải qua nút gốc.
Bài này ko khó nhưng cũng ko dễ đâu.
Ở đây có cách giải và code bằng Java. Bạn xem thử:
http://www.coderanch.com/t/467812/Java-General/java/Algorithm-find-Nodes-having-largest
Xem các post của Embla Tingeling . Đầu tiên là tư tưởng giải, sau đó là code.

@IT-er: em cũng là I tờ KHTN HCM đây, hồi đó môn lày học đại ca Thi Vương đẹp trai đc 8-9 điểm gì đấy, giờ quên miạ nó gòi, bác nói khó ngửi lắm ạ .. 3D
@Bác Chủ: em nghĩ giáo trình đủ đáp ứng đc lời giải bài này, bác ngâm cứu lại xem, môn này khá khó nhưng thi chỉ trong chương trình học thôi, được cái mấy đại ca dạy tài tử quá nên sv cứ trơ mắt ếch, đành tự học thôi :hang:

akiross

31-12-2009, 14:35

:D hồi đó toàn chơi mã giả, có nhớ cú pháp đek đâu mà Cê cộng vơí cả Chà Và

MAXGear™

31-12-2009, 14:45

Cấu trúc dữ liệu và giải thuật

Môn này may mà qua được, nhưng bọn mình làm bắng A-bem-bờ-ly, thế mà tổng kết môn được 6.7 :shot:

akiross

31-12-2009, 14:50

Cấu trúc dữ liệu và giải thuật

Môn này may mà qua được, nhưng bọn mình làm bắng A-bem-bờ-ly, thế mà tổng kết môn được 6.7 :shot:

T___T hợp ngữ hả bác, cái này em ko đc học nhưng mà có học cái môn Ngôn Ngữ Máy, viết thấp hơn nó 1 tý, cờ quạt nhớ nhung tứ lung tung mệt vl

mustexist

31-12-2009, 22:03

có thêm 1 hướng này, các bác thử coi xem có sai ở đâu không?

Vì luôn tồn tại 1 node là gốc của 1 cây con nào đó sao cho đường nối 2 nút có độ dài lớn nhất đi qua.
==> dùng 1 hàm đệ quy tính chiều cao cây con trái, cây con phải.
thì đường kính cây chính bằng max(chiều cao cây con trái + chiều cao cây con phải)
Không biết có sai không các bác :D

vẫn cần bác nào ktra lại cái này :D