1.4.40

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

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 ​$ 时的序列数即为所求的全部序列数。

代码

using System;

namespace _1._4._40
{
    /*
     * 1.4.40
     * 
     * 随机输入下的 3-sum 问题。
     * 猜测找出 N 个随机 int 值中和为 0 的整数三元组的数量所需的时间并验证你的猜想。
     * 如果你擅长数学分析,请为此问题给出一个合适的数学模型,
     * 其中所有值均匀的分布在 -M 和 M 之间,且 M 不能是一个小整数。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int M = 10000;

            for (int n = 125; n < 10000; n += n)
            {
                Random random = new Random();
                int[] a = new int[n];
                for (int i = 0; i < n; ++i)
                {
                    a[i] = random.Next(2 * M) - M;
                }
                Console.WriteLine($"N={n}, 计算值={Math.Pow(n, 3) / (16 * M)}, 实际值={ThreeSum.Count(a)}");
            }
        }
    }
}
上一题 下一题