1

我最近正在阅读Robert Sedgewick的《算法》一书。我在阅读“算法分析”时遇到了一段代码。代码如下：

public static int count(int a[]) {
    int N = a.length;
    int cnt = 0;
    for (int i = 0; i < N; i++) {

        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                if (a[i] + a[j] + a[k] == 0) {  //here 
                    cnt++;
                }
            }
        }
    } 
    return cnt
}

我想知道的是-loop中的if-statement执行了多少次。for本书提供的答案是N(N-1)(N-2)/6。但是我不知道为什么，谁能解释一下。

4

3 回答 3

6

您只需要评估以下总和：

在此处输入图像描述

你可以手动完成，但Wolfram Alpha在这方面做得更好。

不难验证

( N -1)( N -2) = N 2 - 3 N + 2

它显示了您给出的公式。

对于手动分析：

从内部总和开始，这很容易：

在此处输入图像描述

将其插入中间总和给出：

在此处输入图像描述

如果虚拟变量从 0（而不是i+1）开始，这个总和会更容易评估，因此我们应用虚拟变换p = j - i - 1：

在此处输入图像描述

最后，这必须插入外部总和：

在此处输入图像描述

于 2013-08-07T13:54:43.267 回答
0

我一直在玩这个。似乎这个问题既是数学问题，也是计算问题。

第一件事是第一件事。if 语句的实际内容完全是红鲱鱼，因为它们依赖于数组的内容。我使用了从 0 开始的前 x 个自然数（实际上是数组的索引），因此 if 语句永远不会解析为 true。

为了测试 if 语句被访问n(n-1)(n-2) 次的断言，我将代码更改为以下内容：

public class Iteration {



public static void main(String[] args) {
    int[] a = {0,1,2,3,4};

    System.out.println(count(a));



}

public static int count(int a[]) {
    int N = a.length;
    int cnt = 0;
    int access = 0;

    for (int i = 0; i < N; i++) {

        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {

                access++;
                System.out.println(access + " " +a[i] + a[j] + a[k]);
                if (a[i] + a[j] + a[k] == 0 ) {  //here 
                    cnt++;
                }
            }
        }
    } 
    return cnt;
}
}

控制台返回如下：

1 012 2 013 3 014 4 023 5 024 6 034 7 123 8 124 9 134 10 234 0

这是所提供整数的唯一组合的计数。所以我从Maths is fun中查找了三位数字的独特组合的公式。

然后简要介绍公式中的“6”。由于 3 位数字的每个组合只出现一次，请考虑您可以订购 3 位数字的次数（让我们看看 1、2 和 3）：

123 132 213 231 312 321

6次！但是由于这种组合只出现一次（123），我们将总数除以 6 来找出返回的数量。上面的链接进一步描述了数学的详细信息，包括通用解决方案，无论使用的整数数量如何，以及循环的大小。

于 2013-08-07T14:22:59.960 回答
0

变量 i、j 和 k 取自集合 {0,1,...,N-1}。但它们总是有序的，所以可能性的数量是 C(N,3)=N!/((N-3)!3!)。

于 2013-08-07T19:14:04.993 回答