笔试面试题目:判断2^n, 3^n, 4^n, 5^n

    科技2022-07-17  121

          原文发表于:

     

        F公司的笔试面试题目如下: 如何判断一个正整数是否为2的n次幂,3的n次幂,4的n次幂,5的n次幂?其中n为非负整数。要求:使用四种不同的算法。

     

    2的n次幂

         2的n次幂的判断,是一个比较常见的问题。容易看出,2的n次幂的二进制中,有且仅有一个1,  所以,可用如下思路来判断:

    package main import "fmt" func is2Pow(n uint32) bool { if n == 0 { return false } if n & (n - 1) == 0 { return true } return false } func main() { for i := uint32(0); i < 100; i++ { if is2Pow(i) { fmt.Println(i) } } }

          

    3的n次幂

         因为3是质数,可以先找出32位正整数中3的n次幂的最大值,然后,思路就很自然了,如下:

    package main import "fmt" func is3Pow(n uint32) bool { if n == 0 { return false } if 3486784401 % n == 0 { return true } return false } func main() { for i := uint32(0); i < 100; i++ { if is3Pow(i) { fmt.Println(i) } } }

     

    4的n次幂

         4的n次幂,首先必须是2的n次幂,且有4^n = (3+1)^n, 根据二项式定理可知:4^n % 3 = 1,  所以,算法代码如下:     

    package main import "fmt" func is4Pow(n uint32) bool { if n == 0 { return false } if n & (n - 1) != 0 { return false } if n % 3 == 1 { return true } return false } func main() { for i := uint32(0); i < 100; i++ { if is4Pow(i) { fmt.Println(i) } } }

     

    5的n次幂

          既然前面的方法都用了,那现在可考虑使用通用的方法:

    package main import "fmt" func is5Pow(n uint32) bool { if n == 0 { return false } if n == 1 { return true } for { if n % 5 != 0 { return false } n = n / 5 if n < 5 { break } } if n == 1 { return true } return false } func main() { for i := uint32(0); i < 100; i++ { if is5Pow(i) { fmt.Println(i) } } }

     

          思路很重要,本文内容很简单,故无需赘述。

          周五了,早休息。

    涛歌依旧 认证博客专家 排名第一 点链接学人工智能 公众号免费领资料 ❤️零基础入门进阶人工智能 ❤️欢迎关注涛哥公众号,免费领海量学习资料。涛哥:毕业后就职于华为和腾讯。微信:ai_taogeyijiu
    Processed: 0.010, SQL: 8