经典算法题——五家共井

时间 2020-09-20 标签经典算法题五家共井

古代数学巨著《九章算数》中有这么一道题叫“五家共井，甲二绠（汲水用的井绳）不足，如（接上）乙一绠；乙三绠不足，如丙一绠；html

丙四绠不足，如丁一绠；丁五绠不足，如戊一绠；戊六绠不足，如甲一绠，皆及。优化

意思就是说五家人共用一口井，甲家的绳子用两条不够，还要再用乙家的绳子一条才能打到井水；乙家的绳子用三条不够，还要再用丙家的绳子spa

一条才能打到井水；丙家的绳子用四条不够，还要再用丁家的绳子一条才能打到井水；丁家的绳子用五条不够，还要再用戊家的绳子一条才能打3d

到井水；戊家的绳子用六条不够，还要再用甲家的绳子一条才能打到井水。code

最后问：井有多深？每家的绳子各有多长？htm

分析：一样这套题也是属于不定方程，拿这个题目的目地就是让你们可以在不定方程组这种范畴问题上作到“触类旁通”，根据题意blog

咱们设井深为h，各家分别为a,b,c,d,e，则能够列出以下方程组：get

2a+b=h ①数学

3b+c=h ②string

4c+d=h ③

5d+e=h ④

6e+a=h ⑤

首先咱们看下普通青年的想法，他们的想法是找a,b,c,d,e之间的对应关系。

依次将②代入①，③代入②，④代入③，⑤代入④可得以下方程组：

a=b+c/2

b=c+d/3

c=d+e/4

d=e+a/5

从计算机的角度来讲，我不但愿有小数的出现，因此我可推断： c必定是2的倍数，d必定是3的倍数，e必定是4的倍数，a必定是5的倍数，根据这种关系咱们

就能够有以下代码：

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c, d, e, h;

            a = b = c = d = e = h = 0;

            bool flag = true;

            while (flag)
            {
                //4的倍数
                e += 4;

                a = 0;

                while (flag)
                {
                    //5的倍数
                    a += 5;

                    d = e + a / 5;

                    c = d + e / 4;

                    if (c % 2 != 0)
                        continue;

                    if (d % 3 != 0)
                        continue;

                    b = c + d / 3;

                    if (b + c / 2 < a)
                        break;

                    if (b + c / 2 == a)
                        flag = false;
                }
            }

            h = 2 * a + b;

            Console.WriteLine("a={0},b={1},c={2},d={3},e={4} ------h={5}\n", a, b, c, d, e, h);

            Console.Read();
        }
    }
}

一样咱们的时间复杂度是O(N²)，急需优化。

咱们再来看看文艺青年的想法，他们的想法是找a,b,c,d,e中的某个数与h的对应关系。

好比我就找c与h的对应关系，上面的①②③④⑤可写成以下方程组：

b=h-2a ⑥

c=h-3b ⑦

d=h-4c ⑧

e=h-5d ⑨

a=h-6e ⑩

将⑥，⑧，⑨，⑩分别代入⑦，一阵痉挛后可知：

c=(148/721)h

上面的公式也就代表了c和h的比例关系，咱们令 h=721k,则 c=148k，将其代入⑥，⑦，⑧，⑨，⑩可得以下方程组

a=265k

b=191k

c=148k

d=129k

e=76k

x=721k

又由于k>0，因此题目有无数个解。这里我就取0<k<5，不然绳子已经到达极限了，须要用蛟龙号去深潜了。

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int k = 1; k < 5; k++)
            {
                int h = 721 * k;

                int a = 265 * k;

                int b = 191 * k;

                int c = 148 * k;

                int d = 129 * k;

                int e = 76 * k;

                Console.WriteLine("a={0},b={1},c={2},d={3},e={4} ------h={5}\n", a, b, c, d, e, h);
            }

            Console.Read();
        }
    }
}

相信你们之后遇到相似的问题，应该会成竹在胸了。

出处：http://www.cnblogs.com/huangxincheng/archive/2012/08/06/2625427.html