模塊十五-算法初步

模塊十五算法初步考綱解讀高考大綱考試內容要求層次ABC算法的含義程序框圖的三種根本邏輯結構輸入語句、輸出語句、賦值語句、條件語句、循環(huán)語句分析解讀〔1〕理解算法的概念與特點，會用自然語言描述算法，能熟練運用程序框圖表示算法.〔2〕理解根本算法語句，掌握算法的根本思想，能編寫程序解決簡單問題.〔3〕理解輾轉相除法、更相減損法、秦九韶算法、插入法和冒泡法這些古代數(shù)學開展的奉獻，理解進位制.知識導航考點剖析考點一算法與程序框圖1、算法概念：在數(shù)學上，現(xiàn)代意義上的“算法”通常是指可以用計算機來解決的某一類問題是程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內完成2、程序框圖根本概念：〔1〕程序構圖的概念：程序框圖又稱流程圖，是一種用規(guī)定的圖形、指向線及文字說明來準確、直觀地表示算法的圖形。一個程序框圖包括以下幾局部：表示相應操作的程序框；帶箭頭的流程線；程序框外必要文字說明?！?〕構成程序框的圖形符號及其作用程序框名稱功能起止框表示一個算法的起始和結束，是任何流程圖不可少的。輸入、輸出框表示一個算法輸入和輸出的信息，可用在算法中任何需要輸入、輸出的位置。處理框賦值、計算，算法中處理數(shù)據需要的算式、公式等分別寫在不同的用以處理數(shù)據的處理框內。判斷框判斷某一條件是否成立，成立時在出口處標明“是”或“Y”；不成立時標明“否”或“N”?！?〕、算法的三種根本邏輯結構：順序結構、條件結構、循環(huán)結構。順序結構：順序結構是最簡單的算法結構，語句與語句之間，框與框之間是按從上到下的順序進行的，它是由假設干個依次執(zhí)行的處理步驟組成的，它是任何一個算法都離不開的一種根本算法結構。條件結構：條件結構是指在算法中通過對條件的判斷根據條件是否成立而選擇不同流向的算法結構。循環(huán)結構：在一些算法中，經常會出現(xiàn)從某處開始，按照一定條件，反復執(zhí)行某一處理步驟的情況，這就是循環(huán)結構，反復執(zhí)行的處理步驟為循環(huán)體，顯然，循環(huán)結構中一定包含條件結構。循環(huán)結構又稱重復結構，循環(huán)結構可細分為兩類：一類是當型循環(huán)結構，另一類是直到型循環(huán)結構?？键c二根本算法語句1、輸入、輸出和賦值語句〔1〕、輸入語句的作用是實現(xiàn)算法的輸入信息功能；〔3〕“提示內容”提示用戶輸入什么樣的信息，變量是指程序在運行時其值是可以變化的量；〔4〕輸入語句要求輸入的值只能是具體的常數(shù)，不能是函數(shù)、變量或表達式；〔5〕提示內容與變量之間用分號“；”隔開，假設輸入多個變量，變量與變量之間用逗號“，”隔開?！?〕、輸出語句的作用是實現(xiàn)算法的輸出結果功能；〔3〕“提示內容”提示用戶輸入什么樣的信息，表達式是指程序要輸出的數(shù)據；〔4〕輸出語句可以輸出常量、變量或表達式的值以及字符?！?〕、賦值語句的作用是將表達式所代表的值賦給變量；賦值語句中的“＝”稱作賦值號，與數(shù)學中的等號的意義是不同的。賦值號的左右兩邊不能對換，它將賦值號右邊的表達式的值賦給賦值號左邊的變量；賦值語句左邊只能是變量名字，而不是表達式，右邊表達式可以是一個數(shù)據、常量或算式；〔5〕對于一個變量可以屢次賦值。2、條件語句條件語句的一般格式有兩種：〔1〕IF—THEN—ELSE語句；〔2〕IF—THEN語句。3、循環(huán)語句循環(huán)結構是由循環(huán)語句來實現(xiàn)的。對應于程序框圖中的兩種循環(huán)結構，一般程序設計語言中也有當型〔WHILE型〕和直到型〔UNTIL型〕兩種語句結構。即WHILE語句和UNTIL語句?？键c三算法案例1、輾轉相除法。也叫歐幾里德算法，用輾轉相除法求最大公約數(shù)的步驟如下：〔1〕：用較大的數(shù)m除以較小的數(shù)n得到一個商和一個余數(shù)；〔2〕：假設＝0，那么n為m，n的最大公約數(shù)；假設≠0，那么用除數(shù)n除以余數(shù)得到一個商和一個余數(shù)；〔3〕：假設＝0，那么為m，n的最大公約數(shù)；假設≠0，那么用除數(shù)除以余數(shù)得到一個商和一個余數(shù)；……依次計算直至＝0，此時所得到的即為所求的最大公約數(shù)。2、更相減損術我國早期也有求最大公約數(shù)問題的算法，就是更相減損術。在《九章算術》中有更相減損術求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母?子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯為：〔1〕：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。假設是，用2約簡；假設不是，執(zhí)行第二步?！?〕：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比擬，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，那么這個數(shù)〔等數(shù)〕就是所求的最大公約數(shù)。3、輾轉相除法與更相減損術的區(qū)別：〔1〕都是求最大公約數(shù)的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數(shù)上輾轉相除法計算次數(shù)相對較少，特別當兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。〔2〕從結果表達形式來看，輾轉相除法表達結果是以相除余數(shù)為0那么得到，而更相減損術那么以減數(shù)與差相等而得到4、秦九韶算法秦九韶算法概念：f(x)=anxn+an-1xn-1+….+a1x+a0求值問題f(x)=anxn+an-1xn-1+….+a1x+a0=(anxn-1+an-1xn-2+….+a1)x+a0=((anxn-2+an-1xn-3+….+a2)x+a1)x+a0=......=(...(anx+an-1)x+an-2)x+...+a1)x+a0求多項式的值時，首先計算最內層括號內依次多項式的值，即v1=anx+an-1，然后由內向外逐層計算一次多項式的值，即v2=v1x+an-2v3=v2x+an-3......vn=vn-1x+a0，這樣，把n次多項式的求值問題轉化成求n個一次多項式的值的問題。5、兩種排序方法：直接插入排序和冒泡排序〔1〕、直接插入排序根本思想：插入排序的思想就是讀一個，排一個。將第１個數(shù)放入數(shù)組的第１個元素中，以后讀入的數(shù)與已存入數(shù)組的數(shù)進行比擬，確定它在從大到小的排列中應處的位置．將該位置以及以后的元素向后推移一個位置，將讀入的新數(shù)填入空出的位置中．〔由于算法簡單，可以舉例說明〕〔2〕、冒泡排序根本思想：依次比擬相鄰的兩個數(shù),把大的放前面,小的放后面.即首先比擬第1個數(shù)和第2個數(shù),大數(shù)放前,小數(shù)放后.然后比擬第2個數(shù)和第3個數(shù)......直到比擬最后兩個數(shù).第一趟結束,最小的一定沉到最后.重復上過程,仍從第1個數(shù)開始,到最后第2個數(shù)......由于在排序過程中總是大數(shù)往前,小數(shù)往后,相當氣泡上升,所以叫冒泡排序.真題演練由于北京市近五年來僅在2011年和2012年考查了該專題知識，因此本專題的“真題演練”版塊還將選取近兩年全國卷的試題作為練習。1.【2012北京,4,5分】執(zhí)行如下圖的程序框圖，輸出的S值為〔〕A.2B.4C舉一反三1.1【2012天津,3,5分】閱讀右邊的程序框圖，運行相應的程序，當輸入x的值為-25時，輸出x的值為〔A〕-1〔B〕1〔C〕3〔D〕91.2【2012陜西,10,5分】右圖是用模擬方法估計圓周率的程序框圖，表示估計結果，那么圖中空白框內應填入〔〕A.B.C.D.1.3【2012山東,6,5分】執(zhí)行下面的程序圖，如果輸入，那么輸出的的值為〔A〕2〔B〕3〔C〕4〔D〕52.【2011北京,4,5分】執(zhí)行如下圖的程序框圖，輸出的s值為A．-3B．-C．D．2舉一反三2.1【2012遼寧,9,5分】執(zhí)行如下圖的程序框圖，那么輸出的S的值是(A)1(B)(C)(D)42.2【2012福建,12,5分】閱讀右圖所示的程序框圖，運行相應地程序，輸出的s值等于_____________________.2.3【2012安徽,3,5分】如下圖，程序框圖〔算法流程圖〕的輸出結果是〔〕3.【2012課標全國,6,5分】如果執(zhí)行右邊的程序框圖，輸入正整數(shù)和實數(shù)，輸出，那么〔〕為的和為的算術平均數(shù)和分別是中最大的數(shù)和最小的數(shù)和分別是中最小的數(shù)和最大的數(shù)舉一反三3.1【2012湖南,14,5分】如果執(zhí)行如圖3所示的程序框圖，輸入,n=3,那么輸出的數(shù)S=.3.2【2012江西,14,5分】下列圖為某算法的程序框圖，那么程序運行后輸出的結果是______________.3.3【2012浙江,12,5分】假設某程序框圖如下圖，那么該程序運行后輸出的值是__________4.【2011課標全國,3,5分】執(zhí)行程序框圖，如果輸入的N是6，那么輸出的p是〔〕A．120B．720C．1440D．5040舉一反三4.1【2012湖北,12,5分】閱讀如下圖的程序框圖，運行相應的程序，輸出的結果.4.2【2012廣東,13,5分】執(zhí)行如下圖的程序框圖，假設輸入n的值為8，那么輸出s的值為．4.3【2012江蘇,4,5分】下列圖是一個算法流程圖，那么輸出的k的值是．輕松驛站數(shù)學笑話1.無窮是什么?一位富翁偶然聽到一個數(shù)學教授給學生談論“無窮”，心里便琢磨，這“有限多個”好理解，比方，我的錢財，可這“無窮”是什么呢？難道就是跟自然數(shù)一樣多，或者“更多”？富翁想知道自己理解的究竟對不對，于是就問教授：“教授先生，‘無窮’是什么？”教授答復說：“無窮就是沒有窮人，都象您一樣富有?！苯淌诳吹礁晃滩焕斫獾臉幼?，就進一步解說：“想一想，如果地球上的人有無窮多個，比方說，可以和自然數(shù)對應起來，而且每個人只有一元錢，不要多，那么第一個人問第二個人借一元，第二個問第三個人借一元，依次往后借，如此下去，第一個人就有2元錢，其他人也沒有少錢?！备晃厅c頭成認，并說：“那還是沒有我的錢多?！苯淌诮又f：“如果第一個人重復一百萬次，那不就是百萬富豪了？！”富翁這才恍然大悟，明白了“無窮”是什么。寫于數(shù)學樓)2.名人的生日眾所周知,名人、偉人都有不尋常的個人特性。如果你學代數(shù)，算一算他們的生日,你就會發(fā)現(xiàn)，所有的名人和偉人的生日都具有如下的一個特點：如：愛因斯坦的生日是：1879年3月14日，將年月日寫在一起是1879314。把這個數(shù)隨意排列一下，可得到另一個數(shù)，比方：4187139。用大的數(shù)減去小的數(shù)得到一個差：4187139-1879314=2307825。將差的各個位數(shù)相加得到一個數(shù)，2+3+0+7+