Scratch算法練習(xí)

Intoweb

1. 為什么要做算法練習(xí)

對(duì)于計(jì)算機(jī)來(lái)說(shuō)，針對(duì)一個(gè)問(wèn)題選擇合適的解決方案的方法就是算法。算法可以是一系列的數(shù)學(xué)計(jì)算，也可以是一系列的操作步驟。總之，它存在的意義就是為了有針對(duì)性地解決問(wèn)題。每個(gè)問(wèn)題都有它獨(dú)特的一面，正所謂算法沒(méi)有最好的，只有最合適的。

軟件開發(fā)領(lǐng)域日新月異，編程語(yǔ)言會(huì)推陳出新，掌握的技術(shù)可能會(huì)淘汰，但算法卻是軟件不變的核心內(nèi)容。因此，學(xué)好算法能夠有效提高編程能力，以后也能更好地學(xué)習(xí)新語(yǔ)言。

2. 什么是眾數(shù)

找眾數(shù)（Mode）是計(jì)算機(jī)程序設(shè)計(jì)入門的經(jīng)典算法練習(xí)之一。在一組數(shù)據(jù)中出現(xiàn)次數(shù)最多的數(shù)值，叫眾數(shù)（Mode），多用于統(tǒng)計(jì)目標(biāo)沒(méi)有明顯次序（如非數(shù)值性資料）無(wú)法良好定義算術(shù)平均數(shù)和中位數(shù)的情況。

例如：1，2，6，6，4，6的眾數(shù)是6。

有時(shí)眾數(shù)在一組數(shù)中有好幾個(gè)，如果有兩個(gè)或兩個(gè)以上數(shù)值出現(xiàn)次數(shù)都是最多的，那么這幾個(gè)數(shù)值都是這組數(shù)據(jù)的眾數(shù)。

例如：1，2，2，3，3，4的眾數(shù)是2和3。

如果所有數(shù)值出現(xiàn)的次數(shù)都一樣，那么這組數(shù)據(jù)沒(méi)有眾數(shù)。

例如：1，1，2，2，3，3列表共6項(xiàng)3種數(shù)值，出現(xiàn)次數(shù)最多是2次，列表數(shù)字出現(xiàn)次數(shù)的平均數(shù)也為2，所以沒(méi)有眾數(shù)。

現(xiàn)有一個(gè)長(zhǎng)度為n的序列，請(qǐng)你編程求出它的眾數(shù)。當(dāng)然眾數(shù)可能有多個(gè)，降低難度要求只需要輸出其中一個(gè)就可以了。

3. 算法分析

找眾數(shù)的算法有很多種比如“觀察法”、“金氏插入法”、“皮爾遜經(jīng)驗(yàn)法”等。由于題目只要求找到一個(gè)眾數(shù)即可，參考這些經(jīng)典算法后有以下幾種思路供你參考。

1） 方法一：每次取出列表第一項(xiàng)，統(tǒng)計(jì)該項(xiàng)數(shù)值在列表中出現(xiàn)的次數(shù)，記錄下來(lái)，然后將該項(xiàng)刪除。這樣依次重復(fù)統(tǒng)計(jì)每項(xiàng)數(shù)值出現(xiàn)的次數(shù)，直到列表為空。

用專門變量記錄出現(xiàn)次數(shù)最多的那個(gè)數(shù)值，這個(gè)數(shù)值可能就是數(shù)列中的眾數(shù)。

除此之外，我們還需要排除所有數(shù)值出現(xiàn)次數(shù)相同的情況，如果這個(gè)數(shù)值出現(xiàn)的次數(shù)>列表數(shù)值出現(xiàn)次數(shù)的平均數(shù)，則代表眾數(shù)存在，否則就沒(méi)有眾數(shù)。數(shù)值出現(xiàn)次數(shù)的平均數(shù)=列表項(xiàng)目總數(shù)÷列表中數(shù)值的種類。

這種方法由于會(huì)刪除原列表1，所以是一種破壞型的方法。可以新增備份列表2解決這個(gè)問(wèn)題。

2） 方法二：統(tǒng)計(jì)列表1中每一項(xiàng)數(shù)值出現(xiàn)的次數(shù)，一一對(duì)應(yīng)存儲(chǔ)到列表2中，然后從列表2中找到最大的那個(gè)數(shù)，那么該項(xiàng)對(duì)應(yīng)列表1的數(shù)就可能是眾數(shù)。

再看列表2中所有數(shù)是不是都一樣，只要有一個(gè)不一樣，那么列表1就存在眾數(shù)。

3） 方法三：先排序，然后找出那個(gè)重復(fù)最多的數(shù)就是眾數(shù)了。這種方法用到了排序，排序有很多種算法，本文不再詳述，你可以根據(jù)以前介紹過(guò)的排序方法想想看如何實(shí)現(xiàn)。

4. 方法一代碼分析

