欧氏算法(求最大公因子)
挑战
编写一个程序或函数，该程序或函数接受两个输入整数i和j，并输出它们的最大公因子；使用欧氏算法计算(见下文)。
输入
输入可以作为i和j的以空格分隔的字符串表示形式，也可以看作是两个独立的整数。您可以假设整数小于或等于10,000。您还可以假设输入整数不会是彼此的质数。
欧氏击穿
i和j之间的较大数目除以尽可能小的次数。然后，添加其余部分。使用余数和前一个数字重复此过程，直到余数变为0。
例如，如果输入是1599 650：
1599 = (650 * 2) + 299
650 = (299 * 2) + 52
299 = (52 * 5) + 39
52 = (39 * 1) + 13
39 = (13 * 3) + 0最后一个数，13，是两个输入整数的最大公因子。它可以形象化如下：
输出
您的输出必须是上面形式的细分，然后是换行符和GCD。它可以通过任何介质输出。
示例
输入
18 27
50 20
447 501
9894 2628输出
27 = (18 * 1) + 9
18 = (9 * 2) + 0
9
50 = (20 * 2) + 10
20 = (10 * 2) + 0
10
501 = (447 * 1) + 54
447 = (54 * 8) + 15
54 = (15 * 3) + 9
15 = (9 * 1) + 6
9 = (6 * 1) + 3
6 = (3 * 2) + 0
3
9894 = (2628 * 3) + 2010
2628 = (2010 * 1) + 618
2010 = (618 * 3) + 156
618 = (156 * 3) + 150
156 = (150 * 1) + 6
150 = (6 * 25) + 0
6注:输出不需要间隔，因为它们在上面。间距只是为了清晰。需要括号。
奖金
如果你的输出和上面一样，你可以在你的分数上加10%的加值.
回答 8
Code Golf用户
发布于 2015-09-24 09:15:02
Pyth，33字节
ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H在线试用：游行示威或测试套房
解释：
ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H
Q read the two numbers from input
S sort them
A and assign them to G and H
WG while G != 0:
K%HG assign H mod G to K
s[H\=\(G\*/HG\)\+K ) join the following list items and print:
H=(G*(H/G))+K
A,KG assign K, G to G, H
) end while
H print HCode Golf用户
发布于 2015-09-24 08:25:47
Python 2，70
f=lambda a,b:b and'%d=(%d*%d)+%d\n'%(a,b,a/b,a%b)*(a>=b)+f(b,a%b)or`a`返回多行字符串的递归函数。函数创建第一行，然后用欧几里德算法中的下一对数字将其附加到递归结果中。一旦第二个数字为零，我们就以另一个数字的字符串作为大小写，将其打印在它自己的行的末尾。
格式化是通过字符串替换完成的，使用整数除法来获得乘法器。
一个打嗝是需要开始的较大的数字被采取的模式，较小的数字。方便地，如果数字是在错误的顺序，第一步的欧几里德算法翻转他们。要防止显示此步骤，只需在第一个数字至少是第二个数字的情况下添加当前行(例如，f(9,9))。
Code Golf用户
发布于 2015-09-27 12:43:37
C++，GCC编译器，171个字节( -10%，所以154个字节)
好吧那我第一次试..。
#include<iostream>
using namespace std;
int main()
{
int a,b,c;
cin>>a>>b;
if(a<b)
swap(a,b);
while(b>0)
{
c=a;
cout<<a<<" = ("<<b<<" * "<<a/b<<") + "<<a%b<<endl;
a=b;
b=c%b;
}
cout<<a;
}小贴士编码高尔夫非常感谢。
在使用c++时，是否需要计算标准头文件和int的字节数？不包括它，减少50个字节。
https://codegolf.stackexchange.com/questions/58565
复制相似问题
腾讯云开发者
