首页 > 代码库 > 简单好玩的算法

简单好玩的算法

求最大公约数的辗转相除法

    public static long gcd(long a,long b){
        long max=a>b?a:b;
        long min=a>b?b:a;
        if(max%min==0) return min;
        return gcd(min,max%min);
    }

利用的定理是:
设f(a,b)为a和b的最大公约数,则f(a,b)=f(b,a%b)。
证明:
对于a=b*q+r,有a-b*q=r。假设a和b的最大公约数为c,则a、b一定能被c整除,则m*a±n*b也一定能被c整除,故r也能被c整除。

求最大公约数的更相减损法

    public static long gcd1(long a,long b){
        if(a==b) return a;
        long max=a>b?a:b;
        long min=a>b?b:a;
        return gcd1(min,max-min);
    }

相比辗转相除法,这种方法不需要相比减法较为耗时的取模运算,但是这种方法不稳定,两个数相差很大或两个数相差很小时(其实相差很小会转变为相差很大的情况),这种方法就退化到O(n)了。
更相减损法原理不太懂……

用楼层测试鸡蛋的硬度

给两个蛋,有一百层楼,测试蛋在第几层楼扔下去会碎,如果没碎,蛋可以继续扔。求用最优策略,在最坏情况下要扔的次数。
可能题目描述不清楚,看不懂的百度一下吧

    public static int getTimeInWorstCase(int n){
        //对于第k层,蛋碎了,就从1到k-1层逐层往扔,这时候是k次;如果蛋没碎,就对n-k层继续之前操作。对每个k,取两者较大值;对所有k,取最小值。
        //map[n]= Math.min(Math.max(k,map[n-k]+1)),k=1...n-1,蛋在n层一定会碎,这是题目设定,所以扔到n-1就够了。蛋可能在1层都会碎,所以从1开始扔。
        //map[1]=1
        int[] map=new int[n+1];
        map[1]=1;
        for(int i=2;i<=n;i++){
            int curMin=Integer.MAX_VALUE;
            for(int j=1;j<i;j++){
                int temp=Math.max(j,map[i-j]+1);
                if(temp<curMin)
                    curMin=temp;
            }
            map[i]=curMin;
        }
        return map[n];
    }

还可以拓展到很多个蛋的情况。
对于两个蛋,还有一种不用动态规划的方法,但不懂为什么能这么做。
分为若干段,如果在第一个点a碎了,就从1开始到a-1,一共a次,如果第一个点没碎,就在第二个点b扔,b碎了,就从a+1到b-1扔;这是要保证a=b-a-1+2,即这一段长度为b-a=a-1后面的若干段以此类推。
所以对于n层,n<=a+(a-1)+(a-2)+…1,当n=100时,a>=14,得结果14

快速幂

    public static int myPow(int a, int b){
        int res=1,base=a;
        while(b!=0){
            if((b&1)!=0){

                res*=base;
            }
            base*=base;
            b=b>>1;
        }
        return res;
    }

原理:
2^11=(2^(2^0)) * (2^(2^1)) * (2^(2^3))
当二进制位为1时才相乘,为0乘以base。

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

    简单好玩的算法