1 条题解

  • 4
    @ 2019-04-21 11:12:47

    很恶心的数学结论题,反正我是解释不清这个公式怎么来的了。
    能做出来的人要么是找规律能力很强,要么是数理逻辑很好。
    这里搬运下别人的证明。

    最少步数的前提
    1:在任何一步中,两族青蛙的状态或不动或向对方运动
    2:任何一步都是可逆的
    设n为每族青蛙的“蛙”数
    A:先不考虑‘借助前面青蛙的背,跳到前面青蛙的前面一格’的情况,即每次只能跳1格(此时假设多只青蛙可以站在同一格),那么任何一族的所有青蛙共需要跳n*(n+1)次(平均思想,即平均每只都跳n+1次),所以两族一共要跳2*n*(n+1)次;
    B:但是由于‘多只青蛙可以站在同一格’是有悖与题目的,所以再来考虑‘借助前面青蛙的背,跳到前面青蛙的前面一格’的情况。这种情况每发生一次,有一只青蛙就可以跳2个,即可以比A少跳1次。又因为两族的青蛙都会一对一的挡在对方前面,所以共有n*n次情况发生,即可以比A少跳n*n次。同时,这种情况不会多于n*n,原因如下:
    若有一只青蛙跳了n次后,还要跳一次,那么他有2种选择:
    1.跳过对方青蛙:这样,就不满足前提1
    2.跳过对方青蛙:这样,就不满足前提2(况且他的前面是不会有空位的,因为无法产生这种空位,例:00_xx ---|> _xx00 是不可能的~~~)
    综上所述,最少步数m=2*n*(n+1)-n*n=n*n+2n

    #include <iostream>
    
    using namespace std;
    
    int main()
    {
        int x;
        cin>>x;
        cout << x*(x+2) << endl;
    }
    
  • 1

信息

ID
1047
难度
2
分类
其他 | 数学 点击显示
标签
递交数
51
已通过
31
通过率
61%
上传者