算法初步-完整版課件

第一章算法初步章末歸納總結(jié)一、本章要點歸納(一)算法與程序框圖．1．算法含義在數(shù)學中，現(xiàn)代意義上的“算法”通常是指可以用計算機來解決的某一類問題的程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成．2．算法的描述方法(1)用自然語言描述算法；(2)用程序框圖描述算法；(3)用形式語言描述算法．3．循環(huán)結(jié)構(gòu)有兩種：當型(WHILE型)循環(huán)和直到型(UNTIL型)循環(huán)．當型循環(huán)在執(zhí)行循環(huán)體前先對控制循環(huán)的條件進行判斷，當條件滿足時，反復執(zhí)行循環(huán)體，否則跳出循環(huán)；直到型循環(huán)在執(zhí)行了一次循環(huán)體后，對控制循環(huán)的條件做出判斷，當條件不滿足時反復執(zhí)行循環(huán)體，滿足則不再執(zhí)行循環(huán)體跳出循環(huán)，例如：(1)用當型循環(huán)結(jié)構(gòu)設計一個計算2＋4＋6＋…＋100的值的算法，畫出程序框圖．算法分析：用一個累加變量sum，初值設為0，用一個計數(shù)變量i，初值設為2，其值取2～100的偶數(shù)，程序框圖如圖所示．請寫出其算法語句，并且用直到型結(jié)構(gòu)設計出算法．(2)用直到型結(jié)構(gòu)設計一個算法，求20＋21＋22＋…＋263的值，并畫出程序框圖．算法分析：需要一個累加變量和一個計數(shù)變量，將累加變量的初始值設為0，計數(shù)變量從0～63取值．程序框圖：請自己用當型結(jié)構(gòu)設計出求解這個問題的算法，并用算法語句表達出來．(二)基本算法語句1．輸入語句格式INPUT

“提示內(nèi)容”；變量作用從鍵盤輸入變量的值說明INPUT語句也可以同時輸入多個變量的值，格式為：INPUT“提示內(nèi)容”；變量名1，變量名2，變量名3，……各變量名之間用逗號隔開，提示內(nèi)容可以省略．2．輸出語句格式PRINT

“提示內(nèi)容”；表達式(或變量名或常量)說明PRINT語句也可以輸出幾個變量的值，格式為：PRINT“提示內(nèi)容”；變量名1，變量名2，變量名3，……當輸出一個表達式時，輸出的是表達式的值．3．賦值語句格式變量名＝表達式或常量作用把“＝”右邊的常量或表達式的值賦給“＝”左邊的變量說明(1)“＝”叫賦值號，賦值號左邊只能是變量．(2)賦值號左右兩邊不能交換．(3)不能用賦值語句進行代數(shù)式(或符號)的演算．(4)賦值號與數(shù)學中的等號意義不完全相同．4．條件語句格式1作用根據(jù)判斷結(jié)果選擇執(zhí)行的語句，如果條件為真，就執(zhí)行語句體1；條件為假，就執(zhí)行語句體2.格式2作用如果條件成立，就執(zhí)行語句體，否則執(zhí)行ENDIF后面的語句．5．循環(huán)語句(1)當型循環(huán)：又叫前測試型循環(huán)格式作用如果條件成立，就執(zhí)行循環(huán)體，條件不成立就跳出循環(huán)執(zhí)行WEND后面的語句．(2)直到型循環(huán)：又叫后測試型循環(huán)格式作用反復執(zhí)行循環(huán)體直到條件成立時結(jié)束循環(huán)，執(zhí)行LOOPUNTIL條件后的語句．說明當型循環(huán)與直到型循環(huán)實質(zhì)是一樣的，它們可以相互轉(zhuǎn)化，它們的區(qū)別是當型循環(huán)的循環(huán)體可以一次都不執(zhí)行，而直到型循環(huán)的循環(huán)體至少執(zhí)行一次．6．簡單的QBASIC運算簡介(1)邏輯運算格式條件1

AND條件2作用條件1和條件2同時成立時，結(jié)果為真，否則結(jié)果為假；格式條件1

