策略问题

策略问题

/ 53 / 0

1、赛马问题 64/8/4=11、36/6/3=8、25/5/3=7

①全部分组跑 获得每组名次 次数=赛道数

②取第一名跑一次 淘汰后边(组数-目标数)组, 第一名确定 次数=1

③按刚才顺序排剩余几组从,取左上三角(向右目标数、向下目标数)剩余马,除去第一名剩余的进行比赛,次数与剩余有关系剩余马数量=(目标数^2 - 目标数)/2 +目标数 - 1(第一名) 如8赛道剩余9,6赛道剩余5,5赛道剩余5

④然后对剩余马进行比赛即可得出结果

如8赛道 还需2次因为剩余9大于8要增加1次,6和5再需要一次即可 

2、超级无敌的倒水问题解法

① 扩展欧几里得算法(参考链接https://blog.csdn.net/lanchunhui/article/details/50594649)

两个容器容量互质才有解?

问题:假设你有一个3升的容器和一个5升的容器(以及充足的水源),如何精确地取出4升水来?(为了下文叙述的方便,我们不妨把3升的容器和5升的容器分别记做容器A和容器B)。这里提供一种解法:

将A装满(3升),全部倒入B
再次将A装满(3升),用A中的水将B装满,此时A有1升,B有5升
B中的水全部倒出,将A中的1升水倒入B,此时A没有水,B有一升
再次将A装满(3升),将A中的水全部倒入B,此时B中恰有4升的水
显然这类问题可以有其他的解决方案。我们可轻易地编出其他类似的问题,比如是否能够用7升的水杯和13升的水杯量出5升的水,再比如能否用9升的水杯和15升的水杯量出10升的水,不胜枚举。三升五升得四升的问题还算直观,稍作思考便可构造解决方案。7升13升得5升,似乎就没那么直观了。而且还有一个问题,首先需要判断是否可行,然后才是给出解决方案。

这样的问题存在一个万能的解法吗?答案是肯定的。注意到,用3升的容器和5升的容器量出4升的水,这一看似复杂的步骤可以简单地概括为:不断地将整杯整杯的A往B里倒,期间只要B被装满就把B倒空。即求解 3xmod5=43xmod5=4,使用 扩展欧几里得算法及其应用 一文的算法我们可轻易解得 x=3x=3。首先根据扩展欧几里得算法,问题有解。x=3x=3 时,对应的解决方案见上文。

接着看 7 升 13 升得 5 升,也即 7xmod13=57xmod13=5,7,137,13 互质,首先判断有解,即存在这样一个解决方案。这个方案是怎样的呢?

第一步,首先来看贝祖等式时的情况,也即 7xmod13=17xmod13=1时,此时解得 x=2x=2,也即 2 个 A 倒入 B,A余一升(得1升)

第二步,7xmod13=57xmod13=5,此时 x=(2×5)%13=10x=(2×5)%13=10,也即对第一步的行为执行五次,如下:

将装满 7 升水的 A 倒入 B ⇒ A(0升),B(7升)
将装满7升水的 A 倒入 B,直到 B 加满为止 ⇒ A(1升),B(13升)
将 B 清空,⇒ A (1升),B(0升)
将 A 中的一升水倒入 B,⇒ A(0升),B(1升)(1,2,3,4 步为一个单元)
将 A 加满倒入 B,⇒ A(0升),B(8升)
再次将 A 加满倒入 B,直到 B 满为止,⇒ A(2升),B(13升)
将 B 清空,⇒ A(2升),B(0升)
将 A 中的 2 升水倒入 B,⇒ A(0升),B(2升)
。。。
直到 A(5升),B(0升);
我们进一步将问题抽象,用容积分别为 aa 和 bb 的水杯量出体积为 cc 的水,实际上相当于求解方程 a⋅xmodb=ca⋅xmodb=c。如果 a,ba,b 互质,问题保证有解。如果 c==gcd(a,b)c==gcd(a,b) 或者 c==k⋅gcd(a,b)c==k⋅gcd(a,b),用扩展欧几里得算法便可求解 xx,然后得最终的量水方案。如果 cc 不能被 gcd(a,b)gcd(a,b) 整除,方程无解,也即问题无解,比如9升15升的容器得10升的水,1010 不能被 gcd(9,15)=3gcd(9,15)=3 整除。

def ext_euclid(a, b):
                    # 扩展的欧几里得算法
                    # 用以求解
                    # d = gcd(a, b) = a*x+b*y
    if b == 0:
        return (a, 1, 0)
    d, x, y = ext_euclid(b, a%b)
    return (d, y, x-a//b*y)

def mod_linear_equation(a, b, c):
    d, x, y = ext_euclid(a, b)
    if c % d:
        raise 'no solution'
    return x * c//d % b

if __name__ == '__main__':
    print(mod_linear_equation(3, 5, 4))
                # 3
    print(mod_linear_equation(7, 13, 5))
                # 10

② 网格法(参考链接http://numb3rs.wolfram.com/501/puzzle.html)

小的容器不断取水倒入大的容器中直到满足条件结果为止,3升 5升如下图

 3,13,23,33,43,5 
3,0     2,5
2,0     1,5
1,0     0,5
 0,00,10,20,30,4 

 

0 人收藏

发表评论