使命召唤6通关存档,天海翼哪一部最好看,宁波电影院
原创
欧几里德算法是用来求最大公约数的：
我要评论1 int gcd(int a,int b)
2 {
3 return b==0?a:gcd(b,a%b);
4 }
扩展欧几里德算法描述为：已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。
扩展欧几里德常用在求解模线性方程及方程组中。（百度百科）
求解x，y的代码如下：
1 int gcd(int a,int b) //扩展欧几里德
2 {
3 int d;
4 if(b==0)
5 {
6 x=1;
7 y=0;
8 return a;
9 }
10 else
11 {
12 d=gcd(b,a%b);
13 int temp;
14 temp=x;
15 x=y;
16 y=temp-(a/b)*y;
17 return d;
18 }
19 }
已知 a*x+b*y==gcd(a，b)，gcd(a，b)==gcd(b，a%b)，将 gcd(b，a%b) 代入 a*x+b*y 可得 b*x1+(a%b)*y1==a*x+b*y（ 注意，(x，y) 和（x1,y1）是不同的 ，(x1，y1)是(x，y) 下层的递归值 ）
然后我们需要知道一个公式，a%b==a-（a/b）*b，将上式变形得 b*x1+（ a-(a/b)*b ）*y1==a*x+b*y，整理可得 a*y1+b*（x1-（a/b）*y）==a*x+b*y；
由此我们可知：
x==y1;
y==x1-（a/b）*y;
当递归到底层时，此时 b==0 ，从而能轻易的得出 gcd（a，b）==a，x==1，y==0；知道了最底层的（x，y），我们就可以根据公式递归回去求上面层的（x，y）。
此刻我们只求出了 a*x+b*y==gcd（a，b）的一组解，下面给出公式求剩下的解：
x=x0+a/gcd(a，b)*t；
y=y0-b/gcd(a，b)*t；
（x0，y0）为我们在上面求得的第一组解（x，y）；（t为任意整数，t==0时，就是我们上面的第一组解）
1 #include<stdio.h>
2
3 int x,y;
4
5 int gcd(int a,int b) //扩展欧几里德
6 {
7 int d;
8 if(b==0)
9 {
10 x=1;
11 y=0;
12 return a;
13 }
14 else
15 {
16 d=gcd(b,a%b); //d存储最大公约数
17 int temp;
18 temp=x;
19 x=y;
20 y=temp-(a/b)*y;
21 return d;
22 }
23 }
24
25 int main()
26 {
27 int a,b;
28 scanf("%d%d",&a,&b);
29 int Byue=gcd(a,b);
30 printf("最大公约数为：%d\n",Byue);
31 printf("第一组解为：%d %d\n",x,y);
32 printf("有其余解如下：\n");
33 int t;
34 for(t=1;t<=10;t++) //另外给出10组解
35 printf("%d %d\n",x+b/Byue*t,y-a/Byue*t);
36
37 return 0;
38 }
下面讨论二元一次方程 ax+by==c的解。
在 ax+by==gcd（a，b）（设解为x0，y0）的基础上等号两边同时乘以 c/gcd（a，b）就可以转换过来了。
所以方程的解为 ：
x=x0*（ c/gcd（a，b））；
y=y0*（ c/gcd（a，b））；
所以我们每求得一组 ax+by==gcd（a，b）的解，就能得到一组 ax+by==c 的解。
1 #include<stdio.h>
2
3 int x,y;
4
5 int gcd(int a,int b) //扩展欧几里德
6 {
7 int d;
8 if(b==0)
9 {
10 x=1;
11 y=0;
12 return a;
13 }
14 else
15 {
16 d=gcd(b,a%b); //d存储最大公约数
17 int temp;
18 temp=x;
19 x=y;
20 y=temp-(a/b)*y;
21 return d;
22 }
23 }
24
25 int main()
26 {
27 int a,b,c;
28 printf("请输入 ax+by==c 中的 a,b,c: ");
29 scanf("%d%d%d",&a,&b,&c);
30 int Byue=gcd(a,b);
31 printf("最大公约数为：%d\n",Byue);
32 printf("第一组解为：%d %d\n",x*(c/Byue),y*(c/Byue));
33 printf("有其余解如下：\n");
34 int t;
35 for(t=1;t<=10;t++) //另外给出10组解
36 printf("%d %d\n",( x+b/Byue*t )*(c/Byue),( y-a/Byue*t )*(c/Byue));
37
38 return 0;
39 }
10:11:49
2018-04-19
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论