数据结构与算法练习（2）

今天药忘吃喽~ 2022-10-09 03:24 176阅读 0赞

### 文章目录 ###

*   *  6.连续数字最大乘积
     *  7.特殊毕达哥拉斯三元组
     *  8.素数的和
     *

## 6.连续数字最大乘积 ##

> 在下面这个1000位正整数中，连续4个数字的最大乘积是9 × 9 × 8 × 9 = 5832。
> 
> 7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843  
> 8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557  
> 6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749  
> 3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776  
> 6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397  
> 5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474  
> 8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586  
> 1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408  
> 0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606  
> 0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
> 
> 找出这个1000位正整数中乘积最大的连续13个数字，它们的乘积是多少？

解题思路：

1.  通过滑动窗口实现，即控制窗口的大小为13，如果窗口所对的字符串中包含0，则直接将窗口的起点跳到0的下一位，否则计算乘积并与之前的最大值比较并更新，同时窗口后移一位，并循环。
2.  通过简单循环实现，每次计算13位的乘积，同时更新最大值、再后移一位，如果某一位为0时不计算、后移一位再计算。

代码如下：

def str_product(num_str):
        res = 1
        for num in num_str:
            res *= int(num)
        return res
    
    def successive_13_product1():
        '''滑动窗口'''
        num_str = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843'\
        '8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557'\
        '6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749'\
        '3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776'\
        '6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397'\
        '5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474'\
        '8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586'\
        '1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408'\
        '0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606'\
        '0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
        start = 0
        end = 12
        max_result = 1
        sub_str = num_str[start:end + 1]
        if '0' not in sub_str:
            res = str_product(sub_str)
            if res > max_result:
                max_result = res
        while end < 999:        
            end += 1
            if num_str[end] == '0':
                start = end + 1
                end = start + 12           
            else:
                start += 1
                sub_str = num_str[start:end + 1]
                res = str_product(sub_str)
                if res > max_result:
                    max_result = res
        return max_result
    
    
    print(successive_13_product1())
    
    def successive_13_product2(size):
        '''循环'''
        num_str = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843'\
        '8586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557'\
        '6689664895044524452316173185640309871112172238311362229893423380308135336276614282806444486645238749'\
        '3035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776'\
        '6572733300105336788122023542180975125454059475224352584907711670556013604839586446706324415722155397'\
        '5369781797784617406495514929086256932197846862248283972241375657056057490261407972968652414535100474'\
        '8216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586'\
        '1786645835912456652947654568284891288314260769004224219022671055626321111109370544217506941658960408'\
        '0719840385096245544436298123098787992724428490918884580156166097919133875499200524063689912560717606'\
        '0588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
        max_result = 1
        str_len = len(num_str)
        for i in range(str_len - size):
            res = 1
            for j in range(i, i + size):
                if num_str[j] == '0':
                    break
                res *= int(num_str[j])
            if res > max_result:
                max_result = res
        return max_result
    
    print(successive_13_product2(13))

输出：

23514624000
    23514624000

性能分析：  
从前面的分析可以看出，第一种方式循环的次数更少、运行时间更短。

## 7.特殊毕达哥拉斯三元组 ##

> 毕达哥拉斯三元组是三个自然数a < b < c组成的集合，并满足a2 \+ b2 = c2，  
> 例如，32 \+ 42 = 9 + 16 = 25 = 52。  
> 有且只有一个毕达哥拉斯三元组满足 a + b + c = 1000。求这个三元组的乘积abc。

解题思路：  
可以看到，这样的三元组可以构成直角三角形，a是短直角边、b是长直角边、c是斜边，最简单的实现方式是两层嵌套循环，循环的范围都是1-1000，但是显然这样循环次数会比较大。  
经过分析可以知道，a是最短边，所以其长度是小于周长的三分之一的，所以循环范围为`1-1000/3`，b是大于a的，且`b+c=1000-a`、`b<c`，所以b的范围是`a+1-(1000-a)/2`，c即为`1000-a-c`，显然，此时循环次数会大大减小。

代码如下：

def get_pythagorean_triple():
        res = 1
        for i in range(1, 1000 // 3 + 1):
            for j in range(i + 1, (1000 - i) // 2 + 1):
                k = 1000 - i - j
                if i ** 2 + j ** 2 == k ** 2:
                    res *= (i * j * k)
                    break
        return res
    
    
    print(get_pythagorean_triple())

输出：

31875000

性能分析：  
本方法相比于简单循环，大大降低了循环次数，相率有所提升。

## 8.素数的和 ##

> 所有小于10的素数的和是2 + 3 + 5 + 7 = 17。  
> 求所有小于两百万的素数的和。

解题思路：  
实现函数判断每一个数是否为素数，并相加即可。在判断素数时可以进一步减少循环次数，如果是大于2的偶数则肯定不是素数，则不需要进行循环，为奇数时，不需要再循环偶数。

代码如下：

def is_prime(n):
        is_prime = True
        if n < 2:
            is_prime = False
        elif n == 2:
            pass
        else:
            if n & 1 == 0:
                is_prime = False
            else:
                for i in range(3, int(pow(n, 0.5)) + 1, 2):
                    if n % i == 0:
                        is_prime = False
                        break
        return is_prime
    
    def sum_prime(n):
        prime_sum = 0
        for i in range(2, n + 1):
            if is_prime(i):
                prime_sum += i
        return prime_sum
    
    print(sum_prime(2000000))

输出：

142913828922

##  ##