2023學年完整公開課版算法的概念

算法的概念連云港市贛榆實驗中學趙統(tǒng)順華羅庚泡茶問題：燒水泡茶，它需要做4項工作，即洗好水壺（2分鐘），洗好茶杯（3分鐘），準備茶葉（1分鐘），燒開水（10分鐘）思考：你會怎么做？方法一：第一步：洗好水壺；第二步：燒水；第三步：水燒開后，洗刷茶具，拿茶葉；第四步：沏茶。方法二：第一步：洗好水壺；第二步：燒水；第三步：燒水過程中，洗刷茶具，拿茶葉；第四步：水燒開后沏茶。算法的定義：用計算機編寫程序解決問題的時候，首先應(yīng)確定解決問題的思路和方法，并寫出正確的求解步驟，這就是所謂的算法。簡單的說，算法就是解決問題的方法和步驟。例題：查找數(shù)字：編寫一個在包含16個數(shù)的有序數(shù)列中（序號從1到16）查找數(shù)字的程序：當輸入某個數(shù)字時，程序立刻顯示出該數(shù)字所在的序號。比如：查找973方法一：順序查找方法二：隨機查找方法三：二分查找比較次數(shù)：4比較次數(shù)：16比較次數(shù)：不確定拓展：假設(shè)有1024個數(shù)字，查找最后一個數(shù)字為例。第一次：1024/2=512第二次：512/2=256第三次：256/2=128第四次：128/2=64第五次：64/2=32第六次：32/2=16第七次：16/2=8第八次：8/2=4第九次：4/2=2第十次：2/2=1

通過例題，不難看出，不同的算法，其效果和效率也大不相同。算法的優(yōu)劣直接影響著所編寫程序的質(zhì)量，算法是程序的靈魂。小結(jié)：探究學習：（課本P98）

設(shè)計多種算法解決下面問題：1.求1+2+3+4+···+100的值。方法一：逐步累加第一步：1+2=3第二步：3+3=6第三步：6+4=10·····第99步：4950+100=5050方法二：公式項數(shù)*(首項+末項)/2優(yōu)點：不用動太多腦筋優(yōu)點：計算速度快缺點：計算步驟太多缺點：不容易找到公式探究學習：（課本P98）

設(shè)計多種算法解決下面問題：2.求1-2+3-4+5-6+···+99-100的值。方法一：逐步累加第一步：1-2=-1第二步：-1+3=2第三步：2-4=-2·····第99步：方法三：=（1-2）+（3-4）+···+（99-100）=-1*50=-50方法二：兩次使用公式項數(shù)*(首項+末項)/21+3+5+···+99=25*100=25002+4+6+···+100=25502500-2550=-50優(yōu)點：不用動太多腦筋優(yōu)點：計算速度快缺點：計算步驟太多缺點：不容易找到公式優(yōu)點：計算速度更快缺點：不容易看小結(jié)算法有優(yōu)劣之分，選擇合適的算法能夠提高程序的質(zhì)量。所以，在解決問題時，我們要有意識地設(shè)計與篩選優(yōu)質(zhì)算法，優(yōu)化問題的解決方案，以節(jié)省資源，提高效率。知識擴充：打開文件：桌面——學生文件——算法知識擴充1.著名計算機科學家李國杰院士對算法的精辟論述事實上，計算機發(fā)展到今天，能有如此廣泛而神奇的應(yīng)用，除了半導體集成電路芯片制造工藝提高以外，主要靠軟件，而軟件的核心是算法（不是編程技巧）。從國際上來說，無論是制造芯片的eda軟件、多媒體應(yīng)用的信息壓縮技術(shù)還是“深藍”計算機下棋贏了卡斯帕羅夫，都是靠巧妙的算法。在海灣戰(zhàn)爭中，多國部隊龐大的武器、物資流動和人員調(diào)配中算法起了關(guān)鍵作用，它的作用可以和芯片平分秋色。從國內(nèi)看，北大方正的“華光系統(tǒng)”的核心是王選在20世紀70年代中期創(chuàng)立的算法，近年來方正開發(fā)的彩排系統(tǒng)，關(guān)鍵也在算法。算法設(shè)計是人類智慧的結(jié)晶，計算機的知識創(chuàng)新，主要就是算法的創(chuàng)新，創(chuàng)建一種新算法其意義不亞于建造一種新機型。知識擴充：2.算法應(yīng)具備五個重要特征（1）有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束。（2）確定性：算法中的每一步驟必須有確切的定義，不允許存在二義性。（3）可行性：算法中所描述的每一步驟都應(yīng)能有效地執(zhí)行，并最終能得到確定的結(jié)果。（4）輸入：一個算法有零個或多個輸入。（5）輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。知識擴充：3.算法優(yōu)劣的標準判斷算法的優(yōu)劣主要可以從以下幾個方面來考慮：（1）正確性。首先這個算法必須是正確的。正確性是指所寫的算法能滿足具體問題的要求，即對任何合法的輸入，算法都會得出正確的結(jié)果。（2）可讀性。可讀性是指該算法被理解的難易程度。一個算法可讀性的好壞十分重要，如果一個算法比較抽象，難以理解，那么這個算法就不易交流和推廣，對于修改、擴展、維護都十分不利。（3）健壯性。健壯性就是指當輸入的數(shù)據(jù)非法或不合理時，算法也會做出相應(yīng)的判斷，而不會因為輸入錯誤造成程序癱瘓。（4）時間復雜度和空間復雜度。時間復雜度，簡單地說就是算法運行所花費的時間，所花費的時間應(yīng)該是越少越好。不同的算法具有不同的時間復雜度，當解決一個簡單問題，就感覺不到時間復雜度的重要性，而當解決一個復雜問題時，便會察覺到時間復雜度是十分重要的。空間復雜度是指算法運行所需的存儲空間的多少。隨著計算機硬件的發(fā)展，空間復雜度已經(jīng)顯得不再那么重要了，但在具體設(shè)計算法時也應(yīng)該注意。知識擴充：總結(jié)

1.算法的概念：解決問題的思路和步驟。2.算法的地位：是程序的靈魂。3.算法具有優(yōu)劣性