当前位置:首页 » Project Euler » 详细页

Arranged probability 题号:100 难度: 30 中英对照

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 1012 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

Solution

即求下列方程的整数解: $$ \frac{b}{n}\frac{b-1}{n-1} = \frac{1}{2} $$ 其中$n$是盘子总数$b$是蓝色盘子的个数。 对方程进行变形: $$ b^2-b=\frac{1}{2}(n^2-n) $$ $$ 2b^2-2b-n^2+n=0 $$ 这是一个丢番图方程,[点击此处](https://www.alpertron.com.ar/QUAD.HTM)可求得递推公式: $$b_{k+1}=3b_k+2n_k-2$$ $$n_{k+1}=4b_k+3n_k-3$$ 利用 $b_0=15,n_0=21$ ,用此递推公式用迭代算法即可求得一个数$n$,满足比给定的一个最小值大。

Code

using System;
namespace euler
{
    class Problem100
    {
        public static void Main(string[] args)
        {
            var start = DateTime.Now;
            var result = Run();
            var end = DateTime.Now;
            Console.WriteLine(result);
            Console.WriteLine("{0} ms", (end - start).TotalMilliseconds);
            Console.Read();
        }
        public static long Run()
        {
            long b = 15;
            long n = 21;
            long target = 1000000000000;
            while (n < target)
            {
                long btemp = 3 * b + 2 * n - 2;
                long ntemp = 4 * b + 3 * n - 3;
                b = btemp;
                n = ntemp;
            }
            return b;            
        }
    }
}
756872327473
7.999 ms
public class p100 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        long result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    public static long run() {
        long b = 15;
        long n = 21;
        long target = 1000000000000l;
        while(n < target){
            long btemp = 3 * b + 2 * n - 2;
            long ntemp = 4 * b + 3 * n - 3;
            b = btemp;
            n = ntemp;
        }
        return b;
    }
}
756872327473
0ms