天天看點

經典算法題每日演練——第二題 五家共井

          古代數學巨著《九章算數》中有這麼一道題叫“五家共井,甲二绠(汲水用的井繩)不足,如(接上)乙一绠;乙三绠不足,如丙一绠;

丙四绠不足,如丁一绠;丁五绠不足,如戊一绠;戊六绠不足,如甲一绠,皆及。

意思就是說五家人共用一口井,甲家的繩子用兩條不夠,還要再用乙家的繩子一條才能打到井水;乙家的繩子用三條不夠,還要再用丙家的繩子

一條才能打到井水;丙家的繩子用四條不夠,還要再用丁家的繩子一條才能打到井水;丁家的繩子用五條不夠,還要再用戊家的繩子一條才能打

到井水;戊家的繩子用六條不夠,還要再用甲家的繩子一條才能打到井水。

最後問:井有多深?每家的繩子各有多長?

分析:同樣這套題也是屬于不定方程,拿這個題目的目地就是讓大家能夠在不定方程組這種範疇問題上做到“舉一反三”,根據題意

        我們設井深為h,各家分别為a,b,c,d,e,則可以列出如下方程組:

        2a+b=h   ①

        3b+c=h   ②

        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的倍數,根據這種關系我們

就可以有如下代碼:

經典算法題每日演練——第二題 五家共井

同樣我們的時間複雜度是o(n2),急需優化。

我們再來看看文藝青年的想法,他們的想法是找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,否則繩子已經到達極限了,需要用蛟龍号去深潛了。

經典算法題每日演練——第二題 五家共井

相信大家以後遇到類似的問題,應該會胸有成竹了。

繼續閱讀