此代碼的數學歸納？

我真的不明白我如何使用此代碼的歸納證明。我只是想知道如何證明這個代碼和算法的正確性。此代碼的數學歸納？

證明我們永遠不會計算已經計數的物品。

算法countCells（X，Y）

如果在所述小區（X，Y）是外

電網的結果是0;

否則如果
單元在（x，y）處的顏色不是異常顏色，則結果爲0;

else
將單元格的顏色設置爲（x，y）爲臨時的顏色;結果爲1加上包含最近鄰居的每個斑點中的單元的數量;

public int countCells(int x, int y) 
{ 
    int result; 

    if(x<0 || x>=N || y<0 || y>=N) // N is the maximum value of the matrix 
     return 0; 
    else if(!getColor(x,y).equals(ABNORMAL)) // 
     return 0; 
    else 
    { 
     recolor(x, y, TEMPORARY); 
     return 1 + countCells(x-1, y+1) + countCells(x, y+1) 
      + countCells(x+1, y+1) + countCells(x-1, y) 
      + countCells(x+1, y) + countCells(x-1, y-1) 
      + countCells(x, y-1) + countCells(x+1, y-1) 
    } 
}

下面的鏈接顯示這是如何工作

http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=104&docId=186514818

來源

2013-12-15 user3104266

*證明正確性*？你可以指定countCells應該做什麼*正確的事情？ – johnchen902

在我看來，這是一種洪水算法，它在'（x，y）'開始時計算異常顏色連接單元的數量。儘管如此，沒有什麼可證明的。 –

您並不能證明代碼的正確性，而是基於它的算法。那麼你的算法是否會計算blob中包含單元格的總元素？ –

證明通過感應

證明爲基礎的情況下條件（N = 1）

證明對於所有的假設步驟（n = k）

證明用於感應步驟+ 1（N = K + 1）

所以調用與步驟1中的鹼的作用，令k等於一些其他通用輸入，然後執行輸入+ 1

基本上你想測試你的函數的邊緣情況，以確保它們正常工作。您的老師可能希望您只爲上述功能編寫測試條件。

來源

2013-12-15 13:21:25 FaddishWorm

謝謝。但我仍然不明白我是如何通過這種算法的歸納得到證明的。我剛剛發佈了這個算法的工作原理。你能點擊我上面寫的鏈接嗎？ – user3104266

此代碼的數學歸納？

回答

相關問題