1.5.21

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

解答

给出我电脑上的结果:

实验结果:10
1/2NlnN:11.5129254649702

实验结果:29
1/2NlnN:29.9573227355399

实验结果:132
1/2NlnN:73.7775890822787

实验结果:164
1/2NlnN:175.281065386955

实验结果:418
1/2NlnN:406.013905218706

实验结果:1143
1/2NlnN:922.931359327004

实验结果:2004
1/2NlnN:2067.66981643319

实验结果:4769
1/2NlnN:4578.95382842474

实验结果:10422
1/2NlnN:10045.1360479662

实验结果:21980
1/2NlnN:21864.7288781659

代码

using System;
using UnionFind;

namespace _1._5._21
{
    /*
     * 1.5.21
     * 
     * Erdös-Renyi 模型。
     * 使用练习 1.5.17 的用例验证这个猜想:
     * 得到单个连通分量所需生成的整数对数量为 ~1/2NlnN。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            for (int n = 10; n < 10000; n *= 2)
            {
                int total = 0;
                for (int i = 0; i < 100; ++i)
                {
                    UF uf = new UF(n);
                    total += ErdosRenyi.Count(uf);
                }

                Console.WriteLine("实验结果:" + total / 100);
                Console.WriteLine("1/2NlnN:" + Math.Log(n) * n * 0.5);
                Console.WriteLine();
            }
        }
    }
}

另请参阅

UnionFind 库

上一题 下一题