求余数的各种方法

本文介绍了求余数的几种方法,包括辗转相除法(欧几里德法)、穷举法、更相减损术和Stein算法。辗转相除法基于欧几里得定理,通过不断除法和取余来求解最大公约数。穷举法则是从小到大枚举公约数。更相减损术是中国古代《九章算术》中的算法,通过不断相减直至相等来求解。Stein算法利用数的性质,对奇数和偶数情况分别处理,实现高效求解最大公约数。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

1.辗转相除法辗转相除法(又名欧几里德法)
C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理: a b=0 gcd(a,b) = gcd(b,a mod b) b!=0根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下:①函数嵌套调用其算法过程为: 前提:设两数为a,b设其中a 做被除数,b做除数,temp为余数1、大数放a中、小数放b中;2、求a/b的余数;3、若temp=0则b为最大公约数;4、如果temp!=0则把b的值给a、temp的值给a;5、返回第二步;
2.穷举法(利用数学定义)
穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数 。①定义1:对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除,则temp即为最大公约数。
3. 更相减损法
更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”更相减损术,是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”
翻译成现代语言如下:
第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。
第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等 为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”,就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
4.Stein算法 Stein算法由J. Stein 1961年提出,这个方法也是计算两个数的最大公约数。来研究一下最大公约数的性质,发现有 gcd( kx,ky ) = kgcd( x,y ) 这么一个非常好的性质。试取 k=2࿰

### MATLAB 中计算余数方法 在 MATLAB 中,`rem` `mod` 都可以用来计算两个数值之间的余数。以下是它们的具体用法及其差异。 #### 基本语法 - **`rem` 函数** `R = rem(A,M)` 返回 A 被 M 整除后的余数[^1]。其基本定义为:如果 `A` `M` 的符号相同,则返回的结果 `A` 的符号一致;否则,结果可能带有负号。 - **`mod` 函数** `B = mod(A,M)` 返回 A 被 M 整除后的余数[^2]。它的核心公式为 \( B = A - M \cdot \text{floor}(A/M) \),并且遵循特殊规则:当 M=0 时,\( \text{mod}(A,0)=A \)[^3]。 #### 关键区别 两者的不同主要体现在处理正负数的情况上: - 如果希望余数的符号跟随 **除数 (M)**,则应使用 `rem()` 函数[^4]; - 如果希望余数的符号跟随 **被除数 (A)**,则应使用 `mod()` 函数。 #### 示例代码 下面通过具体例子展示两种方法的应用: ```matlab % 定义变量 a = [-5, 5]; m = [3, -3]; % 使用 rem 函数 r_rem_pos_divisor = rem(7, 3); % 正常情况下的余数 r_rem_neg_dividend = rem(-7, 3); % 处理负被除数 r_rem_neg_divisor = rem(7, -3); % 处理负除数 % 使用 mod 函数 r_mod_pos_divisor = mod(7, 3); r_mod_neg_dividend = mod(-7, 3); r_mod_neg_divisor = mod(7, -3); disp('Rem Results:'); disp(r_rem_pos_divisor); % 输出 1 disp(r_rem_neg_dividend); % 输出 -1 disp(r_rem_neg_divisor); % 输出 1 disp('Mod Results:'); disp(r_mod_pos_divisor); % 输出 1 disp(r_mod_neg_dividend); % 输出 2 disp(r_mod_neg_divisor); % 输出 -2 ``` 上述代码展示了对于不同的输入组合,`rem` `mod` 如何分别给出不同的结果。 --- ### 总结 无论是 `rem` 还是 `mod`,都可以满足大多数场景下余数的需。但在涉及正负数的情况下,需特别注意两者的行为差异并选择合适的函数来实现预期效果。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值