依次對(duì)比并記錄重復(fù)次數(shù)最多的數(shù)值，并刪除對(duì)比過(guò)的數(shù)值（如圖1）。

1） 創(chuàng)建變量：眾數(shù)、眾數(shù)出現(xiàn)次數(shù)、有無(wú)眾數(shù)用來(lái)記錄成果。列表長(zhǎng)度、搜索項(xiàng)、搜索項(xiàng)次數(shù)、數(shù)字種類作為中間變量。index作為臨時(shí)變量。

2） 創(chuàng)建列表1，將隨機(jī)數(shù)加入這個(gè)列表。將列表1復(fù)制到備份列表2。解決找眾數(shù)過(guò)程中列表1會(huì)被刪除的問(wèn)題（如圖2）。

3） 初始化各個(gè)變量，有無(wú)眾數(shù)設(shè)為“無(wú)”，列表長(zhǎng)度為列表1項(xiàng)目數(shù)。

4） 把列表1第1項(xiàng)設(shè)為“搜索項(xiàng)”，依次比對(duì)整個(gè)列表，記錄該搜索項(xiàng)出現(xiàn)的次數(shù)，并刪除所有與該搜索項(xiàng)相同的數(shù)值。這樣重復(fù)刪除直到列表1為空時(shí)就比對(duì)完成了。

5） 如果新的搜索項(xiàng)出現(xiàn)次數(shù)大于眾數(shù)出現(xiàn)次數(shù)，將眾數(shù)設(shè)為該搜索項(xiàng)，將眾數(shù)出現(xiàn)次數(shù)設(shè)為搜索項(xiàng)次數(shù)。當(dāng)列表被清空時(shí)，眾數(shù)就是表中出現(xiàn)次數(shù)最多的數(shù)值了（如圖3）。

6） 判斷有無(wú)眾數(shù)。如果眾數(shù)出現(xiàn)次數(shù)大于數(shù)字出現(xiàn)的平均數(shù)就可以判斷有眾數(shù)了。如果有眾數(shù)就用連接塊整合輸出最終結(jié)果即可（如圖4，5）。

5. 方法二代碼分析

統(tǒng)計(jì)列表中每一項(xiàng)數(shù)值出現(xiàn)的次數(shù)，從中找到最大數(shù)，它對(duì)應(yīng)列表中的項(xiàng)就是眾數(shù)（如圖6）。

1） 定義變量：眾數(shù)是第幾項(xiàng)、眾數(shù)出現(xiàn)次數(shù)、有無(wú)眾數(shù)用來(lái)記錄眾數(shù)。搜索項(xiàng)、搜索項(xiàng)次數(shù)、列表長(zhǎng)度、index用來(lái)統(tǒng)計(jì)列表每項(xiàng)出現(xiàn)的次數(shù)。

2） 生成隨機(jī)列表1，建立列表2用于存儲(chǔ)列表1每項(xiàng)在列表中重復(fù)出現(xiàn)的次數(shù)。

3） 統(tǒng)計(jì)列表某一項(xiàng)在列表中出現(xiàn)的次數(shù)。把列表搜索項(xiàng)依次比對(duì)整個(gè)表格，將重復(fù)出現(xiàn)次數(shù)記錄在搜索項(xiàng)次數(shù)中并存入列表2（如圖7）。

4） 完成統(tǒng)計(jì)后列表2中記錄了每項(xiàng)重復(fù)出現(xiàn)的次數(shù)，下面找出列表2中最大的項(xiàng)（如圖8）。

5） 找到列表2中最大的一項(xiàng)。從列表2第一項(xiàng)開始找到較大的項(xiàng)記錄在“眾數(shù)出現(xiàn)次數(shù)”中，重復(fù)“列表項(xiàng)目數(shù)”次就對(duì)比了全部項(xiàng)，這時(shí)“眾數(shù)出現(xiàn)次數(shù)”就是列表中最大的項(xiàng)，這項(xiàng)的順序位置記錄在“眾數(shù)是第幾項(xiàng)”中對(duì)應(yīng)到列表1中就找到這個(gè)列表的眾數(shù)了（如圖9）。

6） 在比對(duì)列表2中最大數(shù)的同時(shí)，我們還要同時(shí)判斷列表是否有眾數(shù)。只要列表2中的數(shù)值有一次出現(xiàn)不相等，就代表列表1有眾數(shù)（如圖10）。

7） 輸出結(jié)果，完成循環(huán)。如果有眾數(shù)，用連接塊將結(jié)果說(shuō)出來(lái)就可以了（如圖11）。

通過(guò)對(duì)兩種找眾數(shù)算法的簡(jiǎn)析，我們練習(xí)了兩種找眾數(shù)的算法。你可以根據(jù)對(duì)這個(gè)問(wèn)題的理解繼續(xù)改進(jìn)算法或找到新的算法，還可以試試看能不能找到列表中所有的眾數(shù)。