精华内容
下载资源
问答
  • 关于求最大公约数的辗转相除法,用C语言编写的源代码。
  • 其计算原理依赖于下面的定理: 定理:gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0) 证明:a可以表示成a = kb + r,则r = a mod b 辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的: ⒈ 若 r ...

    #include

    int fun(int a,int b)/* 2个数的公约数 */

    {

    int t;

    while(b)

    {

    t = a%b;

    a = b;

    b = t;

    }

    return a;

    }

    int main()

    {

    int a[100];

    int n;

    int i;

    int res;

    scanf("%d",&n);/* 先输入数的总数n */

    if(n < 2)

    {

    printf("n不能小于2\n");

    return 0;

    }

    for(i=0;i

    scanf("%d",&a[i]);

    res = fun(a[0],a[1]);

    for(i=2;i

    res = fun(res,a[i]);

    printf("%d\n",res);

    return 0;

    }

    ade6df7f03e4b5928c4fa78a6c734d93.png

    欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。

    其计算原理依赖于下面的定理:

    定理:gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)

    证明:a可以表示成a = kb + r,则r = a mod b

    辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:

    ⒈ 若 r 是 a ÷ b 的余数,且r不为0, 则

    gcd(a,b) = gcd(b,r)

    ⒉ a 和其倍数之最大公因子为 a。

    另一种写法是:

    ⒈ 令r为a/b所得余数(0≤r

    若 r= 0,算法结束;b 即为答案。

    ⒉ 互换:置 a←b,b←r,并返回第一步。

    展开全文
  • 实现过程。用大数a除小数b,直到余数为0,如果余数不为0{则将小数赋给大数,余数赋给小数}我的代码:int main(void) {int a, b,yushu;printf("input integer a:");scanf("%i",&a);printf("input integer b:");...

    实现过程。

    用大数a除小数b,直到余数为0,如果余数不为0{

    则将小数赋给大数,

    余数赋给小数

    }

    我的代码:

    int main(void) {

    int a, b,yushu;

    printf("input integer a:");

    scanf("%i",&a);

    printf("input integer b:");

    scanf("%i",&b);

    while((yushu = a % b) !=0){

    a = b;

    b = yushu;

    }

    printf("gcd is %i",b);

    return 0;

    }

    参考答案《programming in c 3rd edition》:

    int main(void) {

    int u, v, temp;

    printf("Please type in two nonnegative integers.\n");

    scanf("%i%i", &u, &v);

    while (v != 0) {

    temp = u % v;

    u = v;

    v = temp;

    }

    printf("Their greatest common divisor is %i\n", u);

    return 0;

    }

    go实现

    package main

    import "fmt"

    func main() {

    fmt.Printf("Please type in two nonnegative integers.\n")

    var u, v, temp int

    fmt.Scanf("%d%d", &u, &v)

    for v != 0 {

    temp = u % v

    u = v

    v = temp

    }

    fmt.Printf("Their greatest common divisor is %v", u)

    }

    展开全文
  • 该楼层疑似违规已被系统折叠隐藏此楼查看此楼有三种算法:1,欧几里得辗转相除法。2,开方算法。3,求素数的埃拉托塞尼筛法。其中3,已经解决,参见百度百科:素数普遍公式。其中2: 开立方公式:设A = X^3,求X.称为...

    该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

    有三种算法:

    1,欧几里得辗转相除法。

    2,开方算法。

    3,求素数的埃拉托塞尼筛法。

    其中3,已经解决,参见百度百科:素数普遍公式。

    其中2:     开立方公式:

    设A = X^3,求X.称为开立方。 开立方有一个标准的公式:

    X(n+1)=Xn+(A/X^2-Xn)1/3    (n,n+1是下角标)

    例如,A=5,k=3,即求

    5介于1的3次方;至2的3次方;之间(1的3次方=1,2的3次方=8)

    初始值X0可以取1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,都可以。例如我们取X0 = 1.9按照公式:

    第一步:X1=1.9+(5/1.9^2;-1.9)1/3=1.7。

    即5/1.9×1.9=1.3850416,1.3850416-1.9=-0.5149584,-0.5149584×1/3=-0.1716528,1.9+(-0.1716528)=1.7。即取2位数值,,即1.7。

    第二步:X2=1.7+(5/1.7^2;-1.7)1/3=1.71。

    即5/1.7×1.7=1.73010,1.73-1.7=0.03,0.03×1/3=0.01,1.7+0.01=1.71。取3位数,比前面多取一位数。

    第三步:X3=1.71+(5/1.71^2;-1.71)1/3=1.709.

    第四步:X4=1.709+(5/1.709^2;-1.709)1/3=1.7099

    这种方法可以自动调节,第一步与第三步取值偏大,但是计算出来以后输出值会自动转小;第二步,第四步输入值

    偏小,输出值自动转大。即5=1.7099^3;

    当然初始值X0也可以取1.1,1.2,1.3,。。。1.8,1.9中的任何一个,都是X1 = 1.7 > 。当然,我们在实际中初始值最好采用中间值,即1.5。 1.5+(5/1.5²-1.5)1/3=1.7。

    如果用这个公式开平方,只需将3改成2,2改成1。即

    X(n + 1) = Xn + (A / Xn − Xn)1 / 2.

    例如,A=5:

    5介于2的平方至3的平方;之间。我们取初始值2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9都可以,我们最好取 中间值2.5。 第一步:2.5+(5/2.5-2.5)1/2=2.2;

    即5/2.5=2,2-2.5=-0.5,-0.5×1/2=-0.25,2.5+(-0.25)=2.25,取2位数2.2。

    第二步:2.2+(5/2.2-2.2)1/2=2.23;

    即5/2.2=2.272,2.272-2.2=-0.072,-0.072×1/2=-0.036,2.2+0.036=2.23。取3位数。

    第三步:2.23+(5/2.23-2.23)1/2=2.236。

    即5/2.23=2.242,2.242-2.23=0.012,0.012×1/2=0.006,2.23+0.006=2.236.

    每一步多取一位数。这个方法又叫反馈开方,即使你输入一个错误的数值,也没有关系,输出值会自动调节,接近准确值。

    关于这个方法的说明;1980年王晓明利用牛顿二项式推出这个公式,找到江西师范大学,一位教授觉得面熟,当场又推演一遍,与牛顿切线法一样。辽宁鞍山的傅钟鹏在他的《数学雅典娜》一书中介绍,天津新蕾出版社。由于是牛顿的公式,作者王晓明不敢贪天之功。所以傅钟鹏老师在文章介绍也明确说明是由牛顿切线法推出。

    展开全文
  • 辗转相除法 C语言实现

    千次阅读 2020-04-01 21:17:17
    int gcd(int a, int b) { int temp; if (a < b) { temp = a; a = b; b = temp; } while (b != 0) { temp = a % b; a = b; b = temp; } ...
    int gcd(int a, int b)
    {
        int temp;
        if (a < b) {
            temp = a;
            a = b;
            b = temp;
        }
        while (b != 0) {
            temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

     

    展开全文
  • 辗转相除法最大的用途就是用来求两个数的最大公约数。用(a,b)来表示a和b的最大公约数。有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c)。 (证明过程请参考其它资料)例:求 15750 与27216的最大公约数。解:...
  • 满意答案junj270推荐于 2017.11.23采纳率:59%等级:8已帮助:1959人用辗转相除法(即欧几里得算法)求两个正整数的最大公约数.解析:设两个数m,n,假设m>=n,用m除以n,求得余数q.若q为0,则m为最大公约数;若q不等于0...
  • 辗转相除法C语言

    2021-01-11 00:20:16
    =0,则m=n,n=r,再回去执行① #include int gongyue(int m,int n) /*辗转相除法求最大公约数*/ { int r; if(m==n) return m; else while((r=m%n)!=0) { m=n; n=r; } return n; } int gongbei(int m,int n...
  • 辗转相除法求最大公约数 除了暴力枚举法求最大公约数外,我们还能用更加高效的方法求最大两个整数的最大公约数 那就是辗转相除法 原理:两个正整数a和b(a>b),其最大公约数等于a除以b的余数c和b之间的最大公...
  • 辗转相除法最大的用途就是用来求两个数的最大公约数。用(a,b)来表示a和b的最大公约数。有定理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c)。 (证明过程请参考其它资料)例:求 15750 与27216的最大公约数。解:...
  • 1、给定n个数据, 求最小值出现的位置(如果最小值出现多次,求出第一次出现的位置即可)。最大值第三行i<=n五行k+1 2、编写程序求无理数e的值并输出。计算公式为:e=1+1/1!+1/2!+1/3!+......+1/n!...
  • #include //辗转相除法算两个数的最大公约数/*(eg18 12)m n t18 1212 6 66 0 0*/int main(void){int m,n,t;scanf("%d%d",&m,&n);while(n!=0){t=m%n;m=n;n=t;printf("m=%d,n=...
  • 辗转相除法详解(C语言实现)

    千次阅读 2020-11-05 08:51:00
    辗转相除法,被称为欧几里得(Euclidean)算法,是求最大公约数的算法。 基本原理 两个正整数a和b(a > b),他们的最大公约数等于a除以b的余数和b之间的最大公约数。 算法实现 思想 a = b * q1 + r1 b = r1 * q2 +...
  • 满意答案smrmhm2013.06.03采纳率:40%等级:12已帮助:12477人辗转相除法 百科名片 欧几里德辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯...
  • 辗转相除法,一种求最大公约数的算法已知:A / B = C ······ R (A、B、C、R皆是整数)假设:D是A的余数,D也是B的余数,那么D就是A和B的公约数D是A和B的约数,则A和B是D的倍数,B * C也是D的倍数既然A与B*C都是...
  • 辗转相除法最大的用途就是用来求两个数的最大公约数。下面通过本文给大家介绍C语言辗转相除法求2个数的最小公约数,非常不错,感兴趣的朋友一起看看吧
  • C语言辗转相除法求最大公约数

    万次阅读 多人点赞 2019-04-04 07:45:54
    辗转相除法是在在维基百科中的意思是: 在数学中,辗转相除法,又称欧几里得算法(英语:Euclidean algorithm),是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题i和ii)中,而在...
  • C语言学习记录——辗转相除法

    千次阅读 2019-10-23 12:26:48
    第一节课通过一个辗转相除法的例子去说明计算机-程序-算法三者之间的关系。 这也更新了以前我的一个认知,以前一直认为上面三种角色中,算法是最难理解的,最具有逻辑性的;可是这位老师却说,算法才是最接近我们的...
  • 辗转相除法求模逆(C语言

    千次阅读 2020-07-06 20:39:11
    方法: 这里是引用初等数论(严士健 第三版)第27页的辗转相除法的表格形式的辗转相除法。 首先我们先要引入概念: 对于二元一次不定方程的求解: 即 ax+by=1的求解方法, ax+by=1,(a,b)=1 a=bq1 + r 1 , 01 b=r1q2...
  • 简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
  • c语言 辗转相除法求最大公约数

    万次阅读 多人点赞 2016-09-22 21:34:22
    C语言编写辗转相除法求最大公约数。
  • Visual Studio 2017 C语言实现辗转相除法   这两天在看关于密码学的内容,看到了关于欧几里得算法的内容,于是便想着用C语言来实现一下欧几里得算法,在VS2017中的代码实现如下: #define _CRT_SECURE_NO_...
  • 辗转相除法   首先我们需要先去了解一下辗转相除法又叫欧几里德算法。欧几里德算法是用来求两个正整数最大公约数的算法。是由古希腊数学家欧几里德在其著作《The Elements》中最早描述了这种算法,所以被命名为...
  • C语言辗转相除法

    2021-04-14 11:57:45
    那么我们先不要去想辗转相除法,而是去思考如何设计代码来完成目的。 假设有两个数字:24,18 我们需要求出他们之间的最大公约数。 这个最大公约数是不是需要满足1、能同时整除两个数字 2、在公约数
  • C语言辗转相除法求最大公约数
  • C语言实现辗转相除法,一个很简单的示例。希望有用!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,073
精华内容 1,229
关键字:

辗转相除法c语言

c语言 订阅