算法初步課件_11_算法的概念

1、X20 世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明世紀(jì)最偉大的科學(xué)技術(shù)發(fā)明-計(jì)算機(jī)計(jì)算機(jī)計(jì)算機(jī)是對(duì)人腦的模擬，它強(qiáng)化了人的思維智能；計(jì)算機(jī)是對(duì)人腦的模擬，它強(qiáng)化了人的思維智能；沒有軟件的支持，超級(jí)計(jì)算機(jī)只是一堆廢鐵而已；沒有軟件的支持，超級(jí)計(jì)算機(jī)只是一堆廢鐵而已；什么是算法呢什么是算法呢？ 簡(jiǎn)單地說，算法就是解決問題的程序或步驟。簡(jiǎn)單地說，算法就是解決問題的程序或步驟。二元一次方程組二元一次方程組 12 12yxyx的求解過程的求解過程.歸納它的步驟歸納它的步驟:第一步第一步: 2+，得，得 5x=1 第三步第三步:第二步第二步: 解得解得 x= 第二步第二步: 解解得得 53y51代入將51x,得得 一般地一

2、般地, 按照一定規(guī)則解決某一類問題的明確和有按照一定規(guī)則解決某一類問題的明確和有限的步驟稱為限的步驟稱為算法算法(algorithm)。 所謂所謂 “ “算法算法”就是解題方法的精確描述就是解題方法的精確描述. .從更廣義從更廣義的角度來看的角度來看, ,并不是只有并不是只有“計(jì)算計(jì)算”的問題才有算法的問題才有算法, ,日常日常生活中處處都有生活中處處都有. .如如樂譜樂譜是樂隊(duì)演奏的算法是樂隊(duì)演奏的算法, ,菜譜菜譜是做菜是做菜肴的算法肴的算法, ,珠算口訣珠算口訣是使用算盤的算法是使用算盤的算法. .它是解決某一類問題的程序或步驟它是解決某一類問題的程序或步驟. .：3.算法的基本思想與特

3、征算法的基本思想與特征:2.算法的表示方法：算法的表示方法：自然語言、程序框圖、程序自然語言、程序框圖、程序(1)解決某一類問題解決某一類問題(2)在在有限步有限步之內(nèi)完成之內(nèi)完成(3)每一步的明確性和有效性每一步的明確性和有效性(4)每一步具有順序性每一步具有順序性(一般性一般性)(有限性有限性)(確定與可行性確定與可行性)(順序性順序性)例例1 1 在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936936分解分解成素因數(shù)的乘積成素因數(shù)的乘積.(4000.(4000以內(nèi)的素?cái)?shù)表見課本附錄以內(nèi)的素?cái)?shù)表見課本附錄1)1)解解: :算法步驟如下：算法步驟如下：1.1.判斷判

4、斷936936是否為素?cái)?shù)：否是否為素?cái)?shù)：否. .2.2.確定確定936936的最小素因數(shù)：的最小素因數(shù)：2. 936=22. 936=24684683.3.判斷判斷468468是否為素?cái)?shù)：否是否為素?cái)?shù)：否. .4.4.確定確定468468的最小素因數(shù)：的最小素因數(shù)：2. 936=22. 936=22 22342345.5.判斷判斷234234是否為素?cái)?shù)：否是否為素?cái)?shù)：否. .6.6.確定確定234234的最小素因數(shù)：的最小素因數(shù)：2. 936=22. 936=22 22 21171177.7.判斷判斷117117是否為素?cái)?shù)：否是否為素?cái)?shù)：否. .8.8.確定確定117117的最小素因數(shù)：的最小

5、素因數(shù)：3. 936=23. 936=22 22 23 339399.9.判斷判斷3939是否為素?cái)?shù)：否是否為素?cái)?shù)：否. .10.10.確定確定3939的最小素因數(shù)：的最小素因數(shù)：3. 936=23. 936=22 22 23 33 31313判斷判斷1313是否為素?cái)?shù)：是否為素?cái)?shù)：1313是素?cái)?shù)，所以分解結(jié)束是素?cái)?shù)，所以分解結(jié)束. .分解結(jié)果是：分解結(jié)果是： 936=2936=22 22 23 33 31313例例2 2、寫出以下問題的算法：、寫出以下問題的算法：一位商人有一位商人有9 9枚銀元，其中有枚銀元，其中有1 1枚略輕的是假銀元枚略輕的是假銀元. .你能你能用天平（不用砝碼）將假銀元找出來嗎？用天平（不用砝碼）將假銀元找出來嗎？一個(gè)人帶一只狼和一只羚羊還有一堆白菜過河，只有一一個(gè)人帶一只狼和一只羚羊還有一堆白菜過河，只有一條船，船可以容納一個(gè)人和一個(gè)動(dòng)物（或菜）沒有人在條船，船可以容納一個(gè)人和一個(gè)動(dòng)物（或菜）沒有人在的時(shí)候，狼就會(huì)吃掉羚羊，羚羊會(huì)吃掉白菜請(qǐng)?jiān)O(shè)計(jì)過河的