[MUSIC CHƠI] 

Andi PENG: Chào mừng bạn đến tuần thứ 3 của phần. Cảm ơn, anh chàng này, tất cả đều đến đến thời điểm này bắt đầu sớm hơn ngày hôm nay. Chúng tôi đã có một tốt đẹp, ít nhóm thân mật ngày hôm nay. Vì vậy, chúng tôi hy vọng sẽ nhận được để kết thúc, có lẽ, sớm, một chút sớm hôm nay. Vì vậy, một cách nhanh chóng, chỉ cần một số thông báo cho chương trình ngày hôm nay. Trước khi chúng tôi bắt đầu, chúng tôi sẽ chỉ đi qua một số vấn đề về hậu cần ngắn gọn, pset câu hỏi, & rút, những điều như thế. Và sau đó chúng tôi sẽ nhảy ngay vào. Chúng tôi sẽ sử dụng một trình gỡ lỗi được gọi là GDB để bắt đầu lật tẩy mã của chúng tôi, mà David giải thích trong bài giảng ngày khác. Chúng tôi sẽ đi qua bốn loại của các loại. Chúng tôi sẽ đi qua chúng khá nhanh chóng kể từ khi họ đang khá tích cực. Nhưng biết rằng tất cả các slide và mã nguồn luôn trực tuyến. Vì vậy, cảm thấy tự do, tại nhìn chăm chú của bạn, để quay trở lại và hãy nhìn vào đó. 

Chúng tôi sẽ đi qua ký hiệu tiệm cận, mà chỉ là một cách ưa thích nói "runtimes," nơi chúng ta có O lớn, mà David giải thích trong bài giảng. Và chúng tôi cũng có Omega, mà là thời gian chạy thấp hơn bị ràng buộc. Và chúng ta sẽ nói nhiều hơn một chút chuyên sâu về cách những người làm việc. Và cuối cùng, chúng ta sẽ đi qua tìm kiếm nhị phân, bởi vì rất nhiều bạn của những người đã có liếc nhìn psets của bạn có thể biết rằng đó là một câu hỏi đó là trong pset của bạn. Vì vậy, tất cả các bạn sẽ được hạnh phúc rằng chúng tôi bao gồm điều này hôm nay. 

Và cuối cùng, mỗi bạn phần thông tin phản hồi, tôi thực sự còn lại khoảng 15 phút ở Cuối cùng chỉ cần đi qua logistics của pset3, bất kỳ câu hỏi, có thể một chút hướng dẫn, nếu bạn muốn, trước khi chúng tôi bắt đầu lập trình. Vì vậy, hãy cố gắng để có được thông qua vật liệu khá nhanh chóng. Và sau đó chúng ta có thể dành thời gian lấy thêm nhiều câu hỏi cho các pset. ĐƯỢC. 

Nhanh chóng, vì vậy chỉ cần một vài thông báo trước khi chúng tôi bắt đầu ngày hôm nay. Trước hết, chào đón để làm nó thông qua hai của psets của bạn. Tôi lấy một cái nhìn tại yeah, chúng ta hãy your-- nhận được một tràng pháo tay cho rằng một. Trên thực tế, tôi đã thực sự, thực sự ấn tượng. Tôi phân loại các pset đầu tiên cho các bạn tuần và bạn kẻ cuối cùng đã không thể tin được. 

Phong cách là ở điểm bên cạnh một vài ý kiến. Hãy chắc chắn rằng bạn luôn luôn cho ý kiến ​​mã của bạn. Nhưng psets của bạn là ở điểm. Và giữ cho nó lên. Và đó là tốt cho các học sinh lớp để thấy rằng các bạn đang đặt trong khi nhiều nỗ lực trong phong cách của bạn và thiết kế của bạn trong mã của bạn mà chúng tôi muốn cho bạn xem. Vì vậy, tôi đi dọc theo lòng biết ơn của tôi cho phần còn lại của các hỗ trợ kỹ thuật. 

Tuy nhiên có một vài câu hỏi & rút Tôi chỉ muốn đi qua đó sẽ làm cho cả cuộc sống của tôi và rất nhiều các khác Hỗ trợ kỹ thuật "sống một chút dễ dàng hơn. Thứ nhất, tôi đã nhận thấy điều này qua week-- có bao nhiêu bạn đã được chạy trên check50 mã của bạn trước khi bạn gửi? ĐƯỢC. Vì vậy, tất cả mọi người nên làm check50, because-- một secret-- chúng tôi thực sự chạy check50 như là một phần của tính đúng đắn của chúng tôi kịch bản để kiểm tra mã của bạn. Vì vậy, nếu mã của bạn được không check50, trong tất cả các khả năng, nó có lẽ sẽ không kiểm tra của chúng tôi là tốt. Đôi khi các bạn có câu trả lời đúng. Giống như, trong tham lam, một số bạn có con số đúng, bạn chỉ cần in ra một số công cụ bổ sung. Và đó là công cụ bổ sung thực sự không kiểm tra, bởi vì máy tính không thực sự biết những gì nó đang tìm kiếm. Và do đó, nó sẽ chỉ chạy qua, thấy rằng sản lượng của bạn không phù hợp với những gì chúng tôi mong đợi câu trả lời được, và đánh dấu nó là sai. 

Và tôi biết rằng đã xảy ra trong một số trường hợp của bạn trong tuần này. Vì vậy, tôi đã đi lại và tự regraded mã của tất cả mọi người. Trong tương lai mặc dù, xin vui lòng, xin vui lòng chắc chắn rằng bạn đang chạy kiểm tra 50 trên mã của bạn. Bởi vì nó là loại đau đớn cho TA phải đi lại và tự chuyển loại mỗi pset duy nhất cho mỗi duy nhất, ví dụ ít bỏ lỡ. Vì vậy, tôi đã không mất đi bất kỳ điểm. Tôi nghĩ rằng tôi có thể cất cánh một hoặc hai cho thiết kế. Trong tương lai, mặc dù nếu bạn đang không check50, điểm sẽ được thực hiện off cho đúng đắn. 

Hơn nữa, psets là do thứ Sáu lúc giữa trưa. Tôi nghĩ rằng có một bảy phút thời gian ân hạn cuối mà chúng tôi cung cấp cho bạn. Mỗi lần Harvard, họ được phép là bảy phút cuối để tất cả mọi thứ. Vì vậy, ở đây tại Yale, chúng tôi sẽ tuân thủ đó là tốt. Nhưng khá nhiều, lúc 12:07, nếu pset của bạn không có trong, nó sẽ được đánh dấu là muộn. Và như vậy trong khi nó được đánh dấu là muộn, TA-- tôi vẫn sẽ được chấm điểm psets của bạn. Vì vậy, bạn vẫn sẽ thấy một lớp xuất hiện. Tuy nhiên, biết rằng ở kết thúc học kỳ, tất cả psets muộn sẽ chỉ được tự động xóa trắng bởi máy tính. 

Chúng tôi làm điều này vì hai lý do. Một, đôi khi chúng ta có được phép, như lời bào chữa của hiệu trưởng, sau này mà tôi không biết về chưa. Vì vậy, chúng tôi muốn chắc chắn rằng chúng tôi đang phân loại tất cả mọi thứ chỉ trong trường hợp, như thế, tôi thiếu cái cớ của một hiệu trưởng. Và thứ hai, giữ trong tâm trí, bạn vẫn có thể thả một pset đó có đầy đủ điểm phạm vi. Và vì vậy chúng tôi muốn đến lớp tất cả các psets bạn chỉ để đảm bảo rằng phạm vi của bạn ở đó và bạn đang cố gắng cho họ. Vì vậy, ngay cả khi nó là muộn, bạn sẽ vẫn có được tín dụng cho phạm vi điểm, tôi nghĩ. 

Vì vậy, đạo đức của câu chuyện là, làm cho bảo psets của bạn đang ở đúng thời gian. Và nếu họ không ở trên thời gian, biết rằng nó không phải là tuyệt vời. Vâng, trước khi đi tiếp, không ai có bất kỳ câu hỏi về phản hồi pset? Yeah. 

Đung Bạn nói chúng tôi có thể thả một trong những psets? 

Andi PENG: Yeah. Vì vậy, có chín psets tổng thể trong quá trình của các học kỳ. Và nếu bạn có phạm vi points-- quá phạm vi chỉ là, khá nhiều, bạn đang cố các vấn đề, là bạn đưa trong thời gian, bạn đang hiển thị mà bạn đã chứng minh bạn đã đọc spec. Đó là khá nhiều phạm vi. Và nếu bạn đang thực hiện phạm vi điểm, chúng tôi có thể thả thấp nhất một ra khỏi phạm vi đầy đủ. Vì vậy, đó là lợi thế của bạn để hoàn thành và cố gắng mỗi pset. 

Ngay cả upload-- nếu không ai trong số họ làm việc, tải lên tất cả. Và sau đó chúng tôi sẽ hy vọng có thể cung cấp cho bạn một số những điểm trở lại. Mát. Bất kỳ câu hỏi khác? Thật tuyệt. 

Thứ hai, văn phòng hours-- một vài ghi chú nhanh chóng về giờ làm việc. Vì vậy, đầu tiên, đi vào đầu tuần. Không ai bao giờ ở giờ làm việc vào thứ Hai. Christabel đến giờ làm việc đêm qua. Yeah, Christabel. Và những gì mà chúng ta đã có tại văn phòng giờ đêm qua, Christabel? 

Đung Chúng tôi đã có kem. 

Andi PENG: Vì vậy, đó là đúng, chúng tôi đã có kem tại văn phòng giờ đêm qua. Trong khi tôi không thể hứa với bạn rằng chúng tôi sẽ có kem vào giờ văn phòng mỗi tuần, những gì tôi có thể hứa với bạn là sẽ có một cách đáng kể sinh viên tốt hơn để tỷ lệ TA. Giống như VN, nó giống như 3-1. Trong khi đó, độ tương phản mà với Thứ năm, bạn đã có khoảng 150 thực sự nhấn mạnh trẻ em và không có kem. Và nó chỉ là không hiệu quả cho bất cứ ai. Vì vậy, đạo đức của câu chuyện là, đến sớm đến giờ làm việc và những điều tốt đẹp sẽ xảy ra. 

Ngoài ra, đến chuẩn bị đặt câu hỏi. Bạn biết? Bất kể những gì hỗ trợ kỹ thuật, tôi nghĩ, đã nói, chúng tôi đã nhận được một vài sinh viên Những người đến hôm qua là, như, 10:50 không đọc spec được như thế giúp tôi, giúp tôi. Thật không may vào thời điểm đó, có không nhiều, chúng tôi có thể làm gì để giúp đỡ bạn. Vì vậy, xin vui lòng đến vào đầu tuần. Hãy đến sớm để giờ hành chính. Hãy chuẩn bị sẵn sàng để đặt câu hỏi. Hãy chắc chắn là bạn, là một sinh viên, là nơi bạn cần phải để các Hỗ trợ kỹ thuật có thể hướng dẫn bạn trên, đó là những gì giờ văn phòng nên được phân bổ cho. 

Thứ hai, vì vậy tôi biết giáo sư muốn chúng ta ngạc nhiên với các bài kiểm tra. Tôi đã có một giáo sư người như, yo, bằng cách này, nhớ giữa kì bạn có vào thứ hai tới. Vâng, tôi đã không biết về giữa kì. Vì vậy, tôi sẽ được rằng TA nhắc nhở bạn rằng tất cả các bài kiểm tra 0-- vì, bạn biết đấy, chúng tôi CS. Bây giờ chúng ta đã mảng làm, bạn sẽ có được tại sao nó đố 0, không phải thi đố 1, eh? ĐƯỢC. Oh, tôi đã nhận một số cười thầm rằng một ngày. ĐƯỢC. 

Vì vậy, đố 0 sẽ October 14 nếu bạn đang ở trong phần thứ hai-thứ tư và 15 tháng 10, nếu bạn đang ở trong phần thứ ba, thứ năm. Điều này không áp dụng cho những người bạn ở Harvard who-- Tôi nghĩ rằng tất cả các bạn sẽ có dùng câu đố của bạn vào ngày 14. 

Vì vậy, yeah, tuần tới, nếu David, trong bài giảng, đi, yeah, vì vậy về điều đó đố tuần tới, tất cả các bạn sẽ không bị sốc vì bạn đã đến phần và bạn biết rằng bạn đố 0 là trong hai tuần. Và chúng tôi sẽ phải xem xét lại phiên họp và tất cả mọi thứ. Vì vậy, không phải lo lắng về sợ hãi cho điều đó. Bất kỳ câu hỏi before-- bất kỳ câu hỏi ở tất cả các vấn đề liên quan đến hậu cần, chấm điểm, giờ làm việc, phần? Yeah. 

Đung Vì vậy, các bài kiểm tra là sẽ có trong bài giảng? 

Andi PENG: Yeah. Vì vậy, các bài kiểm tra, tôi nghĩ, là 60 phút được phân bổ trong đó khe thời gian mà bạn sẽ chỉ mất trong giảng đường. Vì vậy, bạn không cần phải đi vào trên, như, một ngẫu nhiên 07:00. Tất cả đều tốt. Yeah. Mát. 

