C语言程序设计编程精选44例(5)

两个整数的最大公约数(亦称公约数)是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 ? 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。 例如，计算a = 1071和b = 462的最大公约数的过程如下：从1071中不断减去462直到小于462（可以减2次，即商q0 = 2），余数是147： 1071 = 2 × 462 + 147.

然后从462中不断减去147直到小于147（可以减3次，即q1 = 3），余数是21： 462 = 3 × 147 + 21.

再从147中不断减去21直到小于21（可以减7次，即q2 = 7），没有余数： 147 = 7 × 21 + 0.

此时，余数是0，所以1071和462的最大公约数是21。

输入

输入为多行，每行有一对非负整数a,b，且a*b不会超出int类型的数据范围。输入至EOF结束。

输出

每行输出一对a,b的最大公约数和最小公倍数，顺序与输入对应。

样例输入

1 1 2 3 2 2 3 2 4 6 7 5 12 6 18 9 24 36

样例输出

1 1 1 6 2 2

1 6 2 12 1 35 6 12 9 18 12 72

提示

按照题目描述所给的算法解题，注意以下几点：辗转相除法对两个数的大小关系有要求，根据倍数和约数的数学定义，一个非0数和0的约数是多少？辗转相除法的计算过程是符合这种定义的。

解答：

#include int main() { int a,b,i,c; for(;scanf(\ { c=a*b; if(a==0&&b!=0) printf(\ else if(a!=0&&b==0) printf(\ else { while(a!=b) { if(a>b) a=a-b; if(a

问题17: Sum Problem

题目描述

计算若干整数的和，这些整数都是小于1000的非负整数。

输入

输入为多行，每行为一组测试样例。每个测试样例以一个整数N开始，后面接着是N个整数。

输出

每组测试样例对应一行输出，输出所给的N个整数之和，顺序与输入对应。

样例输入

3 1 2 3

5 10 15 20 30 50

样例输出

6 125

提示

用双重循环解决这个问题，外层循环控制用例的输入，内层循环控制读取N个整数。

解答：

#include int main() { int n,a,i,s; for(;scanf(\ { s=0; for(i=1;i<=n;i++) { scanf(\ s=s+a; } printf(\ } }

问题18: Sum Problem (II) : Input/Output Pratice 题目描述

计算若干整数的和，这些整数都是小于1000的非负整数。

输入

输入的第一行是一个整数M，后面有M个测试样例。每个测试样例以一个整数N开始，后面接着是N个整数。

输出

每组测试样例对应一行输出，为所给的N个整数之和，顺序与输入对应。

样例输入

2

3 1 2 3

5 10 15 20 30 50

样例输出

6 125

提示

用双重循环解决这个问题，外层循环控制用例的输入，内层循环控制读取N个整数。

解答：

#include int main() { int m,n,a,i,j,s; scanf(\ for(j=1;j<=m;j++) { scanf(\ { s=0; for(i=1;i<=n;i++) { scanf(\ s=s+a; }

}

} }

printf(\

问题19: Sum Problem (III) : Input/Output Pratice 题目描述

计算若干整数的和，这些整数都是小于1000的非负整数。

输入

输入为多行，每行为一组测试样例。每个测试样例以一个整数N开始，后面接着是N个整数。当输入的N为0时表示输入结束。

输出

每组测试样例对应一行输出，为所给的N个整数之和，顺序与输入对应。

样例输入

3 1 2 3

5 10 15 20 30 50 0

样例输出

6 125

提示

用双重循环解决这个问题，外层循环控制用例的输入，内层循环控制读取N个整数。

解答：

#include int main() {