如果递归调用应该在a或b变为0时停止并返回，为什么这个最大的公约数程序的输出是-1

递归调用的最大公约数程序输出为-1的原因是因为在递归调用过程中，没有处理a和b同时为0的情况。

最大公约数（Greatest Common Divisor，简称GCD）是指能够同时整除两个或多个整数的最大正整数。递归调用的最大公约数程序通常使用欧几里得算法（Euclidean algorithm）来计算。

下面是一个修正后的递归调用的最大公约数程序：

def gcd(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    else:
        return gcd(b, a % b)

在修正后的程序中，当a或b变为0时，会返回另一个非零的数作为最大公约数。这是因为任何数与0的最大公约数都是它本身。

对于输入为a=0和b=0的情况，修正后的程序会返回0作为最大公约数。这是因为0与任何数的最大公约数都是0。

推荐的腾讯云相关产品：腾讯云函数（云原生无服务器计算服务），腾讯云数据库（云原生数据库服务），腾讯云服务器（云原生服务器计算服务）。

腾讯云函数：https://cloud.tencent.com/product/scf

腾讯云数据库：https://cloud.tencent.com/product/cdb

腾讯云服务器：https://cloud.tencent.com/product/cvm

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

辗转相除法

否则，将b的值赋给a，将r的值赋给b，然后返回步骤2继续执行。这个算法会一直递归执行，直到余数为0为止。由于每一步的除数都会变小，所以这个过程最终一定会停止，并且得到的结果就是两个数的最大公约数。...下面是一个简单的C语言程序，用于演示如何使用辗转相除法来求两个整数的最大公约数（GCD）： 1：代码 #include // 函数声明 int gcd(int a, int b);...%d", &num1, &num2); // 调用gcd函数计算最大公约数并输出结果 int result = gcd(num1, num2); printf("The GCD...b); } 在上面的代码中，我们定义了一个gcd函数，它接收两个整数a和b作为参数，并返回它们的最大公约数。...否则，我们递归地调用gcd函数，将b和a % b（即a除以b的余数）作为新的参数。在main函数中，我们读取用户输入的两个整数，调用gcd函数计算它们的最大公约数，并输出结果。

811 0

算法基础学习笔记——⑭欧拉函数快速幂扩展欧几里得算法中国剩余定理

eulerTotient函数遍历从1到n的所有数字，检查它们是否与n互质（即它们的最大公约数为1），并统计互质的数字的个数。最后，程序输出计算得到的欧拉函数值。...重复这个过程，直到指数变为0，然后返回计算得到的结果。可以运行上述代码，输入一个基数和指数，程序将计算并输出幂运算的结果。...否则，我们递归调用函数，将b mod a和a作为新的输入，并获取递归返回的最大公约数、系数x1和系数y1。...最后，我们在main函数中接受用户输入的两个整数a和b，并调用extendedEuclidean函数来计算最大公约数和系数。然后，我们输出最大公约数和系数的结果。...你可以运行上述代码，输入两个整数，程序将计算并输出最大公约数和满足贝祖等式的系数。

1651 0

小小GCD、LCM拿下拿下

最大公约数（GCD）也称为最大公因数或最大公因子，是指两个或多个整数共有的约数中最大的一个。在数学中，这是指能够同时被这些整数整除的最大的正整数。...不过，第一种写法在n为0时直接返回结果，避免了一次递归调用，可能会有微小的性能优势。但在实际应用中，这种差异通常可以忽略不计，大家觉得哪个好记就记哪个就行。...这个过程会不断重复，直到其中一个变为0，最后返回的是a+b，下面我们模拟一下过程。最大公约数（GCD）模板： int gcd(int m,int n){//辗转相除法 return n==0?...输入格式第一行包含两个整数 a,b。第二行包含一个整数 q。接下来 q 行，每行包含两个整数 l,r。输出格式每个询问输出一行答案，即满足条件的最大的 x，如果询问无解，则输出 −1。...输入样例： 9 27 3 1 5 10 11 9 11 输出样例： 3 -1 9 解题思路：本题考察为最大公约数+二分查找，首先有了a,b，我们先求出这两个数的最大公约数，即所有的公约数都要小于这个数

511 0

【C语言】4种方法求最大公约数和最小公倍数及比较它们的运行时间

如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。...实质上是以下式子：根据这一定理可以采用函数嵌套调用和递归调用进行求两个数的最大公约数和最小公倍数,现分别叙述如下： ①函数嵌套调用求最大公约数：其算法过程为：设两数为...a; //返回最大公约数到调用函数处 } //辗转相除法函数嵌套求两数的最小公倍数 int multiple (int a,int b) { int divisor (int a,int...b); int temp; temp=divisor(a,b); //再次调用自定义函数，求出最大公约数 return (a*b/temp); //返回最小公倍数到主调函数处进行输出...解题步骤： 1、求最大公约数 对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。

1.7K2 0

小甲鱼《零基础学习Python》课后笔记（二十二）：函数——递归是神马

递归需要满足：调用自身；有停止条件。 2.思考一下，按照递归的特性，在编程中有没有不得不使用递归的情况？...例如汉诺塔，目录索引（因为你不知道目录里是否还有目录），树结构的定义等. 3.用递归去计算阶乘问题或斐波那契数列是很糟糕的算法，你知道为什么吗？...5.拿手机拍一张“递归自拍照片” 拍这个的话需要两面镜子，那会是一个没有停止条件的递归，无限循环反射下去。...动动手 0.使用递归编写一个power()函数内建函数pow()，即power(x,y)为计算并返回x的y次幂的值。...使用递归编写一个函数，利用欧几里得算法求最大公约数，例如gcd(x,y)返回值为参数x和参数y的最大公约数。

6102 0

C++求解有关分数的题目

//用辗转相除法来递归求最大公约数 { return !...输入格式：输入第一行给出正整数N（≤100）；第二行中按照a1/b1 a2/b2 …的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。...输出格式：在一行中按照a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。...输入样例1： 4 1/2 1/6 3/6 -5/10 输出样例1： 1/6 输入样例2： 2 4/3 2/3 输出样例2： 1 解题思路：先判断是不是第一次输入，如果是第一次输入就把本次输入的分数赋值给...//用辗转相除法来递归求最大公约数 { return !

4212 0

求最大公约数算法_求最大公约数最快方法

根据上面的原理，辗转相除法的算法流程可以如下：步骤1：计算a与b的余数r。步骤2：如果r为0，则返回gcd = b。否则，转到步骤3。...如果调用时a值大于b值，比如a为51，b为21，那么情况跟上述算法原理是相符的。...如果调用时a值小于b值，比如a为21，b为51，那么，21除以51的余数r为21，不为0，于是接着调用GetGCD(51, 21)，看到了没？这就和a > b的情况是一样的了。...也就是说我们根本无需判断a和b的大小，当a值小于b值时，算法的下一次递归调用就能够将a和b的值交换过来。...比如当a为100000，b为1时，算法要递归99999次。四终极版本一般情况下，以上两个版本完全够用。如果追求最佳算法性能的终极版本，那就去看《编程之美》第2.7节吧。五参考资料 1.

6301 1

详解Winograd变换矩阵生成原理

为什么提这个是因为，之前我在理解Winograd这个算法的是陷入了一个误区，一直是从深度学习卷积（Correlation）应用的这个角度去理解这个算法，然后一直想不明白，后来换成是从Convolution...简单复习下整除的定义：整除可以记作，即存在一个整数使得。然后如果，则称和互素，表示它们的最大公约数为1。而两个整数是否互素和它们本身是否是素数无关。...然后对等式做下变换：然后考虑 a 和 b 的最大公约数 GCD(a,b) 可知：接着同样根据取模运算规则和上面的两个公式可得：所以同理可得也可以整除，也就是所以通过上面的推导可得：然后就可以根据这个求解最大公约数的递归式来写实现代码了...2.3、扩展欧几里得算法在介绍扩展欧几里得算法之前先来看下“裴蜀等式”，下面引用wikipedia上的解释[19]: 在数论中，裴蜀等式或裴蜀定理是一个关于最大公约数（或最大公因式）的定理。...余式是-1 第二步, ，商是，余式是0，停止递归，设置第三步, 第四步, 得解，两边同乘-1得，求得逆元是-1 所以求解过程：相当于求解方程的解第一步，，商是，余式是2 第二步,，商是，

1.1K3 0

递归函数及例题_递归树求解递归式例题

定义：一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的。...如果最后一位数是0，则不输出，直接再次调用int_inverts(n/10,flag)函数。如果不是，修改flag的值，先输出，然后在调用int_inverts(n/10,flag)。...有谁来对上联或下联? 例题2：求最大公约数 题目描述设计递归函数;计算正整数a和b的最大公约数并返回输入与输出要求：输入两个正整数a和b，输出两数的最大公约数数，占一行。...解题思路：递归出口： n=1或n=0 , 直接返回值n；地推关系： b_shift_d(n) = n%10 + 2*b_shift_d(n/10); 示例1： image.png 示例...解题思路：全排列问题解题思路及代码问题7：整数划分问题：问题描述：整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。

6674 0

11.09作业详解（弹球距离，素数，最大公约数最小公倍数，求整数位数及其各位数字之和，打印乘法表）

，且想办法然函数中的某个形参无限逼近与该条件，由题目可知，这个限制条件是让h*p^n逼近与0.001即可，当h*p^n满足小于0.001时返回h*p^(n-1)，然后再往前推直到求到第一个dist函数,...由于h*p^2>0.001,返回h+h*p^2+h*p^2...直到返回到第一次调用的dist函数即可。...a)*a); return 0; } 先求最大公约数，方法有很多，例如辗转相除，更相减损我这里用的是更相减损法，原理就是当a与b两个数不相等是将两数相减并赋值给较大的数，当减到两数相同时，这时两数的值即为它们的最大公约数...，而最小公倍数就简单多了，用a,b两数除以最大公约数后相乘再乘上个最大公约数就能得到最小公倍数啦。...123%10=3，第二次12%10=2，第三次1%10=1...这道题只用求和，所以不需要考虑求出各个位上的数字的顺序，如果题目要求正向输出各个位上的数字，就在while中把各个位上的数字赋给一个数组，

1081 0

数据结构和算法-数学问题-最大公约数

比如，12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。...辗转相除法的执行过程如下：（1）对于已知两自然数a、b，假设a>b；（2）计算a除以b，将得到的余数记为r；（3）如果r=0，则b为求得的最大公约数，否则执行下面一步；（4）将b的值保存到a中，...欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来。...Stein算法的执行过程如下：（1）对于已知两自然数a、b,a和b谁大谁小没有要求；（2）首先判断a或b的值，如果a=0，b就是最大公约数；如果b=0，a就是最大公约数，从而可以直接完成计算操作。...（4）判断m和n是否为偶数，若都是偶数，记录下公约数为2，同时使m=m/2，n=n/2，。（5）若m是偶数，n是奇数，使m=m/2，递归调用。（6）若n是偶数，m是奇数，使n=n/2，递归调用。

1.1K1 0

【C语言刷题——Leetcode12道题】带你起飞，飞进垃圾堆

请你找到并返回这个整数示例：输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6 来源：力扣（LeetCode）字面意思，直接做题即可： 1351....找出数组的最大公约数 给你一个整数数组 nums ，返回数组中最大数和最小数的最大公约数 。两个数的最大公约数 是能够被两个数整除的最大正整数。...示例 1：输入：nums = [2,5,6,9,10] 输出：2 解释： nums 中最小的数是 2 nums 中最大的数是 10 2 和 10 的最大公约数是 2 示例 2：输入：...nums = [7,5,6,8,3] 输出：1 解释： nums 中最小的数是 3 nums 中最大的数是 8 3 和 8 的最大公约数是 1 示例 3：输入：nums = [3,3]...统计各位数字之和为偶数的整数个数给你一个正整数 num ，请你统计并返回小于或等于 num 且各位数字之和为偶数的正整数的数目。

