递归法分解整数,数学整数因式分解

  递归法分解整数,数学整数因式分解

  最大质因数的递归求解Python:问题描述:求任意正整数的最大质因数,并给出代码和注释:

  #最大质因数def calc(x:int)-int:#函数参数类型设置和返回值类型设置如果x==1:##如果这个数是1,那么最大质因数一定是1,毫无疑问,对于range(2,x)中的I返回1:##如果这个数不是1,从2开始一直找到这个数的前一个数,找到这个数的最小因子如果x%i==0: ##,然后用这个数除以最小因子, 然后将结果的最大质量因子返回给调用者return calc(int(x/i)) return x##如果这个数既不是1也不是1和除它本身以外的任何因子,那么这个数本身就是最大质量因子print(calc(600851475143))。 递归思想、代码和注释分析:代码部分非常简单易懂,都是一些基本的python语法。我想说一下注释部分,是根据我个人对递归的理解写的。在此,我想和大家分享一下我对递归的拙见。

  首先,在递归问题求解的过程中,每次递归只是用不同的参数重复工作,所以即使递归函数中只写了一个函数定义,我们也可以假设它完全胜任我们需要的工作。接下来我们给它设置一个出口,让它在最简单的情况下直接完成工作,这种情况下就是x==1的情况;最简单的案例完成后,我们可以开始研究更复杂的案例。这是要具体分析的,我们已经假设它完全胜任我们需要的工作。所以在这种情况下,我们找到x的最小因子后,直接用x除以这个最小因子,然后找到这个结果的最大定性因子(注意,这一步就是我们前面提到的“假设它完全胜任我们需要的工作”,直接把要求抛给函数。至于怎么做?最后,不要忘记遗漏可能的特例,在这种情况下,其中x是一个质数。

  我觉得递归的难点只在于逻辑层的嵌套,但实际上我们不必让思想完全进入递归。我们只在外部逻辑的每一步中完成我们的任务。至于实际上是怎么做的,我不需要知道。

  为什么要从除法的结果中寻找最大质因数?除1之外的最小因子和它本身与最大质因数

实际上这个最小因子必定是个质数,而且最小因子一定是小于等于最大质因子的

之间的关系我还没有总结出来。那为什么要用x除以最小因子,然后在结果中求x的最大质因数呢?我觉得可以,因为最大质因数,首先是一个质数,就像沙子里最大的石头。无论我们如何过滤沙子,石头仍然存在。我们把求最小因子的范围设为2到X-1,

如果最小因子等于最大质因子,那么除法的结果里面既没有更大的质因子,又没有小于最大质因子的因子,也就是说,除法的结果只能是最大质因子的n次方;如果最小因子小于最大质因子,那么除法结果里面就必定包含最大质因子

,所以我们除以X后,这块石头还是在除法的结果里。我们所做的划分只是起到一个过滤网的作用,或者说是这样吗?我们假设函数完全胜任我们需要的工作,我们只需要向它抛出参数。我们只需要确定参数是正确的,而且我们已经确定石头在我们传递的参数中,所以得到正确的结果是理所当然的。

递归法分解整数,数学整数因式分解