Scratch算法練習(xí)

Intoweb

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

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

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

2. 什么是眾數(shù)

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

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

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

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

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

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

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

3. 算法分析

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

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

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

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

這種方法由于會刪除原列表1，所以是一種破壞型的方法?？梢孕略鰝浞萘斜?解決這個問題。

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

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

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

4. 方法一代碼分析

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

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

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

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

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

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ù)就是表中出現(xiàn)次數(shù)最多的數(shù)值了（如圖3）。

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

5. 方法二代碼分析

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

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

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

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

4） 完成統(tǒng)計后列表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ù)”次就對比了全部項(xiàng)，這時“眾數(shù)出現(xiàn)次數(shù)”就是列表中最大的項(xiàng)，這項(xiàng)的順序位置記錄在“眾數(shù)是第幾項(xiàng)”中對應(yīng)到列表1中就找到這個列表的眾數(shù)了（如圖9）。

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

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

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