计算最大公约数

mapaler 2019-12-17

计算最大公约数

  1. 穷举法

    穷举范围: t=min(a,b)

    从t开始逐次减1,并进行检验 第一个满足条件即可

  2. 辗转相除法 (欧几里得法)

    do{ 			//计算a,b的最大公约数
        r=a%b;
    	a=b;
        b=r;
    }while(r!=0);
  3. 更相损减法

    int gcd(int a,int b)
    {
        if(a==b) return a;
        else if(a>b) return gcd(a-b,b);
        else return gcd(a,b-a);
    }
    int gcd(int a,int b)
    {
        while(a!=b)
        {
            if(a==b) return a;
            if(a>b) a=a-b;
            else b=b-a;
        }
    }

n位逆序数

void reverse(int n)
{
    while(n!=0)
    {
		printf("%d",n%10);
        n /= 10;
    }
    printf("\n");
}



//改进:引入动态局部变量
void reverse(int n)
{
    int a;
    int sum=0;
    while(n!=0)
    {
        a=n%10
		//printf("%d",n%10);
        sum=sum*10+a;
        n /= 10;
    }
    //printf("\n");
    return sum;
}

个人网站:DiffidentAres’s Blog

相关推荐