Python中的蛮力算法

2025年1月5日 | 阅读6分钟

暴力算法是一种直观的问题解决方法，它通过系统地测试所有可行的选择来找到解决方案。当更有效的方法难以实现或任务规模足够小时，暴力法是可行的，因此常被使用。

示例 1

这是一个基础的 Python 暴力法，用于查找给定范围内的所有素数。

暴力破解法

程序

def is_prime(number):
    if number <= 1:
        return False
    for i in range(2, int(number**0.5) + 1):
        if number % i == 0:
            return False
    return True

def find_primes_in_range(start, end):
    primes = []
    for num in range(start, end + 1):
        if is_prime(num):
            primes.append(num)
    return primes

# Example usage:
start_range = 10
end_range = 50
prime_numbers = find_primes_in_range(start_range, end_range)
print("Prime numbers in the range", start_range, "to", end_range, "are:", prime_numbers)

输出

Prime numbers in the range 10 to 50 are: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

说明

在此示例中，`is_prime()` 是一个检查数字是否为素数的函数。它从 2 迭代到数字的平方根，检查是否能被整除。`find_primes_in_range()` 是一个函数，通过系统地检查每个数字来查找给定范围内的所有素数。

高效方法

程序

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False

    for current in range(2, int(limit**0.5) + 1):
        if sieve[current]:
            for multiple in range(current**2, limit + 1, current):
                sieve[multiple] = False

    primes = [num for num, is_prime in enumerate(sieve) if is_prime]
    return primes

def find_primes_in_range(start, end):
    if start < 2:
        start = 2

    primes = sieve_of_eratosthenes(end)
    return [prime for prime in primes if start <= prime <= end]

# Example usage:
start_range = 10
end_range = 50
prime_numbers = find_primes_in_range(start_range, end_range)
print("Prime numbers in the range", start_range, "to", end_range, "are:", prime_numbers)

输出

Prime numbers in the range 10 to 50 are: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

说明

此算法采用埃拉托斯特尼筛法高效地查找给定范围内的素数。它首先使用该筛法找到小于等于结束值的素数，然后筛选出指定范围内的素数。对于查找范围内的素数，此方法比暴力法快得多。

示例 2

让我们使用暴力方法查找列表中的最大元素。

程序

def find_max(list1):
  """ Finds the maximum element in a list using a brute-force algorithm. """

  max_value = list1[0]
  for element in list1:
    if element > max_value:
      max_value = element
  return max_value


# Example usage:

list1 = [1, 5, 3, 7, 9]
max_value = find_max(list1)
print("The maximum value is", max_value)

输出

The maximum value is 9

说明

此算法迭代列表，并将每个元素与当前最大值进行比较。如果元素大于当前最大值，则更新最大值。算法在迭代结束时返回最大值。

高效方法

程序

list1 = [1, 5, 3, 7, 9]
max_value = max(list1)
print("The maximum value is", max_value)

输出

The maximum value is 9

说明

`max` 函数经过了极大的优化，提供了一种更简单、更有效的方法来确定列表或可迭代对象中的最大值。可用时，应使用内置函数，它们通常针对性能进行了优化，无需专门实现。

示例 3

让我们使用暴力方法查找能被 1 到 20 的所有数字整除的最小正整数（1 到 20 的 LCM）。

程序

def brute_force_lcm(n):
    current_number = n
    while True:
        divisible = True
        for i in range(1, n + 1):
            if current_number % i != 0:
                divisible = False
                break
        if divisible:
            return current_number
        current_number += n

n = 20
result_brute_force = brute_force_lcm(n)
print(f"The smallest number divisible by all numbers from 1 to {n} (brute force): {result_brute_force}")

输出

The smallest number divisible by all numbers from 1 to 20 (brute force): 232792560

说明

代码会一直运行，直到找到一个满足条件（能被 1 到 20 的所有数字整除）的数字。这种方法是暴力的，因为它单独检查所有可能的正整数，直到找到一个有效结果。对于较大的 n 值，它可能效率不高，但最终会给出正确答案。

高效方法

程序

from math import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

def efficient_lcm(n):
    result = 1
    for i in range(1, n + 1):
        result = lcm(result, i)
    return result
n=20
result_efficient = efficient_lcm(n)
print(f"The smallest number divisible by all numbers from 1 to {n} (efficient): {result_efficient}")

输出

