《算法的概念》PPT課件

鄒 城 二 中 數(shù) 學(xué) 組 ： 高 明 海 一 人 帶 著 一 只 狼 、 一 只 羊 和 一 箱 蔬 菜 要 過 河 ,但 只有 一 條 小 船 .乘 船 時 ， 每 次 只 能 帶 狼 、 羊 和 蔬 菜 中 的 一種 .當(dāng) 有 人 在 場 時 ， 狼 、 羊 、 蔬 菜 都 相 安 無 事 .一 旦 人不 在 ,狼 會 吃 羊 ,羊 會 吃 菜 .請 設(shè) 計 一 個 方 案 ,安 全 地 將 狼 、羊 和 蔬 菜 帶 過 河 . 過 河 游 戲新 課 引 入 ： 請 看 以 下 趣 味 游 戲 :,下 面 就 是 一 種 操 作 步 驟發(fā) 郵 件 的 方 法 很 多 ;第 一 步 登 錄 電 子 信 箱如 何 發(fā) 電 子 郵 件 ？;第 二 步 點 擊 “ 寫 信 ” ;第 三 步 輸 入 收 件 人 地 址;第 四 步 輸 入 主 題 ;第 五 步 輸 入 信 件 內(nèi) 容第 六 步 點 擊 “ 發(fā) 送 ” . ., ; , ,.,也 是 按 一 定 程 序 操 作 的程 用 配 方 法 解 一 元 二 次 方按 照 某 一 程 序 進 行 操 作 就 可 以元 一 次 方 程 組 時例 如 用 加 減 消 元 法 解 二 此解 決 數(shù) 學(xué) 問 題 也 常 常 如序 執(zhí) 行 的 一 系 列 操 作 種 順都 是 在 一 定 條 件 下 按 某我 們 做 任 何 一 件 事 一 般 地 ,對 于 一 類 問 題 的 機 械 式 地 、 統(tǒng) 一地 、 按 部 就 班 地 求 解 過 程 稱 為 算 法 (algorithm)它 是 解 決 某 一 問 題 的 程 序 或 步 驟 . 所 謂 “ 算 法 ” 就 是 解 題 方 法 的 精 確 描 述 .從 更 廣 義 的 角 度 來 看 ,并 不 是 只 有 “ 計 算 ” 的問 題 才 有 算 法 ,日 常 生 活 中 處 處 都 有 .如 樂 譜 是樂 隊 演 奏 的 算 法 ,菜 譜 是 做 菜 肴 的 算 法 ,珠 算 口訣 是 使 用 算 盤 的 算 法 ， 等 . 請 你 寫 出 解 下 面 二 元 一 次 方 程 組 的 詳 細 過 程 . 2 12 1x yx y 第 二 步 , 解 得 1 ;5x 第 三 步 , - 2得 5y=3; 第 四 步 , 解 得 3 ; 5y 1 ,53.5xy 第 五 步 , 得 到 方 程 組 的 解 為第 一 步 , + 2得 5x=1; 解 ： 做一做 你 能 寫 出 解 一 般 的 二 元 一 次 方 程 組 的 步 驟 嗎 ？ 1 1 1 1 2 2 12 2 2 (1) 0(2)a x b y c a b a ba x b y c 第 一 步 , 2 1(1) ( 2 )b b 得 ： 1 2 2 1 1 2 2 1 .a b a b x c b c b （ 3） 第 二 步 ,解 （ 3） 得 1 2 2 11 2 2 1 .c b c bx a b a b 思考 2 1 1 22 1 1 2 .ac acy ab ab 第 四 步 ,解 （ 4） 得 2 1(1) (2)a a 得 ：第 三 步 , 2 1 1 2 2 1 1 2.a b ab y a c ac （ 4） 第 五 步 ,得 到 方 程 組 的 解 為 1 2 2 11 2 2 12 1 1 22 1 1 2 ,.c b c bx a b a ba c a cy a b a b 解 ， 得 2 1 1 22 1 1 2a c a cy a b a b 將 帶 入 得 2a 1a 得 1 1 12 2 2a x b y ca x b y c 1 2 2 12 1 1 2b c b cx a b a b 解 得 5 1.x 第 一 步 ：第 二 步 ：第 三 步 ： + 2， 得 1 .5x 2 1,2 1x yx y 15x 將 代 入 ,得 3 .5y 思 考 這 兩 個 解 方 程 組 的 算 法的 適 用 范 圍 有 何 不 同 ？第 一 步 ：第 二 步 ：第 三 步 ：2 1 1 2 2 1 1 2( )a b a b y a c a c - 1 2 2 1( 0)a b a b 練 習(xí) 1. 給 出 求 1+2+3+4+5+6的 一 個 算 法 .解 法 1.按 照 逐 一 相 加 的 程 序 進 行 .第 一 步 :計 算 1+2,得 3;第 二 步 :將 第 一 步 中 的 運 算 結(jié) 果 3與 3相 加 得 6;第 三 步 :將 第 二 步 中 的 運 算 結(jié) 果 6與 4相 加 得 10;第 四 步 :將 第 三 步 中 的 運 算 結(jié) 果 10與 5相 加 得 15;第 五 步 :將 第 四 步 中 的 運 算 結(jié) 果 15與 6相 加 得 21. 解 法 2.可 以 運 用 下 面 公 式 直 接 計 算 .( 1)1 2 3 4 2n nn 第 一 步 ,取 n =6;第 二 步 ,計 算 ;2 )1( nn第 三 步 ,輸 出 計 算 結(jié) 果 .點 評 :解 法 1繁 瑣 ,步 驟 較 多 ; 解 法 2簡 單 ， 步驟 較 少 . 找 出 好 的 算 法 是 我 們 的 追 求 目 標(biāo) . 在 數(shù) 學(xué) 中 ， 算 法 通 常 是 指 按 照 一 定 規(guī) 則解 決 某 一 類 問 題 的 明 確 和 有 限 的 步 驟 .現(xiàn) 在 ，算 法 通 常 可 以 編 成 計 算 機 程 序 ， 讓 計 算 機 執(zhí)行 并 解 決 問 題 .2.算 法 的 要 求(1)寫 出 的 算 法 ,必 須 能 解 決 一 類 問 題 (例 如 解 任意 一 個 二 元 一 次 方 程 組 ),并 且 能 重 復(fù) 使 用 ;(2) 算 法 過 程 要 能 一 步 一 步 執(zhí) 行 ,每 一 步 執(zhí) 行 的操 作 ,必 須 確 切 ,不 能 含 混 不 清 ,而 且 在 有 限 步 之內(nèi) 完 成 后 能 得 出 結(jié) 果 .1.算 法 的 定 義 講 授 新 課 3.算 法 的 基 本 特 征 :明 確 性 :算 法 對 每 一 個 步 驟 都 有 確 切 的 、 非 二義 性 的 規(guī) 定 ,即 每 一 步 對 于 利 用 算 法 解 決 問 題 的人 或 計 算 機 來 說 都 是 可 讀 的 、 可 執(zhí) 行 的 ,而 不 需要 計 算 者 臨 時 動 腦 筋 . 有 效 性 :算 法 的 每 一 個 步 驟 都 能 夠 通 過 基 本 運算 有 效 地 進 行 ,并 得 到 確 定 的 結(jié) 果 ； 對 于 相 同 的輸 入 ,無 論 誰 執(zhí) 行 算 法 ,都 能 夠 得 到 相 同 的 最 終結(jié) 果 講 授 新 課有 限 性 :算 法 應(yīng) 由 有 限 步 組 成 ,至 少 對 某 些 輸 入,算 法 應(yīng) 在 有 限 多 步 內(nèi) 結(jié) 束 ,并 給 出 計 算 結(jié) 果 信 息 輸 出 :一 個 算 法 至 少 要 有 一 個 有 效 的 信息 輸 出 ,這 就 是 問 題 求 解 的 結(jié) 果 .不 唯 一 性 :求 解 某 一 個 題 的 解 法 不 一 定 是 唯一 的 , 對 于 一 個 問 題 可 以 有 不 同 的 算 法 .4.算 法 的 描 述 : 描 述 算 法 可 以 有 不 同 的 方 式 ,常 用 的 有 自然 語 言 、 程 序 框 圖 、 程 序 設(shè) 計 語 言 、 偽 代 碼 等 .數(shù) 據(jù) 輸 入 :算 法 一 定 要 根 據(jù) 輸 入 的 初 始 數(shù) 據(jù) 或給 定 的 初 值 才 能 正 確 執(zhí) 行 它 的 每 一 步 驟 . 自 然 語 言 就 是 人 們 日 常 使 用 的 語 言 ,可 以 是漢 語 、 英 語 或 數(shù) 學(xué) 語 言 等 .用 自 然 語 言 描 述 算 法的 優(yōu) 點 是 通 俗 易 懂 ,當(dāng) 算 法 中 的 操 作 步 驟 都 是 順序 執(zhí) 行 時 比 較 容 易 理 解 .缺 點 是 如 果 算 法 中 包 含判 斷 和 轉(zhuǎn) 向 ,并 且 操 作 步 驟 較 多 時 ,就 不 那 么 直觀 清 晰 了 .(1)自 然 語 言(2)程 序 框 圖(3)程 序 設(shè) 計 語 言 1.1.2程 序 框 圖 中 講 解1.2基 本 算 法 語 句 中 講 解 例 1.(1)設(shè) 計 一 個 算 法 判 斷 7是 否 為 質(zhì) 數(shù) .第 一 步 , 用 2除 7,得 到 余 數(shù) 1.因 為 余 數(shù) 不 為 0， 所 以 2不 能 整 除 7.第 二 步 , 用 3除 7,得 到 余 數(shù) 1.因 為 余 數(shù) 不 為 0， 所 以 3不 能 整 除 7.第 三 步 , 用 4除 7,得 到 余 數(shù) 3.因 為 余 數(shù) 不 為 0， 所 以 4不 能 整 除 7.第 四 步 , 用 5除 7,得 到 余 數(shù) 2.因 為 余 數(shù) 不 為 0， 所 以 5不 能 整 除 7.第 五 步 , 用 6除 7,得 到 余 數(shù) 1.因 為 余 數(shù) 不 為 0， 所 以 6不 能 整 除 7.因 此 ， 7是 質(zhì) 數(shù) . 例 1.(2)設(shè) 計 一 個 算 法 判 斷 35是 否 為 質(zhì)數(shù) .第 一 步 , 用 2除 35,得 到 余 數(shù) 1.因 為 余 數(shù) 不 為 0， 所 以 2不 能 整 除 35.第 二 步 , 用 3除 35,得 到 余 數(shù) 2.因 為 余 數(shù) 不 為 0， 所 以 3不 能 整 除 35.第 三 步 , 用 4除 35,得 到 余 數(shù) 3.因 為 余 數(shù) 不 為 0， 所 以 4不 能 整 除 35.第 四 步 , 用 5除 35,得 到 余 數(shù) 0.因 為 余 數(shù) 為 0， 所 以 5能 整 除 35.因 此 ， 35不 是 質(zhì) 數(shù) . 變 式 1:寫 出 “ 判 斷 53是 否 質(zhì) 數(shù) ” 的 算 法 算 法 要 “ 面 面 俱 到 ” ,不 能 省 略 任 何 一 個 細 小 的 步 驟 ,只 有 這 樣 ,才 能 在 人 設(shè) 計 出 算 法 后 ,把 具 體 的 執(zhí) 行 過 程 交 給 計 算 機 完 成 . 設(shè) 計 一 個 具 體 問 題 的 算 法 時 ,與 過 去 熟 悉 地 解 數(shù) 學(xué) 題 的 過 程有 直 接 的 聯(lián) 系 ,但 這 個 過 程 必 須 被 分 解 成 若 干 個 明 確 的 步 驟 ,而 且 這 些 步 驟 必 須 是 有 效 的 .注 意 ： 變 式 2:任 意 給 定 一 個 大 于 1的 整 數(shù) n,試 設(shè) 計 一 個程 序 或 步 驟 對 n是 否 為 質(zhì) 數(shù) 做 出 判 定 .分 析 :回 顧 這 個 問 題 的 解 題 過 程 .算 法 步 驟 :第 一 步 :判 斷 n是 否 等 于 2. 若 n=2,則 n是 質(zhì) 數(shù) ;若 n2,則 執(zhí) 行 第 二 步 . 第 二 步 :依 次 檢 驗 2(n-1)這 些 整 數(shù) 是 不 是 n的約 數(shù) ,即 是 不 是 整 除 n的 數(shù) .若 有 這 樣 的 數(shù) ,則 n不 是 質(zhì) 數(shù) ;若 沒 有 這 樣 的 數(shù) ,則 n是 質(zhì) 數(shù) . 例 2.用 二 分 法 設(shè) 計 一 個 求 方 程2 2 0 x 的 近 似 根 的 算 法 .( 0)x 二 分 法 對 于 區(qū) 間 a,b 上 連 續(xù) 不 斷 、 且f(a)f(b)0的 函 數(shù) y=f(x),通 過 不 斷 地把 函 數(shù) f(x)的 零 點 所 在 的 區(qū) 間 一 分為 二 ， 使 區(qū) 間 的 兩 個 端 點 逐 步 逼 近零 點 ， 進 而 得 到 零 點 或 其 近 似 值 的方 法 叫 做 二 分 法 . 第 四 步 , 若 f(a) f(m) 0,則 含 零 點 的 區(qū) 間 為 a,m ；第 二 步 , 給 定 區(qū) 間 a,b ,滿 足 f(a) f(b) 0第 三 步 , 取 中 間 點 2a bm 第 五 步 ,判 斷 f(m)是 否 等 于 或 者 a,b 的 長度 是 否 小 于 d， 若 是 ， 則 m是 方 程 的 近 似 解 ;否則 ， 返 回 第 三 步 將 新 得 到 的 含 零 點 的 仍 然 記 為 a,b . 否 則 ， 含 零 點 的 區(qū) 間 為 m, b .算 法 步 驟 ：第 一 步 , 令 ,給 定 精 確 度 d.2( ) 2f x x a b |a-b|1 2 11 1.5 0.51.25 1.5 0.251.375 1.5 0.1251.375 1.437 5 0.062 51.406 25 1.437 5 0.031 251.406 25 1.421 875 0.015 6251.414 625 1.421 875 0.007 812 51.414 062 5 1.417 968 75 0.003 906 25當(dāng) d=0.005時 ， 按 照 以 上 算 法 ， 可 得 下 面 表 和 圖 . y=x2-21 21.51.3751.25 于 是 ， 開 區(qū) 間 （ 1.4140625,1.41796875） 中的 實 數(shù) 都 是 當(dāng) 精 確 度 為 0.005時 的 原 方 程 的 近似 解 . 練 習(xí) 題2. 任 意 給 定 一 個 正 實 數(shù) ,設(shè) 計 一 個 算 法 求以 這 個 數(shù) 為 半 徑 的 圓 的 面 積 .3. 任 意 給 定 一 個 大 于 1 的 正 整 數(shù) n ， 設(shè)計 一 個 算 法 求 出 n 的 所 有 因 數(shù) . 4. 寫 出 求 一 元 二 次 方 程 ax2+bx+c=0 的 根 的 算 法 . 小 結(jié) ： 算 法 的 特 征 是 什 么 ？ n明 確 性 n有 效 性 n有 限 性算 法 的 概 念 ： 算 法 通 常 指 可 以 用 來 解 決 的 某一 類 問 題 的 步 驟 或 程 序 ， 這 些 步 驟 或 程 序 必 須 是 明確 的 和 有 效 的 ， 而 且 能 夠 在 有 限 步 之 內(nèi) 完 成 的 . 作 業(yè) ：1. 寫 出 你 在 家 里 燒 開 水 過 程 的 一 個 算 法 .2. 已 知 平 面 直 角 坐 標(biāo) 系 的 兩 點 A(-2， 0)， B(4， 2)， 寫 出 求 直 線 AB的 方 程 的 一 個 算 法 。