算法学习笔记之五家共井问题

左手的ㄟ右手 2022-08-21 07:48 83阅读 0赞

问题：  
五家人共用一口井，甲家的绳子用两条不够，还要再用乙家的绳子一条才能打到井水；乙家的绳子用三条不够，还要再用丙家的绳子一条才能打到井水；丙家的绳子用四条不够，还要再用丁家的绳子一条才能打到井水；丁家的绳子用五条不够，还要再用戊家的绳子一条才能打到井水；戊家的绳子用六条不够，还要再用甲家的绳子一条才能打到井水。  
最后问：井有多深？每家的绳子各有多长？  
这道题其实不难，大家应该都可以做出来，和上次的百钱买百鸡的问题差不多，那就有人问了，那为什么还要写出来呢，当然是普通方法会让复杂度让人难以接受的，复杂度为O(n2),需要优化。

我们令甲为a，乙为b，丙为c,丁为d，戊为e，井深为h,则

2a+b=h   ①
    
        3b+c=h   ②
    
        4c+d=h   ③
    
        5d+e=h   ④
    
        6e+a=h   ⑤

将其变形：  
b=h-2a ⑥

c=h-3b ⑦

d=h-4c ⑧

e=h-5d ⑨

a=h-6e ⑩  
将⑥，⑧，⑨，⑩分别代入⑦,可得：  
c=(148/721)h  
令 h=721k,则 c=148k，将其代入⑥，⑦，⑧，⑨，⑩可得：  
a=265k

b=191k

c=148k

d=129k

e=76k

h=721k  
因为绳长和井深不可能为负，所以k > 0，当然这样这个题目就有无数个解的，我这里去 0 < k <４；  
代码为：

public static void main(String[] args) {
    
            for (int i = 1; i < 4; i++) {
                int a = 265 * i;
                int b = 191 * i;
                int c = 148 * i;
                int d = 192 * i;
                int e = 76 * i;
                int h = 721 * i;
                System.out.println("甲绳：" + a + "乙绳：" + b + "丙绳：" + c + "丁绳：" + d + "戊绳：" + e + "井深："  + h);
            }
        }

结果：  
![这里写图片描述][20160423113602462]  
这样复杂度就变为０（ｎ）了，在这样我把这种方法叫做“统一变量法”（即减少循环的次数），大家以后遇到类似的题目可以尝试下哦。。。。

[20160423113602462]: /images/20220724/fa86c2a3911d4532bf6cc4ed98bf114d.png