Chủ đề này có 13 trả lời

[chungtm2000]

các bác giải giùm em bài toán này với ạ:

Cho : n đoạn thẳng đồng phẳng, các đoạn thẳng đó không cắt nhau. một đoạn thẳng bất kỳ được giới hạn bởi 2 điểm Ai (xi, yi, zi) và Bi (xi, yi, zi).
Tìm tất cả các hình đa giác nhỏ nhất được tạo bởi n đoạn thẳng đó
( nếu bác nào cần hình vẽ minh họa, hãy để lại địa chỉ mail em gửi hình, ở đây em không biết làm cách nào để gửi lên cả )

[chungtm2000]

17 người xem không ai trả lời tôi cả

[tvkhoa71]

bạn mình oi, bạn cgo là n đoạn đồng phẳng, tức là ở trên 1 mặt phẳng. Hơn nữa các đọan thẳng này lại không cắt nhau, vậy làm sao tạo ra hình đa giác được, hay là t2im các đa giác nối các đầu mút của các đoạn thẳng.
Khoa.

[chungtm2000]

Hơn nữa các đọan thẳng này lại không cắt nhau
Khoa.

to tvkhoa71 : các đoạn thẳng đó có thể giao nhau ở đầu mút ( có thể coi là không cắt nhau). Đây chính là dạng bài toán que diêm đó tvkhoa71 à, bạn có thể hiểu đầu bài cụ thể hơn như thế này:

+Đầu vào:
+Cho các đoạn thẳng không cắt nhau từng đôi một(có thể giao nhau ở đầu mút)
+Tọa độ các điểm ở mỗi đầu của đoạn thẳng

+Yêu cầu:
+Tìm tất cả các hình đa giác tạo bởi các đoạn thẳng nói trên

[ntson]

Bạn nên cho biết giới hạn số đoạn thẳng.
Tôi có 1 cách làm này:
_ Gọi A là tập tất cả các đầu mút của các đoạn thẳng. Như vậy đỉnh của các đa giác chỉ nằm trong tập này.
_ Tìm xem mỗi điểm trong A nằm trên đoạn thẳng nào.
_ Xây dựng đồ thị G đỉnh là các điểm trong A.
_ Nếu 2 điểm cùng nằm trên 1 đoạn thẳng thì nối 2 điểm đó = 1 cung.
_ Dùng depth first search (loang sâu) để tìm tất cả các chu trình trong đồ thị. Mỗi chu trình là 1 đa giác.
Độ phức tạp của tt là n^2.

Có gì cần hỏi thêm thì add nick YM mình vào: ntsonicon . Ở đây không có nhiều người trả lời được câu hỏi của bạn đâu. Cứ nhìn những thread khác thì rõ.

[Trytolive]

Đây là diễn đàn toán học nên các bài tìm thuật toán cho các vấn đề tin học sẽ ít được mọi người quan tâm.

Bài này thì không khó nhưng tìm một lời giải tối ưu thì khó.

Tuy nhiên, máy tính mạnh như hiện nay sẽ dư sức với thuật toán bét nhất.

PS:Mình có thử sang diễn đàn tin học xem thử nhưng tồi lắm.

[chungtm2000]

To ntson: rất cảm ơn bạn tôi cũng có cách làm nhưng tôi không ưng nó lắm, nếu có thể chúng ta hẹn nhau một thời điểm thích hợp để cùng online hoặc gặp trực tiếp cũng được, bạn có thể quyết định hình thức trao đổi. Nick của tôi là chungtm20000, điện thoại là 0989668496. Rất mong được bạn chỉ giáo

[Alligator]

...
Có gì cần hỏi thêm thì add nick YM mình vào: ntsonicon . Ở đây không có nhiều người trả lời được câu hỏi của bạn đâu. Cứ nhìn những thread khác thì rõ.

Có thể đó là sự thật, nhưng cách nói dễ gây hiểu lầm là có ý chê bai, vốn là một điều không nên làm trong một nơi trao đổi có tính thân hữu. "Lời nói không mất tiền mua..." sau này bạn ntson tập ứng xử tế nhị hơn nhé.

[ntson]

Cái forum này rất hay nhưng có vẻ mọi người không nhiệt tình lắm. Có quá nhiều câu hỏi nhưng không có câu trả lời hoặc chỉ nói qua loa theo kiểu biết nhưng mà không thèm nói. Diễn đàn là nơi mọi người trao đổi, đóng góp xây dựng. Nếu chỉ có đi hỏi hoặc đọc câu hỏi và câu trả lời của người khác thì lấy đâu những bài viết có chất lượng. Đó là ý kiến của mình.

[Trytolive]

Cái forum này rất hay nhưng có vẻ mọi người không nhiệt tình lắm. Có quá nhiều câu hỏi nhưng không có câu trả lời hoặc chỉ nói qua loa theo kiểu biết nhưng mà không thèm nói. Diễn đàn là nơi mọi người trao đổi, đóng góp xây dựng. Nếu chỉ có đi hỏi hoặc đọc câu hỏi và câu trả lời của người khác thì lấy đâu những bài viết có chất lượng. Đó là ý kiến của mình.

Dù sao thì vẫn tốt hơn các diễn đàn khác.

Mọi người không có thời gian nhiều đâu.

[chungtm2000]

trời đất, thế là bây giờ đây topic này giờ trở thành cái gì rồi nhỉ ?

[HungCTran]

Chao NTSon cách của bạn thấy có vẻ rất hay, câu chữ rất là xuyên suốt, nhưng bạn dùng thuật toán gì để xử lý "Nếu 2 điểm cùng nằm trên 1 đoạn thẳng thì nối 2 điểm đó = 1 cung", xin hết.
HungCTran

[HaiDang]

bài này phải sử dụng vét thôi, giống như dạng bài tìm số tổ hợp àh, đệ qui là ra hết, vấn đề là giới hạn N bao nhiêu........

[smalteagle]

Chao NTSon cách của bạn thấy có vẻ rất hay, câu chữ rất là xuyên suốt, nhưng bạn dùng thuật toán gì để xử lý "Nếu 2 điểm cùng nằm trên 1 đoạn thẳng thì nối 2 điểm đó = 1 cung", xin hết.
HungCTran

Có thể làm đơn giản là duyệt qua tất cả các đoạn thẳng, ta sẽ được 2 đỉnh mút của đoạn thẳng đó, đây cũng là 2 đỉnh trong đồ thị đang xây dựng. Ta thêm 1 cung nối 2 đỉnh này của đồ thị.
To ntson : Thuật toán DFS có thể đảm bảo tìm được tất cả các chu trình của đồ thị được không ?