8902 0

JavaScript数据结构与算法-Array

如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？思路：这个题和上面那个题，最大的区别是，数组中有重复的数字，也得返回，。...例如：[2,2]和[1,2,1],如果不删，返回结果是[2,2]，正确结果是[2]。...示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。思路：我一开始想的是，转成数字直接+1，结果发现如果数字超出最大数字就会出错。...例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。...// 此方法主要用到这样一个定理：a和b的公约数==b和a%b的公约数==a%b和b%(a%b)的公约数…………；另外要知道.a和0的公约数==a; function Mgn(num1,num2){

5922 0

【蓝桥杯系列】第一节 C的基本用法

通过 return 语句可以提前结束函数并返回调用处。若省略返回值则执行到大括号并返回调用处。参数列表中为函数需要的各个参数，在调用时需要提供对应的参数。...} else{ return x; // 必要的出口 }}int main(){ printf("%d",f(1)); return 0;} 递归是在函数内调用函数本身的一种方式...题目9：最大公约数和最小公倍数写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果两个整数由键盘输入。...(a % b)){ return b; } gcd(b, a % b);} // 最大公约数 * 最小公倍数 = 两数乘积int lcm(){ return num1 *...– 样例输入：O S, GOMR YPFSU/ – 样例输出：I AM FINE TODAY. 生成元 – 如果 x 加上 x 的各个数字之和得到 y，就说 x 是 y 的生成元。

1.1K7 0

三种算法求两个正整数的最大公约数和最小公倍数；求三个数的最大公约数和最小公倍数「建议收藏」

基本要求：1.程序风格良好(使用自定义注释模板)，两种以上算法解决最大公约数问题，提供友好的输入输出。提高要求：1.三种以上算法解决两个正整数最大公约数问题。...那么，最后一个除数就是所求的最大公约数； 5. 输出最大公约数和最小公倍数。 2.辗转相除法（三个数）如果求三个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。...最后所得的一个最大公约数，就是所求的几个数的最大公约数。 3.穷举法（两个数）用穷举法求解两个数的最大公约数步骤如下： 1. 输入两个正整数； 2. i = a(或b)； 3....4.相减法（两个数） 1.输入两个正整数a和b； 2.如果a > b，则a = a – b； 3.如果a < b，则 b = b – a； 4.如果a = b，则a（或b）即为两数的最大公约数 5.如果...基本要求：1.程序风格良好(使用自定义注释模板)，两种以上算法解决最大公约数问题，提供友好的输入输出。提高要求：1.三种以上算法解决两个正整数最大公约数问题。

2.6K2 0

Java常见的坑(二)

实际上我们知道字符串与任何数值的相加都会变为字符串，上述事例也不例外， numbers输出其实实际上是调用了Object.toString()方法，让numbers转变为'[c' + '@' + 无符号的十六进制数...改观那么既然知道了原因，该如何去解决这个问题才是我们应该考虑的问题，恰好String 类为我们提供了String.valueOf(char[] c)把char数组变为字符串 1 // 修改程序...调用这些方法导致的结果是，终结器会在那些其他线程正在并发操作的对象上运行，从而导致不确定的行为或死锁。总之，System....通过调用 System.Halt 可以在不执行关闭挂钩的情况下停止 VM，但是很少使用这个方法。...与大多数StackOverflowError异常一样，本程序也包含了一个无限递归，当你调用一个构造器时，实例变量的初始化操作将先于构造器的程序体运行，上述例子中，internalInstance变量的初始化操作递归调用了构造器

5561 0

c++期末总结

= 除等于 a=4; a/=2; a=2; %= 模等于 a=3; a%2; a=1; 2.3、比较运算符作用：用于表达式的比较，并返回一个真值或假值请详细看表格即可运算符术语示例结果 =...2.4、逻辑运算符作用：用于根据表达式的值返回真值或假值请详细看表格即可运算符术语示例结果 ! 非 !a 如果a为假，则!a为真；如果a为真，则!a为假。...break; } if (b == c+1) { return 1; } else return 0; } 3.2求最大公约数最小公倍数最大公约数和最小公倍数：两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积...）=29 用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。...因为这个加密就是直接加个数，但是要注意的是char类型是有范围的 3.6逆序输出 #include using namespace std; int main() { int

1290 0

c++学习总结(二）——递归函数

它是直接或间接调用的函数，通常可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算。大大减少了程序的代码量。...然后执行本“层”的后继语句； .遇到子程序运行完后，就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后继语句； .继续执行步骤3，从调用中逐“层”返回，最后返回到主程序。...n=0，则f=1；如果n>0，则继续调用函数f=n*f（n-1）; .返回主程序，打印f(x)的结果。...1:n*f(n-1); //调用函数f(n-1)递归求(n-1)! } 3.用递归方法求m,n两数的最大公约数。（m>0,n>0）求两个数的最大公约数，这里用辗转相除法。....求m除以n的余数； .如果余数不为0，则让m=n,n=余数，重复步骤,即调用子程序； .如果余数为0，则终止调用子程序； .输出此时的n值。

6545 0

Day3 函数和模块的使用

test.py import module1 as m1 import module2 as m2 m1.foo() m2.foo() 但是如果将代码写成了下面的样子，那么程序中调用的是最后导入的那个...函数内部使用循环计算出两个数的最大公约数 gcd，然后根据最大公约数计算出最小公倍数 lcm，最后返回最大公约数和最小公倍数。你可以根据实际需求调用这个函数来计算最大公约数和最小公倍数。...首先判断 n 是否小于等于 1，如果是，则返回 False，表示不是素数。接着判断 n 是否小于等于 3，如果是，则返回 True，因为 2 和 3 都是素数。...在循环中，如果 n 能被 i 或 i+2 整除，则返回 False。如果循环结束后都没有返回 False，则说明 n 是素数，返回 True。...然后，程序通过 input 函数获取用户输入的正整数，并将其存储在变量 num 中。最后，调用 is_palindromic_prime 函数判断 num 是否为回文素数，并输出相应的结果。

1311 0

写不好代码注释？这份注释指南一定要收好

在本函数中，如果 n 小于等于 0，返回 0；如果 n 等于 1，返回 1；否则，返回 fibonacci(n - 1) + fibonacci(n - 2)，通过递归计算得出结果 """...比如：“这个变量 max_attempts 表示尝试连接数据库的最大次数。”...假设我们有一个函数用于计算两个数的最大公约数：def greatest_common_divisor(a, b): """ 此函数用于计算两个整数的最大公约数 参数: a (int...): 第一个整数 b (int): 第二个整数返回: int: 两个数的最大公约数 算法: 使用欧几里得算法，其基本步骤为：用较大数除以较小数得到余数，然后将较小数作为新的较大数...，余数作为新的较小数，重复此过程，直到余数为 0，此时的除数即为最大公约数 """ while b!

2061 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云