<!-- flowchart 箭头图标 勿删 -->
<svg style="display: none;">
<path d="M5,0 0,2.5 5,5z" id="raphael-marker-block" stroke-linecap="round" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path>
</svg>
<p>1.<strong>目的：</strong> 从键盘输入两个数，输出两个正整数的最大公约数，用c语言实现。 <br>
2.<strong>算法设计思路：</strong> GCD常见算法有辗转相除法，更相减损术法，穷举法，Stein算法，本次采用3种方法，进行代码的实现。 <br>
(1)辗转相除法 <br>
两整数a和b： <br>
① a%b得余数c <br>
② 若c=0，则b即为两数的最大公约数，结束 <br>
③ 若c≠0，则a=b，b=c，再回去执行① <br>
(2)更相减损术法 <br>
两整数a和b： <br>
① 若a>b，则a=a-b <br>
② 若a③ 若a=b，则a（或b）即为两数的最大公约数，结束 <br>
④ 若a≠b，则再回去执行① <br>
(3)穷举法： <br>
① i= a b中的小数 <br>
② 若a，b能同时被i整除，则i即为最大公约数，结束 <br>
③ i–，再回去执行② <br>
3.<strong>流程图：</strong></p>
<p><img alt="" src="https://201907.oss-cn-shanghai.aliyuncs.com/cs/5606289-f2547a07429cc61a044999b3345f47fb" title=""></p>
<p>4.<strong>代码如下：</strong></p>
<pre class="blockcode"><code class="hljs cpp"><span class="hljs-comment">//*********求最大公约数问题***********</span>
<span class="hljs-comment">//作者：刘婉</span>
<span class="hljs-comment">//版本:v1.0</span>
<span class="hljs-comment">//创建时间:2017年3月16日</span>
<span class="hljs-comment">//主要功能:求两个正整数的最大公约数</span>
<span class="hljs-comment">//</span>
<span class="hljs-comment">//************************************</span>
<span class="hljs-preprocessor">#include<stdio.h></span>
<span class="hljs-keyword">int</span> main()
{
<span class="hljs-keyword">int</span> Euclidean (<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y); <span class="hljs-comment">//对Euclidean函数的声明</span>
<span class="hljs-keyword">int</span> Minue(<span class="hljs-keyword">int</span> g,<span class="hljs-keyword">int</span> h); <span class="hljs-comment">//对Minue函数的声明</span>
<span class="hljs-keyword">int</span> Example(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b); <span class="hljs-comment">//对Example函数的声明</span>
<span class="hljs-keyword">int</span> A,B,C;
<span class="hljs-keyword">int</span> d=<span class="hljs-number">1</span>;
<span class="hljs-keyword">while</span>(d==<span class="hljs-number">1</span>)
{
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"请输入两个正整数："</span>);
<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d,%d"</span>,&A,&B);
<span class="hljs-keyword">if</span>(A<<span class="hljs-number">0</span>||B<<span class="hljs-number">0</span>)
{
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"输入错误，请退出（注意应输入两个正整数）"</span>);
<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
C=Euclidean(A,B); <span class="hljs-comment">//调用Euclidean函数，有两个实参，最大公约数赋给变量C</span>
C=Minue(A,B); <span class="hljs-comment">//调用Minue函数</span>
C=Example(A,B); <span class="hljs-comment">//调用Example函数</span>
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"利用辗转相除法求得这两个正整数的最大公约数为:%d\n"</span>,C);
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"利用更相减损术法求得这两个正整数的最大公约数为:%d\n"</span>,C);
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"利用穷举法法求得这两个正整数的最大公约数为:%d\n"</span>,C);
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"1.继续查询 2.退出\n"</span>);
<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%d"</span>,&d);
}
<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
<span class="hljs-comment">//利用辗转相除法求最大公约数</span>
<span class="hljs-keyword">int</span> Euclidean(<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y) <span class="hljs-comment">//定义Euclidean函数</span>
{
<span class="hljs-keyword">int</span> r;
<span class="hljs-keyword">if</span>(x>y)
<span class="hljs-keyword">while</span>(r!=<span class="hljs-number">0</span>)
{
r=x%y;
x=y;
y=r;
<span class="hljs-keyword">return</span> y;
}
<span class="hljs-keyword">else</span>
<span class="hljs-keyword">while</span>(r!=<span class="hljs-number">0</span>)
{
r=y%x;
y=x;
x=r;
}
<span class="hljs-keyword">return</span> x;
}
<span class="hljs-comment">//利用更相减损术求最大公约数</span>
<span class.z{\1 |
|
转播
