Khi bạn phải ném trứng từ sân thượng: Vấn đề viết mã hàng ngày

Vấn đề mã hóa hàng ngày 24

Chào mừng trở lại với một vấn đề khác cần giải quyết! Hôm nay, chúng ta đang giải quyết vấn đề trứng rơi từ trên mái nhà bằng một bài toán rất hay, bao gồm hai giải pháp khả thi: một khá ngây thơ và một giải pháp thông minh hơn. Phần cuối cùng này cũng sẽ cho chúng ta cơ hội nói về một thuật toán khá nổi tiếng.

Như mọi khi, vấn đề của ngày hôm nay được cung cấp bởi bản tin tuyệt vời Vấn đề mã hóa hàng ngày , bạn có thể đăng ký miễn phí để nhận thử thách viết mã hàng ngày. Hãy xem thử và cố gắng giải quyết vấn đề của bạn!

Nói thế đủ rồi; Hãy xem vấn đề!

Vấn đề

Vấn đề này đã được Goldman Sachs hỏi trong một cuộc phỏng vấn xin việc. Hãy xem vấn đề.

Bạn được tặng N quả trứng giống hệt nhau và được vào một tòa nhà có k tầng. Nhiệm vụ của bạn là tìm ra tầng thấp nhất có thể khiến trứng vỡ nếu rơi từ tầng đó. Một khi trứng đã vỡ thì không thể thả được nữa. Nếu một quả trứng vỡ khi rơi từ tầng xth , bạn có thể cho rằng nó cũng sẽ vỡ khi rơi từ bất kỳ tầng nào lớn hơn x .

Viết một thuật toán tìm số lần thả thử tối thiểu, trong trường hợp xấu nhất, để xác định được tầng này.

Ví dụ: nếu N = 1 và k = 5 , chúng ta sẽ cần thử thả quả trứng ở mỗi tầng, bắt đầu từ tầng đầu tiên cho đến khi đạt đến tầng thứ năm, vì vậy giải pháp của chúng ta sẽ là 5 .

Vì vậy, chúng tôi được giao một số quả trứng để ném từ các tầng khác nhau của tòa nhà. Chúng tôi rất tiếc rằng từ một tầng nhất định (mà chúng tôi sẽ gọi là targetFloor ), những quả trứng ném ra không bị vỡ khi rơi xuống đất.

Từ tầng đó đến mọi tầng bên dưới, trứng sẽ không bị vỡ khi ném ra ngoài cửa sổ. Những gì chúng tôi được yêu cầu làm là tìm một phương pháp hiệu quả để tìm targetFloor .

Đúng như dự đoán, chúng ta sẽ thấy hai phương pháp để giải quyết vấn đề này: một phương pháp thực sự đơn giản, sẽ buộc phải giải quyết nhanh chóng nhưng sẽ không hiệu quả. Cách thứ hai sẽ hiệu quả hơn nhiều và sẽ cố gắng giải quyết vấn đề bằng cách thực hiện ít bước nhất.

Nó cũng sẽ cho chúng ta cơ hội nói về một thuật toán thực sự nổi tiếng và quan trọng; một trong những điều bạn cần biết để làm… về cơ bản là bất cứ điều gì!

Thiết lập môi trường

Để bắt đầu, chúng ta cần thiết lập một chút môi trường, cụ thể là tòa nhà và targetFloor . Để tạo tòa nhà, chúng ta chỉ cần tạo một mảng chứa số tầng, từ tầng trệt đến tầng nᵗʰ. Sau đó, chúng tôi tạo một số ngẫu nhiên sẽ là targetFloor của chúng tôi.

Chúng ta sẽ viết lại vấn đề này trong Go: đủ đơn giản để có thể đọc được nhưng đủ phức tạp để hiểu được cơ chế bên trong.