Được rồi. Vì vậy, chúng ta sẽ giới thiệu một khái niệm để bạn tuần này rằng David có đã loại của đụng vào trong bài giảng trong tuần vừa qua. Nó được gọi là GDB. Và bao nhiêu người bạn, trong khi ở quá trình viết psets của bạn, đã nhận thấy một nút lớn mà nói "Debug" trên đỉnh của IDE của bạn? ĐƯỢC. Vì vậy, bây giờ chúng ta sẽ thực sự có được khai quật những bí ẩn của những nút mà thực sự làm. Và tôi đảm bảo với bạn, nó là một xinh đẹp, điều đẹp đẽ. 

Vì vậy, cho đến bây giờ, tôi nghĩ rằng có được hai điều sinh viên đã thường làm khi gỡ lỗi psets. Một, họ hoặc thêm vào printf () - vì vậy mỗi vài dòng, họ thêm vào một printf () - oh, biến này là gì? Oh, biến này là gì now-- và bạn loại thấy sự tiến triển mã của bạn khi nó chạy. Hoặc phương pháp thứ hai trẻ em làm là rằng họ chỉ viết toàn bộ điều và sau đó đi như thế này ở cuối. Hy vọng rằng nó hoạt động. Tôi đảm bảo với bạn, GDB là tốt hơn hơn cả các phương pháp đó. Yeah. Vì vậy, đây sẽ là người bạn tốt nhất của bạn mới. Bởi vì đó là một điều đẹp trực quan hiển thị cả mã những gì bạn đang làm tại một điểm cụ thể cũng như tất cả những gì của bạn biến được thực hiện, giống như những gì giá trị của họ, ở thời điểm cụ thể. Và bằng cách này, bạn có thể thực sự đặt breakpoint trong mã của bạn. Bạn có thể chạy qua từng dòng. Và GDB sẽ chỉ có cho bạn, hiển thị cho bạn, những gì tất cả các biến của bạn được, họ đang làm gì, những gì đang xảy ra trong các mã. Và trong một cách như vậy, đó là để dễ dàng hơn để xem những gì đang xảy ra thay vì printf-ing hoặc viết xuống báo cáo của bạn. 

Vì vậy, chúng tôi sẽ làm một ví dụ về điều này sau. Vì vậy, điều này có vẻ trừu tượng chút. Không có lo lắng, chúng tôi sẽ làm ví dụ. Và do đó, về cơ bản, ba lớn nhất, được sử dụng nhiều chức năng mà bạn sẽ cần trong GDB Tiếp theo là, Bước qua, và Bước vào nút. Tôi sẽ đi qua ở đó, trên thực tế, ngay bây giờ. 

Vì vậy, tất cả các bạn có thể thấy rằng hay tôi nên phóng to một chút? Ở phía sau, bạn có thể nhìn thấy không? Tôi có nên phóng to? Chỉ một ít thôi? OK, mát mẻ. Hiện chúng tôi đi. ĐƯỢC. 

Vì vậy, tôi có, ở đây, tôi thực hiện cho tham lam. Và trong khi rất nhiều các bạn đã viết tham lam trong khi vòng lặp form-- đó là một cách hoàn toàn chấp nhận làm it-- một cách khác để làm điều đó là để đơn giản chia trong modulo. Bởi vì sau đó bạn có thể có của bạn giá trị và sau đó có còn lại của bạn. Và sau đó bạn có thể chỉ thêm nó tất cả cùng nhau. Liệu các logic của những gì tôi đang làm ở đây có ý nghĩa với tất cả mọi người, trước khi chúng tôi bắt đầu? Loại? Mát. Thật tuyệt. Đó là một mảnh khá sexy mã, tôi sẽ nói. Giống như tôi đã nói, David, trong giảng bài, sau một thời gian, tất cả các bạn sẽ bắt đầu nhìn thấy mã như một cái gì đó là đẹp. Và đôi khi bạn thấy đẹp mã, đó là một cảm giác tuyệt vời như vậy. 

Vì vậy, tuy nhiên, trong khi mã này là rất xinh đẹp, nó không hoạt động đúng cách. Vì vậy, chúng ta hãy chạy check50 về điều này. Kiểm tra 50 20-- oop. 2? Là pset2 đó? Yeah. Oh, pset1. ĐƯỢC. Vì vậy, chúng tôi chạy check50. 

Và như các bạn có thể thấy ở đây, nó rớt một vài trường hợp. Và đối với một số bạn, trong trình làm bộ vấn đề của bạn, bạn giống như, ah, tại sao không phải là nó làm việc. Tại sao nó làm việc cho một số giá trị nhưng không phải cho người khác? Vâng, GDB sẽ giúp con bạn ra lý do tại sao những yếu tố đầu vào không được làm việc. 

ĐƯỢC. Vì vậy, chúng ta hãy xem, một trong những kiểm tra tôi đã thất bại trong check50 là giá trị đầu vào của 0,41. Vì vậy, câu trả lời chính xác mà bạn cần phải nhận là 4. Nhưng thay vì những gì tôi đang in ra là 3-n, đó là không đúng. Vì vậy, chúng ta hãy chỉ chạy này bằng tay, chỉ chắc chắn rằng check50 đang làm việc. Hãy làm ./greedy. Rất tiếc, tôi phải thực hiện tham lam. Hiện chúng tôi đi. Bây giờ ./greedy. 

Còn nợ bao nhiêu? Hãy làm 0,41. Và vâng, chúng ta thấy ở đây mà nó xuất ra 3 khi câu trả lời chính xác, trong thực tế, nên là 4. Vì vậy, hãy nhập GDB và xem cách chúng tôi có thể đi về sửa chữa vấn đề này. 

Vì vậy, bước đầu tiên trong luôn luôn gỡ lỗi mã của bạn là để thiết lập một breakpoint, hoặc một điểm mà tại đó bạn muốn máy tính hoặc các debugger để bắt đầu tìm kiếm tại. Vì vậy, nếu bạn không thực sự biết vấn đề của bạn là, thường, điều điển hình chúng ta muốn làm là để đặt breakpoint của chúng tôi tại chính. Vì vậy, nếu các bạn có thể thấy điều này nút màu đỏ ở ngay đó, vâng, tôi đã được thiết lập một breakpoint cho các chức năng chính. Tôi bấm vào đó. 

Và sau đó tôi có thể đi đến nút gỡ lỗi của tôi. Tôi nhấn nút đó. Hãy để tôi thu nhỏ trở lại nếu tôi có thể. Hiện chúng tôi đi. Vì vậy, chúng ta có, ở đây, một bảng điều khiển ở bên phải. Tôi xin lỗi, kẻ ở phía sau, bạn có thể không thực sự thấy thực sự tốt. Nhưng về cơ bản, tất cả bảng bên phải này đang làm được theo dõi của cả hai được đánh dấu dòng, đó là các dòng mã mà hiện máy tính đang chạy, cũng như tất cả các biến của bạn Xuống đây. 

Vì vậy, bạn đã có xu, tiền xu, n, tất cả các tuyên bố với những thứ khác nhau tại điểm này. Không có lo lắng, bởi vì chúng tôi đã không thực sự khởi tạo chúng cho bất kỳ biến nào. Vì vậy, trong máy tính của bạn, bạn máy tính chỉ là nhìn thấy, oh, 32767 là chức năng được sử dụng cuối cùng mà không gian bộ nhớ trong máy tính của tôi. Và đó là nơi mà xu hiện tại là. Nhưng không một khi bạn chạy các mã nó nên trở thành khởi tạo. 

Vì vậy, hãy đi qua, dòng bởi dòng, những gì đang xảy ra ở đây. ĐƯỢC. Vì vậy, ở đây là ba nút mà tôi vừa giải thích. Bạn có Play, hoặc các chức năng Run, nút, bạn có nút Step hơn, và bạn cũng có nút Step vào. Và về cơ bản, cả ba họ chỉ cần đi qua mã của bạn và làm những việc khác nhau. 

Vì vậy, thông thường, khi bạn gỡ lỗi, chúng tôi không muốn chỉ cần nhấn Play, vì Play sẽ chỉ chạy mã của bạn để kết thúc của nó. Và sau đó bạn sẽ không thực sự biết vấn đề của bạn là trừ khi bạn thiết lập nhiều các điểm ngắt. Nếu bạn thiết lập nhiều các điểm ngắt, nó sẽ chỉ tự động chạy từ một breakpoint, kế tiếp, đến tiếp theo. Nhưng trong trường hợp này, chúng tôi đã chỉ một mà, bởi vì chúng tôi muốn làm việc theo cách của chúng tôi từ trên xuống dưới. Vì vậy, chúng ta sẽ bỏ qua nút ngay bây giờ cho các mục đích của chương trình này. 

Vì vậy, Bước qua chức năng chỉ bước trên mỗi dòng và cho bạn biết những gì máy tính là làm. Bước vào chức năng đi vào các chức năng thực tế đó là trên dòng code của bạn. Vì vậy, ví dụ, như printf (), đó là một chức năng, phải không? Nếu tôi muốn thể chất bước vào printf () chức năng, Tôi thực sự sẽ đi vào chi tiết của mã nơi printf () được viết và xem những gì đang xảy ra ở đó. 

Nhưng thông thường, chúng ta giả định rằng mã mà chúng tôi cung cấp cho bạn các công trình. Chúng tôi giả định printf () đang làm việc. Chúng tôi giả định rằng getInt () đang làm việc. Vì vậy, không cần thiết phải bước vào những chức năng. Nhưng nếu có chức năng mà bạn tự viết mà bạn muốn kiểm tra ra những gì đang xảy ra, bạn sẽ muốn bước vào chức năng đó. 

Vì vậy, ngay bây giờ chúng tôi chỉ cần đi bước qua đoạn mã này. Vì vậy, chúng ta hãy xem. Oh, in ấn, "Oh hai, làm thế nào nhiều thay đổi được nợ? " Chúng tôi không quan tâm. Chúng tôi biết đó là làm việc, vì vậy chúng tôi bước qua nó. 

Vì vậy, n, mà là float của chúng tôi chúng tôi đã initialized-- hoặc declared-- lên ở đầu, chúng tôi hiện bằng đó để GetFloat (). Vì vậy, chúng ta hãy bước qua đó. Và chúng ta thấy tại dưới đây, các chương trình đang thúc giục tôi để nhập vào một giá trị. Vì vậy, hãy nhập giá trị mà chúng ta muốn để kiểm tra ở đây, đó là 0,41. Thật tuyệt. 

Vì vậy bây giờ n-- làm các bạn thấy ở đây, tại bottom-- nó stored-- bởi vì chúng tôi đã không làm tròn được nêu ra, đó là lưu trữ trong khổng lồ như thế này float đó là 0,4099999996, đó là đủ để chúng tôi gần mục đích, ngay bây giờ, 0,41. Và sau đó chúng ta sẽ thấy sau này, khi chúng tôi Tiếp tục đẩy mạnh hơn các chương trình, sau đây, n đã trở thành tròn và xu đã trở thành 41. Thật tuyệt. Vì vậy, chúng ta biết rằng làm việc tròn của chúng tôi. Chúng tôi biết rằng chúng tôi có số lượng chính xác của cent, vì vậy chúng tôi biết rằng đó là không thực sự là vấn đề. 

Vì vậy, chúng tôi tiếp tục đẩy mạnh vào trong chương trình này. Chúng tôi đi đây. Và như vậy sau khi dòng mã này, chúng tôi nên biết bao nhiêu phần tư chúng tôi có. Chúng tôi bước qua. Và bạn nhìn thấy chúng tôi, trên thực tế, có một quý bởi vì chúng tôi đã trừ 25 từ giá trị ban đầu của chúng tôi là 41. Và chúng tôi có 16 trái cho xu của chúng tôi. 

Có phải mọi người hiểu như thế nào chương trình được đẩy mạnh thông qua và tại sao xu đã trở thành 16 và tại sao, bây giờ, tiền xu đã trở thành 1? Được tất cả mọi người sau logic? Mát. Vì vậy, như trong thời điểm này, làm việc của chương trình, phải không? Chúng tôi biết nó đang làm chính xác những gì chúng ta muốn nó. Và chúng tôi đã không thực sự phải in ra, oh, những gì là cent, ở thời điểm này, là những gì đồng tiền vào thời điểm này. 

Chúng tôi tiếp tục đi qua các chương trình. Bước qua. Mát. Chúng tôi đi qua hào. Thật tuyệt. Chúng tôi thấy rằng nó được thực hiện off $ 0,10 cho một đồng xu. Và bây giờ chúng tôi có hai đồng tiền. Đúng rồi. 

Chúng tôi đi qua đồng xu và chúng ta thấy mà chúng tôi đã có trái qua cent. Hmm, đó là lạ. Up ở đây tại chương trình, tôi đã được yêu đã trừ đồng xu của tôi. Có lẽ tôi chỉ là không làm điều đó đúng tuyến. Và than ôi, bạn có thể nhìn thấy ở đây, bởi vì chúng tôi biết rằng chúng ta đang bước thông qua đường dây 32 và 33, đó là nơi mà chương trình chúng tôi không đúng cách có biến chạy. Vì vậy, chúng ta có thể nhìn và thấy, oh, Tôi trừ cent ở đây, nhưng tôi không thực sự thêm vào giá trị đồng tiền của tôi. Tôi thêm để cent. Và tôi không muốn thêm vào cent, tôi muốn thêm vào đồng tiền. Vì vậy, nếu chúng ta thay đổi mà để tiền xu, chúng ta đã có một chương trình làm việc. Tôi có thể chạy check50. Bạn chỉ có thể thoát ra khỏi GDB đúng ở đây và sau đó chạy check50 một lần nữa. Tôi chỉ có thể làm điều này. Tôi phải làm cho tham lam. 0,41. Và ở đây, nó đang in ra câu trả lời đúng. 

