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  , 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!   Vấn đề mã hóa hàng ngày  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 đề.      quả trứng giống hệt nhau và được vào một tòa nhà có   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   , 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   . Bạn được tặng N k xth 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à   , 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à   . Ví dụ: nếu N = 1 k = 5 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à   ), những quả trứng ném ra không bị vỡ khi rơi xuống đất. targetFloor  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à   . Để 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à   của chúng tôi. targetFloor targetFloor  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.   https://Gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  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   bằng mô-đun   được tích hợp trong Go. targetFlor math/rand  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 đề:   https://Gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  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à   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:  targetFloor  Về cơ bản, chúng tôi đoán rằng Tầng   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: targetFloor  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   đượ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   đơ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. phép tìm kiếm nhị phân chia để trị  Đ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ã!   https://Gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Chúng ta hãy nhìn sâu hơn. Hàm tìm kiếm nhị phân có 4 đối số:    , một mảng các số nguyên, là tòa nhà mà chúng ta đang lặp lại; overArray    , chỉ số dưới cùng của tòa nhà; bottom    , chỉ số tầng trên cùng của tòa nhà; top    , biến giữ   để kiểm tra xem chúng ta có thể tìm thấy nó trong tòa nhà hay không. breakFloor targetFloor  Sau đó, chúng ta lặp lại tòa nhà trong khi   thấp hơn   : 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. bottom top  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ề   , 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. -1  Chúng tôi tính toán phần tử   là tầng giữa   và   và chúng tôi kiểm tra xem   hay không. Nếu đúng như vậy, chúng tôi sẽ trả về   . middlePoint bottom top middlePoint == breakFloor middlePoint  Nếu không, chúng tôi sẽ điều chỉnh   hoặc   cho phù hợp: nếu   lớn hơn   , đ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   có thể thành   . bottom top middlePoint breakFloor top middlePoint — 1  Nếu   nhỏ hơn   , chúng tôi sẽ điều chỉnh   của mình bằng cách đặt là   . middlePoint breakFloor bottom middlePoint+1  Bây giờ để kiểm tra mọi thứ, trong hàm   , chúng ta tạo môi trường như trước và tạo một biến mới có tên   sẽ chứa kết quả của chúng ta. main bsFloor  Để 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ả   và   , được tạo ngẫu nhiên trước đó. bsFloor targetFloor  Độ 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à   . Để 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. O(log(n))  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.  trang!   Ko-fi  Và, như mọi khi, cảm ơn vì đã đọc!   Nicola   Cũng được xuất bản  ở đây

Read My Stories

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

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

About Author

BÌNH LUẬN

chuyên mục

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI

Related Stories

581 Stories To Learn About Non Fiction

61 Stories To Learn About Polotical Philosophy

179 Stories To Learn About Reading

145 Stories To Learn About Book

581 Stories To Learn About Non Fiction

61 Stories To Learn About Polotical Philosophy

179 Stories To Learn About Reading

145 Stories To Learn About Book

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps