/*
stein 算法求最大公约数，和欧基里德算法相比，效果更好:
主要思想如下： 化归思想
1.m为奇数时:
(1)n也为奇数：gcd(m,n) = gcd((m+n)/2,(m-n)/2) ;
(2)n为偶数： gcd(m,n) = gcd(m,n/2) ;
2.m为偶数时：
(1) n也为偶数:gcd(m,n) = gcd(m/2,n/2);
(2) n为奇数: gcd(m,n) = gcd(m/2,n);
3.m == n 时,gcd(m,n) = m 退出
*/
#include <stdio.h>
int stein_gcd ( int m , int n )
...{
int temp,total=0 ;
if ( m < n )
...{
temp = m ;
m = n ;
n = temp ;
}
if ( n == 0 )
return 0 ;
while ( m != n )
...{
if ( m & 1) /**//* 如果m 为奇数, 因为奇数的后面总有一个1,所以可以通过与1且一下来判断是否是偶数*/
...{
if ( n & 1) /**//* m,n都为奇数*/
...{
temp = m ;
m = (m+n)>>1 ;
n = (temp-n)>>1;
}
else
...{
n >>= 1 ;
}
}
else /**//* m为偶数 */
...{
if ( n & 1) /**//*n 为奇数*/
...{
m >>= 1 ; /**//*由于在这个过程中，m可能小于n ,所以要判断一下*/
if ( m < n )
...{
temp = m ;
m = n ;
n = temp ;
}
}
else
...{
m >>= 1 ;
n >>= 1 ;
total ++ ; /**//*记录缩小的倍数*/
}
}
}
m <<= total ; /**//*还原大小*/
return m ;
}
int main(void)
...{
int m,n,max=0;
scanf("%d %d",&m,&n);
max = stein_gcd(m,n);
printf("max= %d ",max);
/**//*
test
while( (scanf("%d",&m)) && m != 0 )
{
if ( m & 1)
printf("%d是奇数 ",m);
else
printf("%d是偶数 ",m);
}
*/
system("pause");
return 0 ;
}
stein 算法求最大公约数，和欧基里德算法相比，效果更好: 主要思想如下： 化归思想 1.m为奇数时: (1)n也为奇数：gcd(m,n) = gcd((m+n)/2,(m-n)/2) ; (2)n为偶数： gcd(m,n) = gcd(m,n/2) ; 2.m为偶数时： (1) n也为偶数:gcd(m,n) = gcd(m/2,n/2); (2) n为奇数: gcd(m,n) = gcd(m/2,n); 3.m == n 时,gcd(m,n) = m 退出 */ #include <stdio.h>int stein_gcd ( int m , int n )...{ int temp,total=0 ; if ( m < n ) ...{ temp = m ; m = n ; n = temp ; } if ( n == 0 ) return 0 ; while ( m != n ) ...{ if ( m & 1) /**//* 如果m 为奇数, 因为奇数的后面总有一个1,所以可以通过与1且一下来判断是否是偶数*/ ...{ if ( n & 1) /**//* m,n都为奇数*/ ...{ temp = m ; m = (m+n)>>1 ; n = (temp-n)>>1; } else ...{ n >>= 1 ; } } else /**//* m为偶数 */ ...{ if ( n & 1) /**//*n 为奇数*/ ...{ m >>= 1 ; /**//*由于在这个过程中，m可能小于n ,所以要判断一下*/ if ( m < n ) ...{ temp = m ; m = n ; n = temp ; } } else ...{ m >>= 1 ; n >>= 1 ; total ++ ; /**//*记录缩小的倍数*/ } } } m <<= total ; /**//*还原大小*/ return m ;} int main(void)...{ int m,n,max=0; scanf("%d %d",&m,&n); max = stein_gcd(m,n); printf("max= %d ",max); /**//* test while( (scanf("%d",&m)) && m != 0 ) { if ( m & 1) printf("%d是奇数 ",m); else printf("%d是偶数 ",m); } */ system("pause"); return 0 ;}