马上求解······c++题目 - 编程论坛

#2

buffer2011-04-18 21:57

欧几里德算法

程序代码：

int gcd(int a, int b)
{
return b? gcd(b,a%b):a;
}
int lcm(int a, int b)
{
return a*(b/gcd(a,b));
}

#3

ucyan2011-04-18 23:17

程序代码：

#include <iostream>
using namespace std;
int hcf (int a, int b)
{
    int r, t;
    if (a < b)
    {
        t = a; a = b; b = t;
    }
    r = b % a;
    while (r != 0)
    {
        b = a;
        a = r;
        r = b % a;
    }
    return a;
}

int lcf (int a, int b)
{
    return a * (b / hcf(a,b));
}

int main()
{
    int x, y;
    cout<< "输入两个整数：" <<endl;
    cin>> x >> y;
    cout<< "最大公约数：" << hcf(x,y) << " 最小公倍数：" << lcf(x,y) <<endl;
    return 0;
}

相对简单的~~

#4

Lyone2011-04-19 10:56

程序代码：

int Lcm(int *pn, int amount)//最小公倍数，*pn是数组，amount是数组的长度
{
    int MaxData = pn[0];
    int LimitI = pn[0];
    for (int i=1;i<amount;i++)
    {
        LimitI *= pn[i];
        if (MaxData<pn[i])
            MaxData=pn[i];
    }
    int j;
    for (i=MaxData;i<LimitI;i++)
    {
        for (j=0;j<amount;j++)
        {
            if (i%pn[j]!=0)
                break;
        }
        if (j==amount)
            break;
    }
    return i;
}

int Gcd(int *pn, int amount)//最大公约数，*pn是数组地址，amount是数组长度
{
    int MinData = *pn;
    for (int i=1;i<amount;i++)
    {
        if (MinData>pn[i])
            MinData = pn[i];
    }
    int j;
    for (i=MinData;i>0;i--)
    {
        for (j=0;j<amount;j++)
        {
            if (pn[j]%i!=0)
                break;
        }
        if (j==amount)
            break;
    }
    return i;
}

前段时间正好要用到这两个数，不过我这个不是单求两个整数，而是可以求一个数组的最大公约数，最小公倍数。
PS:学习了楼上两位的方法，谢谢。

#5

linw12252011-04-19 22:03

回复楼主独步天涯

#include<iostream>

using namespace std;

int main()
{
    int gongyue( int a, int b);
    void gongbei(int d, int e,int f);

    int m,n;
    int i;

    cout<<"please input two numbers:";
    cin>>m>>n;

    i=gongyue(m,n);
    gongbei(m,n,i);

    return 0;
}

int gongyue( int a, int b)
{
    int temp,a1,b1;

    a1=a;
    b1=b;
    temp=a;

    if(a<b)
    {
        a=b;
        b=temp;
    }

    while(b!=0)
    {
        temp=b;
        b=a%b;
        a=temp;
    }

    cout<<a1<<"和"<<b1<<"最大公约数是："<<a<<endl;

    return a;
}

void gongbei(int d, int e,int f)
{
    long int j;

    j=d/f*e;

    cout<<d<<"和"<<e<<"的最小公倍数是："<<j<<endl;
}