Trước tiên, chúng tôi tạo mảng sẽ đóng vai trò là tòa nhà của mình: chúng tôi có thể cung cấp cho nó kích thước mà chúng tôi muốn, kích thước càng lớn thì tòa nhà sẽ càng cao. Sau đó, chúng tôi tạo một phiên bản của targetFlor bằng mô-đun math/rand được tích hợp trong Go.

Về cơ bản, chúng tôi tạo một số nguyên ngẫu nhiên mới trong khoảng từ 0 đến chiều cao của tòa nhà (… chiều dài của mảng :D) sử dụng làm nguồn thời gian hiện tại.

Giải pháp Brute Force

Tất nhiên, giải pháp đơn giản nhất có thể là ném từng quả trứng ở mỗi tầng ra ngoài, để xem trứng bắt đầu vỡ ở tầng nào. Vì chúng ta có một biến chứa thông tin đó nên người ta có thể chỉ cần thực hiện vòng lặp for để giải quyết vấn đề:

Mặc dù đây là giải pháp đơn giản nhất nhưng tiếc là nó lại rất kém hiệu quả. Hãy tưởng tượng nếu tầng bên phải là tầng trên cùng: người ta phải đập 100.000 quả trứng để giải bài toán: đó sẽ là một quả trứng tráng khổng lồ nhưng khá lãng phí!

Nói chung, giải pháp này có độ phức tạp về thời gian là O(n) vì độ phức tạp của giải pháp tăng tuyến tính với độ phức tạp của bài toán đầu vào. Tuy nhiên, đây không phải là giải pháp hiệu quả nhất mà chúng tôi có thể nghĩ ra.

Một giải pháp hiệu quả

Hãy nghĩ về một giải pháp hiệu quả sau đó. Thay vì đi từng tầng, đập từng quả trứng ở mỗi tầng, chúng ta có thể đoán và dựa trên kết quả của lần đoán đó để điều chỉnh lần đoán tiếp theo.

Dưới đây là một ví dụ: giả sử chúng ta có một tòa nhà 10 tầng và targetFloor là tầng 7 (tất nhiên là chúng ta không biết điều đó). Chúng ta có thể đưa ra những dự đoán sau:

Về cơ bản, chúng tôi đoán rằng Tầng targetFloor là tầng giữa của tòa nhà. Chúng ta ném quả trứng từ đó và kết quả có thể xảy ra là hai:

• quả trứng vỡ nghĩa là chúng ta đang ở trên cao quá. Chúng ta có thể loại bỏ tầng cao hơn tầng này, bao gồm cả tầng này và tiếp tục dự đoán của mình.

• Quả trứng không vỡ nghĩa là chúng ta ở quá thấp hoặc ở đúng tầng. Chúng tôi loại bỏ mọi tầng thấp hơn tầng này, bao gồm và

Vì điều này, giờ đây chúng tôi đưa ra một phỏng đoán có căn cứ khác về tầng giữa hoặc tòa nhà “còn lại” và áp dụng chiến lược tương tự như đã thấy ở trên. Chúng ta có thể tiếp tục phương pháp này cho đến khi chỉ còn lại một tầng.

Nếu bạn tình cờ nhận ra cách tiếp cận này thì bạn hoàn toàn đúng: đây chỉ đơn giản là một phép tìm kiếm nhị phân được áp dụng cho một bài toán “thế giới thực”. Tìm kiếm nhị phân là một thuật toán chia để trị đơn giản và gọn gàng, nghĩa là ở mỗi bước, quy mô của bài toán sẽ giảm đi một nửa cho đến khi chúng ta tìm ra lời giải.

Điều này có nghĩa là thuật toán này nhanh hơn nhiều so với thuật toán trước. Hãy xem mã!

Chúng ta hãy nhìn sâu hơn. Hàm tìm kiếm nhị phân có 4 đối số:

• overArray , một mảng các số nguyên, là tòa nhà mà chúng ta đang lặp lại;

• bottom , chỉ số dưới cùng của tòa nhà;

• top , chỉ số tầng trên cùng của tòa nhà;

• breakFloor , biến giữ targetFloor để kiểm tra xem chúng ta có thể tìm thấy nó trong tòa nhà hay không.

