文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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

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

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

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

代码语言：python
代码运行次数：0
复制
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

相关搜索:数字货币和区块链数字版权在区块链数博会区块链论坛手机云服务怎么用手机云服务收费吗手机云服务是什么手机云服务打不开手机云服务安全吗手机云服务aPP手机通讯录云服务
相关搜索:
页面内容是否对你有帮助？
有帮助
没帮助

相关·内容

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

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

12410

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

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

59520

【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.6K20

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

根据上面的原理，辗转相除法的算法流程可以如下： 步骤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.

61411

详解Winograd变换矩阵生成原理

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

1.1K30

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

定义： 一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的 。...如果最后一位数是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： 整数划分问题： 问题描述： 整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。

65340

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中把各个位上的数字赋给一个数组，

9210

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

比如，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.1K10

【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 且各位数字之和为 偶数 的正整数的数目。

84720

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){

58520

【蓝桥杯系列】第一节 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.1K70

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

基本要求：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.5K20

Java常见的坑(二)

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

54910

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

11100

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 是否为回文素数，并输出相应的结果。

12210

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

在本函数中，如果 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!

6510

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值。

63750

常规笔试算法总结.md

所谓迭代，是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。 为什么这么说呢？...另外，如果递归一旦忘记了返回，或者错误的设置了返回条件，那么执行这样的递归代码就会变成一个无底洞：只进不出！所以在写递归代码的时候，千万要记住口诀：递归递归，归去来兮！出来混，总有一天是要还的！...答： 一、函数调用自身 二、设置了正确的返回条件 请聊一聊递归的优缺点（无需官方陈词，想到什么写什么就可以） 答： 优点： 1）递归的基本思想是把规模大的问题转变成规模小的问题组合，从而简化问题的解决难度...缺点： 1）由于递归的原理是函数调用自个儿，所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”（当然法拉利也奢侈，但还是很多人趋之若鹜）。...2）初学者很容易错误的设置了返回条件，导致递归代码无休止调用，最终栈溢出，程序崩溃。 1.计算闰年与平年 定义闰年的原理:能被4整除但不能被100整除,或者能被400整除都是闰年。

35410

常规笔试算法总结.md

所谓迭代，是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。 为什么这么说呢？...另外，如果递归一旦忘记了返回，或者错误的设置了返回条件，那么执行这样的递归代码就会变成一个无底洞：只进不出！所以在写递归代码的时候，千万要记住口诀：递归递归，归去来兮！出来混，总有一天是要还的！...答： 一、函数调用自身 二、设置了正确的返回条件 请聊一聊递归的优缺点（无需官方陈词，想到什么写什么就可以） 答： 优点： 1）递归的基本思想是把规模大的问题转变成规模小的问题组合，从而简化问题的解决难度...缺点： 1）由于递归的原理是函数调用自个儿，所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”（当然法拉利也奢侈，但还是很多人趋之若鹜）。...2）初学者很容易错误的设置了返回条件，导致递归代码无休止调用，最终栈溢出，程序崩溃。 1.计算闰年与平年 定义闰年的原理:能被4整除但不能被100整除,或者能被400整除都是闰年。

23120
点击加载更多

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

更多标签

活动推荐

    运营活动

    活动名称
    广告关闭

    腾讯云开发者

    扫码关注腾讯云开发者

    扫码关注腾讯云开发者

    领取腾讯云代金券

    热门产品

    热门推荐

    更多推荐

    Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

    腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

    领券