《算法的概念》PPT課件.ppt

1.1.1 算 法 的 概 念1.1 算 法 與 程 序 框 圖 發(fā) 電 子 郵 件 的 方 法 很 多 ， 下 面 是 其 中 的 一 種 操 作 步驟 ： ;第 二 步 點(diǎn) 擊 “ 寫 信 ” ;第 三 步 輸 入 收 件 人 地 址;第 四 步 輸 入 主 題 ;第 五 步 輸 入 信 件 內(nèi) 容第 六 步 點(diǎn) 擊 “ 發(fā) 送 ” .;第 一 步 登 錄 電 子 信 箱新 課 導(dǎo) 入假 如 你 的 朋 友 不 會 發(fā) 電 子 郵 件 ， 你 怎 么 教 會 他 ？ 我 們 做 任 何 事 情 都 是 在 一 定 條 件 下 按 某 種順 序 執(zhí) 行 的 一 系 列 操 作 。 解 決 數(shù) 學(xué) 問 題 也 是 如此 。 例 如 用 加 減 消 元 法 解 二 元 一 次 方 程 組 時 ，就 可 以 按 照 某 一 步 驟 進(jìn) 行 操 作 。 請 你 寫 出 解 下 面 二 元 一 次 方 程 組 的 詳 細(xì) 過 程 . 2 12 1x yx y 第 二 步 , 解 得 1 ;5x 第 三 步 , - 2得 5y=3; 第 四 步 , 解 得 3 ;5y 1,53.5xy 第 五 步 , 得 到 方 程 組 的 解 為第 一 步 , + 2得 5x=1; 解 ： 你 能 寫 出 解 一 般 的 二 元 一 次 方 程 組 的 步 驟 嗎 ？ 第 一 步 , 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 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 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 ,.cb c bx a b a ba c a cy a b a b 這 兩 個 解 方 程 組 的 算 法 的 適 用 范 圍 有 何 不 同 ？ 在 數(shù) 學(xué) 中 ， 算 法 通 常 是 指 按 照 一 定 規(guī) 則 解 決 某一 類 問 題 的 明 確 和 有 限 的 步 驟 .現(xiàn) 在 ， 算 法 通 常 可以 編 成 計(jì) 算 機(jī) 程 序 ， 讓 計(jì) 算 機(jī) 執(zhí) 行 并 解 決 問 題 .2.算 法 的 要 求(1)寫 出 的 算 法 ,必 須 能 解 決 一 類 問 題 (例 如 解 任 意 一個 二 元 一 次 方 程 組 ),并 且 能 重 復(fù) 使 用 ;(2) 算 法 過 程 要 能 一 步 一 步 執(zhí) 行 ,每 一 步 執(zhí) 行 的 操 作 ,必 須 確 切 ,不 能 含 混 不 清 ,而 且 在 有 限 步 之 內(nèi) 完 成 后能 得 出 結(jié) 果 .1.算 法 的 定 義探 究 新 知描 述 算 法 可 以 有 不 同 的 方 式 ， 例 如 ， 可 以 用 自 然 語 言 和 數(shù) 學(xué) 語言 加 以 敘 述 ； 也 可 以 用 算 法 語 言 給 出 精 確 的 說 明 ； 或 者 用 框 圖直 觀 地 顯 示 算 法 的 全 貌 。 處 理 同 一 個 問 題 可 能 有 不 同 的 算 法 ， 采 用 什 么 樣 的算 法 更 簡 單 、 方 便 呢 例 2、 著 名 數(shù) 學(xué) 家 華 羅 庚 “ 燒 水 泡 茶 ” 的 兩 個 算 法 。 算 法 一 ：第 一 步 ： 燒 水 ； 第 二 步 ： 水 燒 開 后 ， 洗 刷 茶 具 ；第 三 步 ： 沏 茶 。 區(qū) 別 是 在 什 么 時 間 洗 刷 茶 具 。 第 二 個 算 法 的 科 學(xué) 性 在 于 應(yīng) 用 了 “ 統(tǒng) 籌 方 法 ” 。 因 此 ， 我 們 可 以 明 白 一 個 好 算 法 必 須 用 到科 學(xué) 的 方 法 。 我 們 應(yīng) 該 好 好 學(xué) 習(xí) 各 學(xué) 科 處 理 問 題 的 科 學(xué) 方 法 。算 法 二 ：第 一 步 ： 燒 水 ； 第 二 步 ： 燒 水 過 程 中 ， 洗 刷 茶 具 ； 第 三 步 ： 水 燒 開 后 沏 茶 。 大 家 講 討 論 一 下 這 兩 個 算 法 的 區(qū) 別 在 哪 里 ？ 哪 個 算法 更 高 效 ？ 為 什 么 ？ （ 1） 有 限 性 ： 算 法 應(yīng) 由 有 限 步 組 成 ,至 少 對 某 些 輸 入 ,算 法 應(yīng) 在 有 限 多 步 內(nèi) 結(jié) 束 ,并 給 出 計(jì) 算 結(jié) 果 （ 2） 確 定 性 ： 即 算 法 中 的 每 一 步 應(yīng) 該 是 確 定 的 并 且 能 有效 地 執(zhí) 行 且 得 到 確 定 的 結(jié) 果 ；（ 3） 有 序 性 ： 即 算 法 從 初 始 步 驟 開 始 ， 分 為 若 干 明 確 的步 驟 ， 前 一 步 是 后 一 步 的 前 提 ， 只 有 執(zhí) 行 完 前 一 步 才 能 進(jìn)行 下 一 步 ， 而 且 每 一 步 都 是 正 確 無 誤 的 ， 從 而 組 成 了 一 個有 著 很 強(qiáng) 邏 輯 性 的 步 驟 序 列 ；（ 5） 普 遍 性 ： 即 很 多 具 體 的 問 題 ， 都 可 以 設(shè) 計(jì) 合 理 的 算法 去 解 決 。3.算 法 的 基 本 特 征 :（ 4） 不 唯 一 性 :求 解 某 一 個 題 的 解 法 不 一 定 是 唯 一 的 , 對 于 一 個 問 題 可 以 有 不 同 的 算 法 . 例 1.(1)設(shè) 計(jì) 一 個 算 法 判 斷 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è) 計(jì) 一 個 算 法 判 斷 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ù) . 變 式 一 ： 設(shè) 計(jì) 一 個 算 法 判 斷 1997是 否 為 質(zhì) 數(shù)第 一 步 ， 令 i=2第 二 步 ， 用 i除 1997， 得 到 余 數(shù) r。第 三 步 ， 判 斷 “ r=0” 是 否 成 立 ， 若 是 ， 則 1997不 是 質(zhì) 數(shù) ， 結(jié) 束 算 法 ;否 則 ， 將 i的 值 增 加 1， 仍用 i表 示 。第 四 步 ， 判 斷 “ i1996是 否 成 立 ， 若 是 ， 則1997是 質(zhì) 數(shù) ， 結(jié) 束 算 法 ； 否 則 ， 返 回 第 二 步 。 任 意 給 定 一 個 大 于 1的 整 數(shù) n,試 設(shè) 計(jì) 一 個 程 序 或 步 驟 對 n是 否 為 質(zhì) 數(shù) 做 出 判 定 .分 析 :回 顧 這 個 問 題 的 解 題 過 程 .算 法 步 驟 :第 一 步 :判 斷 n是 否 等 于 2. 若 n=2,則 n是 質(zhì) 數(shù) ;若 n2,則 執(zhí) 行 第 二 步 . 第 二 步 :依 次 檢 驗(yàn) 2(n-1)這 些 整 數(shù) 是 不 是 n的 約 數(shù) , 即 是 不 是 整 除 n的 數(shù) .若 有 這 樣 的 數(shù) ,則 n不 是 質(zhì) 數(shù) ;若沒 有 這 樣 的 數(shù) ,則 n是 質(zhì) 數(shù) .探 究 第 一 步 , 給 定 大 于 1的 整 數(shù) n. 第 二 步 , 令 i=1. 第 三 步 , 用 i除 n,得 到 余 數(shù) r. 第 四 步 ,判 斷 ” r=0” 是 否 成 立 .若 是 ,則 n不 是 質(zhì) 數(shù) ,結(jié) 束 算 法 ;否 則 ,將 i的 值 增 加 1,仍 用 i表 示 . 第 五 步 , 判 斷 ” i(n-1)” 是 否 成 立 .若 是 ,則 n是質(zhì) 數(shù) ,結(jié) 束 算 法 ;否 則 ,返 回 第 三 步 .任 意 給 定 一 個 大 于 1的 整 數(shù) n,試 設(shè) 計(jì) 一 個 程序 或 步 驟 對 n是 否 為 質(zhì) 數(shù) 做 出 判 定 . 2 2 0 0 x x 例 2： 用 二 分 法 設(shè) 計(jì) 一 個 求 方 程 的 近 似 根 的 算 法 對 于 區(qū) 間 a,b 上 連 續(xù) 不 斷 、 且 f(a)f(b)0的 函數(shù) y=f(x),通 過 不 斷 地 把 函 數(shù) f(x)的 零 點(diǎn) 所 在 的 區(qū) 間 一分 為 二 ,使 區(qū) 間 的 兩 個 端 點(diǎn) 逐 步 逼 近 零 點(diǎn) ， 進(jìn) 而 得 到 零點(diǎn) 或 其 近 似 值 的 方 法 叫 做 二 分 法 。二 分 法 的 基 本 思 想 ：分 析 ： 2 2( ) 2, 2 0 ( )f x x x f x 令 則 方 程 的 解 就 是 函 數(shù) 的 零 點(diǎn) 。 第 四 步 , 若 f(a) f(m) 2x +4； 求 M(1， 2)與 N(3， 5)兩 點(diǎn) 連 線 的 方 程 可 先 求 MN的 斜 率 再 利 用 點(diǎn) 斜 式 方 程 求 得 A. 1 個 B. 2 個 C. 3 個 D. 4 個21 C 6 寫 出 求 1 2 3 100的 一 個 算 法 .可 以運(yùn) 用 公 式 1 2 3 n直 接 計(jì) 算 .第 一 步 ；第 二 步 ；第 三 步 輸 出 運(yùn) 算 結(jié) 果 . ( 1)2n n 取 n 100 計(jì) 算 ( 1)2n n 7 已 知 一 個 學(xué) 生 的 語 文 成 績 為 89， 數(shù) 學(xué) 成 績 為96， 外 語 成 績 為 99， 求 他 的 總 分 和 平 均 成 績 的一 個 算 法 為 ：第 一 步 取 A 89， B 96， C 99;第 二 步 ；第 三 步 ；第 四 步 輸 出 D， E. 計(jì) 算 總 分 D A+B+C 計(jì) 算 平 均 成 績 E 3D 思 考 ： 有 人 對 歌 德 巴 赫 猜 想 “ 任 何 大 于 4的 偶 數(shù) 都 能 寫 成 兩 個 奇 質(zhì) 數(shù) 之 和 ”設(shè) 計(jì) 了 如 下 操 作 步 驟 ：第 一 步 ： 檢 驗(yàn) 6=3+3 第 二 步 ： 檢 驗(yàn) 8=3+5第 三 步 ： 檢 驗(yàn) 10=5+5 . . . . . . 利 用 計(jì) 算 機(jī) 無 窮 地 進(jìn) 行 下 去 ！ 請 問 ， 利 用 這 種 程 序 能 夠 證 明 猜 想 的 正 確 性嗎 ？ 這 是 一 種 算 法 嗎 ？ 2.算 法 的 特 征 是 什 么 ？有 限 性 確 定 性 邏 輯 性1.算 法 的 概 念 算 法 通 常 指 可 以 用 來 解 決 的 某 一 類 問 題 的 步 驟 或程 序 ， 這 些 步 驟 或 程 序 必 須 是 明 確 的 和 有 效 的 ， 而 且能 夠 在 有 限 步 之 內(nèi) 完 成 的 .課 堂 小 結(jié) 不 唯 一 性 普 遍 性 1. 任 意 給 定 一 個 正 實(shí) 數(shù) ,設(shè) 計(jì) 一 個 算 法 求 以 這 個 數(shù)為 半 徑 的 圓 的 面 積 .算 法 步 驟 :第 一 步 :給 定 一 個 正 實(shí) 數(shù) r;第 二 步 :計(jì) 算 以 r為 半 徑 的 圓 的 面 積 S= r2;第 三 步 :得 到 圓 的 面 積 S.課 后 練 習(xí)