判断一个数是否能被3整除的递归函数

Question

我需要创建一个递归函数，如果输入的数字可以被 3 整除，它 return 我是真的。我知道没有递归它更简单，但我需要创建一个这种类型的函数。

我已经创建了一个函数，但我想知道是否可以创建一个更好的函数，因为 'num'，该函数不起作用。我想我应该利用这个事实：一个自然数可以被 3 整除，如果它的数字的总和可以被 3 整除。

这是我的代码：

def divThree(num):
    if num==3:
        return true
    else:
        divThree(num-3)

编辑：我创建了一个更好的函数，但我不明白为什么 return 如果数字可以被 3 整除，我就不对了。相反，如果不是，则继续最大递归错误。

def recursiveThree(num):
  if num==3 or num==6 or num==9:
    return true
  else:
    sum=0
    sNum=str(num)
    for i in range(0,len(sNum)):
      sum=sum+int(sNum[i])
    recursiveThree(sum)

Answer 1

使用 3 作为除数时，您需要检查数字是否有零余数。

使用 % 运算符检查余数。因此，如果您想查看某个数是否可以被 3 整除，请使用 num % 3 == 0 如果余数为零，则该数可以被 3 整除。

这 returns 正确：

print (6 % 3 == 0)
returns True

这个returns错：

print (5 % 3 == 0)
returns False

这是一个简单的函数来检查真假：

def divThree(numb):
    return numb % 3 == 0

print (divThree(99))

编辑：

我不确定你要检查的数字有多大，但我用我认为很大的数字测试了这个函数并且它起作用了。我可能只是不明白你需要考虑什么。

def divThree(numb):
    return numb % 3 == 0

print (divThree(4325609549876542987503216540321540104986213754901245217346214390735402153407213540213457183254098263487053214132754073254921534987053245321454))

Returned True

Answer 2

您可以使用模数然后将其减去 num

来找出要使数字被 3 整除需要多少时间

 def divThree(num):
      if num % 3 == 0:
        return True
      a = num % 3
      return divThree(num-a)

Answer 3

你递归放大要减去的因子：

def divisible_by_tree(num, factor=3):
    if factor < num:
        num = divi(num, factor * 2)
    if num >= factor:
        num -= factor
    if factor > 3:
       return num
    return num == 0

Answer 4

最直接的解决方案是使用模 3 检查可分性，但这不会是递归的。
另一种解决方案是递归地一直除以 3，直到减到 1，但对于大值，这会导致堆栈溢出。
第三种适合递归的解决方案是利用属性如果一个数的各位数字之和可以被 3 整除，那么这个数也可以被 3 整除。

这是避免模运算并处理非常大的数字的第三个选项的实现：

def divThree(num):
    if num < 10:
        return (num in [3, 6, 9])
    else:
        return divThree(sum([int(digit) for digit in str(num)]))

如果您希望它也能被 3 整除，您可以在第一个 return 的列表中添加 0。

如果要同时容纳正值和负值，请在前面添加：

if num < 0:
    return divThree(-num)

作为要执行的第一个检查。

Answer 5

这是一种晦涩的方法，有几个更好的答案，但是实现同余定理，你可以说：

from random import randint # For test trials

def isDivisByThree(n):
    sN = str(n)
    if(len(sN) == 1):
        bIsProductOfThree=True if(n==3 or n==6 or n==9) else False
        return bIsProductOfThree
    else:
        sumOfDigits = 0
        for x in sN:
            sumOfDigits += int(x)
        # end for
        return isDivisByThree(sumOfDigits)
    # end if
# end isDivisByThree(...)

def main():
    for testTrialCount in range(1, 35+1):
        testSubject = randint(1, 2147483647)
        result = isDivisByThree(testSubject)
        if(result):
            print("Test Trial #" + str(testTrialCount) + ": " + str(testSubject) + " is divisble by 3!")
        else:
            print("Test Trial #" + str(testTrialCount) + ": " + str(testSubject) + " is NOT divisble by 3.")
        # end if
    # end for
# end main()

main()

之所以可行，是因为与应用同余相关的定理指出：如果 d|(b-1) 那么 n = (a_k * ... * a_1 * a_0) 可被 d 整除当且仅当数字总和 a_k + ... + a_1 + a_0 可被 d[= 整除35=]。（其中 d 是除数（本例中为 3），b 是表示数字的基数（本例中为 10）。）

前 10 次试验的示例输出：

Test Trial #1: 458327921 is NOT divisble by 3. Test Trial #2: 23787660 is divisble by 3! Test Trial #3: 820562190 is divisble by 3! Test Trial #4: 1466915534 is NOT divisble by 3. Test Trial #5: 1395854683 is NOT divisble by 3. Test Trial #6: 1844052852 is divisble by 3! Test Trial #7: 261731131 is NOT divisble by 3. Test Trial #8: 624183104 is NOT divisble by 3. Test Trial #9: 788686237 is NOT divisble by 3. Test Trial #10: 1075010016 is divisble by 3! ...

编辑:

啊，我看到 pjs 用类似的解决方案击败了我。

Answer 6

C 语言（易于翻译）

bool divisible_by_three (int x) {
    if (x < 0) return divisible_by_three (-x);
    else if (x >= 3) return divisible_by_three (x % 3);
    else return (x == 0);
}

是的，它是递归的。给你的老师的练习：找到错误。

判断一个数是否能被3整除的递归函数

Recursive function to know if a number is divisible by 3

python

math

recursion

division

python-2.7