算法15---数论7---一些细节题
1 整除,求余数
算法导论:31.1-12 试写出计算β位整除除以短整数的高效算法,以及计算β位整数除以短整数的余数的高效算法。所给出的算法运行时间应为θ(β^2).
1 //位运算的乘法与除法 2 #include <stdio.h> 3 4 5 6 //位运算的乘法 7 int bit_Multiplication(int a,int b) 8 { 9 int ans=0; 10 for (int i=1;i;i<<=1,a<<=1) 11 { 12 if (b&i) 13 { 14 ans+=a; 15 } 16 } 17 return ans; 18 } 19 //位运算的除法 20 int bit_Division1(int x,int y) 21 { 22 int ans=0; 23 for (int i=31;i>=0;i--) 24 { 25 if ((x>>i)>=y) 26 { 27 ans+=(1<<i); 28 x-=(y<<i); 29 } 30 } 31 return ans; 32 } 33 //计算整数的二进制位数 34 int bit_num(int d) 35 { 36 int i=0; 37 while (d) 38 { 39 d>>=1; 40 i++; 41 } 42 return i; 43 } 44 //位运算的除法 计算商 45 int bit_Division2_quotient(int x,int y) 46 { 47 int c2=bit_num(x),c1=bit_num(y),quotient=0; 48 for (int i=c2-c1;i>=0;i--)//i=c2-c1防止除数y移位后超过无符号整数最大值 时间复杂度O(c2-c1) 49 { 50 unsigned int a=(y<<i);//有了i=c2-c1保证了y<<i不会溢出 a有c1+c2-c1=c2位 51 if (a<=x) 52 { 53 quotient+=(1<<i); 54 x-=a; 55 } 56 } 57 //总的时间复杂度为 O(c2)=O(x的二进制位数)=O(b^2) b为除数的十进制位数 58 return quotient; 59 } 60 //位运算的除法 计算余数 与计算商一样,只是返回值不同 61 int bit_Division2_Remainder(int x,int y) 62 { 63 int c2=bit_num(x),c1=bit_num(y),quotient=0; 64 for (int i=c2-c1;i>=0;i--)//i=c2-c1防止除数y移位后超过无符号整数最大值 时间复杂度O(c2-c1) 65 { 66 unsigned int a=(y<<i);//有了i=c2-c1保证了y<<i不会溢出 a有c1+c2-c1=c2位 67 if (a<=x) 68 { 69 quotient+=(1<<i); 70 x-=a; 71 } 72 } 73 //总的时间复杂度为 O(c2)=O(x的二进制位数)=O(b^2) b为除数的十进制位数 74 return x; 75 } 76 77 78 int main() 79 { 80 printf("%d ", bit_Multiplication(350,43)); 81 printf("%d ", bit_Division1(350,43)); 82 printf("divide:%d ", bit_Division2_quotient(350,43)); 83 printf("remainder :%d ", bit_Division2_Remainder(350,43)); 84 85 return 0; 86 }
2 二进制转10进制
31.1-13 写出一个高效算法,用于将β位二进制整数转化为响应的十进制表示。证明:如果长度至多为β的整数的乘法或除法运算所需时间为M(β),则执行二进制到十进制转换所需时间为θ(M(β)lgβ)。(提示:应用分治法,分别使用独立的递归计算结果的前段和后段)。
/* 题目:最大公约数 author taoliu——alex 2016.10 number5 主要实现: 2-10,递归实现 */ #include <stdio.h> #include <string.h> #define BIT 6//二进制整数的位数,可根据所要输入的二进制位数设置BIT。 //方法1,直接二进制转10进制; int Bit_merge(int a[],int p,int r) { int ans=0; for (int i=p;i<=r;i++) { ans+=a[i]<<i; } return ans; } //方法2 int merge(int a[],int p) { int ans=0; ans+=a[p]<<p; return ans; } int bit_Multiplication(int a[],int p,int r)//x为二进制数 { int q; int sum; if (p==r) { sum+=merge(a,r); } if (p<r) { q=(p+r)/2; bit_Multiplication(a,p,q); bit_Multiplication(a,q+1,r); } return sum; } int main() { int a[BIT]={1,0,1,1,1,0}; printf(" "); printf("%d ",bit_Multiplication(a,0,BIT-1) ); return 0; }
3 欧几里得算法算法的扩展形式
可以利用欧几里得算法计算出满足下列条件的整系数x和y;
d = gcd(a,b)=ax+by;
算法伪代码
extended_euclid(a,b)
if b==0
return(a,1,0)
else
(d',x',y')=extended_euclid(b,a mod b)
(d,x,y)=(d',y'x'-a/b*y')
return (d,x,y)
/* 题目:欧几里得算法扩展 author taoliu——alex 2016.10 number5 主要实现: */ #include <stdio.h> struct a { int d; int x; int y; }s; struct a extended_eucild(int a,int b) { if(b==0) { s.d=a; s.x=1; s.y=0; return s; } else { struct a ss=extended_eucild(b,a%b); s.d=ss.d; s.x=ss.y; s.y=ss.x-(a/b)*ss.y; return s; } } int main() { struct a s=extended_eucild(899,493); printf("%d,%d,%d ",s.d,s.x,s.y ); return 0; }