Vì vậy, các bạn có thể thấy, GDB là một công cụ thực sự mạnh mẽ khi chúng tôi có rất nhiều mã xảy ra và rất nhiều biến rằng thật khó cho chúng tôi, như một con người, để theo dõi. Các máy tính, trong GDB debugger, có khả năng để theo dõi tất cả mọi thứ. Tôi biết, trong Visionaire, các bạn có thể có thể đã đạt một số lỗi segmentation bởi vì bạn đang chạy ngoài giới hạn của mảng của bạn. Trong ví dụ của Caesar, đó là chính xác những gì tôi đã thực hiện ở đây. 

Vì vậy, tôi quên kiểm tra điều gì sẽ xảy ra nếu tôi không có hai đối số dòng lệnh. Tôi chỉ không đưa vào tờ séc đó. Và do đó, nếu tôi chạy Debug-- tôi đặt breakpoint của tôi sang phải ở đó. Tôi chạy Debug. 

ĐƯỢC. Yeah. Vì vậy, trên thực tế, GDB đã được yêu đã nói với tôi có là một lỗi phân khúc đó. Tôi không biết những gì đang xảy ra đúng đó, nhưng khi tôi chạy nó, nó đã làm việc. Khi bạn chạy dòng mã thông qua và GDB có thể chỉ đột nhiên bỏ về bạn, đi lên và nhìn những gì các lỗi màu đỏ là. Nó sẽ cho bạn biết, hey, bạn có một lỗi phân khúc, có nghĩa là bạn cố gắng truy cập không gian trong một mảng không tồn tại. Yeah. 

Vì vậy, trong các vấn đề tiếp theo thiết lập trong tuần này, các bạn có lẽ sẽ có rất nhiều biến nổi xung quanh. Bạn sẽ không chắc chắn những gì Chúng nghĩa là tại một thời điểm nhất định. Vì vậy, GDB thực sự sẽ giúp bạn trong việc tìm hiểu những gì họ đang tất cả bằng và có thể thấy rằng thị. Có ai nhầm lẫn về cách bất kỳ điều đó đã làm việc? Mát. Được rồi. Vì vậy, sau đó, chúng tôi sẽ nhảy ngay vào bốn khác nhau loại của các loại cho tuần này. Làm thế nào nhiều bạn, đầu tiên hết, trước khi chúng ta bắt đầu, đã đọc toàn bộ spec cho pset3? ĐƯỢC. Tôi tự hào về các bạn. Điều đó giống như một nửa của lớp, mà là nhiều hơn đáng kể so với thời gian trước. 

Vì vậy, đó là tuyệt vời, bởi vì khi chúng ta nói về nội dung trong lecture-- hoặc xin lỗi, trong section-- tôi thích để liên quan rất nhiều mà trở lại với những gì các pset là và làm thế nào bạn muốn thực hiện điều đó trong pset của bạn. Vì vậy, nếu bạn đến gặp đọc spec, nó sẽ thấy được dễ dàng hơn nhiều cho bạn để hiểu những gì tôi đang nói về khi tôi nói, oh hey, điều này có thể là một thực sự nơi tốt để thực hiện việc này. Vì vậy, những người bạn của những người đã đọc spec biết rằng, như là một phần của pset của bạn, bạn sẽ phải viết một kiểu loại. Vì vậy, điều này có thể rất hữu ích cho rất nhiều bạn ngày hôm nay. 

Vì vậy, chúng tôi sẽ bắt đầu với, về cơ bản, kiểu đơn giản nhất các loại, các loại lựa chọn. Các thuật toán điển hình cho làm thế nào chúng tôi đi về điều này is-- David đã đi qua các tất cả trong bài giảng, vì vậy tôi sẽ nhanh chóng di chuyển dọc here-- cơ bản là, bạn có một mảng các giá trị. Và sau đó bạn tìm thấy giá trị nhỏ nhất không được phân loại và bạn trao đổi các giá trị đó với giá trị chưa phân loại đầu tiên. Và sau đó bạn chỉ cần giữ lặp đi lặp lại với phần còn lại của danh sách của bạn. 

Và đây là một lời giải thích trực quan làm thế nào mà có thể làm việc. Vì vậy, ví dụ, nếu chúng ta bắt đầu với một mảng của năm yếu tố, chỉ số 0-4, có 3, 5, 2, 6, và 4 giá trị đặt trong array-- vậy ngay bây giờ, chúng tôi chỉ cần đi để giả rằng họ đang tất cả được phân loại bởi vì chúng tôi đã không kiểm tra khác. 

Vậy làm thế nào một loại lựa chọn sẽ công việc là nó sẽ đầu tiên chạy qua toàn bộ của mảng được phân loại. Nó sẽ nhận ra giá trị nhỏ nhất. Trong trường hợp này, 3, bên phải bây giờ, là nhỏ nhất. Nó được cho 5. Nope, 5 là không lớn than-- hoặc xin lỗi, không phải là ít than-- 3. Vì vậy, giá trị tối thiểu vẫn là 3. Và sau đó bạn sẽ có được đến 2. Các máy tính thấy, oh, 2 là ít hơn 3. 2 bây giờ phải là giá trị tối thiểu. Và do đó, 2 giao dịch hoán đổi với giá trị đầu tiên. 

Vì vậy, một đường chuyền sau đó, chúng tôi thực sự thấy rằng 2 và 3 được đổi chỗ. Và chúng tôi chỉ cần đi để tiếp tục làm này một lần nữa với phần còn lại của mảng. Vì vậy, chúng ta sẽ chỉ cần chạy qua bốn chỉ số cuối cùng của mảng. Chúng ta sẽ thấy rằng 3 là giá trị nhỏ nhất tiếp theo. Vì vậy, chúng tôi đang đi để trao đổi điều đó với 4. Và sau đó, chúng tôi chỉ cần đi để giữ chạy qua cho đến khi, cuối cùng, bạn để có được một mảng được sắp xếp trong đó 2, 3, 4, 5, 6 trong số tất cả được sắp xếp. Có tất cả mọi người hiểu được logic làm thế nào một loại lựa chọn công trình? 

Bạn chỉ có một số loại của một giá trị tối thiểu. Bạn đang theo dõi của những gì được. Và bất cứ khi nào bạn tìm thấy nó, bạn thay đổi nó với giá trị đầu tiên trong array-- hoặc, không phải là value-- đầu tiên giá trị tiếp theo trong mảng. Mát. 

Vì vậy, như các bạn loại thấy từ một cái nhìn ngắn gọn, chúng ta sẽ giả này ra. Vì vậy, nếu các bạn ở phía sau muốn tạo thành một nhóm, tất cả mọi người ở một bảng có thể hình thành một đối tác ít, tôi sẽ để cung cấp cho các bạn giống như ba phút chỉ nói chuyện qua logic, tiếng Anh, làm thế nào chúng ta có thể có thể thực hiện giả để viết một loại lựa chọn. Và có kẹo. Hãy đến và nhận được kẹo. Nếu bạn đang ở phía sau và bạn muốn kẹo, tôi có thể ném kẹo vào bạn. Trên thực tế, làm you-- mát. Ồ xin lỗi. ĐƯỢC. 

Vì vậy, nếu chúng ta muốn, như một lớp học, ghi giả để làm thế nào người ta có thể tiếp cận vấn đề này, chỉ cảm thấy miễn phí. Tôi sẽ chỉ đi xung quanh và, theo thứ tự, yêu cầu các nhóm cho các dòng tiếp theo của những gì chúng ta nên làm. Vì vậy, nếu các bạn muốn bắt đầu tắt, điều đầu tiên là những gì Phải làm gì khi bạn đang cố gắng để thực hiện một cách để giải quyết chương trình này để chọn lọc sắp xếp một danh sách? Hãy chỉ giả sử chúng ta có một mảng, tất cả phải không? 

Đung Bạn muốn tạo ra một số loại [Không nghe thấy] mà bạn chạy qua toàn bộ mảng của bạn. 

Andi PENG: Đúng vậy. Vì vậy, bạn sẽ muốn lặp qua mọi không gian, phải không? Vì vậy, tuyệt vời. Nếu các bạn muốn để cho tôi tiếp theo line-- yeah, ở phía sau. 

Đung Kiểm tra xem chúng tất cả cho nhỏ nhất. 

Andi PENG: Hiện chúng tôi đi. Vì vậy, chúng tôi muốn đi qua và kiểm tra xem những gì giá trị tối thiểu là, phải không? Tôi sẽ viết tắt đó để "min". Những gì các bạn muốn làm sau khi bạn đã tìm thấy những giá trị tối thiểu? 

Đung [Không nghe thấy] Andi PENG: Vì vậy, bạn sẽ muốn chuyển đổi nó với sự đầu tiên của mảng đó, bên phải? Đó là khởi đầu, tôi sẽ nói. Được rồi. Vì vậy, bây giờ mà bạn đã đổi chỗ đầu tiên một, những gì bạn muốn làm gì sau đó? Vì vậy, bây giờ chúng ta biết rằng một trong những điều này ở đây phải có giá trị nhỏ nhất, phải không? Sau đó, bạn có một phần còn lại bổ sung của mảng đó là không được phân loại. Vì vậy, những gì bạn muốn làm ở đây, nếu bạn kẻ muốn cung cấp cho tôi những dòng tiếp theo? Đung Vì vậy, sau đó bạn muốn lặp thông qua phần còn lại của mảng. Andi PENG: Yeah. Và vì vậy những gì không lặp lại thông qua loại hàm ý chúng ta có lẽ sẽ cần? Loại of-- gì 

Đung Oh, một biến? Andi PENG: Có thể một vòng lặp for, phải không? Vì vậy, chúng ta có lẽ sẽ muốn để lặp through-- tuyệt vời. Và sau đó bạn sẽ quay trở lại và có thể kiểm tra tối thiểu một lần nữa, bên phải? Và bạn sẽ tiếp tục lặp này, vì các vòng chỉ cần đi để tiếp tục chạy, phải không? 

Vì vậy, các bạn có thể thấy, chúng tôi chỉ có một mã giả nói chung làm thế nào chúng ta muốn chương trình này để xem xét. Iterate này đây, những gì chúng tôi làm thường cần phải viết trong mã của chúng tôi nếu chúng ta muốn lặp thông qua một mảng, kiểu cấu trúc? Tôi nghĩ Christabel đã nói điều này trước. 

Đung A cho vòng lặp. 

Andi PENG: A cho vòng lặp? Đúng như vậy. Vì vậy, đây có lẽ là sẽ là một vòng lặp for. Kiểm tra ở đây sẽ có nghĩa là gì? Thông thường, nếu bạn muốn kiểm tra nếu một cái gì đó là một cái gì đó else-- 

Đung Nếu. 

Andi PENG: An nếu, phải không? Và sau đó hoán đổi ở đây, chúng tôi sẽ đi qua sau, vì David đã đi qua mà trong bài giảng là tốt. Và sau đó lặp thứ hai implies-- 

Đung Một vòng lặp for. 

Andi PENG: --another cho vòng lặp, chính xác. Vì vậy, nếu chúng tôi đang tìm kiếm lúc này một cách chính xác, chúng tôi có thể thấy rằng chúng tôi có thể sẽ cần một vòng lặp lồng nhau cho với một câu lệnh điều kiện trong đó và sau đó một mảnh thực tế của mã đó là đi để trao đổi các giá trị. Vì vậy, tôi đã chỉ nói chung bằng văn bản một mã giả ở đây. Và sau đó chúng tôi đang thực sự đi thể chất, như một lớp, cố gắng thực hiện điều này hôm nay. Chúng ta hãy quay trở lại vào IDE này. 

Uh-oh. Tại sao là not-- có nó được. ĐƯỢC. Xin lỗi, chúng tôi cố gắng để phóng to một chút hơn. Hiện chúng tôi đi. Tất cả tôi đang làm ở đây là tôi đã tạo ra một chương trình gọi là "lựa chọn / sort.c." Tôi đã tạo ra một mảng của chín giá trị, 4, 8, 2, 1, 6, 9, 7, 5, 3. Hiện nay, như bạn có thể thấy, họ không có thứ tự. n là có được những con số đó cho bạn biết số lượng các giá trị bạn có trong mảng của bạn. Trong trường hợp này, chúng ta có chín giá trị. Và tôi đã chỉ có một vòng lặp ở đây mà in ra mảng phân loại. 

Và cuối cùng, tôi cũng đã có một cho vòng lặp mà chỉ cần in nó ra một lần nữa. Vì vậy, về mặt lý thuyết, nếu chương trình này đang làm việc một cách chính xác, lúc kết thúc, bạn sẽ thấy một vòng lặp in trong đó 1, 2, 3, 4, 5, 6, 7, 8, 9 là tất cả một cách chính xác theo thứ tự. 