The smallest number divisible by all numbers from 1 to 20 (efficient): 232792560

说明

高效的方法是直接使用 LCM 的属性和 `lcm` 函数来计算 LCM，这使得它比暴力方法快得多，尤其对于较大的 n 值。它可以在不检查所有可能整数的情况下高效地提供正确答案。

示例 4

让我们看一个使用暴力方法在列表中查找目标元素的示例。

程序

def is_target_in_subset(subset, target):
    found = False  # Initialize the found variable to False

    for element in subset:
        if element == target:
            found = True  # Update found if the target is found
            break  # Exit the loop

    return found

# Example usage:
subset = [2, 5, 8, 10, 12]
target_value = 8
result = is_target_in_subset(subset, target_value)

if result:
    print("The target value", target_value, "was found in the subset.")
else:
    print("The target value", target_value, "was not found in the subset.")

输出

The target value 8 was found in the subset.

说明

在此示例中，暴力策略会迭代子集中的各项，将每一项与所需值进行比较。如果找到匹配项，则将 `found` 变量设置为 `True`，并终止循环。该函数在检查所有元素后返回 `found`，指示目标值是否在子集中找到。

高效方法

程序

def is_target_in_subset_efficient(subset, target):
    # Create a HashSet (dictionary) to store the elements of the subset
    subset_set = set(subset)
    
    # Check if the target value is in the HashSet (constant-time lookup)
    return target in subset_set

# Example usage:
subset = [2, 5, 8, 10, 12]
target_value = 8
result = is_target_in_subset_efficient(subset, target_value)

if result:
    print("The target value", target_value, "was found in the subset.")
else:
    print("The target value", target_value, "was not found in the subset.")

输出

The target value 8 was found in the subset.

说明

对于此任务，使用 HashSet 或字典效率很高，因为它提供了平均恒定的查找时间，非常适合需要反复检查值是否在给定集合中的情况。

优点

暴力算法在某些情况下具有各种优势，使其适用。
暴力方法通常易于构建和理解。它们不需要复杂的数据结构或困难的逻辑，这在任务简单或需要快速开发时可能很有益。
在适当使用时，暴力算法是可靠的，并确保解决方案正确。由于算法系统地探索了所有可能性，因此没有出错的余地。
暴力算法对于选择有限的小型问题很有用。在这种情况下，暴力技术的效率可能超过其简单性。
暴力算法可用于评估更高级算法的性能。
暴力算法可以帮助您深入理解问题。它们迫使您调查所有可能性，以识别可用于创建更有效算法的趋势或想法。

局限性

在安全相关的应用中，攻击者可以利用暴力法系统地测试所有可能的输入、密码或密钥，以获得未经授权的访问。
总的来说，暴力技术必须针对需要快速决策的实时或动态情况进行改进。
暴力技术在扩展性方面可能效率不高。当处理复杂情况时，由于必须权衡许多选项，它们会变得不切实际。
暴力方法会检查所有可能的答案，包括错误的答案。随着问题规模的增长，这种低效率成为一个大问题。
暴力算法通常具有指数级时间复杂度，这意味着解决问题所需的时间随着问题规模的增长呈指数级增长。因此，它们可能更适用于大型输入。

结论

总之，暴力算法是一种基本而直观的问题解决方法。它包括尝试所有可能的解决方案，并逐个系统地检查，直到找到正确的解决方案。暴力算法很有用，尤其适用于准确性至关重要的规模较小或简单的问题。它们可以作为创建更有效算法的有用起点。然而，对于更复杂或更大型的问题，通常需要高级算法和优化技术才能在合理的时间内获得实际结果。

下一主题Python 中的数据挖掘算法

Python中的蛮力算法

示例 1

暴力破解法

高效方法

示例 2

高效方法

示例 3

高效方法

示例 4

高效方法

优点

局限性

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中的蛮力算法

示例 1

暴力破解法

高效方法

示例 2

高效方法

示例 3

高效方法

示例 4

高效方法

优点

局限性

结论

相关帖子

Pandas中的流水线

Python中的os.sched_setaffinity()方法

使用Python .docx模块处理图像

Python在竞争性编程中的应用

PATCH方法 - Python Requests

Python中的Dedupe库

如何在Python中从文件夹读取多个文本文件

Python Pandas中不同类型的连接

Python中的字符串Slugification

Trino Python客户端完整指南

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器