第一周算法的概念

1、算法的概念信息技術(shù)教研室新課導(dǎo)言新課導(dǎo)言1、在高中階段開設(shè)信息技術(shù)課的意義和作用： 提升信息素養(yǎng)和創(chuàng)新實(shí)踐能力提升信息素養(yǎng)和創(chuàng)新實(shí)踐能力；2、高中信息技術(shù)課包含的模塊 信息技術(shù)基礎(chǔ)、算法與程序設(shè)計(jì)、多媒體技術(shù)應(yīng)用、 網(wǎng)絡(luò)技術(shù)應(yīng)用、數(shù)據(jù)管理技術(shù)、人工智能初步。3、我校高一階段所選的學(xué)習(xí)模塊 (學(xué)業(yè)水平考試) 信息技術(shù)基礎(chǔ)、算法與程序設(shè)計(jì)、信息技術(shù)基礎(chǔ)、算法與程序設(shè)計(jì)、 多媒體技術(shù)應(yīng)用、網(wǎng)絡(luò)技術(shù)應(yīng)用多媒體技術(shù)應(yīng)用、網(wǎng)絡(luò)技術(shù)應(yīng)用4、與信息技術(shù)相關(guān)的兩個(gè)競賽 信息學(xué)奧賽、智能機(jī)器人競賽信息學(xué)奧賽、智能機(jī)器人競賽5、上課方式與紀(jì)律要求 一、什么是算法 1、為什么選擇算法模塊： 1）走進(jìn)計(jì)算機(jī)內(nèi)部，了解和

2、掌握其問題解決的 方式方法與步驟； 2）培養(yǎng)利用計(jì)算機(jī)解決問題的分析思維方式； 3）為學(xué)習(xí)編寫程序打下良好的思想基礎(chǔ)，掌握 算法的本質(zhì)； 4）高考的需要。算法問題引入 問題問題1 1： 兩個(gè)大人和兩個(gè)小孩一起渡河，渡口只有一條小船，每次只能渡1 個(gè)大人或兩個(gè)小孩，他們四人都會(huì)劃船，但都不會(huì)游泳。試問他們?cè)鯓佣蛇^河去？請(qǐng)寫出一個(gè)渡河方案。執(zhí)行步驟：第一步，兩個(gè)小孩同船過河去；第二步，一個(gè)小孩劃船回來；第三步，一個(gè)大人劃船過河去；第四步，對(duì)岸的小孩劃船回來；第五步，兩個(gè)小孩同船渡過河去；第六步，一個(gè)小孩劃船回來；第七步，余下的一個(gè)大人獨(dú)自劃船渡過河去；第八步，對(duì)岸的小孩劃船回來；第九步，兩個(gè)小孩再

3、同時(shí)劃船渡過河去。算法問題引入 問題問題2 2：求數(shù)學(xué)、語文和外語三科的平均成績。 變量的概念并解釋。 具體執(zhí)行步驟： 第一步，輸入三科成績，分別用a、b、c表示； 第二步，把a(bǔ)、b、c三個(gè)數(shù)代入公式 x=(a+b+c)/3中，x代表平均分； 第三步，輸出平均分x。知識(shí)運(yùn)用題目：任意給定一個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法求以這個(gè)題目：任意給定一個(gè)正實(shí)數(shù)，設(shè)計(jì)一個(gè)算法求以這個(gè) 數(shù)為半徑的圓的面積數(shù)為半徑的圓的面積.執(zhí)行步驟： 第一步，輸入任意一個(gè)正實(shí)數(shù)r. 第二步，計(jì)算以r為半 徑的圓的面積：s= r2. 第三步，輸出圓的面積S. 算法的概念算法的概念 算法： 通常指可以用來解決的某一類問題的步驟或 程序

4、，這些步驟或程序必須是明確的和有效的，而且能夠在有限步之內(nèi)完成的。算法的描述算法的描述自然語言;流程圖;偽代碼;程序設(shè)計(jì)語言等。 算法的分類算法的分類1. 數(shù)值型：數(shù)值型：如解方程（或方程組），解不等式（或不等式組），套用公式判斷性的問題，累加，累乘等一類問題的算法描述，可通過相應(yīng)的數(shù)學(xué)模型借助一般數(shù)學(xué)計(jì)算方法，分解成清晰的步驟，使之條理化即可。2.非數(shù)值型：非數(shù)值型：如排序、查找、變量變換、文字處理等需先建立過程模型，通過模型進(jìn)行算法設(shè)計(jì)與描述。 算法的特點(diǎn)算法的特點(diǎn)1.有窮性：一個(gè)算法必須保證執(zhí)行有限步后結(jié)束。2.確切性：算法的每一步必須有確切的定義。3.順序性與正確性：算法從初始步驟開始