Vì vậy, chúng tôi đã có giả của chúng tôi ở đây. Có ai muốn đối với: Tôi chỉ sẽ đi hỏi cho volunteers-- cho tôi biết chính xác những gì để gõ nếu chúng ta muốn, đầu tiên, chỉ cần lặp thông qua vào đầu mảng này? Các dòng mã tôi là gì có lẽ sẽ cần phải ở đây? 

Đung [Không nghe thấy] 

Andi PENG: Yeah, cảm thấy miễn phí đối với: xin lỗi, bạn không phải đứng cảm giác up-- miễn phí để nâng cao tiếng nói của bạn một chút. 

Đung Đối int i bằng 0-- 

Andi PENG: Yeah, tốt. 

Đung i nhỏ hơn chiều dài mảng. 

Andi PENG: Vì vậy, hãy tâm ở đây, bởi vì chúng tôi không có một chức năng mà cho chúng ta biết độ dài của một mảng, chúng tôi đã có một giá trị mà các cửa hàng đó. Bên phải? Một điều cần lưu trong mind-- trong một mảng chín các giá trị, các chỉ số là gì? Hãy chỉ nói rằng mảng này là 0-3. Bạn thấy rằng cuối cùng chỉ số thực sự là 3. Nó không phải 4, mặc dù có bốn giá trị trong mảng. 

Vì vậy, ở đây, chúng ta phải rất cẩn thận của những điều kiện của chúng tôi cho chiều dài là có được. 

Đung Nó sẽ không thể n trừ đi 1? Andi PENG: Nó sẽ n trừ đi 1, chính xác. Liệu đó có ý nghĩa, tại sao nó n trừ đi 1, tất cả mọi người? Đó là bởi vì mảng là zero-lập chỉ mục. Họ bắt đầu từ 0 và chạy lên n trừ đi 1. Vâng, đó là một chút khéo léo. ĐƯỢC. Và sau đó-- Đung Isnt'1 đó đã đưa về chăm sóc, mặc dù bởi chỉ cần không nói "ít hơn hoặc bằng "và chỉ nói" ít hơn? " 

Andi PENG: Đó là một Câu hỏi thực sự tốt. Vì vậy, có. Nhưng cũng có thể, cách mà chúng tôi thực hiện quyền kiểm tra, bạn cần so sánh hai giá trị. Vì vậy, bạn thực sự muốn rời khỏi "để" trống rỗng. Bởi vì nếu bạn so sánh thế này, bạn sẽ không có bất cứ điều gì sau khi nó để so sánh, phải không? Yeah. Vì vậy, i ++. Hãy thêm dấu ngoặc của chúng tôi ở. Lỗi chính. Thật tuyệt. Vì vậy, chúng tôi có đầu của vòng ngoài của chúng tôi. Vì vậy, bây giờ chúng ta có thể muốn tạo ra một biến để giữ theo dõi các giá trị nhỏ nhất, phải không? Có ai muốn để cho tôi dòng mã mà sẽ làm điều đó? Những gì chúng ta cần, nếu chúng ta đang đi muốn để lưu trữ một cái gì đó? 

Bên phải. Có lẽ một tên tốt hơn cho rằng sẽ be-- "temp" hoàn toàn works-- có lẽ đúng hơn là một tên sẽ được, nếu chúng ta muốn value-- nhỏ nhất 

Đung Min. Andi PENG: min, có chúng tôi đi. min sẽ là tốt. Và đây, những gì chúng tôi muốn khởi tạo nó? Đây là một chút khéo léo. Bởi vì ngay bây giờ tại bắt đầu của mảng này, bạn đã không nhìn bất cứ điều gì, phải không? Vì vậy, những gì, tự động, nếu chúng tôi chỉ là trên i bằng 0, những gì chúng ta muốn khởi tạo giá trị tối thiểu đầu tiên của chúng tôi đến? Đung i. Andi PENG: i, chính xác. Christabel, tại sao chúng ta muốn để khởi tạo nó i? 

Đung Bởi vì, tốt, chúng tôi đang bắt đầu với 0. Vì vậy, bởi vì chúng tôi không có gì để so sánh nó đến, tối thiểu sẽ kết thúc được 0. 

Andi PENG: Chính xác. Vì vậy, cô ấy hoàn toàn đúng. Bởi vì chúng tôi đã không thực sự nhìn bất cứ điều gì chưa, chúng ta không biết những gì giá trị nhỏ nhất của chúng tôi là. Chúng tôi muốn chỉ cần khởi tạo nó i, trong đó, hiện nay, là phải ở đây. Và khi chúng ta tiếp tục di chuyển xuống mảng này, chúng ta sẽ thấy rằng, với mỗi thêm pass, i increments. Và vì vậy tại thời điểm đó, i có lẽ sẽ muốn là tối thiểu, bởi vì nó sẽ là bất cứ điều gì là sự khởi đầu của mảng được phân loại. Mát. 

Vì vậy, bây giờ chúng tôi muốn thêm một vòng lặp ở đây đó là đi lặp lại qua các không được phân loại, hoặc phần còn lại của mảng này. Có ai muốn để cho tôi một dòng mã mà sẽ làm điều đó? Hint-- những gì chúng ta cần phải xuống đây? Điều gì đang xảy đến trong này cho vòng lặp? Yeah. Đung Vì vậy, chúng tôi muốn có một số nguyên khác nhau, bởi vì chúng tôi đang chạy qua phần còn lại của mảng thay vì i, như vậy có lẽ j. 

Andi PENG: Yeah, j âm thanh tốt với tôi. Bình đẳng? 

Đung Vì vậy, sẽ là i + 1, vì bạn đang bắt đầu từ giá trị tiếp theo. Và sau đó đến end-- vậy một lần nữa, j là ít hơn n trừ đi 1, và sau đó j ++. Andi PENG: Great. 

Và sau đó ở đây, chúng ta sẽ muốn để kiểm tra xem tình trạng của chúng tôi được đáp ứng, bên phải? Bởi vì bạn muốn thay đổi giá trị tối thiểu nếu nó thực sự nhỏ hơn so với những gì bạn đang so sánh nó, phải không? Vì vậy, những gì chúng ta sẽ muốn ở đây? Kiểm tra để xem. Loại gì của câu Chúng ta có lẽ sẽ ti muốn sử dụng nếu chúng tôi muốn kiểm tra một cái gì đó? 

Đung Một câu lệnh if. 

Andi PENG: Một câu lệnh if. Vì vậy if-- và những gì sẽ được với điều kiện là chúng tôi muốn bên trong của câu lệnh if của chúng tôi? 

Đung Nếu giá trị của j là ít hơn giá trị của i-- 

Andi PENG: Chính xác. Vì vậy if-- nên mảng này được gọi là "mảng". Thật tuyệt. Vì vậy, nếu array-- đó là cái gì? Nói lại đi. 

Đung Nếu mảng j là ít hơn mảng-i, sau đó chúng tôi sẽ thay đổi min. Vì vậy, các min sẽ là j. 

Andi PENG: Liệu đó có ý nghĩa? ĐƯỢC. Và bây giờ xuống đây, chúng tôi thực sự muốn thực hiện việc hoán đổi, phải không? Vì vậy, nhớ lại, trong bài giảng, rằng David, khi ông đã cố gắng để trao đổi những gì đã the-- nước cam it-- và milk-- 

Đung Đó là gộp. 

Andi PENG: Yeah, đó là loại gộp. Nhưng đó là một khá tốt Khái niệm thời gian chứng minh. Vì vậy, suy nghĩ về giá trị của bạn ở đây. Bạn đã có một mảng min, một mảng của tôi, hoặc bất cứ điều gì chúng tôi đang cố gắng để trao đổi tại đây. Và có lẽ bạn không thể đổ chúng vào nhau cùng một lúc, phải không? Vì vậy, những gì chúng ta đi cần phải tạo ở đây để trao đổi các giá trị chính xác? 

Đung A biến tạm thời. 

Andi PENG: Một biến tạm thời. Vì vậy, chúng ta hãy làm int temp. Hãy xem, đây sẽ là một tốt hơn thời gian đối với: whoa, đó là cái gì? ĐƯỢC. Vì vậy, đây sẽ là một tốt hơn thời gian để đặt tên cho "temp." biến Vì vậy, chúng ta hãy làm int temp. Chúng ta sẽ đến set temp bằng ở đây? Đung Min? Andi PENG: Đó là một chút khéo léo. Nó thực sự không quan trọng cuối cùng. Nó không có vấn đề gì thứ tự mà bạn chọn để trao đổi trong miễn là bạn đang làm cho chắc chắn rằng bạn đang theo dõi những gì bạn đang trao đổi. 

Đung Nó có thể là mảng-i. 

Andi PENG: Vâng, chúng ta hãy làm mảng-i. Và sau đó các dòng tiếp theo là những gì mã chúng tôi muốn có ở đây? Đung mảng-i bằng mảng j. Andi PENG: Và cuối cùng? Đung mảng j bằng mảng-i. Đung Hoặc mảng j equals mảng temp-- hay, temp. 

Andi PENG: OK. Vì vậy, chúng ta hãy chạy này và xem nếu nó sẽ làm việc. Ở đâu mà ra? Oh, đó là một vấn đề. Thấy, trên đường 40, chúng tôi cố gắng sử dụng mảng j? Nhưng nơi nào j chỉ tồn tại trong? 

Đung Trong vòng lặp for. Andi PENG: Đúng vậy. Vì vậy, những gì chúng ta sẽ cần phải làm gì? 

Đung Xác định nó bên ngoài the-- Đung Vâng, tôi đoán bạn có sử dụng một lệnh if khác, phải không? Vì vậy, như thế nào, nếu minimum-- tất cả các quyền, hãy để tôi nghĩ. 

Andi PENG: Guys, thử để có một cái nhìn Hãy thấy, những gì một cái gì đó chúng ta có thể làm ở đây? 

Đung OK. Vì vậy, nếu tối thiểu không bằng j-- vì vậy nếu tối thiểu là vẫn i-- sau đó chúng ta sẽ không phải trao đổi. 

Andi PENG: Liệu rằng bằng i? Làm những gì bạn muốn nói ở đây? 

Đung Hoặc yeah, nếu tối thiểu nào tôi không bằng nhau, yeah. Andi PENG: OK. Vâng mà giải quyết, loại, vấn đề của chúng tôi. Nhưng điều đó vẫn không giải quyết được Vấn đề của những gì sẽ xảy ra nếu j-- từ j không tồn tại bên ngoài của nó, những gì Bạn chúng tôi muốn làm gì với nó? Khai báo bên ngoài? Hãy thử chạy này. Uh-oh. Loại của chúng tôi không phải làm việc. 

Như bạn có thể thấy, ban đầu của chúng tôi mảng có những giá trị. Và sau đó nó cần phải có được trong 1, 2, 3, 4, 5, 6, 7, 8, 9. Nó không hoạt động. Ahh. Chúng ta làm gì? Đung Debug. Andi PENG: Được rồi, chúng ta có thể cố gắng đó. Chúng tôi có thể gỡ lỗi. Thu nhỏ một chút. Hãy đặt breakpoint của chúng tôi. Hãy đi like-- OK. 

Vì vậy, bởi vì chúng ta đã biết rằng những dòng này, 15 đến 22, được working-- bởi vì tất cả tôi đang làm là chỉ lặp lại thông qua và printing-- Tôi có thể đi trước và bỏ qua. Hãy bắt đầu tại dòng 25. Oop, hãy để tôi bỏ nó đi. 

Đung vậy của breakpoint nơi gỡ lỗi khởi động? Andi PENG: Hoặc dừng. Đung Hoặc dừng. Andi PENG: Yeah. Bạn có thể thiết lập nhiều các điểm ngắt và nó chỉ có thể nhảy từ một đến khác. Nhưng trong trường hợp này, chúng ta không biết nơi mà các lỗi đang xảy ra. Vì vậy, chúng tôi chỉ muốn bắt đầu từ trên xuống dưới. Yep. ĐƯỢC. 

Vì vậy, dòng này ở đây, chúng ta có thể bước vào. Bạn có thể thấy ở đây, chúng tôi đã có một mảng. Đó là những giá trị đó là trong mảng. Bạn có thấy rằng, làm thế nào chỉ số 0, nó tương ứng với value-- oh, Tôi sẽ cố gắng để phóng to. Xin lỗi, nó thực sự khó để see-- ở mảng chỉ số 0, chúng ta có một giá trị của 4 và sau đó vân vân và vân vân. Chúng tôi có các biến địa phương của chúng tôi. Ngay bây giờ tôi là bằng 0, mà chúng tôi muốn nó được. 

Và như vậy chúng ta hãy giữ bước qua. Tối thiểu của chúng tôi là bằng 0, mà chúng tôi cũng muốn nó được. Và sau đó chúng tôi nhập thứ hai của chúng tôi cho vòng lặp, nếu mảng-j là ít hơn so với mảng-i, mà nó không được. Vì vậy, bạn đã thấy như thế nào mà bỏ qua điều đó? 

