Đến nội dung

Hình ảnh

Bài toán qua cầu

- - - - -

  • Please log in to reply
Chủ đề này có 17 trả lời

#1
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viết
Chuyện xảy ra trong thời chiến. :geq

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á :equiv ). 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
queensland

queensland

    Hạ sĩ

  • Thành viên
  • 97 Bài viết
Bài này ngày trước có người đố mình, nói là bài thi tuyển lập trình viên ở một hãng phần mềm tên tuổi, yêu cầu giải trong vòng 10 phút.

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
tnk

tnk

    Thượng sĩ

  • Thành viên
  • 214 Bài viết
bài này là bài thi tuyển của Microsoft.
Em là bông hoa kì diệu
Anh là hòn ngọc sáng trong...

#4
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viết
Đúng đây là bài thi tuyển vào Microsoft nhưng xưa lắm rồi. Mới đây hình như bài này được sử dụng làm đề thi chuyên tin học bảng B. Đối với người lập trình thì tìm thuật giải cho bài này không khó lắm - phần còn lại nhường cho máy tính cày ( nhưng thuật giải tối ưu để còn sử dụng trong bài tổng quát thì khá khó ). Còn các bạn có đầu óc suy luận khá tốt thì hãy tìm phương án bằng cỗ máy hoàn hảo nhất trong tự nhiên - con người. Nhớ là đừng dùng giấy bút nhé. Hãy suy nghĩ....

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 :geq

#5
mathsbeginner

mathsbeginner

    Trung sĩ

  • Founder
  • 120 Bài viết
Anh 1 phút cứ đưa từng người sang một là nhanh nhất.

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 :geq )

#6
queensland

queensland

    Hạ sĩ

  • Thành viên
  • 97 Bài viết

Anh 1 phút cứ đưa từng người sang một là nhanh nhất.

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?

#7
mathsbeginner

mathsbeginner

    Trung sĩ

  • Founder
  • 120 Bài viết
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í. Để 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 :D

Tổng cộng là 19 phút.

#8
queensland

queensland

    Hạ sĩ

  • Thành viên
  • 97 Bài viết

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í.

Đúng rồ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

Chỗ này nên xem lại.

Tổng cộng là 19 phút.

Giải pháp này... chưa tốt.

#9
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viết
Bài học vỡ lòng 1:Người đem đèn quay trở lại là người đi nhanh nhất. :D

#10
vicky361080

vicky361080

    Lính mới

  • Thành viên
  • 8 Bài viết
chi cân 18 phut la xong

#11
NangLuong

NangLuong

    Thành viên Diễn đàn Toán.

  • Hiệp sỹ
  • 2488 Bài viết
Có thể đứng một chỗ rọi đèn cho người khác đi sang được không nhỉ (vì chẳng lẽ đèn chỉ chiếu đúng một chỗ thôi sao :( ). Nếu được như thế, thì anh 1 phút rọi đèn cho 2 ông 10 phút và 5 phút dẫn nhau đi, khi ông 5 phút qua hết thì ông 10 phút mới đi được nửa đường do đó ông 2 phút sẽ bắt đầu đi, khi ông 2 phút đi hết thì ông 10 phút vẫn chưa qua khi đó ông 1 phút sẽ bắt đầu đi. Khi ông 1 phút qua hết thì vẫn phải đợi ông 10 phút 1 phút nữa mới sang tới nơi, Như vậy tổng thời gian mất 10 phút.

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
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viết
Cảm ơn NangLuong đã post một bài học hay.

Có thể đứng một chỗ rọi đèn cho người khác đi sang được không nhỉ

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 :(.

Đáp số là 17 phút. Mọi người hãy cố lên

#13
huylop9h

huylop9h

    Lính mới

  • Thành viên
  • 3 Bài viế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

#14
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viế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

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 :).

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
thánhtoán

thánhtoán

    Toán học là bể khổ

  • Thành viên
  • 195 Bài viết
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

#16
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viết

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

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. :D

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á :D )

#17
munmun

munmun

    Binh nhì

  • Thành viên
  • 13 Bài viết
Bài nài mình nghĩ chỉ cần 1 fút để làm thôi ...
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 :D)

#18
Trytolive

Trytolive

    Trung sĩ

  • Thành viên
  • 196 Bài viết
munmun đã đưa ra phương án chính xác.

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. :P




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh