算法設(shè)計(jì)與分析 課件 1.2.1-算法分析準(zhǔn)則 - 正確性

信息工程大學(xué)算法設(shè)計(jì)與分析算法分析—正確性國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版正確性對(duì)算法的任何有效（合法）輸入，算法能在有限時(shí)間內(nèi)，給出問(wèn)題的正確結(jié)果。證明步驟

1.建立一個(gè)給出算法輸入后算法產(chǎn)生什么樣的結(jié)果的命題。2.證明算法中使用的各種方法是正確的。3.證明命題是正確的。正確性

1.

j=1;2.whilej≤nandL[j]≠xdo3.j=j+1;4.ifj>nthenj=0;5.

output(j)

命題1：如果L是一個(gè)具有n項(xiàng)的表，若表中有一個(gè)等于X的項(xiàng)，那么這個(gè)算法以將j置成表中等于X的項(xiàng)的下標(biāo)而結(jié)束；否則，若表中沒(méi)有等于X的項(xiàng)，則這個(gè)算法將j置成0而結(jié)束。命題2：給定一個(gè)具有n項(xiàng)（n≥0）的數(shù)組L，并且給定X，當(dāng)X在L之中時(shí)，順序搜索算法將j置成X在L中第一次出現(xiàn)處的下標(biāo)而結(jié)束，否則算法將j置成0而結(jié)束。正確性缺點(diǎn)：一是沒(méi)有說(shuō)明當(dāng)x在表中多次出現(xiàn)時(shí)的結(jié)果；二是沒(méi)有指明算法在n為何值時(shí)工作。

1.

j:=1;2.whilej≤nandL[j]≠xdo3.j:=j+1;4.ifj>nthenj:=0;5.output(j)

命題3：對(duì)于1≤k≤n+1,假若算法第k次地執(zhí)行第2行中的測(cè)試，則下列條件成立：1.j=k而且對(duì)1≤i＜k,L(i)≠X。2.若k≤n而且L(k)=X，則算法將在執(zhí)行了第2行中的測(cè)試和第4行以后結(jié)束，此時(shí)j仍然等于k。3.若k=n+1，則算法將在執(zhí)行了第2行中的測(cè)試和第4行以后結(jié)束，此時(shí)j=0。數(shù)學(xué)歸納法證明的思路：1.證明k=1時(shí)，命題3成立；2.假設(shè)k<n+1時(shí)，命題3成立；3.證明k+1時(shí)，命題3成立命題3：對(duì)于1≤k≤n+1,假若算法第k次地執(zhí)行第2行中的測(cè)試，則下列條件成立：1.j=k而且對(duì)1≤i＜k,L(i)≠X。2.若k≤n而且L(k)=X，則算法將在執(zhí)行了第2行中的測(cè)試和第4行以后結(jié)束，此時(shí)j仍然等于k。3.若k=n+1，則算法將在執(zhí)行了第2行中的測(cè)試和第4行以后結(jié)束，此時(shí)j=0。證明一個(gè)算法的正確性，首先需要建立（），并常用（）進(jìn)行證明。A：給出輸入后算法將要產(chǎn)生什么結(jié)果的命題B：解決問(wèn)題的方法C：數(shù)學(xué)歸納法D：反證法測(cè)試正確性是如何證明的；