Sau đó, chúng ta lặp lại tòa nhà trong khi bottom thấp hơn top : trong tìm kiếm nhị phân, khi hai đối số vị trí xen kẽ và hoán đổi, điều đó có nghĩa là không tìm thấy phần tử được tìm kiếm.

Do đó, nếu thuật toán kết thúc trong tình huống này, vòng lặp sẽ kết thúc và chúng ta trả về -1 , nghĩa là phần tử mà chúng ta đang tìm kiếm không có trong mảng. Nếu chúng tôi vẫn đang tìm kiếm phần tử, chúng tôi sẽ áp dụng những gì được hiển thị trong hình trên.

Chúng tôi tính toán phần tử middlePoint là tầng giữa bottom và top và chúng tôi kiểm tra xem middlePoint == breakFloor hay không. Nếu đúng như vậy, chúng tôi sẽ trả về middlePoint .

Nếu không, chúng tôi sẽ điều chỉnh bottom hoặc top cho phù hợp: nếu middlePoint lớn hơn breakFloor , điều đó có nghĩa là chúng tôi ở quá cao trên tòa nhà nên chúng tôi hạ thấp dự đoán của mình bằng cách đặt tầng top có thể thành middlePoint — 1 .

Nếu middlePoint nhỏ hơn breakFloor , chúng tôi sẽ điều chỉnh bottom của mình bằng cách đặt là middlePoint+1 .

Bây giờ để kiểm tra mọi thứ, trong hàm main , chúng ta tạo môi trường như trước và tạo một biến mới có tên bsFloor sẽ chứa kết quả của chúng ta.

Để xác nhận rằng thuật toán của chúng tôi đã đưa chúng tôi đến kết quả đúng, chúng tôi in ra cả bsFloor và targetFloor , được tạo ngẫu nhiên trước đó.

Độ phức tạp thời gian

Như chúng tôi đã dự đoán trước đó, thuật toán này nhanh hơn thuật toán tuyến tính rất nhiều. Vì chúng ta chia đôi tòa nhà ở mỗi bước nên chúng ta có thể tìm thấy tầng chính xác trong log₂(n) trong đó n bằng len(building) .

Điều này có nghĩa là độ phức tạp về thời gian của thuật toán này là O(log(n)) . Để cung cấp cho bạn một số so sánh giữa giải pháp tuyến tính và giải pháp cuối cùng này, nếu tòa nhà có 100 tầng, thuật toán tuyến tính trong trường hợp xấu nhất sẽ thực hiện 100 lần lặp, trong khi thuật toán tìm kiếm nhị phân lấy log₂100 = 6,64, tức là 7 lần lặp.

Ngoài ra, cái cuối cùng này ngày càng hiệu quả hơn cái tuyến tính vì tòa nhà càng phát triển thì tìm kiếm nhị phân càng hiệu quả. Đối với một tòa nhà có 1.000.000.000 tầng, tòa nhà tuyến tính mất 1.000.000.000 bước, trong khi tòa nhà nhị phân lấy log₂1.000.000.000 = 29,9, tức là 30 bước. Một cải tiến lớn!

Phần kết luận

Đây chính là nó! Tôi hy vọng bạn thích bài viết này cũng như tôi thấy vui khi cố gắng giải quyết thử thách! Nếu vậy hãy để lại một hoặc hai tràng vỗ tay, đó sẽ là một sự hỗ trợ tuyệt vời! Nếu bạn thích những loại bài viết này và muốn xem thêm, hãy theo dõi trang vì tôi sẽ đăng loại nội dung này bất cứ khi nào có thể.

Cuối cùng, nếu bạn thấy bài viết này thú vị hoặc hữu ích và muốn đóng góp bằng cách mời uống cà phê, vui lòng làm như vậy trên trang của tôi. Ko-fi trang!

Và, như mọi khi, cảm ơn vì đã đọc!

Nicola

Cũng được xuất bản ở đây