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

野性酷女 2022-10-07 10:53 275阅读 0赞

### 文章目录 ###

*   *  1.最大质因数
     *  2.最大回文乘积
     *  3.最小倍数
     *  4.并非盈数之和
     *  5.第10001个素数

## 1.最大质因数 ##

> 13195的所有质因数为5、7、13和29。  
> 600851475143最大的质因数是多少？

解题思路：  
本题有2种实现方式：

1.  找出这个数的所有质因数，再找出其中最大的那一个；
2.  不断递归调用，判断每次得到的数是否为质数，如果不是，则继续查找。

代码如下：

def max_prime1(num):
        '''普通方法'''
        prime = 1
        temp = num   
        while temp > 1:
            num_root = int(pow(num, 0.5))
            for i in range(2, num_root+1):
                if temp % i == 0:
                    temp /= i
                    if i > prime:
                        prime = i
                    break
        return prime
    
    def max_prime2(num):
        '''递归方法'''
        if num == 1:
            return 1
        for i in range(2, int(pow(num, 0.5))+1):
            if num % i == 0:
                return max_prime2(num // i)
        return num
    
    print(max_prime1(600851475143))
    print(max_prime2(600851475143))

输出：

6857
    6857

性能分析：  
第2种方法的性能更高，因为第2种方法相对于第1种，遍历的次数更少。

## 2.最大回文乘积 ##

> 回文数就是从前往后和从后往前读都一样的数。由两个2位数相乘得到的最大回文乘积是 9009 = 91 × 99。找出由两个3位数相乘得到的最大回文乘积。

解答思路：  
本题也有2种解答方式，两种方式均需要判断一个数是否是回文数，区别在于处理三位数因数的方式：

*  单层循环，从999\*999开始，一直往下找，找到第一个为两个三位数乘积并且为回文数的数即为所找的数；
 *  双层循环，内外循环都从999开始，找到内层与外层的乘积为回文数的数，再找出其中最大的数，即为结果。

代码如下：

def is_three_multi(num):
        '''判断一个数是否是两个三位数的乘积'''
        is_multi = False
        for j in range(100, int(pow(num, 0.5)+1)):
            if num % j == 0 and num // j < 1000 and num // j >= 100:
                is_multi = True
                break
        return is_multi
    
    def is_palindrome(num):
        '''判断一个数是否是回文数'''
        is_palin = False
        num_str = str(num)
        str_len = len(num_str)
        half_len = str_len // 2
        for k in range(half_len):
            if num_str[k] != num_str[str_len-1-k]:
                break
        else:
            is_palin = True
        return is_palin
    
    def max_palindrome_multiply1():
        '''单层循环方法'''
        for i in range(999*999, 100*100-1, -1):
            if is_three_multi(i):
                if is_palindrome(i):
                    return i
        return None
    
    print(max_palindrome_multiply1())
    
    
    def is_palindrome(num):
        '''判断一个数是否是回文数'''
        is_palin = False
        nums = []
        while num > 0:
            nums.append(num % 10)
            num //= 10
        num_len = len(nums)
        for i in range(num_len//2):
            if nums[i] != nums[num_len - 1 - i]:
                break
        else:
            is_palin = True
        return is_palin
    
    def max_palindrome_multiply2():
        '''双层循环方法'''
        max_pro = 1
        for i in range(999, 99, -1):
            for j in range(999, 99, -1):
                pro = i * j
                if pro > max_pro and is_palindrome(pro):
                    max_pro = pro
                    break
        return max_pro
    
    print(max_palindrome_multiply2())

输出：

906609
    906609

性能分析：  
经过测试，两种方法的效率相近。

## 3.最小倍数 ##

> 2520是最小的能够被1到10整除的数。  
> 最小的能够被1到20整除的正数是多少？

解题思路：  
本题有3种实现方式：

1.  本题求最小的能够被1到20整除的正数，其实就是求1到20的最小公倍数，1到n的最小公倍数也是n\*(n-1)的倍数，通过不断判断n\*(n-1)的倍数是否都能被1到n整除，如果能整除则这个数就是寻找的答案。
2.  从1开始累乘，如果当前的数与乘积互质、则乘这个数，否则乘这个数与这个数乘积的最大公因数的商。
3.  先找出2-20所有的质数，并得到它们的乘积作为初始值S，剩下的全是非质数，对于每一个非质数找出组成这个非质数的最小质数z，如果这个非质数能整除S，则S不变，否则S乘z，详细思路可查看[https://blog.csdn.net/weixin\_30471561/article/details/99387184][https_blog.csdn.net_weixin_30471561_article_details_99387184]。

代码如下：

import sys
    
    def min_cumulative_number1(n):
        max_int = sys.maxsize
        base = n * (n - 1)
        min_cumul = 1
        for i in range(1, max_int):
            min_cumul = base * i
            for j in range(1, n + 1):
                if min_cumul % j != 0:
                    break
                if j == n:
                    return min_cumul
        return min_cumul
    
    print(min_cumulative_number1(20))
    
    def max_common_divider(m, n):
        '''寻找两个数的最大公因数'''
        if m < n:
            m, n = n, m
        while n != 0:
            m, n = n, m % n
        return m
            
    
    def min_cumulative_number2(n):
        res = 1
        for i in range(1, n + 1):
            common_divider = max_common_divider(res, i)
            if common_divider == 1:
                res *= i
            else:
                res *= (i // common_divider)
        return res
    
    print(min_cumulative_number2(20))
    
    
    def is_prime(n):
        '''判断一个数是否是质数'''
        is_prime = True
        for i in range(2, int(pow(n, 0.5)) + 1):
            if n % i == 0:
                is_prime = False
                break
        return is_prime
    
    def min_prime(n):
        '''寻找一个数的最小质数'''
        res = 1
        for i in range(2, int(pow(n, 0.5)) + 1):
            if n % i == 0:
                res = i
                break
        return res
    
    def get_primes(n):
        '''获取前n个数中的素数列表'''
        primes = []
        for i in range(2, n + 1):
            if is_prime(i):
                primes.append(i)
        return primes
    
    
    def min_cumulative_number3(n):
        nums = [i for i in range(2, n + 1)]
        res = 1
        prime_list = get_primes(n)
        for num in prime_list:
            res *= num
            nums.remove(num)
        for num in nums:
            res = res if res % num == 0 else res * min_prime(num)
        return res
    
    print(min_cumulative_number3(20))

输出：

232792560
    232792560
    232792560

性能分析：  
其中第一种方式的性能较低，因为要循环的次数太多（`sys.maxsize`表示Python中最大的整数）；  
第二种和第三种的性能相近。

## 4.并非盈数之和 ##

> 完全数是指真因数之和等于自身的那些数。例如，28的真因数之和为1 + 2 + 4 + 7 + 14 = 28，因此28是一个完全数。  
> 一个数n被称为亏数，如果它的真因数之和小于n；反之则被称为盈数。  
> 由于12是最小的盈数，它的真因数之和为1 + 2 + 3 + 4 + 6 = 16，所以最小的能够表示成两个盈数之和的数是24。  
> 通过数学分析可以得出，所有大于28123的数都可以被写成两个盈数的和；  
> 尽管我们知道最大的不能被写成两个盈数的和的数要小于这个值，但这是通过分析所能得到的最好上界。  
> 找出所有不能被写成两个盈数之和的正整数，并求它们的和。

解题思路：

1.  寻找所有的盈数，再找出不能写成两个数的和的数，判断和的方式为嵌套循环，时间复杂度较高；
2.  判断一个数是否是盈数、形成盈数的列表，在找不能由两个盈数的和组成的数时，用到的是二分法，复杂度降低。

代码如下：

def find_num_fac_sum(n):
        '''寻找一个数的真因数之和'''
        fac_sum = 0
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                fac_sum += i
        return fac_sum
    
    def find_more_nums(n):
        '''找到前n个数的所有盈数'''
        more_nums = []
        for j in range(1, n + 1):
            if find_num_fac_sum(j) > j:
                more_nums.append(j)
        return more_nums
                
    def not_sum(n, nums):
        '''判断一个数是否能写成两个盈数之和'''
        not_exists = True
        for k in nums:
            if n - k in nums:
                not_exists = False
                break
        return not_exists
                
    def find_no_more_sum_numbers1():
        more_nums = find_more_nums(28123)
        sum_res = 0
        for i in range(1, 28124):
            if not_sum(i, more_nums):
                sum_res += i
        return sum_res
    
    print(find_no_more_sum_numbers1())
    
    
    def is_abundant(n):
        '''判断一个数是否是盈数'''
        fac_sum = 0
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                fac_sum += i
        return fac_sum > n
    
    def find_no_more_sum_numbers2():
        abu_list = []
        for i in range(1, 28124):
            if is_abundant(i):
                abu_list.append(i)
        
        non_abu_sum = 0
        abu_list_len = len(abu_list)
        for j in range(1, 28124):
            non_abu = True
            begin = 0
            end = abu_list_len - 1
            # 二分法判断
            while begin <= end:
                two_sum = abu_list[begin] + abu_list[end]
                if two_sum > j:
                    end -= 1
                elif two_sum < j:
                    begin += 1
                else:
                    non_abu = False
                    break
            if non_abu:
                non_abu_sum += j
        return non_abu_sum
    
    
    print(find_no_more_sum_numbers2())

输出：

4179871
    4179871

性能分析：  
很明显，第二种方法的性能更高。

## 5.第10001个素数 ##

> 列出前6个素数，它们分别是2、3、5、7、11和13。  
> 我们可以看出，第6个素数是13。  
> 第10,001个素数是多少？

解题思路：  
有2种方法，区别主要在于判断素数的思路，一种是直接判断，另外一种是判断是否是大于2的偶数，如果是则不需要再循环判断，否则才需要循环判断，显然，第二种方法效率会相对高一些，因为循环的次数更少了。

代码如下：

def prime1(n):
        '''判断一个数是否是素数'''
        is_prime = True
        for i in range(2, int(pow(n, 0.5)) + 1):
            if n % i == 0:
                is_prime = False
                break
        return is_prime
    
    def n_prime1(n):
        count = 0
        i = 1
        while count < n:
            i += 1
            if prime(i):
                count += 1        
        return i
    
    print(n_prime1(10001))
    
    def prime2(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 n_prime2(n):
        import sys
        count = 0
        for i in range(2, sys.maxsize):
            if prime2(i):
                count += 1
                if count == n:
                    return i
    
    print(n_prime2(10001))

输出：

104743
    104743

性能分析：  
一般情况下，第二种方法的效率更高。

[https_blog.csdn.net_weixin_30471561_article_details_99387184]: https://blog.csdn.net/weixin_30471561/article/details/99387184