[MÜZİK OYUN] 

PROFESÖR: Pekala. Bu CS50 ve bu Haftanın üç sonu. Yani biz bugün burada değilsin, değil Sanders içinde Bunun yerine Weidner Kütüphanesi'nde Tiyatrosu. Hangi İçinde stüdyo Hauser Studio olarak bilinen, ya da biz Stüdyo H söylüyorlar, ya da yerine getirecektir O şaka zevk biz say--, o aslında var sınıf arkadaşı Mark, çevrimiçi, Kim Twitter üzerinden kadar önerdi. Şimdi hakkında serin ne bir stüdyoda burada olmak Ben bu yeşil çevrili ediyorum ki Duvarlar, bir yeşil ekran veya chromakey, yani CS50 en anlamına gelir konuşmak Bana habersizce üretim ekibi, Şu anda, koyarak olabilir Beni en dünyanın herhangi bir yerinde, iyi ya da kötü. 

Şimdi ne olacak ileride sorun set yatıyor İki, bu hafta sizin elinizde ama problem seti Üç önümüzdeki hafta, Sizinle meydan olacak 15 sözde oyun, Eski bir parti lehine olduğunu aldığınız çağırmak olabilir bir sürü sahip bir çocuk olarak aşağı, yukarı kayabilir sayılar, sol ve sağ, ve bir boşluk var bulmaca, içinde hangi içine aslında bu puzzle parçaları kayabilir. Sonuçta bu alıyorsunuz bazı yarı rastgele sırayla bulmaca, ve hedef olduğunu alt, üst sıralamak, bir ila soldan sağa kadar 15 tüm yol boyunca. 

Ne yazık ki, uygulama Elinizde gerekecek Yazılım olacak dayalı değil, fiziksel olarak. Aslında yazmak zorunda gidiyoruz kodu hangi bir öğrenci veya kullanıcı kutu ile 15 oyun. Ve aslında, hacker 15 oyunun baskı, Bir meydan okuma uygulamak olacak, Bu eski okul sadece oyun Oyun değil, çözme Bunun, tanrı modunu uygulamak, bu yüzden, konuşmak için aslında insan için bulmaca çözer, ipucu sağlayarak, ipucu sonra, ipucu sonra. Bu önümüzdeki hafta Bu yüzden daha fazla. Ama önümüzde ne var. 

Şimdilik hatırlamak bu hafta başlarında eğer sen, biz, bu televizyon dizi film vardı böylece biz sıralama yaptıklarını iyi bilge n o büyük bir üst sınır oldu karesi. Diğer bir deyişle, kabarcık sıralama, seçmeli sıralama, ekleme sıralama, hepsi farklı ise Onların uygulanmasında, çalışan karesi bir n içine intikal Çok kötü durumda zaman. Ve biz genelde varsayalım sıralama çok kötü durum biri senin girdiler tamamen ters. Ve gerçekten de epeyce adımlar attı Bu algoritmaların her uygulamaktır. 

Şimdi sınıfın en sonunda hatırlama, biz kabarcık sıralama karşılaştırıldığında Diğer birine karşı seçim tür karşı biz, zaman birleştirme tür denilen ve bunu alıyor öneriyoruz hafta bir ders avantajı sıfır, böl ve fethet. Ve her nasılsa bir çeşit elde logaritmik sonuçta çalışma süresi, yerine bir şey Bu tamamen kuadratik var. Ve bu oldukça logaritmik değil o biraz daha fazla var. Ama sınıftan hatırlayacak olursak, çok daha hızlı, çok oldu. En bıraktığımız yerden bir göz atalım. 

Seçim karşı Kabarcık sıralama sıralama birleştirme sıralama karşı. Şimdi tüm çalıştırıyorsanız teori, aynı zamanda. CPU aynı hızda çalışıyor. Ama ne kadar sıkıcı bu hissedebiliyorum çok çabuk olmaya devam etmektedir, ve ne kadar hızlı, ne zaman enjekte hafta Zero'nun algoritmalar biraz biz şeyleri hızlandırabilir. 

Yani mark sıralama muhteşem görünüyor. Nasıl sipariş, bunu kaldıraç daha hızlı sayıları sıralamak için. Peki geri düşünelim Bir maddeye biz bu hafta sıfır geri vardı Bir telefon rehberi birisi arıyor, ve hatırlatmak Biz teklif pseudocode, hangi aracılığıyla biz bulabilirsiniz Mike Smith gibi biri, Böyle küçük bir şey görünüyordu. 

Şimdi özellikle bir göz atın çizgisinde 7 ve 8, 10 ve 11, Biz tuttu sayede hangi o döngü neden Tekrar ve tekrar hat 3 gidiş, ve tekrar. Ama biz görebilirsiniz çıkıyor Bu algoritma, burada pseudocode, daha bütünsel biraz. Aslında, ben ne arıyorum Burada ekranda at, için arama için bir algoritma Bazı sayfaları kümesinden Mike Smith. Ve gerçekten biz bu basitleştirmek bu çizgiler 7 ve 8'de algoritması 10 ve 11 sadece bu demek ki ben sarı Burada sunulan ettik. Diğer bir deyişle, Mike Smith, önceki kitapta olduğu Biz adım belirtmek gerekmez Adım şimdi nasıl onu bulmak gitmek. Biz belirtmek zorunda değilsiniz 3. satırda geri dönmek için, neden sadece yerine değil, örneğin, daha genel olarak, in Mike arama Kitabın sol yarısı. 

Bunun tersine, eğer Mike aslında daha sonra kitapta, Neden biz sadece unquote arama alıntı yok Kitabın sağ yarısında Mike. Diğer bir deyişle, neden sadece yok çeşit kendimizi diyerek punt, bu Mike için arama Kitabın alt kümesi, ve bizim mevcut bırakın algoritma bize in Mike aramak için nasıl Kitabın o sol yarısı. Diğer bir deyişle, eden algoritma olup olmadığını çalışıyor Bu bu kalınlıkta bir telefon rehberi, kalınlık, veya herhangi kalınlık. Yani biz recursively can Bu algoritmayı tanımlar. Diğer bir deyişle, ilgili Burada ekran bir algoritma Mike Smith için arama için Bir telefon kitabın sayfaları arasında. Yani hat 7 ve 10, diyelim sadece tam olduğunu söylüyorlar. Ve ben bu terimi bir an kullanmak önce, ve aslında, yineleme terim, şimdi içindir ve bu süreç nasılsa tarafından döngüsel bir şey yapma Eğer zaten kodu kullanarak, ve tekrar çağırarak ve tekrar ve tekrar. Şimdi önemli olacak Biz bir şekilde alt o dışarı ve sonsuz uzun bunu yapmayız. Aksi halde biz gidiyoruz gerçekten sonsuz bir döngüye sahiptir. Ama biz bu fikri ödünç alabilir bakalım Bir özyineleme, yine bir şey yapıyor ve tekrar ve tekrar, çözmek için birleştirme yoluyla sıralama sorunu sıralama, daha verimli. 

O yüzden birleştirmeli sıralama vermek. Hadi bir bakalım. Yani burada pseudocode ile, bir Biz sıralama uygulamak, hangi Birleştirme sıralama denilen bu algoritmayı kullanarak. Ve oldukça basit bu var. N elemanlarının girişi, Diğer bir deyişle, eğer Verilen n elemanlar ve numaralar ve Giriş ya da her neyse harfler, Eğer n elemanları, eğer verilen eğer burada n, 2 den az, sadece geri döner. Sağ? N, O, 2 daha az ise nedeniyle demek ki elemanların listemi boyut 0 ya da 1 ya da değil ve Bu önemsiz durumlarda her iki, liste zaten sıralanır. Hiçbir liste varsa, o tür var. Ve uzunlukta bir liste varsa 1, tabii ki sıralanmış oluyor. Yani algoritma sadece ihtiyacı Gerçekten ilginç bir şey yapmak, biz iki ya da daha fazla varsa elemanlar bize verilen. Yani o sihirli bakalım. Başka elemanların sol yarısını sıralamak Daha sonra elemanların sağ yarısını sıralamak, Sonra sıralanmış yarısını birleştirmek. Ve zihin bükme tür ne Burada, ben gerçekten yapmak olduğunu sana sahip görünüyor Henüz bir şey değil mi? Tüm Ben, bir liste verilir söyledim n elemanlar, sol yarısı sıralamak sonra sağ yarısı, daha sonra sıralanmış yarısını birleştirmek, ama nerede gerçek gizli sos nedir? Algoritma nerede? Peki bu iki satır çıkıyor İlk, elemanların çeşit sol yarısı, ve elemanların çeşit sağ yarısı, özyinelemeli aramalar, tabiri caizse. 

Sonuçta, bu da zaman içinde nokta, ben var hangi bir algoritma elemanlarının bir sürü sıralamak? Evet. Tam burada. Bu ekranda sağ burada ve bu yüzden adım aynı setini kullanabilirsiniz sol yarısı sıralamak için, sağ yarısı ben olabildiğince. Ve gerçekten, tekrar ve tekrar. Yani bir şekilde ya da başka ve biz yakında olacak , birleştirme tür sihirli görmek çok kesin gömülü olduğu çizgi, sıralı yarıları birleştirme. Ve bu oldukça sezgisel görünüyor. Sen seni iki yarıyı almak ve nasılsa, onları bir arada birleştirme, ve biz bu göreceğiz somut bir anda. 

Ama bu tam bir algoritmadır. Ve en tam olarak neden görelim. Peki biz bu aynı verilen konum varsayalım Ekranda burada sekiz elemanları, tek sekize kadar, ama onlar değil görünüşte rastgele sırayla. Ve eldeki hedeftir Bu öğeleri sıralamak için. Eh ben nasıl hakkında gidebilir Tekrar kullanarak yapıyor, Bu pseudocode göre, birleştirmeli sıralama? Ve yine, bu ingrain Aklını, sadece bir an için. Ilk vaka güzel önemsiz, bu 2'den az ise, Sadece yapılması gereken hiçbir iş yoktur, geri dönün. Yani gerçekten sadece üç var adımlar gerçekten akılda tutulması gereken. Tekrar ve tekrar, ben istiyorum olacak sol yarısı sıralamak için, Doğru yarısını sıralamak ve sonra bir kez kendi iki yarısı, sıralanır Ben onları bir arada birleştirmek istediğiniz tek sıralı liste halinde. Yani akılda tutmak. 

Yani burada asıl liste. Bunu bir şekilde bu tedavi edelim Dizi, biz başladık olarak haftada iki, burada a, bellek bitişik blok. Bu durumda, sekiz içeren sayılar, arka arkaya arkaya. Ve şimdi birleştirme tür uygulayalım. Yani ilk sıralamak istiyorum Bu listenin sol yarısı, ve bu nedenle, haydi 4, 8, 6, ve 2 üzerine odaklanır. 

Şimdi hakkında nasıl gitmek Boyut 4 listesini sıralama? Peki ben şimdi düşünmek zorundayız Sol yarısının sol sıralama. Yine, Sadece bir an için geri saralım. Sözde kod, bu ise, ve sekiz elemanları verilen ediyorum, 8 açıkça daha fazladır daha ya da 2'ye eşittir. Yani ilk olgu geçerli değildir. Yani sekiz öğeleri sıralamak, ben birinci elemanların sol yarısını sıralamak Sonra ben o zaman ben birleştirme, sağ yarısını sıralamak İki sıralı yarısı, büyüklüğü 4 her. TAMAM. 

Sadece bana söyledim ama eğer sıralama Şimdi büyüklüğü 4 olan sol yarısı, nasıl sol yarısını sıralayabilirim? Peki ben bir varsa dört elementin giriş, Ben ilk sol sıralamak İki, sonra sağ iki ve sonra onları biraraya birleştirmek. Yani yine, biraz olur Bir zihin burada oyun bükme, Senin yüzünden, tür, var Eğer hikayenin neresinde hatırlıyorum, ama günün sonunda, elemanların herhangi bir numara verilir, İlk sıralamak istiyorum sol yarım, sonra sağ yarısı, daha sonra birlikte onları birleştirmek. En tam da bunu başlayalım. Burada sekiz elemanlarının giriş var. Şimdi burada sol yarısında bakıyoruz. Nasıl dört elementin sıralayabilirim? Peki ilk sol yarısını sıralayın. Şimdi nasıl sol yarısını sıralayabilirim? Eh iki unsuru verildi. Yani bu iki unsur sıralamak edelim. 2 ya da daha büyük 2'ye eşit, tabii. Böylece ilk vaka geçerli değildir. 

Yani şimdi sol sıralamak zorunda Bu iki eleman yarısı kadardır. Sol yarısı, tabii ki sadece 4'ü. Peki nasıl bir elemanın bir listesini sıralamak mı? Eh şimdi, bu özel temel durum kontör, tabiri caizse, geçerlidir. 1, 2'den küçük olduğunda, ve benim listesinin gerçekten boyutu 1 göstermektedir. Yani ben sadece dönün. Ben bir şey yapmıyorum. Ve gerçekten, ben var ne bakmak yapılan 4 zaten sıralanır. Sanki zaten değilim Burada kısmen başarılı. 

Şimdi bu tür aptalca görünüyor iddia, ama bu doğrudur etmek. 4 boyutunda 1 listesidir. Zaten sıralanmış oluyor. O sol yarısı. Şimdi sağ yarısını sıralayın. Benim giriş 8, tek unsurdur Benzer şekilde, zaten sıralanır. Aptal, çok, ama yine Bu temel prensip Şimdi inşa etmek için izin gidiyor Bunun başarıyla. 4 şimdi, 8 sıralanır sıralanır Bu son adım neydi? Bu nedenle, üçüncü ve son adım, herhangi bir zaman, bir liste, geri çağırma sıralama ediyoruz , iki yarısını birleştirmek oldu Sol ve sağ. O yüzden tam olarak yapalım. Benim sol yarısı, tabii ki, 4'tür. Benim sağ yarısı 8'dir. 

Yani bu yapalım. Önce tahsis gidiyorum bazı ek bellek, Ben burada temsil edeceğiz sadece ikincil bir dizi olarak, bu sığacak kadar büyük. Ama uzanan hayal edebiliyorum Bu dikdörtgen tüm uzunluğu, daha sonra gerekirse. Ben 4 alıp 8 ve birleştirme nasıl Birlikte büyüklüğü 1 bu iki liste? Burada da oldukça basit. 4 Sonra, önce gelir 8 geliyor. Ben sıralamak isterseniz Çünkü sol yarım, sonra sağ yarısı, ve daha sonra bu iki yarısı birleştirme Birlikte, sıralı sırayla, 4 Sonra, önce gelir 8 geliyor. 

Yani biz bile ilerleme gibi görünüyor Ben herhangi bir fiili çalışma yapmadım ama. Biz hikayenin neresinde Ama unutmayın. Biz aslında sekiz elemanları aldı. Biz 4 olan sol yarısı, sıralanmış. Sonra sol yarısı kriteri 2 oldu sol yarısı, bir. Ve işte başlıyoruz. Biz o adımı bitirdik. 

Biz sıralama ettik Yani eğer biz şimdi, 2 yarım bıraktı 2 sağ yarısını sıralamak gerekir. Yani 2 sağ yarısı Burada bu iki değer, 6 ve 2. O halde şimdi büyüklükte bir giriş atalım 2, ardından da sol yarısı sıralamak ve sağ yarısı, ve sonra onları biraraya birleştirmek. Peki nasıl büyüklükte bir listesini sıralamak do 1, sadece 6 sayı içeren? Zaten bitti. Büyüklüğü 1 Bu liste sıralanır. 

Ben başka bir listesini sıralamak nasıl Boyut 1 olarak adlandırılan sağ yarısını. Eh o da, zaten sıralanır. 2 numaralı yalnız. Yani şimdi ben iki yarısı var, sol ve Tamam, ben onları bir araya birleştirmek gerekir. Gidip kendime bazı ekstra boşluk vereyim. Ve orada, 2 koyun daha sonra 6 Orada, bu suretle Bu listeyi sıralama, sol ve sağ ve sonuçta birlikte birleştirme. Yani biraz daha durumdayım. Ben, bitmiş çünkü değilim açıkça 4, 8, 2, 6 istediğim son sipariş değildir. Ama şimdi, bu boyutta 2 iki listeleri vardır her ikisi de sırasıyla kriteri edilmiştir. Yani şimdi zihninizi en içinde geri sarma durumunda göz, ​​bu bizi nereye mi? Daha sonra, sekiz elemanları ile başladı ben 4, sol yarısında aşağı whittled Daha sonra 2 sol yarısı ve Daha sonra 2 sağ yarısı, Ben sol sıralama, bu nedenle, bitmiş 2 yarısı ve 2'nin sağ yarısı, Üçüncü ve son adım burada ne var? Birlikte birleştirmek zorunda büyüklüğü 2 iki listeleri. O yüzden önümüzdeki gidelim. Ve burada ekranda vermek Bana bazı ek bellek, teknik olsa da, ben fark ettik boşluk kadar üst bir sürü var Orada. Özellikle olmak istiyorum verimli kullanım alanı bilge, Ben sadece elemanları hareketli başlayabileceğini ileri ve geri, alt ve üst. Ama Görsel netlik için, Ben, aşağıda bir yere koymak için gidiyorum güzel ve temiz şeyleri tutmak için. 

Yani büyüklüğü 2 iki liste var. İlk liste 4 ve 8 sahiptir. İkinci liste 2 ve 6 sahiptir. Hadi şu birleşmesine izin Birlikte sıralı sırayla. 2, tabii ki, önce gelir, daha sonra 4, sonra 6, daha sonra 8. Ve şimdi biz almak gibi görünüyor ilginç bir yerde. Şimdi ben kriteri ettik yarısı listelemek ve tesadüfen, bu kadar tüm çift sayılar, ancak gerçekten, sadece bir tesadüftür. Ve ben şimdi sol sıralamış Yarım, 2, 4, 6 ve 8 olacak şekilde. Hiçbir şey sipariş dışında. Bu ilerleme gibi hissediyor. 

Ben ettik gibi şimdi hissediyor Şimdi sonsuza konuşuyor, ne yani eğer bu görülecektir Algoritma gerçekten daha verimli olduğunu. Ama biz doğru gidiyoruz Süper yöntemli. Bir bilgisayar, tabii ki, bunu böyle yapardı. Yani biz neredeyiz? Biz sekiz elemanları ile başladı. Ben 4 sol yarısını sıralanır. Ben ile yapılabilir gibi görünüyor. Şimdi bir sonraki adım için 4 sağ yarısını sıralayın. Ve bu bölüm gidebiliriz Biraz daha fazlasından hızlı, sen her ne kadar Sadece, geri sarma ya da duraklatmak için hoş geldiniz En içinden düşünüyorum Kendi hızı, ama ne Şimdi bir fırsat olduğunu var Dört kesin aynı algoritmayı yapmak Farklı numaralar. 

O yüzden önümüzdeki gidelim ve odaklanmak biz buradayız sağ yarısı. Bu sol yarısı sağ yarısı, ve şimdi sol sol yarısı O sağ yarısında yarısı, ve ben boyutta bir listesini sıralamak nasıl 1 Sadece 1 numara içeren? Çoktan bitti. Ben bir liste için aynı şeyi nasıl sadece 7 içeren büyüklüğü 1? Çoktan bitti. O zaman bu yarısı için üç adım Bu iki unsur birleştirmek olduğunu büyüklüğü 2, 1 ve 7 yeni liste halinde. Tüm yapmış görünmemektedir o kadar ilginç bir çalışma. Bir sonraki ne görelim. Ben sadece sol yarısını kriteri Benim asıl girişin sağ yarısı. Şimdi hakkını sıralamak edelim 5 ve 3 içeren yarısı. Tekrar solda bakalım Yarım, sıralı, sağ yarısı, sıralı, ve birlikte bu iki birleştirme bazı ek uzaya, 3 Daha sonra, önce gelir 5 geliyor. Ve şimdi, biz sıralamış sağ yarısında sol yarısı Özgün bir sorun, ve Doğru yarısı sağ yarısı Özgün bir sorun. Üçüncü ve son adım nedir? Peki birlikte bu iki yarısını birleştirmek için. Yani beni kendime biraz olsun izin Yine ekstra alan, ancak, ben Bu yedek alan kadar üst kullanıyor olabilir. Ama biz devam edeceğiz görsel basit. Şimdi beni 1'de birleşmesine izin ve daha sonra 3 ve 5, ve daha sonra 7. Böylece şimdi beni terk Orijinal problemin sağ yarısı Bu mükemmel olarak sıralanmış. 

Peki ne kalır? Ben deyip duruyorsun gibi hissediyorum tekrar ve tekrar aynı şeyler, ama bu yansıtıcı var: Biz özyineleme kullanıyoruz aslında. Bir kullanarak süreci tekrar ve tekrar algoritması, küçük alt kümeleri üzerinde orijinal sorun. Yani şimdi sol sıralamış Orijinal sorunun yarısı. Ben sağ sıralı yarısı var Özgün bir sorun. Üçüncü ve son adım nedir? Oh, birleştirme ediyor. O yüzden böyle yapalım. En bazı ek tahsis edelim Bellek, ama Tanrım, biz Şimdi her yerde koyabilirsiniz. Biz çok alan mevcut olması Bize, ama biz basit tutacağız. Yerine geri gitmeyi ve ileri bizim orijinal bellek ile, Sadece bunu diyelim görsel aşağıda aşağı birleştirme kadar bitirmek için sol yarım ve sağ yarım. 

Birleştirerek Eee, ne yapmam gerekiyor? Ben sırayla öğeleri almak istiyorum. Yani sol yarısı bakarak, İlk sayı 2 görüyoruz. Ben sağ yarısında bakmak, Ben ilk sayısını görmek çok açıktır ki, 1 olan sayı, ben dışarı koparmak istiyor musunuz ve benim son listenin ilk koydu? Tabii ki, 1. Şimdi aynı soruyu sormak istiyorum. Sol yarısı, ben ettik Hala sayı 2 aldım. Sağ yarısında, Ben 3 numaralı var. Hangisini seçmeliyim istiyorsun? Tabii ki, sayı 2 ve Şimdi adaylar dikkat sağda solda, 3 4 vardır. En, tabii ki, 3 seçelim. Şimdi adaylar 4 üzerinde sağ sol, 5. Biz, tabii ki, 4 seçin. Sağda solda, 5 6. Biz, tabii ki, 5 seçin. Sağda solda, 7 6. Biz 6 seçin ve sonra biz 7 seçin, ve sonra biz 8 seçin. Işte. 

Kelimelerin Yani çok sayıda sonra, biz Sekiz elemanların listesini sıralamış sekize kadar birinin bir liste halinde, Bu, her adımda artıyor ama ne kadar zaman yaptım bunu yapmak için bizi. Eh ben kasten ettik resimsel koydu şeyler dışarı Burada, böylece biz tür bakın veya bölünme takdir fetih o oluyor oldu. 

Eğer sonrasında geri bakmak Nitekim eğer, Ben bu noktalı çizgiler tüm bıraktım Yer tutuculara yapabilirsiniz, tür, tersten görmek, ne tür geri bakmak Tarih şimdi, benim orijinal liste büyüklüğü, 8, tabii ki,. Ve sonra önceden, ben büyüklüğü 4 iki liste ile ilgili, ve daha sonra büyüklüğü 2 dört listeleri, ve daha sonra büyüklüğü 1 sekiz listeleri. 

Peki bu ne, tür, size hatırlatmak? Kuyu, gerçekten, herhangi bir biz ettik algoritmalar bugüne kadar baktı nerede böl ve bölme ve bölme, şeyleri tekrar sahip tutmak ve yine, bu genel bir fikir ile sonuçlanır. Ve böylece bir şey var logaritmik burada olacak. Ve n oldukça günlüğü değil ama logaritmik bileşen var biz sadece yaptığına. 

Şimdi aslında nasıl düşünelim. Yani yine, n log oldu büyük bir çalışma süresi, Biz böyle bir şey yaptım ikili arama, biz şimdi dediğimiz gibi, böl ve fethet stratejisi hangi aracılığıyla Mike Smith bulundu. Şimdi teknik olarak. Bu bile, n log tabanı 2 var En matematik derslerinde olsa, 10 genellikle varsayıyorum temelidir. Ama bilgisayar bilim adamları hemen hemen her zaman düşünmek ve tabanının 2 açısından konuşmak, Böylece biz genellikle sadece günlüğünü demek n yerine n log tabanı 2, ama onlar tam bir konum ve bilgisayar dünyasında aynı bilim ve bir kenara olarak, Bir sabit faktör var İkisi arasındaki fark, bu yüzden Daha resmi nedenlerle, zaten tartışmalı. 

Ama şimdi, biz umurumda ilgili bu örnektir. Yani örnek ispat etmeyelim, ama en En sayıların bir örnek kullanın elinde bir sağlamlık denetimi olarak, eğer olacaktır. Yani daha önce formül günlüğü üssü oldu N 2, ancak bu durumda n budur. Ben n orijinal numaralar vardı, ya da 8 Orijinal sayının özellikle. Şimdi biraz oldu süre, ama ben oldukça emin günlük taban 2 8 3 olan değer, ve aslında ne olduğunu hakkında güzel 3 kaç kez tam sayıdır Eğer bir liste bölebilirsiniz olduğunu tekrar ve tekrar uzunluğunda, 8, ve yine, kalacaksın kadar Sadece büyüklük 1 listeleri ile. Sağ? 8, 4 gider 2'ye gider 1 gider ve işte tam olarak yansıtıcı resim biz sadece bir an önce vardı. Bu yüzden biraz aklı olarak nerede kontrol logaritma aslında yer almaktadır. 

Yani şimdi, başka ne burada söz konusu olan? n. Böylece her fark zaman, liste bölmek Tarihte tersten olsa Burada, ben hala n şeyler yapıyordu. Bu birleştirme aşaması olması gerekmektedir Ben, sayıların her birine dokunmak doğru kaydırın amacıyla kendine uygun bir yer. Yani olsa da bu yüksekliği diyagramı, n ya da 3'ün günlük boyutunu n olduğu özel olarak ise, bir başka deyişle, Burada üç tümen yaptı. Ne kadar iş ben yatay yaptın Bu tabloda her seferinde boyunca? 

Eh, ben n adımları yaptım Ben ettik çünkü eğer, işe , dört elementin ve dört unsuru var ve ben onları biraraya birleştirmek gerekir. Ben geçmesi gerekir Bu dört Bu dört, sonuçta onları birleştirmek için Geri sekiz unsurları içine. Tersine ben sekiz parmakları var I do not olan, buraya ve sekiz fingers-- sorry-- Ben ettik Eğer Buraya dört parmak var Ben, dört parmak yaptığımız Buraya, yapmam, hangi Daha sonra, aynı var: örnek olarak önce ben yaparsam olsa sekiz parmak var Ben, biraz, yapabileceğiniz toplam. Tam burada yapabilirsiniz sonra ben kesinlikle can Bu listelerin her birleştirme Birlikte boyutu 1. Ama ben kesinlikle bakmak zorunda her elemanın tam olarak bir kez. Yani bu işlemin yüksekliği, günlük n, Bu işlem genişliği, yani, konuşma bu yüzden görünüyor, ne n nihayetinde olduğunu olması büyüklük n kez çalışma süresi n oturum açın. 

Diğer bir deyişle, bölünmüş Liste, günlük n kere, ama biz yaptığımız her seferinde, biz elemanların her biri dokunmak Onları birleştirmek için Hep birlikte, hangi adımı n adet, bu yüzden var n kat n log edildi veya bir bilgisayar bilimcisi söyleyebilirim, asimptotik, hangi büyük kelime olurdu Üst açıklamak için Çalışan bir zaman bağlı, biz büyük bir o çalışan log n zaman, tabiri caizse. 

Şimdi, bu, çünkü önemli çalışan süreleri ne olduğunu hatırlamak kabarcık sıralama ve seçim ile sıralama ve yerleştirme sıralama, ve mevcut hatta birkaç diğerleri n biz nerede kalmıştık oldu karesi. Ve sen, biraz burada görebilirsiniz. N karesi ise besbelli n kat n, ama burada biz n defa n log, ve biz zaten biliyoruz hafta sıfır, bu günlük n, logaritmik, bir şey lineer daha iyidir. Sonuçta, resim hatırlama Kırmızı ve sarı ile Biz çekti ve yeşil çizgiler, Yeşil logaritmik hat çok daha düşük oldu. Ve bu nedenle, çok daha iyi ve daha hızlı Düz sarı ve kırmızı çizgiler yerine, n defa gerçekten isimli log n, daha iyi n kat daha n veya n karesi. 

Yani biz var gibi görünüyor Bir algoritma birleştirme tespit sıralama çok çalışan olduğunu Daha hızlı zamanı ve aslında, bu yüzden, bu hafta başlarında, zaman var Biz kabarcık arasındaki yarışma gördüm sıralama, seçme sıralama, birleştirme ve sıralama, sıralama gerçekten kazandı birleştirme. Ve gerçekten de, biz bile beklemedi kabarcık sıralama ve seçme sıralama için bitirmek için. 

Şimdi bir başka geçmek atalım Bu da, biraz daha fazla resmi perspektif, sadece durum, bu daha iyi rezonansa Bu üst düzey tartışma daha. Yani burada algoritma tekrar var. Kendimize soralım, Ne çalışma süresi Bu çeşitli adımlar algoritmaları biridir? İlk bölün edelim Olgu ve ikinci vaka. IF durumunda IF ve ELSE, Burada n, 2 den daha az ise, sadece geri döner. Zaman sabiti gibi hissediyor. Bu iki adımda gibi, tür, var, Burada n, 2 den daha az ise, o zaman geri döner. Ama biz Pazartesi günü yaptığı açıklamada olduğu gibi, sabit zaman, ya da 1 o büyük, iki adım, üç olabilir, adım da 1000 adım. Önemli olan olmasıdır adımda sabit bir sayı. Yani sarı pseudocode vurgulanan Burada, biz onu arayacağım, çalışır zaman sabiti. Yani daha resmi ve Bu ki-- gidiyoruz ölçüde olacak hangi biz n T şimdi-- bu hakkı resmileştirmek, Bir sorun çalışma süresi bu, girdi olarak alır n birşeyler , biri o büyük eşittir Burada n, 2 den az ise. Yani o şartına var. N daha az EĞER Yani, açık olmak 2, biz o zaman, çok kısa bir listesi var n çalışma süresi n, T, 1 ya da 0, bu çok özel durumda, Sadece sabit zaman olacak. O birini almaya gidiyor ne olursa olsun, iki adım adım. Bu adımlar sabit numara. 

Yani sulu kısım mutlaka olmalı pseudocode diğer olgu. ELSE durumda. Elementlerin sırala sol yarısı, sıralama doğru elemanların yarısı, sıralı yarısını birleştirmek. Bu adımların her ne kadar sürer? Peki, eğer çalışan n elemanlarını sıralamak için zaman , o da çok diyelim genel olarak, T, n, Daha sonra sol sıralama elemanların yarı ise, bir tür, demek gibi, 2 ile bölündüğünde, n T, ve benzer sağ yarısını sıralama unsurlardan olduğunu tür, demek gibi, N T 2 ayrılır ve daha sonra sıralanmış yarılarını birleştirme. Eh bende eğer bazı Burada elemanların sayısı, dört ve bazı numarayı gibi Burada elemanların, dört gibi, ve ben bu dört her birleştirmek zorunda içinde ve bu dört her biri bir arada arka arkaya, böylece sonuçta ben sekiz elemanları var. O n adımlarının o büyük olduğunu hissediyor? Ben parmaklarını ve her n var ise Onları yerine birleştirilecek vardır, başka n adımlar gibi. 

Yani aslında formulaically, Biz bu ifade edebiliriz ilk başta biraz scarily olsa bakışta, ama bir şey Bu tam olarak bu mantığı yakalar. Çalışma süresi, T n, IF n daha büyük ya da 2'ye eşittir. Bu durumda, ELSE durumda, n, T 2 ile bölündüğünde, n artı T 2'ye bölünür, artı n o büyük, bazı adım doğrusal sayısı belki tam olarak n, belki 2 kere n, ancak kabaca n emir. Böylece de nasıl biz ise formulaically bu ifade. Şimdi sürece bu bilemeyiz Eğer kafanızda o kaydettik ya o kadar bakmak geri kitabının, o Biraz olabilir sonunda sayfasını hile, ama bu, gerçekten, gidiyor n günlük n o büyük bize ver, nüks çünkü Eğer ekranda burada görüyoruz Aslında birlikte, dışarı yapsam örneklerin sonsuz sayıda, ya formulaically yaptım, sen-cekti Bu görüyoruz bu formüle çünkü kendisi t, özyinelemelidir n sağda bir şey yüzünden, soldan n adet t ve bu can Aslında ifade, sonuçta, n log n gibi büyük gitmek. Ikna değilse, işte Şimdilik sadece para cezası Gerçekten, işte o, iman almak, Bu nüks neden, ne ama bu sadece biraz daha seyir matematiksel yaklaşım Birleştirme tür çalışan anda tek başına pseudocode dayalı. 

Şimdi bir biraz atalım Bunun tüm havalandırma, ve bir göz atın Bazı eski senatör, kim Biraz tanıdık görünebilir, kim Google'ın Eric ile oturdu Bir röportaj için bir süre önce Schmidt, Sahnede, bütün bir demet önünde insanların, sonuçta bahsediyoruz Bir konu, bu oldukça geç tanıdık. Hadi bir bakalım. 

Eric Schmidt,: Şimdi Senatör, Eğer Google'da buradayız ve ben düşünmek istiyorum Bir iş görüşmesi olarak başkanlığı. Şimdi başkan olarak bir iş bulmak zor. BAŞKAN OBAMA: Doğru. Eric Schmidt,: Ve sen Şimdi [duyulamaz] yapacaksın. O Google'da bir iş bulmak da zor. BAŞKAN OBAMA: Doğru. 

Eric Schmidt,: Biz sorularım var, ve bizim adayların soru sormak, ve bu bir Larry Schwimmer değil. 

BAŞKAN OBAMA: Tamam. 

Eric Schmidt,: ne olacak? Siz Şaka mı sanıyorsun? Tam burada. En etkili yolu Nedir Bir milyon 32 bit tamsayı sıralamak? 

BAŞKAN OBAMA: Şey-- Eric Schmidt, Bazen, Belki üzgünüm, belki-- BAŞKAN OBAMA: Hayır, hayır, Hayır, hayır, hayır, bence-- Eric Schmidt,: Bu bu-- değil BAŞKAN OBAMA: Ben düşünüyorum, ben kabarcık düşünüyorum Sıralama gitmek yanlış bir yol olacaktır. Eric Schmidt,: Hadi. Onu kim söyledi? TAMAM. Ben bilgisayar bilimi vermedi on-- 

BAŞKAN OBAMA: Biz ettik Orada bizim casusları var. PROFESÖR: Pekala. Şimdi arkamızda bırakalım algoritmaların teorik Dünyanın asimptotik analizinde bunların ve bazı konularda geri dönmek Haftanın sıfır ve bir, ve baştan bazı eğitim tekerlekleri kaldırmak için, eğer sen. Eğer gerçekten anlamak Böylece sonuçta yere kadar, ne , sizi başlık altında oluyor Yazmak derlemek ve programları çalıştırmak. Bu oldu, özellikle hatırlayın Biz baktı ilk C programı, Bir kanonik, basit bir program türlü, göreceli olarak, burada, bu Merhaba Dünya yazdırır. Ve ben süreç, dedi çağırmak olduğunu Bu kaynak kodu geçer tam olarak bu olduğunu. Sen kaynak kodu almak, pas bir derleyici ile, Clang gibi ve dışarı o nesne kodunu geliyor Bu, sıfır ve olanlar gibi görünebilir bilgisayarınızın CPU, merkezi o işlem ünitesi veya beyin, sonuçta anlar. 

O bir olduğunu çıkıyor Bir basitleştirme bit, Biz şimdi olduğunuzu pozisyon dışında kızdırmak için Gerçekten oldu ne olduğunu anlamak için başlık altında oluyor Çalıştırdığınız her zaman Clang, veya daha genel olarak, Her zaman, bir program yapmak Marka ve CF 50 IDE kullanarak. Özellikle, malzeme gibi Bu ilk olarak oluşturulur ne zaman ilk programı derlemek. Diğer bir deyişle, sizi Kaynak kodunuzu almak ve ilk ne var, derlemek Clang tarafından çıkarılan varlık montaj kodu olarak da bilinir bir şeydir. Ve aslında, tam olarak bu gibi görünüyor. 

Ben bir komut koştu Daha önce komut satırı. Clang çizgi başkentin s merhaba.c, ve bu dosyayı oluşturan Beni çağırdı hello.S için, bunların içinde tam olarak edildi Bu içeriği ve biraz daha Yukarıda ve daha aşağıda biraz ama juiciest koyduk Burada ekranda bilgiler. Eğer yakından bakarsanız, görürsünüz en az birkaç tanıdık anahtar kelimeler. Biz üstünde ana var. Biz ortada aşağı printf var. Ve biz de dünyanın merhaba var aşağı aşağıda tırnak içinde ters eğik çizgi n. 

Burada başka ve her şey çok düşük seviyede olduğu talimatları bilgisayarınızın CPU anladığı. Bellek taşımak CPU talimatları etrafında, bellekten bu yük dizeleri, ve sonuçta, baskı Ekranda şeyler. Şimdi ne olacak sonra bile olur Bu derleme kodu üretilir? Sonuçta, gerçekten yapmak, Hala nesne kodu oluşturmak. Ama adımlar gerçekten var başlık altında devam Böyle biraz daha bak. Kaynak kodu, montaj kodu olur bu daha sonra nesne kodu olur ve burada ameliyat sözler, o Eğer kaynak kodu derleme yaparken, sonra dışarı montaj kodu ve gelir Eğer derleme kod birleştirmek zaman, dışarı nesne kodunu geliyor. 

Şimdi Clang, süper sofistike derleyiciler bir sürü gibi, ve bu adımların hepsini yapıyor Birlikte ve mutlaka yok çıkış herhangi bir ara Hatta görebilirsiniz dosyaları. Bu sadece şeyler derler, Hangi genel bir terimdir olduğunu Tüm bu yöntem tarif edilmiştir. Ama eğer gerçekten istiyorsanız Özellikle olmak, var çok daha fazla hem de oraya gidiyor. 

Ama aynı zamanda o şimdi bile düşünelim süper basit bir program, merhaba.c, Bir işlevi çağrılır. Bu printf denir. Ama ben, gerçekten, printf yazmadım Bu tabiri caizse, c ile birlikte geliyor. Bu bir işlev hatırlama var Standart io.h, beyan hangi Bir başlık dosyası, hangi Bir konu aslında edeceğiz olduğunu uzun zaman önce daha derinlemesine dalmak. Ama bir başlık dosyasıdır tipik eşlik Bir kod dosyasında, kaynak kodu dosyası, bu yüzden tarafından Standart io.h bulunduğunu gibi çok 

Bazen önce, birisi, ya da birileri de yazdı in standart io.c adlı bir dosya ki bu gerçek tanımlar, veya printf uygulamaları, ve diğer fonksiyonların salkımları Aslında yazılır. Biz sahip düşünün Yani, verilen Buradan sola, hello.c üzerine, o zaman derlenmiş, bile, hello.S bize verir Clang bir yerde tasarruf rahatsız etmiyor biz onu görmek ve bu montaj kodu olabilir hello.o, içine monte olur ki Nitekim, varsayılan adıdır Eğer kaynak derleme zaman verilen nesne koduna kod ama değil Henüz çalıştırmak için oldukça hazır, Başka bir adım için ne var ve var Geçtiğimiz birkaç için oluyor hafta, size belki topraklarındaki. 

Özellikle bir yerde CS50 IDE ve bu, çok bir biraz olacak Bir an için oversimplification, orada, ya bir zamanlar oldu, Standart io.c adlı bir dosya, Birisi derlenmiş olduğu Standart io.s veya eşdeğeri, Birisi daha sonra monte olduğunu Standart io.o içine ya da bir içine çıkıyor biraz daha farklı bir dosya Farklı bir olabilir biçimi tamamen uzantıyı dosya, teoride ve kavramsal, tam ama Bu adımlar çeşit gerçekleşmesi gerekiyordu. Demek şimdi bu kadar Hangi Ben bir program yazıyorum zaman, merhaba.c, sadece diyor, merhaba dünya, ve başkasının kodu kullanıyorum Bir zamanlar üzerine printf gibi Zaman, standart io.c adlı bir dosyaya, Daha sonra her nasılsa gözlerimi almak zorunda Nesne kodu, benim sıfırlar ve olanları, ve bu kişinin nesne kodu veya sıfırlar ve olanları, ve her nasılsa içine bunları birbirine bağlamak Bu, merhaba denilen son bir dosya, yer alır sıfır tüm ve benim ana fonksiyonundan olanlar ve sıfırlar tüm ve printf için olanlar. 

Ve gerçekten de, son bir süreçtir denilen nesne kodunu bağlama. Bunu çıktısı ise bir yürütülebilir dosyadır. Yani adalet, en gün, hiçbir şey sonuna Haftanın tek beri değişti, ne zaman İlk program derleme başladı. Gerçekten de, tüm bu olmuştur Kaputun altında oluyor, ama şimdi biz bir konumda konum Nerede biz aslında can Bu çeşitli adımlar ayrı kızdırmak. Ve gerçekten de, sonunda Günün biz hala birler ve sıfırlar, sol hangi büyük segue şimdi aslında C bir özelliği, yani biz büyük olasılıkla kaldıraç yaşadım değil Bugüne kadar, bit operatörleri olarak da bilinir. Diğer bir deyişle, bu noktaya kadar, her biz ettik C C veya değişkenler verilerle ele, Biz gibi şeyler yaşadım karakter ve mantarlar ve ins ve uzun ve çiftler ve benzeri ama bunların hepsi en az sekiz bit. Henüz mümkün olmamıştım bireysel bitlerin işlemek, Hatta tek bir bit olsa da, biz Bir 0 ve 1 temsil edebilir biliyorum. Şimdi C çıkıyor, sen Bireysel bit erişebilirsiniz, Eğer sözdizimi biliyorsanız, hangi ile onlara ulaşmak için. 

Yani bir göz atalım Bitsel operatörleri. Yani resimdeki birkaç sembolleri olduğunu biz tür, çeşit, daha önce görmüştüm. Ben, dikey bir ve işareti bkz bar ve yanı sıra bazıları, ve bu işareti işareti hatırlamak Daha önce gördüğümüz bir şeydir. Eğer varsa mantıksal AND operatörü, İkisi birlikte, ya da mantıksal OR Operatör, nerede iki dikey çubuk var. Bit operatörleri, yaparız tek tek bit üzerinde işlem bkz sadece tek bir işareti kullanın Tek dikey çubuk, şapka simgesi Bir sonraki küçük geliyor tilde ve sonra sol braket dirseğini sola veya Sağ dirsek sağ ayraç. Bunların her biri farklı anlamları vardır. 

Aslında, en bir göz atalım. Eski okul bugün ve kullanım gidelim geçmişin bir dokunmatik ekran, bir beyaz tahta olarak da bilinir. Ve bu beyaz tahta bize izin gidiyor Bazı oldukça basit semboller ifade etmek, ya da daha doğrusu bazı oldukça basit formüller, biz sonuçta o can Kaldıraç, sipariş Bireysel erişmek için C program dahilinde bit. Diğer bir deyişle, hadi yapalım. Bir için diyelim ilk tartışma işareti ile ilgili anı, Hangi lojik AND operatörüdür. Diğer bir deyişle, bu sağlayan bir operatör Bana bir sol değişken olması tipik olarak, ve bir sağ-taraf değişkeni ya da ayrı ayrı bir değer, bu eğer ve Birlikte onları bana son bir sonuç verir. Yani ne demek istiyorsun? Bir programda, bir değişken varsa Bu değerlerin mağaza biri olduğunu, ya en basit tutmak ve sadece izin bireysel sıfırları ve olanları yazmak, işareti operatörü nasıl çalıştığını burada. 0 işareti 0 0 eşit olacak. Şimdi neden? 

