数学归纳法这个code？ [英] Mathematical induction of this Code?

问题描述

我真的不明白我是如何使用的证明用归纳法在这code。 我只是想知道如何证明这个code和算法的正确性。

证明我们永远不会指望它已经计入的项目。

算法countCells（X，Y）

  

如果于（x，y）的细胞是外

     

网格中的结果是0;

     

否则，如果
  细胞于（x，y）的颜色不是异常颜色的结果为0;

     

其他
  设置细胞的于（x，y）处的颜色到临时   颜色;结果是1加上细胞在每片的数量   斑点，其包括近邻;

 公众诠释countCells（INT X，int y）对
{
    INT结果;

    如果（X℃，|| X  -  GT; = N ||ý℃，|| Y'GT; = N）// N是矩阵的最大值
        返回0;
    否则如果（！的getColor（X，Y）.equals（异常））//
        返回0;
    其他
    {
        重新着色（X，Y，暂时的）;
        返回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

解决方案

证明用归纳法

证明了基本情况的条件（N = 1）

证明所有的假设步（N = K）

证明了归纳步+ 1（N = K + 1）

所以，调用函数与基地第1步，令k等于其他一些通用的输入，然后做输入+ 1。

基本上你想测试你的函数的边界情况，以确保它们正常工作。你的老师可能要你只是写测试条件为以上功能。

I don't really understand how I use proof by induction on this Code. I just wanna know how to prove the correctness of this code and algorithm.

Prove that we will never count items which already counted .

Algorithm for countCells(x,y)

if the cell at(x,y) is outside

the grid the result is 0;

else if
the color of the cell at (x, y) is not the abnormal color the result is 0;

else
set the color of the cell at (x, y) to a temporary color; the result is 1 plus the number of cells in each piece of the blob that includes a nearest neighbor;

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)
    }
}

the following link show how this works

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

解决方案

Proof by induction

Prove for base case condition (n = 1)

Prove for all assumption step ( n = k )

Prove for inductive step + 1 (n = k + 1)

So call your function with a base for step 1, let k equal some other generic input, then do the input + 1.

Basically you want to test the edge cases of your functions to ensure that they work properly. Your teacher probably wants you to just write test conditions for the function above.

这篇关于数学归纳法这个code？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！