算法設(shè)計(jì)與分析(第2版)-鄭宗漢-第1章-(編輯修改稿)
2025-09-01 15:24 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 60。第二步 :……第三步 :第四步 :正整數(shù) m和 nm和 n的最大公約數(shù)求余數(shù) r?m%nifr==0?yes終止 (n為答案 )no執(zhí)行第三步。m?n,n?r,返回第一步。 算法的定義和特性最大公約數(shù)問題： 求兩個(gè)正整數(shù) m和 n的最大公約數(shù)輸入 ：一個(gè)算法有 0個(gè)或多個(gè)輸入，它是由外部提供的，作為算法開始執(zhí)行前的初始值，或初始狀態(tài)。算法的輸入是從特定的對(duì)象集合中抽取的。算法中有兩個(gè)輸入 m、 n，就是從正整數(shù)集合中抽取的。輸出 ：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出與輸入有特定的關(guān)系，實(shí)際上是輸入的某種函數(shù)。不同取值的輸入，產(chǎn)生不同結(jié)果的輸出。算法中的輸出是輸入 m、 n的最大公約數(shù)。有限性 ：算法在執(zhí)行有限步之后必須終止。算法（歐幾里德算法）中，對(duì)輸入的任意正整數(shù) m、 n，將 m除以 n的余數(shù)賦予 r之后，再通過 r賦予 n，從而使 n值變小。如此往復(fù)進(jìn)行，最終或者使 r為 0，或者使 n遞減為 1。這兩種情況，都最終使 r=0，而使算法終止。確定性 ：算法的每一個(gè)步驟，都有精確的定義。要執(zhí)行的每一個(gè)動(dòng)作都是清晰的、無歧義的。例如，在算法的第 3行中，如果m、 n是無理數(shù)，那么， m除以 n的余數(shù)就沒有一個(gè)明確的界定。確定性的準(zhǔn)則意味著必須確保在執(zhí)行第 3行時(shí)， m和 n的值都是正整數(shù)。算法規(guī)定了 m、 n都是正整數(shù)，從而保證了后續(xù)各個(gè)步驟中都能確定地執(zhí)行。可行性 ：算法中所有待實(shí)現(xiàn)的運(yùn)算，都是基本的運(yùn)算。原則上可以由人們用紙和筆，在有限的時(shí)間里精確地完成。算法 中整除、判斷、賦值等等運(yùn)算都是可行的。因?yàn)檎麛?shù)可以用有限的方式表示。如果所涉及的數(shù)值必須由展開成無窮小數(shù)的實(shí)數(shù)來精確地完成，則這些運(yùn)算就不是可行的了。注意：有限性的限制是不夠的。一個(gè)實(shí)用的算法，不僅要求步驟有限，同時(shí)要求運(yùn)行這些步驟所花費(fèi)的時(shí)間是人們可以接受的。特性：（ 1）輸入（ 2）輸出（ 3）有限性（ 4）確定性（ 5）可行性14o 引言n 算法的定義和特性n 算法的設(shè)計(jì)和復(fù)雜性分析 算法的設(shè)計(jì)和復(fù)雜性分析o 過程15理解問題算法表示算法分析算法實(shí)現(xiàn)o 例 1百雞問題：n 公雞每只 5元、母雞每只 3元、小雞 3只 1元，用 100元錢買 100只雞，求公雞、母雞、小雞的只數(shù)。n 令 a為公雞數(shù)， 為 b母雞數(shù)， c為小雞數(shù)，則： （ ） （ ）
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1