OR條件2作用條件1與條件2中只要有一個為真，運算結(jié)果即為真．說明邏輯運算不能單獨作為一個語句．(2)關(guān)系運算：關(guān)系運算符有：<，<＝，>，>＝，<>，＝，關(guān)系運算的結(jié)果為真或假．(3)算術(shù)運算：運算符有：加(＋)，減(－)，乘(*)，除(/)，乘方(^)，求余運算(MOD)，取整數(shù)商運算(\)，取整運算(INT)．1°算術(shù)表達式在QBASIC語言中，把符合規(guī)定的由括號、運算符號、常量、函數(shù)等構(gòu)成的式子叫做QBASIC算術(shù)表達式，簡稱算術(shù)式，單獨一個常數(shù)、數(shù)值變量或數(shù)值函數(shù)是算術(shù)表達式的特殊情況，如2＋1.06＋12/3,5,2^3等都是符合規(guī)定的QBASIC算術(shù)表達式．(三)算法案例1．輾轉(zhuǎn)相除法：用兩個正整數(shù)中較大的數(shù)除以較小的數(shù)所得余數(shù)與較小的數(shù)組成一對新數(shù)，重復上面的除法，直到余數(shù)為0時，較小數(shù)為原來兩數(shù)的最大公約數(shù)．2．更相減損術(shù)：用兩個正整數(shù)中較大的數(shù)減去較小的數(shù)所得的差和小數(shù)構(gòu)成一對新數(shù)，重復上面的減法，直到兩數(shù)相等時為止，這個相等的數(shù)就是原來兩數(shù)的最大公約數(shù)．3．秦九韶算法：f(x)＝(…((anx＋an－1)x＋an－2)x…＋a1)x＋a0.4．進位制：(1)把十進制數(shù)化為k進制數(shù)用除k取余法，用k連續(xù)除該十進制數(shù)或所得的商，直到商是0為止，然后把每次所得余數(shù)倒著排成一列，得到一個數(shù)就是相應的k進制數(shù)．(2)把k進制數(shù)化為十進制數(shù)，先把這個k進制數(shù)寫成用各位上的數(shù)字與k的冪的乘積之和形式，再按照十進制的運算規(guī)則計算出結(jié)果，如anan－1…a2a1a0(k)＝an×kn＋an－1×kn－1＋…＋a2k2＋a1k＋a0.二、思想方法(一)本章重要思想—算法思想．算法是數(shù)學及其應用的重要組成部分，是計算科學的基礎，是連接解決問題的方法和計算機能夠識別和理解的程序語言的橋梁，是現(xiàn)代人必須具有的數(shù)學素養(yǎng)．通過本章學習，初步掌握算法分析和程序設計，會用自然語言，程序框圖和類似BASIC語言的算法語句來把算法用程序設計語言表達出來，體會算法思想，發(fā)展有條理地思考與表達能力，提高邏輯思維能力．(二)方法技巧1．對于給定的問題，設計其算法時應注意：(1)與解決該問題的一般方法相聯(lián)系，從中提煉與概括算法步驟；(2)將解決問題的過程劃分為若干步驟；(3)引入有關(guān)的變量對算法步驟加以表述；(4)用簡煉的語言將各個步驟表達出來．2．條件結(jié)構(gòu)主要用在一些需要進行條件判斷的算法中，如分段函數(shù)求值、大小關(guān)系判斷等；循環(huán)結(jié)構(gòu)主要用在一些有規(guī)律的重復計算中，如累加求和、累乘求積、遞推關(guān)系等．3．應注意掌握通過引入第三變量利用三個賦值語句交換兩個變量的值的方法．4．條件語句和循環(huán)語句是解決一些較復雜問題的編程必須用到的兩種語句，在用循環(huán)語句編寫程序時，一是要注意兩種格式的循環(huán)語句在解決同一問題時條件表述的不同，它們恰好相反；二是注意計數(shù)變量的取值范圍，以免出現(xiàn)多一次循環(huán)和少一次循環(huán)的錯誤．5．用輾轉(zhuǎn)相除法與更相減損術(shù)求兩個數(shù)的最大公約數(shù)時，一定要弄清每一次除法(或減法)中的被除數(shù)、除數(shù)(或被減數(shù)、減數(shù))，同時要掌握兩種方法中除法和減法分別應在何種情況下停止運算，并得出結(jié)果．6．要注意不同進位制的數(shù)之間的轉(zhuǎn)換方法．三、題型探究1．程序框圖的閱讀理解[例1]

(12·廣東理)閱讀下圖的程序框圖．若輸入m＝4，n＝6，則輸出a＝________，i＝________.(注：圖中的賦值符號“＝”也可以寫成“←”或“：＝”)[解析]

輸入后m＝4，n＝6，賦值后a＝4，不能被n整除，重新賦值i＝2，a＝8，再檢驗，a仍不能被n整除，再次賦值i＝3，a＝12滿足條件，故輸出a＝12，i＝3.[點評]

注意到賦值語句a＝m×i，因此a的取值僅與m＝4及i的值有關(guān)，若條件成立，則a能被6整除，又能被4整除，故a是6與4的最小公倍數(shù)，∴a＝12，i＝3.(2010·山東理，13)執(zhí)行如圖所示的程序框圖，若輸入x＝10，則輸出y的值為________．(2010·浙江文，4)某程序框圖如圖所示，若輸出S＝57，則判斷框內(nèi)為(

)A．k>4?B．k>5?C．k>6?D．k>7?[答案]

A[解析]

該程序依次如下運行：初值：S＝1，k＝1①k＝2，S＝4②k＝3，S＝11③k＝4，S＝26④k＝5，S＝57最后輸出S＝57，∴判斷框中應填k>4?3．畫程序框圖，編寫程序語句[例3]

(07·廣東)某廠總產(chǎn)值以8%的年平均增長率增長，則經(jīng)過幾年以后總產(chǎn)值可以翻一番？請編寫出計算的程序．[解析]

用P表示總產(chǎn)值，I表示年數(shù)，每經(jīng)過一年，檢驗一次P≥2是否成立，成立時，輸出P，I的值．程序如下：P＝1I＝0DOP＝P*(1＋0.08)I＝I＋1LOOPUNTIL

P>＝2PRINT

“I＝”；IEND程序如下：INPUT

“n，a＝”；n，