Bu çok benzer Boole ifadeleri, biz bugüne kadar ele aldık. Tüm sonra düşünüyorsanız, 0 Yanlış, 0, false false ve yanlış Konuştuğumuz gibi olduğunu mantıksal, ayrıca yanlış. Yani biz de burada 0 olsun. Eğer 0 işareti alırsak 1, iyi ki de çünkü bunun için, 0 olacak Sol taraftaki sentezleme, doğru ya da 1 olduğu gerçek ve doğru olması gerekir. Ama burada biz yanlış var ve gerçek ya da 0 ve 1. Şimdi yine, biz 1 işareti varsa 0, de, 0 olacak ki, ve biz 1 işareti 1 varsa, Sonunda biz 1 bit var. Başka bir deyişle Yani, biz yapmıyoruz Bu operatör ile ilginç şey Henüz, bu işareti operatörü. Bu lojik AND operatörü var. Fakat bu katkı maddeleri şunlardır hangi aracılığıyla yapabileceğimiz yakında göreceğimiz gibi ilginç şeyler. 

Şimdi sadece tek bakalım Burada sağ tarafta üzerinde dikey çubuk. Ben 0 bit ve I varsa VEYA onunla, bit VEYA operatörü başka 0 bit, bu beni 0 vermek için gidiyor. Ben 0 bit ve OR onu birlikte alırsak 1 bit, sonra 1 alacağım. Ve aslında, sadece için netlik, beni geri dönelim O yüzden benim dikey çubuklar 1'ler için yanlış değildir. Bana bütün yeniden edelim zaman 1 biraz daha var Ben eğer açıkça, böylece bir sonraki bakın 1 OR 0, bu 1 olacak olan, ve ben 1 VEYA 1 a varsa, de bir 1 olacak. Yani mantıklı bakın VEYA o olabilir Operatör çok farklı davranır. Bu 0 bana veriyor Veya 0 0 verir ama bana her kombinasyon bana 1 verir. Çok uzun bir tane 1 si Formül, sonuç 1 olacak. 

AND tersine, Operatör, işareti, Ben iki 1'lerinizi varsa denklemi, ben aslında 1 out alırım. Şimdi birkaç diğer var Operatörler de. Bunlardan biri biraz daha karmaşıktır. Bu yüzden bana go ahead ve silelim Bu biraz alan boşaltmak için. Ve en az bir göz atalım Sadece bir an için şapka sembolü. Bu genellikle bir olan karakter yazabilirsiniz Klavyeniz tutma Shift ve senin ABD'nin üstüne numaraları sonra bir Klavye. 

Yani bu özel olduğunu YA operatör özel VEYA. Yani biz sadece VEYA operatörü gördüm. Bu özel VEYA operatörüdür. Aslında fark nedir? Peki Sadece formülüne bakalım, ve sonuçta madde olarak kullanmak. 0 XOR 0. Ben söylemek için gidiyorum her zaman 0'dır. Bu XOR tanımı var. 0 XOR 1 1 olacak. 1 XOR 0, 1 olacak ve 1 XOR 1 olacak? Yanlış? Veya doğru? Bilmiyorum. 0. Şimdi ne olacak oluyor burada? Peki düşünmek Bu operatörün adı. YA şekilde isim, tür, anlaşılacağı Cevap sadece olacak 1 giriş özel ise, münhasıran farklı. Yani burada girişler Aynı nedenle çıkış 0'dır. İşte girişler Aynı nedenle çıkış 0'dır. İşte çıkışlar bunlar farklı are özeldir ve bu nedenle çıkış 1'dir. Bu yüzden çok benzer VE, bu çok benzer ya da daha doğrusu o çok benzer YA, ancak özel bir şekilde. Bu on, artık 1 iki 1'lerinizi çünkü, ve özel olarak, bunlardan sadece biri. Pekala. Ne diğerleri? Peki tilde, bu arada, bir gerçekten güzel ve basit, minnetle. Ve bu bir tek terimli bir anlamına gelir operatörü Bu, sadece bir giriş olarak uygulanır tek işlenen, tabiri caizse. Değil sol ve sağ için. Başka bir deyişle, bir tilde alırsan 0 cevap karşısında olacak. Ve sen 1 tilde alırsak, Cevap karşısında olacak. Yani tilde operatörüdür biraz inkâr etmenin bir yoludur, veya bir biraz saygısız 0-1 ya da 0 1. 

Ve nihayet bizi bırakır Sadece son iki operatörlerle, Sol shift sözde ve sağ shift operatörü sözde. En nasıl bu işin bir göz atalım. Yazılı sola kaydırma operatörü, Böyle iki köşeli parantez içeren, aşağıdaki gibi çalışır. Eğer sola benim giriş, ya da benim işlenen, kaydırma operatörü oldukça basit bir 1'dir. Ve ben sonra bilgisayarı anlatmak 1, yedi yerde söylüyorlar vardiya sol Sonuç I sanki olduğunu Bu 1 almak ve taşımak üzerinde yedi yerde Sol ve varsayılan olarak, Biz varsaymak için gidiyoruz sağa alan sıfır ile doldurulur olacak. Bir başka deyişle, 1 vardiya 7 gidiyor sol ardından 1 bana vermek üzere 1, 2, 3, 4, 5, 6, 7 sıfır. Bir bakıma Yani, yapmanız gereken 1 gibi küçük bir numara almak, ve açıkça çok yapmak Bu şekilde çok daha büyük, çok, ama biz aslında görmeye gidiyoruz Bunun için daha akıllı yaklaşımlar Bunun yerine, hem de, 

Pekala. Bu hafta üç için var. Size yakın zaman göreceksiniz. Bu CS50 oldu. 

[MÜZİK OYUN] 

KONUŞMACI 1: O atıştırma oldu Bir hot fudge sundae yemek bar. Yüzünde her yerinden tüm vardı. O bir sakal gibi o çikolata giyiyor HOPARLÖR 2: Ne yapıyorsun? KONUŞMACI 3: Hmmm? Ne? 

HOPARLÖR 2: Sadece çift dip mi? Sen çift çip daldırma. KONUŞMACI 3: Afedersiniz. HOPARLÖR 2: Sen çip daldırma Bir lokma aldı ve tekrar daldırma. KONUŞMACI 3: HOPARLÖR 2: Bu koyarak gibi Yani dip sizin tüm ağız hakkı. Bir dahaki sefere, bir çip almak Sadece bir kez daldırın ve bitirin. 

KONUŞMACI 3: Dan ne biliyorsun? Sen daldırma istediğiniz şekilde daldırma. Ben daldırma istediğiniz şekilde daldırma edeceğiz.