数据结构与算法练习(1)

文章目录

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

代码如下:

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

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

    原文作者:cutercorley
    原文地址: https://blog.csdn.net/CUFEECR/article/details/117999546
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