Đung Vì vậy nên nếu tối thiểu, tất cả that-- không nên mà được bên trong những người đầu tiên cho vòng lặp? Andi PENG: Không, bởi vì bạn vẫn còn muốn thử nghiệm. Bạn muốn làm một so sánh mỗi thời gian, ngay cả sau khi bạn chạy qua nó. Bạn không chỉ muốn làm điều đó trên pass-thông qua đầu tiên. Bạn muốn làm điều đó với từng vượt qua thêm một lần nữa. Vì vậy, bạn muốn kiểm tra tình trạng của bạn bên trong. Vì vậy, chúng tôi chỉ cần đi để tiếp tục chạy qua đây. Tôi sẽ cung cấp cho các bạn một gợi ý. Nó đã làm với thực tế là khi bạn đang kiểm tra điều kiện của bạn, bạn không kiểm tra cho các chỉ số chính xác. Vì vậy, ngay bây giờ bạn đang kiểm tra mảng chỉ số j là ít hơn so với mảng chỉ số của tôi. Nhưng những gì bạn đang làm tại đầu cho vòng lặp? Bạn không phải cài đặt j bằng i? 

Yeah, vì vậy chúng tôi có thể thực sự thoát khỏi các trình gỡ lỗi ở đây. Vì vậy, chúng ta hãy nhìn vào mã giả của chúng tôi. For-- chúng ta sẽ bắt đầu từ i bằng 0. Chúng ta sẽ đi đến n trừ đi 1. Hãy kiểm tra, chúng tôi đã có quyền đó? Đúng, đó là đúng. 

Vì vậy, sau đó bên trong ở đây, chúng tôi sẽ tạo ra một giá trị tối thiểu và thiết lập đó bằng i. Chúng tôi đã làm điều đó? Yep, đã làm điều đó. Bây giờ chúng tôi ở bên trong vòng lặp, chúng tôi sẽ làm j bằng i cho n trừ đi 1. Chúng tôi đã làm điều đó? Thật vậy, chúng tôi đã làm điều đó. 

Vì vậy, tuy nhiên, những gì chúng ta đang so sánh ở đây? 

Đung j + 1. Andi PENG: Chính xác. Và sau đó bạn sẽ muốn thiết lập tối thiểu của bạn bằng j + 1 là tốt. Vì vậy, tôi đã đi qua mà thực sự nhanh chóng. Do you guys hiểu lý do tại sao nó là j + 1? ĐƯỢC. 

Vì vậy, trong mảng của bạn, trong qua đầu tiên của bạn thông qua, bạn cho vòng lặp, cho int i bằng 0, chúng ta hãy chỉ giả định này đã không được thay đổi nào. Chúng tôi có một mảng, hoàn toàn, chỉ bốn yếu tố không được phân loại, phải không? Vì vậy, chúng ta muốn khởi tạo i bằng 0. Và tôi sẽ chỉ chạy qua vòng lặp này. Và như vậy trong các lần trước, chúng ta đang đi để khởi tạo một biến gọi là "min" mà còn bằng i, vì chúng ta không có một giá trị tối thiểu. Vì vậy, đó là hiện bằng 0 là tốt. Và sau đó chúng ta sẽ đi qua. Và chúng tôi muốn lặp lại. Bây giờ chúng ta đã tìm thấy những gì tối thiểu của chúng tôi là, chúng tôi muốn lặp qua một lần nữa để xem nếu nó so sánh, phải không? Vì vậy, j, ở đây, được đi để tôi bình đẳng, mà là 0. Và sau đó nếu mảng j cộng với tôi, đó là một trong đó là sau hơn, như ít hơn những gì tối thiểu hiện tại của bạn giá trị, bạn muốn trao đổi. 

Vì vậy, chúng ta hãy chỉ nói rằng chúng ta đã có, như, 2, 5, 1, 8. Ngay bây giờ, tôi là bằng 0 và j là bằng 0. Và đó là giá trị nhỏ nhất của chúng tôi. Nếu mảng j cộng i-- vì vậy nếu một trong các đó là sau khi một trong chúng tôi đang tìm kiếm tại là lớn hơn so với cái trước đó, nó sẽ trở thành tối thiểu. 

Vì vậy, ở đây chúng tôi thấy rằng 5 không phải là ít hơn thế. Vì vậy, nó sẽ không là 5. Chúng tôi thấy rằng 1 là ít hơn 2, phải không? Vì vậy, bây giờ chúng ta biết rằng tối thiểu của chúng tôi là sẽ có giá trị chỉ số 0, 1, 2. Yeah? Và sau đó khi bạn nhận được xuống đây, bạn có thể trao đổi các giá trị đúng. 

Vì vậy, khi các bạn đã chỉ có j trước khi, bạn không chỉ nhìn vào một trong các sau đó. Bạn đang tìm kiếm tại giá trị như nhau, trong đó là lý do tại sao nó chỉ là không làm gì cả. Điều đó có ý nghĩa với tất cả mọi người, tại sao chúng ta cần thiết mà cộng 1 có? ĐƯỢC. Bây giờ chúng ta hãy chỉ cần chạy qua nó để làm cho chắc chắn các phần còn lại của mã này là chính xác. Tại sao điều đó xảy ra? Ah, đó là phút ngay tại đây. Chúng tôi đã so sánh các giá trị sai. Ồ không. 

Oh yeah, xuống đây chúng tôi trao đổi các giá trị sai là tốt. Bởi vì chúng tôi đang tìm kiếm tại i và j. Đó là những người chúng tôi đã được kiểm tra. Chúng tôi thực sự muốn trao đổi tối thiểu, tối thiểu hiện hành, với bất cứ ai bên ngoài là. Và như các bạn có thể nhìn xuống ở đây, chúng tôi có một mảng được sắp xếp. Nó chỉ cần có để làm với thực tế là khi chúng tôi đã kiểm tra giá trị chúng tôi đã so sánh, chúng ta không chỉ nhìn vào những giá trị đúng. Chúng tôi đang tìm kiếm tại cùng một ở đây, không thực sự trao đổi nó. Bạn phải nhìn vào một trong những tiếp theo để nó và sau đó bạn có thể trao đổi. Vì vậy, đó là những gì đã được loại bugging mã của chúng tôi trước. Và những gì tôi đã làm ở đây là tất cả mọi thứ trình gỡ lỗi có thể làm cho bạn Tôi chỉ làm nó trên hội đồng quản trị, bởi vì nó dễ dàng hơn để xem hơn là cố gắng để phóng to trên các trình gỡ lỗi. Điều đó có ý nghĩa với tất cả mọi người? Mát. 

Được rồi. Chúng tôi có thể chuyển sang nói về ký hiệu tiệm cận, mà chỉ là một cách nói của runtimes của tất cả các loại. Vì vậy, tôi biết David, trong bài giảng, xúc động khi runtimes. Và ông đã đi qua toàn bộ công thức làm thế nào để tính toán các runtimes. Không có lo lắng về điều đó. Nếu bạn đang thực sự tò mò về cách mà các công trình, cảm thấy miễn phí để nói chuyện với tôi sau khi phần. Chúng tôi có thể đi bộ qua các công thức với nhau. Nhưng tất cả các bạn phải thực sự biết là n bình trên 2 là những điều tương tự như n bình phương. Bởi vì số lượng lớn nhất, số mũ, mọc nhiều nhất. Và do đó, cho các mục đích của chúng tôi, tất cả chúng ta quan tâm là số lượng khổng lồ đang phát triển. 

Vì vậy, các trường hợp tốt nhất là gì thời gian chạy của sắp xếp chọn? Nếu bạn đang đi để có để lặp qua một danh sách và sau đó lặp qua phần còn lại của danh sách đó, bao nhiêu lần bạn sẽ có thể, trong case-- tồi tệ nhất trong tốt nhất trường hợp, sorry-- chạy qua? Có lẽ câu hỏi tốt hơn là hỏi, trường hợp xấu nhất là gì thời gian chạy của sắp xếp chọn. Đung n bình phương. Andi PENG: Nó n bình phương, phải. Vì vậy, một cách dễ dàng để nghĩ về điều này là như thế, bất cứ lúc nào bạn có hai lồng nhau cho các vòng, nó sẽ được n bình phương. Bởi vì không chỉ là bạn chạy qua một lần nữa, bạn phải đi lại xung quanh và chạy qua nó một lần nữa bên trong cho mỗi giá trị. Vì vậy, trong trường hợp đó, bạn đang chạy n lần n bình phương, mà is-- xin lỗi, n lần n, trong đó n bằng với bình phương. 

Và loại cũng là một chút độc đáo trong ý nghĩa rằng nó không quan trọng nếu những giá trị đã có trong trật tự. Nó vẫn sẽ chạy qua anyways. Hãy chỉ nói rằng đây là 1, 2, 3, 4. Bất kể có hay không nó đã ở trật tự, nó vẫn sẽ chạy qua và vẫn còn kiểm tra các giá trị tối thiểu. Nó sẽ làm việc cùng một số kiểm tra mỗi lần duy nhất, ngay cả khi nó không thực sự chạm vào bất cứ điều gì. 

Vì vậy, trong trường hợp này, tốt nhất và tồi tệ nhất runtimes thực sự tương đương. Vì vậy, thời gian chạy dự kiến lựa chọn sắp xếp, mà chúng ta thiết kế bởi các biểu tượng của theta, theta, trong trường hợp này, cũng sẽ được n bình phương. Tất cả ba trong số này sẽ được n bình phương. Là tất cả mọi người rõ ràng vì sao thời gian chạy là n bình? 

Được rồi. Vì vậy, tôi chỉ cần đi để nhanh chóng chạy thông qua phần còn lại của các loại. Các thuật toán cho bong bóng sort-- nhớ, này là người đầu tiên David đã đi qua trong bài giảng. Về cơ bản, bạn bước thông qua toàn bộ danh sách và bạn swap-- bạn chỉ so sánh hai tại một thời điểm. Và nếu có ai là lớn hơn, hơn bạn chỉ cần trao đổi chúng. Vì vậy, nếu đây là lớn hơn, bạn sẽ trao đổi. Tôi đã chính thức ngay tại đây. 

Vì vậy, chúng ta hãy chỉ nói rằng bạn đã có 8, 6, 4, 2. Bạn muốn so sánh 8 và 6. Bạn sẽ cần phải trao đổi chúng. Bạn sẽ so sánh 8 và 4. Bạn sẽ cần phải trao đổi chúng. Nếu bạn phải trao đổi 8 và 2, thay đổi họ là tốt. Vì vậy, trong một cảm giác như vậy, bạn có thể thấy, diễn ra trong một khoảng thời gian dài, cách các giá trị loại bong bóng để kết thúc, đó là lý do tại sao chúng tôi gọi nó bong bóng sắp xếp. 

Chúng tôi sẽ chỉ cần chạy qua lại trên qua thứ hai của chúng tôi, và vượt qua thứ ba của chúng tôi, và vượt qua thứ tư của chúng tôi. Về cơ bản, bong bóng sắp xếp chỉ chạy cho đến khi bạn không thực hiện bất kỳ giao dịch hoán đổi hơn. Vì vậy, trong ý nghĩa đó, đây chỉ là mã giả chung của nó. Không có lo lắng, những tất cả sẽ được trực tuyến. Chúng tôi không có để thực sự đi qua này. 

Chúng tôi chỉ khởi tạo một truy cập biến mà bắt đầu từ 0. Và chúng ta lặp qua toàn bộ mảng. Và nếu một giá trị is-- nếu điều này giá trị lớn hơn giá trị đó, bạn đang đi để trao đổi chúng. Và sau đó bạn chỉ sẽ tiếp tục đi. Và bạn đang đi để đếm. Và bạn chỉ cần đi để tiếp tục làm này khi truy cập lớn hơn 0, có nghĩa là mỗi khi bạn phải trao đổi, bạn biết bạn muốn đi trở lại và kiểm tra lại. Bạn muốn giữ lại kiểm tra cho đến khi bạn biết rằng bạn không phải trao đổi nữa. 

Vì vậy, những gì là tốt nhất và tồi tệ nhất trường hợp thời gian chạy cho bong bóng sắp xếp? Và hint-- này thực sự là khác nhau từ sắp xếp chọn theo ý nghĩa rằng hai câu trả lời này là không giống nhau. Hãy suy nghĩ về những gì sẽ xảy ra trong một trường hợp nếu nó đã được sắp xếp. Và suy nghĩ về những gì sẽ xảy ra nếu nó đã được trong các trường hợp mà trong đó nó đã không được sắp xếp. Và bạn có thể loại chạy thông qua tại sao điều đó đang xảy ra. Tôi sẽ cung cấp cho các bạn, như, 30 giây để suy nghĩ về điều đó. 

ĐƯỢC. Có ai có một đoán vào những gì các thời gian chạy trường hợp tồi tệ nhất của bong bóng sắp xếp là? Yeah. 

Đung nó Sẽ được, như, n lần n trừ đi 1 hoặc một cái gì đó như thế? Giống như, mỗi khi nó chạy, nó chỉ là, như, một hoán đổi ít rằng bất cứ điều gì nó được. 

Andi PENG: Yeah, vì vậy bạn đã hoàn toàn đúng. Và đây là một trường hợp mà trong đó bạn Câu trả lời là thực sự phức tạp hơn so với cái chúng ta cần phải cung cấp cho. Vì vậy, nó sẽ run-- tôi sẽ xóa tất cả điều này ở đây. Là tất cả mọi người tốt? Tôi có thể xoá này? ĐƯỢC. Bạn sẽ phải chạy qua n lần lần đầu tiên, phải không? Và chúng ta sẽ chạy qua n trừ đi 1 lần thứ hai, phải không? Và sau đó bạn sẽ giữ đi, n mỏ 2, vân vân. David đã làm điều này trong một bài giảng, ở đâu, nếu bạn thêm lên tất cả những giá trị, bạn sẽ có được một cái gì đó là like-- yeah-- hơn 2, trong đó chủ yếu chỉ giảm xuống n bình phương. Bạn sẽ nhận được một phần kỳ lạ trong đó. Và do đó, chỉ biết rằng n bình phương luôn được ưu tiên hơn các phân số. Và như vậy trong trường hợp này, điều tồi tệ nhất runtime sẽ được n bình phương. Nếu nó đã được giảm dần trật tự, suy nghĩ, bạn phải thực hiện một trao đổi mỗi lần duy nhất. 

Điều gì sẽ là, có khả năng, trường hợp thời gian chạy tốt nhất? Hãy chỉ nói rằng, nếu trong danh sách là đã theo thứ tự, những gì sẽ là thời gian chạy được? 

Đung n. Andi PENG: Đó là n, chính xác. Và tại sao nó n? Đung Bởi vì bạn chỉ phải kiểm tra mỗi một lần. Andi PENG: Chính xác. Vì vậy, trong thời gian chạy tốt nhất có thể, nếu danh sách này đã là sorted-- hãy nói 1, 2, 3, 4-- bạn sẽ chỉ đi qua, bạn sẽ kiểm tra, bạn sẽ thấy, oh, tất cả họ đều chảo ra. Tôi không có để trao đổi. Tôi đa xong. Vì vậy, trong trường hợp đó, nó chỉ là n hoặc số lượng các bước bạn chỉ phải kiểm tra trong danh sách đầu tiên. 

Và sau đó, bây giờ chúng ta nhấn sắp xếp chèn, nơi các thuật toán cơ bản là để phân chia nó vào một phần được sắp xếp và phân loại. Và sau đó từng người một, các giá trị không được phân loại là lắp vào thích hợp của họ vị trí ở đầu danh sách. 

Vì vậy, ví dụ, chúng ta có một danh sách 3, 5, 2, 6, 4 lần nữa. Chúng tôi biết rằng đó là hiện không được phân loại bởi vì chúng tôi đã chỉ bắt đầu nhìn vào nó. Chúng tôi có một cái nhìn và chúng tôi biết rằng giá trị đầu tiên được sắp xếp, phải không? Nếu bạn chỉ nhìn vào một mảng của kích thước của nó, bạn biết rằng nó được sắp xếp. 

Vì vậy, sau đó chúng ta biết rằng bốn người kia là không được phân loại. Chúng tôi đi qua và chúng ta thấy giá trị đó. Hãy quay trở lại. Thấy rằng giá trị của 5? Chúng ta hãy nhìn vào nó. Chúng tôi so sánh nó với 3. Chúng tôi biết rằng nó lớn hơn 3, vì vậy chúng tôi biết rằng đó là sắp xếp. Vì vậy, bây giờ chúng ta biết rằng hai đầu đều được sắp xếp và cuối cùng ba không. 

Chúng ta hãy nhìn vào 2. Đầu tiên chúng ta kiểm tra xem nó có 5. Có ít hơn 5? Không phải vậy. Vì vậy, chúng ta phải tiếp tục tìm kiếm xuống. Sau đó, bạn kiểm tra 2 off 3. Là nó ít hơn? Không. Vì vậy, bạn biết 2 đã được chèn vào mặt trước và 3 và 5 cả hai đều bị đẩy ra ngoài. Làm điều này một lần nữa với 6 và 4. Và chúng ta chỉ giữ lại kiểm tra cơ bản, nơi mà chúng ta chỉ cần kiểm tra, rà soát, kiểm tra. Và cho đến khi nó ở bên phải vị trí, chúng tôi loại chỉ chèn nó vào đúng vị trí, đó là nơi mà tên của nó đến từ đâu. 

Vì vậy, đó chỉ là những thuật toán, giả cho mỗi gia nhập, loại, về cách chúng tôi sẽ thực hiện một loại chèn. Giả là ở đây. Đó là tất cả trực tuyến. Không phải lo lắng nếu các bạn là cố gắng để sao chép này xuống. Vì vậy, một lần nữa, cùng question-- gì sẽ là tốt nhất và tồi tệ nhất runtimes cho sắp xếp chèn? Nó rất giống với câu hỏi cuối cùng. Tôi sẽ cung cấp cho các bạn, như, 30 giây để suy nghĩ về điều này như là tốt. 

OK Có ai muốn cho tôi thời gian chạy tồi tệ nhất? Yeah. 

Đung n bình phương. 

Andi PENG: Nó n bình phương. Và tại sao nó n bình? 

Đung Bởi vì trong thứ tự ngược lại, bạn có đi qua n lần n, mà is-- Andi PENG: Yeah, chính xác. Vì vậy, điều tương tự như trong các loại bong bóng. Nếu danh sách này là trong thứ tự giảm dần, bạn sẽ phải kiểm tra một lần đầu tiên. Và sau đó với mỗi giá trị bổ sung, bạn sẽ phải kiểm tra xem nó chống lại mỗi giá trị duy nhất, phải không? Và như vậy hoàn toàn, bạn sẽ làm cho một n vượt qua lần khác n vượt qua, mà được n bình phương. Những gì về trường hợp tốt nhất? Yeah. 

Đung n trừ đi 1, bởi vì là một trong những đầu tiên đã được bình phương. 

Andi PENG: Vì vậy, gần gũi. Câu trả lời thực sự là n. Bởi vì trong khi người đầu tiên là sắp xếp, nó có thể không actually-- nó chúng tôi chỉ lucked ra, trong ví dụ, rằng 2 xảy ra là số lượng nhỏ nhất. Nhưng điều đó sẽ không phải luôn luôn là trường hợp. Nếu 2 đã được sắp xếp trong đầu nhưng bạn nhìn và có một 1 ở đây, 1 là sẽ bump nó. Và nó sẽ kết thúc lên được đụng anyways. 

Vì vậy, trong trường hợp tốt nhất, nó thực sự chỉ có được n. Nếu bạn có 1, 2, 3, 4, 5, 6, 7, 8, bạn sẽ chạy qua rằng toàn bộ danh sách một lần để kiểm tra xem nếu tất cả mọi thứ tốt đẹp của. Là tất cả mọi người rõ ràng về hoạt động lần lựa chọn là tốt? Tôi biết tôi sẽ thông qua những thực sự nhanh chóng. Nhưng chỉ biết rằng nếu bạn biết khái niệm chung, bạn nên được tốt. ĐƯỢC. Vì vậy, tôi sẽ chỉ cho các bạn cái có thể, như, một phút để nói chuyện với hàng xóm của bạn về những gì đang có chỉ số những khác biệt chính giữa các loại của các loại. Chúng tôi sẽ đi qua đó sớm. Đung Oh, OK. Andi PENG: Yeah. ĐƯỢC. Cool, hãy triệu tập lại như một lớp học. ĐƯỢC. Vì vậy, đây là loại một mở câu hỏi trong ý nghĩa rằng có rất nhiều câu trả lời cho họ. Và chúng ta sẽ đi qua một số trong số họ một thời gian ngắn. Tôi chỉ muốn để có được các bạn suy nghĩ về những gì phân biệt cả ba loại của các loại. Và tôi nghe, cũng, một tuyệt vời question-- gì merge sort làm gì? Great câu hỏi, bởi vì đó là những gì chúng tôi đang bao phủ tới. 

Vì vậy, hợp nhất phân loại là một loại có chức năng rất khác với các loại khác. Như các bạn có thể see-- David đã làm demo nơi ông đã có tất cả các mát tiếng động khi nhìn thấy như thế nào hợp nhất loại chạy, như thế, vô hạn nhanh hơn so với hai loại khác? ĐƯỢC. Vì vậy, đó là bởi vì hợp nhất loại thực hiện phân chia đó và chinh phục khái niệm mà chúng ta đã nói chuyện về rất nhiều trong bài giảng. Trong ý nghĩa đó, chúng tôi muốn làm việc thông minh hơn, không khó khăn hơn, khi bạn chia và chinh phục các vấn đề, và phá vỡ chúng xuống, và sau đó đặt chúng lại với nhau, những điều tốt đẹp luôn luôn xảy ra. 

Vì vậy, cách đó hợp nhất loại cơ bản các công trình là nó chia một mảng được phân loại trong một nửa. Và sau đó nó có hai nửa của mảng. Và nó chỉ sắp xếp những hai nửa. Nó chỉ cần giữ chia một nửa, trong một nửa, một nửa cho đến khi tất cả mọi thứ được sắp xếp và sau đó đệ quy đặt nó tất cả cùng nhau. 

Vì vậy, đó là thực sự trừu tượng. Vì vậy, đây chỉ là một chút của mã giả. Điều đó có ý nghĩa trong cách nó đang chạy? Vì vậy, chúng ta hãy chỉ nói rằng bạn có một mảng n phần tử, phải không? Nếu n là nhỏ hơn 2, bạn có thể quay trở lại. Bởi vì bạn biết rằng nếu có chỉ có một điều, nó phải được sắp xếp. Ngoài ra, bạn sắp xếp một nửa trái, và sau đó bạn sắp xếp một nửa bên phải, và sau đó bạn hợp nhất. 

Vì vậy, trong khi đó có vẻ rất dễ dàng, trong thực tế, suy nghĩ về nó loại khó khăn. Bởi vì bạn đang như, tốt, đó là loại chạy trên chính nó. Bên phải? Nó đang chạy trên chính nó. Vì vậy, trong ý nghĩa đó, David xúc động khi đệ quy trong lớp. Và đó là một khái niệm chúng ta sẽ nói về nhiều hơn. Đó là điều này, hai dòng ở đây, thực sự chỉ là các chương trình nói cho nó tự chạy với đầu vào khác nhau. Vì vậy, thay vì chạy trốn chính nó với toàn bộ các yếu tố n, bạn có thể phá vỡ nó xuống nửa bên trái và nửa bên phải và sau đó chạy nó một lần nữa. 

Và sau đó chúng tôi sẽ xem xét nó trực quan, bởi vì tôi là một người học trực quan. Nó hoạt động tốt hơn cho tôi. Vì vậy, chúng tôi sẽ xem xét một ví dụ trực quan ở đây. 

Hãy nói rằng chúng tôi có một mảng, sáu yếu tố, 3, 5, 2, 6, 4, 1, không được sắp xếp. Được rồi, có rất nhiều trên trang này. Vì vậy, nếu các bạn có thể ghé qua Bước đầu tiên ở đây, 3, 5, 2, 6, 4, 1, bạn có thể chia nhỏ nó ra. Bạn có 3, 5, 2, 6, 4, 1. Bạn biết rằng những aren't-- bạn không biết nếu họ đang sắp xếp hay không, vì vậy bạn giữ phá vỡ chúng xuống, một nửa, một nửa, một nửa, cho đến khi cuối cùng, bạn chỉ có một phần tử. Và một trong những yếu tố luôn được sắp xếp, phải không? 

Vì vậy, chúng ta biết rằng 3, 5, 2, 4, 6, 1, bởi chính họ, đều được sắp xếp. Và bây giờ chúng tôi có thể đặt chúng lại với nhau. Vì vậy, chúng ta biết được 3, 5. Chúng tôi đưa những người với nhau. Chúng tôi biết đó là sắp xếp. 2 nhân vẫn còn đó. Chúng ta có thể đặt 4 và 6 với nhau. Chúng tôi biết rằng đó là sắp xếp, vì vậy chúng tôi đặt lại với nhau. Và 1 là có. 

Và sau đó bạn chỉ cần nhìn vào hai nửa này ngay tại đây. Bạn có 3, 5, 2, 2, 3, 5. Bạn chỉ có thể so sánh bắt đầu của tất cả mọi thứ. Bởi vì bạn biết rằng điều này được sắp xếp và bạn biết rằng đó là sắp xếp. Vì vậy, sau đó bạn thậm chí không phải so sánh 5, bạn chỉ cần so sánh 3. Và 2 là ít hơn 3, vì vậy Bạn có biết 2 phải đi cuối cùng. 

Điều tương tự cũng ở đó. 1 phải đi đây. Và sau đó khi bạn đi đến đặt hai giá trị với nhau, Bạn có biết rằng điều này được sắp xếp và Bạn có biết rằng đó là sắp xếp. Vì vậy, sau đó là 1 và 2, 1 là ít hơn 2. Điều đó nói với bạn rằng 1 nên đi vào cuối năm nay mà không cần nhìn vào 3 hoặc 5. Và sau đó là 4, bạn có thể chỉ kiểm tra, nó đi ngay đây. Bạn không cần phải nhìn vào 5. Cùng một điều với 6. Bạn biết rằng nó chỉ 6-- không cần phải được xem xét. 

Và như vậy theo cách đó, bạn chỉ tiết kiệm cho mình rất nhiều các bước khi bạn đang so sánh. Bạn không cần phải so sánh mỗi yếu tố chống lại các yếu tố khác. Bạn chỉ cần so sánh với những người mà bạn cần phải so sánh nó với. Vì vậy, đó là loại một khái niệm trừu tượng. Không phải lo lắng nếu nó không khá đánh bạn phải được nêu ra. Nhưng nhìn chung, đây là làm thế nào một loại hợp nhất hoạt động. Câu hỏi, câu hỏi nhanh, trước khi tôi di chuyển trên? Yeah. 

Đung Vì vậy, bạn nói rằng bạn có 1, và sau đó là 4, và 6 và đặt chúng trong. Vì vậy, không those-- không bạn nhìn vào họ như các yếu tố riêng biệt, không phải là toàn bộ? Andi PENG: Yeah. Vì vậy, những gì đang xảy ra là bạn cơ bản đang tạo ra một mảng mới. Vì vậy, bạn biết rằng, ở đây, tôi có hai mảng có kích thước 3, phải không? Vì vậy, bạn biết rằng mảng được sắp xếp của tôi cần phải có sáu yếu tố. Vì vậy, bạn chỉ cần tạo một số tiền mới của bộ nhớ. Vì vậy, bạn đang loại như đang lãng phí bộ nhớ, nhưng điều đó không quan trọng vì nó quá nhỏ. Vì vậy, bạn nhìn vào 1 và bạn nhìn vào 2. Và bạn có biết rằng 1 là ít hơn 2. Vì vậy, bạn có biết rằng 1 cần đi đầu của tất cả những người. 

Bạn thậm chí không cần phải nhìn vào 3 và 5. Vì vậy, bạn biết 1 đến đó. Sau đó, về cơ bản bạn chop off 1. Đó là, như, đã chết cho chúng ta. Sau đó, chúng tôi chỉ có 2, 3, 5, và sau đó 4 và 6. Và sau đó bạn biết rằng, bạn so sánh 4 và 2, oh, 2 nên đi vào đó. Vì vậy, bạn tiếng tom 2 xuống, bạn cắt nó đi. Vì vậy, sau đó bạn chỉ có 3 và 5 trong 4 và 6. Và bạn chỉ cần giữ chặt nó đi cho đến khi bạn đặt chúng trong mảng. 

Đung Vì vậy, bạn chỉ cần luôn luôn so sánh [Không nghe thấy]? 

Andi PENG: Chính xác. Vì vậy, trong ý nghĩa đó, bạn chỉ so sánh, về cơ bản, một số đối số khác. Và bởi vì bạn biết mà nó được sắp xếp, bạn không cần phải xem xét thông qua tất cả các con số. Bạn chỉ cần nhìn vào cái đầu tiên. Và sau đó bạn chỉ có thể tiếng tom chúng xuống, bởi vì bạn biết họ thuộc về nơi họ cần phải thuộc về. Yeah. Câu hỏi hay. 

Và sau đó nếu có của bạn có một chút tham vọng, cảm thấy miễn phí để xem xét mã này. Đây thực sự là thực hiện vật lý làm thế nào chúng ta sẽ viết sắp xếp hợp nhất. Và bạn có thể thấy, nó rất ngắn. Nhưng những ý tưởng đằng sau nó là khá phức tạp. Vì vậy, nếu bạn cảm thấy như bản vẽ này ra trong tối nay ở nhà của bạn, cảm thấy tự do để. 

ĐƯỢC. Vì vậy, David cũng đã đi qua này trong bài giảng. Trường hợp tốt nhất là gì runtimes, runtimes trường hợp xấu nhất, và các runtimes dự kiến ​​sắp xếp hợp nhất? Một vài giây để suy nghĩ. Điều này là khá khó khăn, nhưng loại trực quan nếu bạn nghĩ về nó. Được rồi. 

Đung là điều tồi tệ nhất log n trường hợp n? Andi PENG: Chính xác. Và tại sao nó n log n. 

Đung không phải vì nó trở nên nhanh hơn theo cấp số nhân, Nó giống như một chức năng mà thay vì chỉ đơn giản là n bình phương hay một cái gì đó? Andi PENG: Chính xác. Vì vậy, lý do tại sao thời gian chạy trên này là n log n là because-- bạn là gì làm trong tất cả các bước? Bạn chỉ cần cắt nó ra, phải không? Và như vậy khi chúng tôi đang làm việc đăng nhập, tất cả những gì nó đang làm gì được phân chia một vấn đề trong một nửa, một nửa, một nửa, trong hơn nửa. Và trong ý nghĩa đó, bạn có thể loại loại bỏ các mô hình tuyến tính mà chúng ta đã sử dụng. Bởi vì khi bạn chop mọi thứ trong một nửa, đó là một bản ghi. Đó chỉ là toán học cách đại diện cho nó. 

Và cuối cùng, ở cuối, bạn chỉ cần làm một đường chuyền cuối cùng thông qua để đặt tất cả chúng theo thứ tự, phải không? Và do đó, nếu bạn chỉ cần có để kiểm tra một điều, đó là n. Và như vậy bạn đang loại nhân hai cùng nhau. Vì vậy, nó giống như bạn đã có mà thức kiểm tra n xuống đây với một bản ghi của n trên này này. Và nếu bạn nhân họ, đó là n log n. 

Và do đó, các trường hợp tốt nhất và tồi tệ nhất trường hợp và dự kiến ​​sẽ được tất cả n log n. Nó cũng giống như loại khác. Nó giống như sắp xếp chọn trong ý nghĩa rằng nó không có vấn đề gì của bạn danh sách là, nó chỉ đi để làm điều tương tự mỗi lần duy nhất. ĐƯỢC. Vì vậy, các bạn có thể thấy, mặc dù các loại mà chúng ta đã đi through-- n bình phương, nó không phải là rất hiệu quả. Và ngay cả điều này n log n là không phải là hiệu quả nhất. Nếu các bạn đang tò mò, có cơ chế loại mà rất hiệu quả mà họ đang gần như cơ bản phẳng trong thời gian chạy. 

Bạn đã có một số log n của. Bạn đã có một số bản ghi log n của. Chúng tôi không động chạm đến họ trong lớp học này ngay bây giờ. Nhưng nếu các bạn đang tò mò, cảm thấy tự do để google, có chuyện gì việc phân loại các cơ chế hiệu quả nhất. Tôi không biết, có rất một số những người thực sự buồn cười, like-- có một số thực sự những vui mà mọi người thực hiện. Và bạn tự hỏi làm thế nào họ bao giờ nghĩ về điều đó. Vì vậy, google, nếu bạn có một số phụ tùng Hiện, trên, một số cách hài hước là những gì rằng people-- cũng như người ways-- hiệu quả đã có thể thực hiện các loại. ĐƯỢC. Và đây chỉ là một biểu đồ nhỏ tiện dụng. Tôi biết tất cả các bạn, trước đó đố 0, sẽ được ở trong phòng của bạn có thể cố gắng để ghi nhớ đó. Vì vậy, đó là tốt đẹp trong đó cho các bạn. Chỉ cần đừng quên rằng logic made-- tại sao những con số đã xảy ra. Nếu bạn luôn bị mất, chỉ cần thực hiện chắc chắn rằng bạn biết những gì các loại đang có. Và bạn có thể chạy qua chúng trong tâm trí của bạn để tìm ra lý do tại sao những người câu trả lời là những câu trả lời. 

Được rồi. Vì vậy, chúng ta sẽ di chuyển trên, cuối cùng, để tìm kiếm. Bởi vì như những người bạn những người đã đọc pset, tìm kiếm cũng là một phần của Vấn đề của tuần này đề ra. Bạn sẽ được yêu cầu để thực hiện hai loại tìm kiếm. Một là tìm kiếm tuyến tính và một là một tìm kiếm nhị phân. 

Vì vậy, việc tìm kiếm tuyến tính là khá dễ dàng. Bạn chỉ muốn tìm kiếm yếu tố của một danh sách để xem nếu bạn nhận được nó. Bạn chỉ cần có để lặp qua. Và nếu nó bằng gì gì đó, bạn chỉ có thể trả lại nó, phải không? Nhưng một trong những điều đó chúng tôi nhất thích nói chuyện về là tìm kiếm nhị phân, phải, đó là phân chia và cơ chế chinh phục mà David đã được chứng minh trong bài giảng. 

Hãy nhớ rằng các ví dụ cuốn sách điện thoại rằng ông tiếp tục đưa lên, một trong đó ông loại vật lộn một chút về năm vừa qua, nơi bạn chia các vấn đề trong một nửa, một nửa, một nửa, một lần nữa và một lần nữa, cho đến khi bạn tìm thấy những gì bạn đang tìm kiếm? Và bạn đã có thời gian chạy của điều đó. Và bạn có thể thấy, đó là đáng kể hiệu quả hơn hơn bất kỳ loại hình khác của tìm kiếm. 

Vì vậy, cách mà chúng ta sẽ đi về thực hiện một tìm kiếm nhị phân là, nếu chúng ta có một mảng, Chỉ số 0-6, bảy yếu tố, chúng ta có thể nhìn vào giữa, right-- xin lỗi, nếu câu hỏi của chúng tôi first-- nếu chúng ta muốn đặt câu hỏi về, không mảng chứa đựng yếu tố 7, rõ ràng, là con người, và có như một mảng nhỏ, thật dễ dàng cho chúng tôi nói có. Nhưng cách thức để thực hiện một số nhị phân tìm kiếm sẽ được xem xét ở giữa. 

Chúng ta biết rằng chỉ số 3 là giữa, bởi vì chúng tôi biết có bảy yếu tố. Những gì 7 chia cho 2? Bạn có thể chặt rằng thêm 1. Bạn đã có 3 ở giữa. Vì vậy, là mảng của 3 bằng 7? Nó không phải là, phải không? Nhưng chúng ta có thể làm một vài kiểm tra. Là mảng của 3 ít hơn 7 hoặc là mảng của 3 lớn hơn 7? 

Và chúng ta biết rằng nó ít hơn 7. Vì vậy, chúng ta biết rằng, oh, nó phải không thể là trong nửa trái. Chúng tôi biết rằng nó phải được ở nửa bên phải, phải không? Vì vậy, chúng tôi chỉ có thể chặt một nửa mảng. Chúng tôi thậm chí không có để nhìn vào nó nữa. Bởi vì chúng ta biết rằng một nửa của problem-- của chúng tôi chúng ta biết rằng câu trả lời là trong nửa bên phải của vấn đề của chúng tôi. Vì vậy, chúng ta chỉ cần nhìn vào đó bây giờ. 

Vì vậy, bây giờ chúng ta nhìn vào giữa những gì còn lại. Đó chỉ số 5. Chúng tôi làm việc kiểm tra một lần nữa và chúng tôi thấy rằng nó nhỏ hơn. Vì vậy, chúng tôi nhìn bên trái của điều đó. Và sau đó chúng tôi nhìn thấy tờ séc đó. Là giá trị mảng ở Chỉ số 4 bằng 7? Nó là. Vì vậy, chúng ta có thể trở thành sự thật, bởi vì chúng tôi thấy các giá trị trong danh sách của chúng tôi. Liệu cách tôi đã đi qua đó có ý nghĩa với tất cả mọi người? ĐƯỢC. Tôi sẽ cho các bạn cái có thể, như, ba, bốn phút để tìm ra làm thế nào để giả này. 

Vì vậy, hãy tưởng tượng tôi hỏi bạn phải viết một chức năng gọi là search () đó quay trở lại một giá trị, một giá trị Boolean, đó là sự thật hay false-- như, đúng nếu bạn thấy giá trị, false nếu bạn đã không. Và sau đó bạn có thông qua vào giá trị bạn đang tìm kiếm vào các giá trị, trong đó là array-- oh, chắc chắn tôi đặt mà ở chỗ sai. ĐƯỢC. Anyways, mà cần phải có từng đến quyền của các giá trị. Và sau đó int n là số các phần tử trong mảng đó. Làm thế nào bạn sẽ đi về cố gắng để giả rằng vấn đề trong? Tôi sẽ cung cấp cho các bạn thích ba phút để làm điều đó. Không, tôi nghĩ rằng có only-- yeah, có một trong những quyền lên đây. Đung, được không? Andi PENG: Vâng, tôi đã có em. Là làm việc đó? OK, mát mẻ. 

ĐƯỢC. Tất cả các chàng trai phải, chúng tôi sẽ kiềm chế nó trong. ĐƯỢC. Vì vậy, giả sử chúng ta đã có này đáng yêu ít mảng với giá trị n trong đó. Tôi không vẽ các đường. Nhưng làm thế nào chúng ta sẽ đi về cố gắng viết này? Có ai muốn cung cấp cho tôi những dòng đầu tiên? Nếu bạn muốn cho tôi Dòng đầu tiên của mã giả này. 

Đung [Không nghe thấy] Đung Bạn muốn để lặp through-- Đung Chỉ cần một vòng lặp? Đung --cho. 

Andi PENG: Vì vậy, con này một chút khéo léo. Hãy nghĩ about-- bạn muốn để tiếp tục chạy vòng lặp này hơn và hơn một lần nữa cho đến khi nào? 

Đung Cho đến [Không nghe thấy] giá trị bằng với giá trị đó. Andi PENG: Chính xác. Vì vậy, bạn có thể thực sự chỉ write-- chúng tôi thậm chí có thể đơn giản hóa nó hơn. Chúng tôi chỉ có thể làm một vòng lặp trong khi, phải không? Vì vậy, bạn chỉ có thể có loop-- chúng tôi biết rằng đó là một thời gian. Nhưng đối với ngay bây giờ, tôi sẽ để nói "loop" - thông qua những gì? Vòng until-- là gì điều kiện kết thúc của chúng tôi? Tôi nghĩ rằng tôi nghe nó. Tôi nghe ai đó nói nó. 

Đung giá trị tương đương với trung bình. Andi PENG: Nói lại lần nữa. Đung Hoặc, cho đến khi giá trị mà bạn đang tìm kiếm cho là tương đương với giá trị trung bình. 

Andi PENG: Điều gì nếu nó không ở trong đó? Điều gì nếu giá trị bạn đang tìm kiếm cho là không thực sự trong mảng này? Đung Bạn quay trở lại 1. 

Andi PENG: Nhưng những gì chúng ta muốn vòng lặp cho đến khi chúng tôi có một điều kiện? Yeah. 

Đung Cho đến khi chỉ có một giá trị? Andi PENG: Bạn có thể lặp until-- để bạn biết rằng bạn đang sẽ có một giá trị tối đa, phải không? Và bạn biết rằng bạn đang đi để có một giá trị min, phải không? Bởi vì cũng có, đó là một cái gì đó Tôi quên nói trước, rằng đó là một cái gì đó quan trọng về tìm kiếm nhị phân là mảng của bạn đã được sắp xếp. Bởi vì không có cách nào làm này nếu họ giá trị chỉ là ngẫu nhiên. Bạn không biết nếu một là lớn hơn khác, phải không? 

Vì vậy, bạn biết rằng tối đa của bạn và phút của bạn đang ở đây, phải không? Nếu bạn đang đi để được điều chỉnh tối đa của bạn trong phút bạn và mid-- chúng ta hãy giả định của bạn giữa giá trị là here-- đúng bạn sẽ cơ bản vòng lặp cho đến khi bạn tối thiểu là về giống như tối đa của bạn, phải, hoặc nếu tối đa của bạn không giống như min của bạn. Bên phải? Bởi vì khi điều đó xảy ra, bạn có biết rằng cuối cùng bạn đã đánh giá trị như nhau. Vì vậy, bạn muốn lặp cho đến phút của bạn là nhỏ hơn hoặc bằng với: oops, không ít hơn hoặc bằng, cách khác around-- max là. 

Điều đó có ý nghĩa? Tôi lấy một vài cố gắng để có được quyền đó. Nhưng vòng lặp cho đến giá trị tối đa của bạn về cơ bản là hầu như ít hơn hoặc bằng tối thiểu của bạn, phải không? Đó là khi bạn biết rằng bạn đã hội tụ. Đung Khi sẽ tối đa của bạn giá trị ít hơn mức tối thiểu? Andi PENG: Nếu bạn giữ điều chỉnh nó, mà là những gì chúng ta đang đi được làm trong này. Điều đó có ý nghĩa? Tối thiểu và tối đa chỉ số nguyên mà chúng tôi có lẽ sẽ muốn tạo ra để giữ theo dõi các nơi mà chúng tôi đang tìm kiếm. Vì mảng tồn tại bất kể những gì chúng tôi đang làm. Giống như, chúng tôi không thực sự thể chất cắt bỏ các mảng, phải không? Chúng tôi chỉ điều chỉnh nơi mà chúng tôi đang tìm kiếm. Điều đó có ý nghĩa? 

Đung Yeah. 

Andi PENG: OK. Vì vậy, nếu đó là điều kiện cho vòng lặp của chúng tôi, những gì chúng ta muốn bên trong của vòng lặp này? Chúng ta sẽ phải muốn làm gì? Vì vậy, ngay bây giờ, chúng tôi đã có một tối đa và một phút, phải, có thể tạo ra ở đây một nơi nào đó. Chúng ta sẽ có thể muốn để tìm một trung, phải không? Làm thế nào chúng ta sẽ được có thể tìm thấy giữa? Các mathematical-- là gì Đung Max cộng min chia cho 2. Andi PENG: Chính xác. Điều đó có ý nghĩa? Và các bạn thấy lý do tại sao chúng tôi không chỉ use-- do của việc làm này thay vì chỉ cần làm n chia cho 2? Đó là bởi vì n là một giá trị đó là sẽ ở lại cùng. Bên phải? Nhưng khi chúng ta điều chỉnh tối thiểu của chúng tôi và giá trị tối đa, chúng ta sẽ thay đổi. Và kết quả là, giữa chúng tôi là sẽ thay đổi quá. Vì vậy, đó là lý do tại sao chúng tôi muốn để làm điều này đúng ở đây. ĐƯỢC. 

Và sau đó, bây giờ mà chúng tôi đã tìm thấy our-- yeah. 

Đung Chỉ cần một question-- nhanh khi bạn nói min và max, Chúng ta giả định rằng nó đã được sắp xếp? 

Andi PENG: Vâng, đó thực sự là một điều kiện tiên quyết cho một tìm kiếm nhị phân, mà bạn phải biết nó được sắp xếp. Đó là lý do tại sao sắp xếp, bạn viết trong của bạn vấn đề thiết lập trước khi tìm kiếm nhị phân của bạn. ĐƯỢC. Vì vậy, bây giờ mà chúng ta biết nơi trung điểm của chúng tôi được, những gì bạn muốn làm ở đây? 

Đung Chúng tôi muốn so sánh rằng để một khác. Andi PENG: Chính xác. Vì vậy, bạn đang đi để so sánh giữa giá trị, phải không? Và những gì mà không nói chúng ta khi chúng ta so sánh? Những gì chúng tôi muốn làm sau đó? 

Đung Nếu giá trị lớn hơn trung, chúng tôi muốn cắt nó đi. Andi PENG: Chính xác. Vì vậy, nếu giá trị lớn hơn trung, chúng tôi sẽ muốn thay đổi những đạt cực đại và tối thiểu, phải không? Những gì chúng tôi muốn thay đổi? Vì vậy, nếu chúng ta biết giá trị là một nơi nào đó ở đây, những gì bạn làm chúng ta phải thay đổi? Chúng tôi muốn thay đổi của chúng tôi tối thiểu là mid, phải không? Và sau đó khác, nếu nó ở trong này một nửa, những gì chúng tôi muốn thay đổi? 

Đung tối đa của bạn. Andi PENG: Yeah. Và sau đó bạn chỉ cần đi để giữ cho vòng lặp, phải không? Bởi vì bây giờ, sau một lần lặp thông qua, bạn đã có một tối đa ở đây. Và sau đó bạn có thể tính toán lại một trung. Và sau đó bạn có thể so sánh. Và bạn sẽ tiếp tục đi cho đến phút và đạt cực đại trên cơ bản đã hội tụ. Và đó là khi bạn biết rằng bạn đã nhấn kết thúc của nó. Và một trong hai bạn đã tìm thấy nó hoặc bạn có không vào thời điểm đó. 

Liệu điều này có ý nghĩa với tất cả mọi người? ĐƯỢC. Điều này là khá quan trọng, bởi vì bạn sẽ có để viết này trong mã của bạn đêm nay. Nhưng các bạn có một khá tốt ý nghĩa của những gì bạn cần phải làm, cái nào tốt. ĐƯỢC. Vì vậy, chúng tôi đã có khoảng bảy phút còn lại phần. Vì vậy, chúng ta sẽ nói về pset này rằng chúng tôi sẽ làm. Vì vậy, các pset được chia thành hai nửa. Nửa đầu tiên liên quan thực hiện một tìm thấy trong đó bạn viết một tìm kiếm tuyến tính, một tìm kiếm nhị phân, và một thuật toán sắp xếp. 

Vì vậy, đây là lần đầu tiên thời gian trong một pset nơi chúng tôi sẽ đem lại cho các bạn những gì được gọi là Mã phân phối, đó là mã rằng chúng tôi đã sẵn bằng văn bản, nhưng chỉ để lại một số mảnh off cho bạn để hoàn thành văn bản. Vì vậy các bạn, khi bạn nhìn vào điều này mã, bạn có thể nhận được thực sự sợ hãi. Nếu bạn chỉ thích, ahh, tôi không biết đó là làm, Tôi không biết, như thế, mà có vẻ quá phức tạp, ahh, thư giãn. Đó là OK. Đọc spec. Spec sẽ giải thích cho bạn biết chính xác những gì tất cả các chương trình đang làm. 

Ví dụ, generate.c là một chương trình đó sẽ đến với pset của bạn. Bạn không thực sự cần chạm vào nó, nhưng bạn nên hiểu những gì nó làm. Và generate.c, tất cả nó làm là hoặc tạo ra các số ngẫu nhiên hoặc bạn có thể cung cấp cho nó một hạt giống, giống như một số chuẩn bị trước mà nó cần, và nó tạo ra nhiều con số hơn. Vì vậy, có một cách cụ thể để thực hiện generate.c trong đó bạn chỉ có thể thực hiện một loạt các con số cho bạn để thử nghiệm các phương pháp khác của bạn trên. 

Vì vậy, nếu bạn muốn, cho Ví dụ, kiểm tra tìm bạn, bạn sẽ muốn chạy generate.c, tạo ra một loạt các con số, và sau đó chạy chức năng giúp đỡ của bạn. Chức năng giúp đỡ của bạn là nơi bạn thực chất viết code. Và suy nghĩ của những người giúp đỡ như một tập tin thư viện bạn đang viết tìm được kêu gọi. Và như vậy trong vòng helpers.c, bạn sẽ làm tìm kiếm và phân loại. 

Và sau đó bạn sẽ cơ bản chỉ cần đặt chúng lại với nhau. Spec sẽ cho bạn biết làm thế nào để đặt trên các dòng lệnh. Và bạn sẽ có thể kiểm tra hay không sắp xếp và tìm kiếm của bạn đang làm việc. Mát. Có ai đã bắt đầu và vấn đề gặp phải hoặc câu hỏi họ có ngay bây giờ với điều này? ĐƯỢC. 

Đung đợi. Tôi có một câu hỏi. 

Andi PENG: Yeah. 

Đung Vì vậy, tôi bắt đầu làm tìm kiếm tuyến tính trong helpers.c và nó đã không thực sự làm việc. Nhưng sau đó, tôi phát hiện ra chúng ta chỉ phải xóa nó và làm tìm kiếm nhị phân. Vì vậy, không vấn đề gì nếu nó không hoạt động? 

Andi PENG: Câu trả lời ngắn gọn là không. Nhưng kể từ khi chúng tôi not-- Đung Nhưng không có ai của thực sự kiểm tra. Andi PENG: Chúng tôi không bao giờ sẽ thấy điều đó. Nhưng có thể bạn muốn làm chắc chắn tìm kiếm của bạn đang làm việc. Bởi vì nếu tuyến tính của bạn tìm kiếm không hoạt động, sau đó rất có thể là nhị phân của bạn tìm kiếm không phải là đi để làm việc tốt. Bởi vì bạn có tương tự logic trong cả hai. Và không có, nó không thực sự quan trọng. Vì vậy, những người duy nhất bạn sẽ biến trong là sắp xếp và tìm kiếm nhị phân. Yeah. 

Và cũng có thể, rất nhiều trẻ em đã cố gắng để biên dịch helpers.c. Bạn không thực sự cho phép để làm điều đó, bởi vì helpers.c không có chức năng chính. Và do đó, bạn chỉ nên được thực sự biên dịch tạo ra và tìm thấy, vì thấy cuộc gọi helpers.c và các chức năng bên trong nó. Vì vậy, mà làm cho gỡ lỗi một cơn đau ở mông. Nhưng đó là những gì chúng ta phải làm. Đung Bạn chỉ cần thực hiện tất cả, phải không? Andi PENG: Bạn chỉ có thể làm cho tất cả là tốt, yeah. ĐƯỢC. Vì vậy, đó là nó về những gì các pset là yêu cầu tất cả các bạn phải làm. Nếu bạn có bất kỳ câu hỏi, cảm thấy hỏi tôi sau khi phần. Tôi sẽ ở đây, như thế, 20 phút. 

Và yeah, các pset của thực sự không phải là xấu. Các bạn nên có OK. Những điều này, chỉ cần làm theo hướng dẫn. Loại có một cảm giác, một cách hợp lý, những gì nên xảy ra và bạn sẽ bị phạt. Đừng quá sợ hãi. Có rất nhiều mã đã viết ở đó. Đừng quá sợ hãi nếu bạn làm không hiểu những gì tất cả điều đó có nghĩa. Nếu đó là một rất nhiều, nó hoàn toàn tốt. Và đến giờ làm việc. Chúng tôi sẽ giúp bạn có một cái nhìn. 

Đung Với thêm chức năng, chúng tôi nhìn những người lên? 

Andi PENG: Yeah, những người ở trong mã. Trong các trò chơi của 15, một nửa nó đã được viết cho bạn. Vì vậy, những chức năng này đã có trong mã. Yep. Được rồi. Vâng, tốt nhất của may mắn. Đó là một ngày kinh tởm. Vì vậy, hy vọng các bạn không cảm thấy quá Ơû bên trong và mã hóa.