5、，分為若干明確的步驟，每一個(gè)步驟只能有一個(gè)確定的后繼步驟，前一步是后一步的前提，只有執(zhí)行完前一步才能進(jìn)行下一步，并且每一步都準(zhǔn)確無誤，才能完成問題。4.不唯一性：求解某一個(gè)問題的解法不一定是唯一的，對(duì)于一個(gè)問題可以有不同的算法。知識(shí)運(yùn)用知識(shí)運(yùn)用例例1：輸入兩個(gè)數(shù)：輸入兩個(gè)數(shù)a、b，交換，交換a、b的值并輸出。的值并輸出。算法：第一步，輸入兩個(gè)數(shù)a、b；第二步，把a(bǔ)的值賦給x(x=a);第三步，把b的值賦給a(a=b);第四步，把x的值賦給b(b=x);第五步，輸出a、b的值。知識(shí)運(yùn)用知識(shí)運(yùn)用例例2：任意：任意3個(gè)整數(shù)個(gè)整數(shù)a,b,c求出最大值的算法。求出最大值的算法。 算法：第一步，輸入a、b

6、、c三個(gè)數(shù)；第二步， 令max=a；第三步，如果bmax, 則max=b；第四步，如果cmax, 則max=c；第五步，輸出max，它就是a,b,c中的最大值.深入思考： 寫出一個(gè)求有限整數(shù)序列中的最大值的算法寫出一個(gè)求有限整數(shù)序列中的最大值的算法 算法： 第一步，先假定序列中的第一個(gè)整數(shù)為“最大值”，記為 max； 第二步，判斷序列中是否還有其他整數(shù)，若有，將序列中的下一個(gè)整數(shù)值與“max”比較，如果它大于“max”，將這個(gè)數(shù)記為max；否則，比較結(jié)束，此時(shí)max為序列的最大值。第三步，判斷序列中是否還有其他整數(shù)，如果有，則重復(fù)第二步；否則，比較結(jié)束，此時(shí)max為序列的最大值。例3：任意給定

7、一個(gè)大于1的整數(shù)n，試設(shè)計(jì)一個(gè)算法，對(duì)n是否為質(zhì)數(shù)做出判斷。分析：分析：（1）質(zhì)數(shù)是只能被1和自身整除的大于1的整數(shù). 如：7是質(zhì)數(shù)，35不是質(zhì)數(shù)的算法。（2）要判斷一個(gè)大于1的整數(shù)n是否為質(zhì)數(shù)，只要 根據(jù)質(zhì)數(shù)的定義，用比這個(gè)整數(shù)小的數(shù)去除 n，如果它只能被1和本身整除，而不能被其 它整數(shù)整除，則這個(gè)數(shù)便是質(zhì)數(shù). 算法：算法： 第一步，判斷n是否等于2.若n=2，則n是質(zhì)數(shù)；若n2， 則執(zhí)行第二步. 第二步，依次從2（n-1）檢驗(yàn)是不是n的因數(shù)，即整除n 的數(shù).若有這樣的數(shù)，則n不是質(zhì)數(shù)；若沒有這樣 的數(shù)，則n是質(zhì)數(shù). 細(xì)化第二步：細(xì)化第二步： S1，令i=2； S2，用i除n，得到余數(shù)r；

8、S3，判斷“r=0”是否成立，若是，則n不是質(zhì)數(shù)，結(jié)束算 法；否則，將i的值加1； S4，判斷“i(n-1)”是否成立。若是，則n是質(zhì)數(shù)，結(jié)束 算法；否則，返回S2.練習(xí)1：一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？ 算法： 第一步，把銀元分成3組，每組3枚； 第二步，先將前兩組分別放在天平的兩邊。若 天平不平衡，則假銀元就在輕的那一 組，否則，假銀元在未稱的第3組里； 第三步，取出含假銀元的那一組，從中取兩枚 放在天平的兩邊。若天平不平衡，則 輕的那邊是假銀元，否則，未稱的那枚是假 銀元. 練習(xí)練習(xí)2 2：任意給定一個(gè)大于：任意給定一個(gè)大于1 1的正整數(shù)的正整數(shù)n n， 設(shè)計(jì)一個(gè)算法求出設(shè)計(jì)一個(gè)算法求出n n的所有因數(shù)。的所有因數(shù)。 算法： 第一步，輸入整數(shù)n; 第二步，若n=2，則輸出1，n，結(jié)束算法； 第三步，輸出1，n; 第四步，令i=2