c# - 算法正确性的证明

问题描述

[编辑 1]：- 我不知道为什么这个问题被标记为不集中。我正在寻找这个程序正确性或不正确性的科学证据。如果您无法回答/没有时间回答，如果您能提供进一步阅读的参考资料，我将不胜感激。

[编辑 2]：- 问题陈述：-

给定一组正整数 S 和一个整数 K ，确定它是否可以分成三个不相交的子集，每个子集的元素之和为 K 并且它们覆盖 S。

示例：- S : {7,3,2,1,5,4,8} 和 K 为 10，三个子集将是：- { 7 , 3} {5,4,1} {8,2}

这是 3-way-partition问题的链接。我想出了以下解决方案

using System;

public class Program
{
    public static void Main()
    {
        Console.WriteLine("Hello World");

        int[] arr = {7,3,2, 1, 5, 4, 8};
        int sum = 10;
        int[] visited = new int[arr.Length];

        bool v1 = calc(sum, visited, arr);
        bool v2 = calc(sum, visited, arr);
        bool v3 = calc(sum, visited, arr);
        bool v4 = true;

        foreach (var item in visited)
        {
            if (item == 0)
            {
                v4 = false;
                break;
            }
        }

        Console.WriteLine(v1 && v2 && v3 && v4);  
    }

    public static bool calc(int sum, int[] visited, int[] arr)
    {
        if (sum < 0)
        {
            return false;
        }

        if (sum == 0)
        {
            return true;
        }

        else
        {
            for (int i = 0; i < visited.Length; i++)
            {
                if (visited[i] == 0)
                {
                    visited[i] = 1;

                    int[] newV = new int[visited.Length];
                    // Array.Copy(visited, 0, newV, 0, visited.Length);
                    if (calc(sum - arr[i], visited, arr) == true)
                    {
                        return true;
                    }

                    else
                    {
                        visited[i] = 0;
                    }
                }
            }

            return false;
        }
    }
}

我的方法是使用回溯解决问题三次，并检查数组中是否还有未访问的元素。我如何证明这个算法是否正确

标签： c#algorithmdynamic-programmingproof-of-correctness

证明一个算法不正确只需要一个反例：

[2,2,1,4,3,3]

如果第一个调用需要[2,2,1]，那么剩余的调用将失败，因为[4,3,3]不能分成两种方式。

但是，如果第一个调用需要[4,1]，那么其他两个可以获取[2,3]和[2,3]

c# - 算法正确性的证明

问题描述

解决方案

推荐阅读