Bài toán qua cầu
#1
Đã gửi 26-07-2005 - 10:39
Bốn anh lính đang bị địch truy kích phải vượt qua một cây cầu mới được an toàn. Do bị bom tàn phá nên cây cầu chỉ cho phép tối đa 2 người qua cùng một lúc và phải mang theo đèn ( nếu không sẽ rớt vào các hố do bom phá ). Bốn anh lính chỉ có một cây đèn duy nhất. Do tình trạng bị thương nên các anh lính qua cầu mất thời gian lần lượt là 10,5,2,1 phút. Hãy tìm phương án để các anh lính qua cầu an toàn và tốn thời gian ít nhất.
Rút ra bài học gì? Tổng quát hóa bài toán?
#2
Đã gửi 26-07-2005 - 14:16
Nay bạn bảo là bài tập kinh điển mới hiểu chuyện "thi tuyển lập trình viên" chỉ là tô vẽ!
Thanks Trytolive.
Bài viết đã được chỉnh sửa nội dung bởi queensland: 26-07-2005 - 14:17
#3
Đã gửi 26-07-2005 - 21:25
Anh là hòn ngọc sáng trong...
#4
Đã gửi 27-07-2005 - 13:10
Sau khi giúp 4 anh lính qua cầu an toàn biết đâu lại còn được họ thưởng
#5
Đã gửi 27-07-2005 - 14:17
Bài học: sau hơn 1 ngày mới có người đề ra giải pháp giúp các anh lính --> đã muộn (khổ thân mấy anh )
#6
Đã gửi 28-07-2005 - 00:26
Lời giải này chưa rõ ràng lắm. Thời gian tổng cộng hết bao nhiêu phút thế bạn?Anh 1 phút cứ đưa từng người sang một là nhanh nhất.
#7
Đã gửi 28-07-2005 - 00:39
Tổng cộng là 19 phút.
#8
Đã gửi 28-07-2005 - 07:01
Đúng rồi.Khi đã có hai người (hoặc nhiều hơn) ở phía bên kia cầu thì rõ ràng để cho người đi nhanh nhất trong số ấy cầm đèn quay lại là hợp lí.
Chỗ này nên xem lại.Để có người đi nhanh nhất cầm đèn quay lại thì anh 1 phút dẫn từng anh qua là sáng suốt
Giải pháp này... chưa tốt.Tổng cộng là 19 phút.
#9
Đã gửi 28-07-2005 - 11:11
#10
Đã gửi 31-07-2005 - 12:34
#11
Đã gửi 31-07-2005 - 13:09
Bài học là : Yếu tố quyết định mức độ thành công của một nhóm chính là khả năng của người kém nhất và người đứng đầu phải đánh giá đúng khả năng từng người trong nhóm có giải pháp ưu tiên lớn nhất đối với người kém nhất để làm cho công việc của nhóm đạt hiệu quả tối ưu, còn nếu để ông 1 phút dắt lần lượt từng người qua thì lại là đánh giá ông 5 phút và 2 phút ngang hàng với ông 10 phút.
Nếu ai đã từng đọc quyển The Goal của Eliyahu M. Goldratt và Jeff Cox thì chắc sẽ nhận thấy một số quy tằc quen thuộc từ bài thi này.
Thứ nhất, hiệu suất của một tổ chức được chi phối nhiều nhất bởi nguồn lực với công suất thấp nhất. Trong quyển này, ví dụ minh họa được đưa ra là một cuộc đi hướng đạo sinh của một nhóm học sinh xuyên rừng. Đi hướng đạo sinh nghĩa là đi theo hàng định sẵn, có thể thay đổi thứ tự người trong hàng trong quá trình đi nếu thấy hợp lý, nhưng một khi đã thay đổi thì trật tự đó phải được tuân thủ nghiêm ngặt.
Một đoàn hướng đạo sinh gọi là tốt nếu như hàng được giữ ổn định (không bị lạc hay dãn hàng), kết quả thực nghiệm cho thấy, cậu bé chậm chạp nhất sẽ chi phối mức độ đều bước của hàng. Vì không ai đằng sau cậu này có thể vượt cậu theo quy định nên nếu cậu này quá chậm bị bỏ xa, thì cả nhóm đằng sau cậu cũng sẽ rớt lại. Dẫn đến 2 hậu quả, một là các nguồn lực đằng sau nguồn lực "chậm chạp" không được sử dụng hết, hai là đoàn hướng đạo sinh dễ bị lạc. Cụ thể trong trường hợp bài thi trên, bất cứ ông nào trong các ông 1,2,5 phút đi trước nhau đều được, miễn là phải để ông 10 phút đi đầu thì sẽ tiết kiệm thời gian nhất
Thứ hai, muốn khắc phục tình trạng này, cách đơn giản nhất là nhét cậu bé chậm nhất lên đầu, khi đó bảo đảm hàng sẽ không bị dãn mọi người đều phải theo sát cậu chậm nhất. Cụ thể trong bài thi nói trên, ta cho 3 ông nhanh nhất giúp rọi đèn cho ông 10 phút đi.
Nhưng nếu chỉ như thế thì lại ảnh hưởng đến tiến độ của cả đoàn, vì thế để tăng thêm hiệu suất nữa, ta hãy để các cậu bé nhanh giúp đỡ cậu đi đầu (như xách đồ cho cậu ta chẳng hạn), như thế một phần nào độ chênh lệch giữa các nguồn lực sẽ giảm đi. Ở bài thi này, ta để ông 5 phút giúp ông 10 phút và ông 1 phút giúp ông 2 phút.
Như vậy, một tổ chức tốt là không hẳn là một tổ chức có người thật giỏi đứng đầu, mà là một tổ chức trong đó khả năng mọi người tương đồng nhau, và nếu có sự chênh lệch thì người đứng đầu phải giảm thiểu sự chênh lệch đó và phải hiểu cái gì quyết định mức độ hiệu quả của tổ chức.
Hơi ngoài lề, Eliyahu M. Goldratt là một nhà tư vấn quản trị kinh doanh nổi tiếng thế giới, những ý tưởng, lý thuyết quản trị của ông đưa ra bao giờ cũng có xu hướng phá bỏ những nguyên tắc cũ mà theo ông nói là "dựa trên những giả định (trong toán gọi là tiên đề) sai lầm". Lý thuyết liên quan đến vấn đề nói trên do ông phát triển "The theory of constraints" (Lý thuyết về những nguồn lực mang hiệu suất) là một giáo trình được dạy ở nhiều khóa MBA hàng đầu như Haas - Berkeley ... Tôi chỉ mới có dịp đọc qua quyển The Goal của ông và một bài viết của ông trong tác phẩm nhiều tác giả Rethinking the future và nói chung những ý tưởng ông trình bày đều để lại cho tôi một ấn tượng sâu sắc
#12
Đã gửi 01-08-2005 - 12:30
Không, không, không. Dứt khoát là không được rồi vì đèn đâu đủ công suất để chiếu ánh sáng xa như vậy .Có thể đứng một chỗ rọi đèn cho người khác đi sang được không nhỉ
Đáp số là 17 phút. Mọi người hãy cố lên
#13
Đã gửi 05-08-2005 - 16:43
sau đó cho anh 1phút quay lai đón anh 5phút.khi anh 1phut đến nơi thi`anh 2 cũng qua câu` luc' đo' thì mat 2 phút./.
xong 1 thao tác nha
#14
Đã gửi 05-08-2005 - 17:36
Anh 1 phút không thể để anh 2 phút đi một mình được vì không có đèn thì anh 2 phút sẽ rớt xuống hố mất .[COLOR=red]theo em thì cho anh 1phút và 2phút qua đầu
sau đó cho anh 1phút quay lai đón anh 5phút.khi anh 1phut đến nơi thi`anh 2 cũng qua câu` luc' đo' thì mat 2 phút./.
xong 1 thao tác nha
Nếu hai người cùng qua cầu thì thời gian qua cầu sẽ tính bằng số phút của người đi chậm hơn.
Chắc có lẽ mấy anh lính này bị địch bắt mất thôi vì lâu quá không có ai giúp họ.
#15
Đã gửi 08-08-2005 - 09:30
lần đầu ta sẽ để anh 10 phút và anh 1 phút qua cầu vì anh 1 phút phải đi chậm để dìu anh 10 phút nên sẽ nhớ được vị trí của các hố sau khi đi sang anh ta lai quay lại để đưa đèn nên càng nhớ vị trí của hố trên đường (nhớ bằng cách đếm bước chân chẳng hạn) sau đó anh 5 phút và anh 2 phút sẽ cầm đèn đi qua ,khi 2 người kia qua cầu sẽ đánh tin hiệu để anh 1 phút đi qua anh này bây giờ không cần đèn
thế là họ thoát chết bây giờ chạy tiếp thôi
#16
Đã gửi 08-08-2005 - 12:53
Thông cảm cho mấy anh lính. Họ không được thông minh như đa số người tham gia diễn đàn này đâu. Họ không thể nhớ hết tất cả những chỗ có hố trên cầu.thôi phải đưa ra cách cứu các anh lính thôi không thì họ chết mất
lần đầu ta sẽ để anh 10 phút và anh 1 phút qua cầu vì anh 1 phút phải đi chậm để dìu anh 10 phút nên sẽ nhớ được vị trí của các hố sau khi đi sang anh ta lai quay lại để đưa đèn nên càng nhớ vị trí của hố trên đường (nhớ bằng cách đếm bước chân chẳng hạn) sau đó anh 5 phút và anh 2 phút sẽ cầm đèn đi qua ,khi 2 người kia qua cầu sẽ đánh tin hiệu để anh 1 phút đi qua anh này bây giờ không cần đèn
thế là họ thoát chết bây giờ chạy tiếp thôi
Dù sao cũng cám ơn bạn đưa ra một phương án.
PS:lần sau chắc phải post kỹ hơn. Điều kiện của bài toán cần đầy đủ ( nhưng bó tay thôi vì trí tưởng tượng của mình kém quá )
#17
Đã gửi 11-08-2005 - 15:49
Anh 1 fút dẫn anh 2 fút qua cầu mất 2 fút
Anh 1 fút trở về mất 1 fút
Anh 5 fút và anh 10 fút qua cầu mất 10 fút
Anh 2 fút trở về mất 2 fút
Anh 1 fút và anh 2 fút qua cầu mất 2 fút
Tổng cộng :mất 17 fút
Cách giải cũng vào 2 điều:
khi 1 trong 2 anh fải quay về thì đấy là anh đi nhanh hơn
Khi 2 anh cùng đi thì hiệu số thời gian của 2 anh fải là nhỏ nhất , nếu qua nhỏ nhất thì đến cái nhỏ thứ 2 kô dính vào 2 cái nhỏ nhất kia .... VD: 1 fút 2 fút có hiệu số thời gian nhỏ nhất là 1 , nhỏ thứ 2 của hiệu số thời gian chính là 10 fút -5 fút = 5 fút
Cái này chắc có ích trong làm việc tập thể , ngừời cùng trình làm cùng nhau )
#18
Đã gửi 12-08-2005 - 17:56
Bài học số 1 (vỡ lòng): Tiết kiệm thời gian.
---------------> Trong số những người đã qua cầu thì người nào đi nhanh nhất là người đem đèn trở về.
Bài học số 2: Phân bố nhân lực một cách tốt nhất.
---------------> Trong những công việc đòi hỏi chia nhóm và kết quả công việc phụ thuộc vào năng lực của người yếu nhất thì hãy phân bố những người có năng lực gần nhau nhất vào cùng một nhóm.
Bài học số 3: Phân bố công việc hợp lý.
---------------> Bài học này có lẽ mình cũng chưa hiểu thấu đáo và không biết phải diễn đạt như thế nào. Việc phân bố để anh 1,2 qua cầu trước là yếu tố khiến bài toán trở nên khó đoán. Một công việc đơn giản trong một chuỗi các công việc của dự án được giải quyết có thể nâng cao mức độ thành công của toàn dự án. Đây chính là sự tinh túy của nhà quản trị.
Mong các bạn giúp sức trong việc làm rõ các bài học này.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh