1.4.40

1.4.40 #

解答 #

N 个数可组成的三元组的总数为：

$C(N, 3) = N(N-1)(N-2)/3! = ~ (N^3)/6$ （组合数公式）

$[-M, M]$ 中随机 $N$ 次，有 $(2M+1)^N$ 种随机序列（每次随机都有 $2M+1$ 种可能）

按照分步计数方法，将随机序列分为和为零的三元组和其余 $N-3$ 个数

这些序列中，和为零的三元组有 $3M^2 + 3M + 1$ 种可能。

其他不为零的 $N-3$ 个位置有 $(2M+1)^{(N-3)}$ 种可能。

总共有 $((N^3)/6) \times (3M^2 + 3M + 1) \times (2M+1)^{(N-3)}$ 种可能性

平均值为：

$[((N^3)/6) \times (3M^2 + 3M + 1) \times (2M+1)^{(N-3)}] / (2M+1)^N$ $=N^3/16M$

$3M^2 + 3M + 1$ 的推导：

在 $[-M,M]$ 中取三个数，和为零的序列有几个？假设第一个数取 $0$，取 $(0, 0, 0)$ 的情况最后加上。

剩下两个数只能以 $0$ 为中心对称配对，总共 $2M / 2$ 种组合。

换成排列数（例如 (0 ,1 ,-1) 和 (0 ,-1 ,1) 是两种不同的排列）就是 $2M$ 种。

加上 $(0, 0, 0)$ 就是 $2M+1$ 种序列。

假设第一个数取 $1$，那么 $M$ 就不能再取（剩下的数不能获得 $M+1$），剩下 $2M$ 个数对称配对。

总共 $(2M)/2 * 2 = 2M$ 种排列。

假设第一个数取 $2$，那么 $M$ 和 $M-1$ 就不能再取，剩下 $2M-1$ 个数配对。

总共 $2M-1$ 种序列。

以此类推，第一个数取 $M $ 时，只能在 $-M$ 到 $0$ 之间配对，总共 $M+1$ 种序列。

$-M$ 到 $-1$ 之间的序列数计算完全一样，于是由等差数列求和公式：

$$ \frac{(M+1+2M)M}{2} \times 2 + 2M+1=3M^2+3M+1 $$

第一项为 $1$ 到 $M$ 之间的序列数，乘上 $2$ 再加上取 $0$ 时的序列数即为所求的全部序列数。

代码 #

public static class ThreeSum
{
    /// <summary>
    /// 输出所有和为零的三元组。
    /// </summary>
    /// <param name="a">输入数组。</param>
    public static void PrintAll(int[] a)
    {
        var n = a.Length;
        for (var i = 0; i < n; i++)
        {
            Console.WriteLine($"for number \"{a[i]}\"");
            var count = 0;
            for (var j = i + 1; j < n; j++)
            {
                for (var k = j + 1; k < n; k++)
                {
                    if ((long)a[i] + a[j] + a[k] == 0)
                    {
                        Console.WriteLine($"{a[i]} + {a[j]} + {a[k]}");
                        count++;
                    }
                }
            }
            Console.WriteLine($"Count:{count}");
        }
    }

    /// <summary>
    /// 计算和为零的三元组的数量。
    /// </summary>
    /// <param name="a">输入数组。</param>
    /// <returns></returns>
    public static int Count(int[] a)
    {
        var n = a.Length;
        var count = 0;
        for (var i = 0; i < n; i++)
        {
            for (var j = i + 1; j < n; j++)
            {
                for (var k = j + 1; k < n; k++)
                {
                    if ((long)a[i] + a[j] + a[k] == 0)
                    {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}