首页 > 代码库 > 简单好玩的算法
简单好玩的算法
求最大公约数的辗转相除法
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。
简单好玩的算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。