scilab算法

来源：学生作业帮编辑：拍题作业网作业帮分类：数学作业时间：2024/04/29 17:18:26

求两数最大公约数的算法之一——辗转相除法，用通俗的符号表示，希望简练一些（要用基本的符号）

解题思路：看一些例子
解题过程：
辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

证明：
设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq1＋r1（0≤r1＜b）。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q2＋r2（0≤r2＜r1）。若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1，……如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

[编辑] 算法

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

1. 若 r 是 a ÷ b 的余数, 则

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

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

另一种写法是：

1. a ÷ b，令r为所得余数（0≤r＜b）

若 r = 0，算法结束；b 即为答案。

2. 互换：置 a←b，b←r，并返回第一步。

[编辑] 虚拟码

这个算法可以用递归写成如下:

function gcd(a, b) {
if a mod b<>0
return gcd(b, a mod b);
else
return a;
}

或纯使用循环:

function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}

其中“a mod b”是指取 a ÷ b 的余数。

例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0

只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。

辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。
最终答案：略

Scilab的运算问题 Scilab软件使用问题 scilab 怎么念 scilab怎么读----------------------- scilab怎么读 scilab怎么读?音标或拼音高中数学scilab指令表需要背诵吗用scilab编的程序,二分法求值的算法(算法) scilab程序哪位仁兄能发给我已经编写好的scilab的数学计算程序（如解方程,公式计算等）（1）请问谁能编写辗转相除法的scilab代码? 编写一个计算1+2+2^2+2^3+.+2^63的程序（Scilab）