水仙花数

水仙花数 (Narcissistic Number)，又称为自恋数，是一种特殊的数字。一个 n 位数如果等于其各位数字的 n 次方之和，则称该数为水仙花数。下面我们来寻找所有的 3 位数中的水仙花数。

In [1]:

for i in range(100, 1000):
    a = i // 100
    b = i // 10 % 10
    c = i % 10
    if a**3 + b**3 + c**3 == i:
        print(f"{i} 是水仙花数")

153 是水仙花数
370 是水仙花数
371 是水仙花数
407 是水仙花数

回文数

回文数是指一个字符串 (或数字) 从前往后读和从后往前读都相同的序列。例如，字符串 “radar” 和 “level” 都是回文字符串，而 “hello” 不是。

In [2]:

def is_palindrome(s):
    return s == s[::-1]

In [3]:

strs = ["radar", "level", "hello"]
for s in strs:
    result = is_palindrome(s)
    print(f'"{s}" 是回文数：{result}')

"radar" 是回文数：True
"level" 是回文数：True
"hello" 是回文数：False

素数

素数 (Prime Number) 是指大于 1 的自然数，且只能被 1 和自身整除的数。换句话说，素数没有其他的因数。例如，2、3、5、7、11、13 等都是素数。下面我们来寻找 100 以内的所有素数。

In [4]:

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

In [5]:

primes = [num for num in range(100) if is_prime(num)]
print(f"100 以内的所有素数：{primes}")

100 以内的所有素数：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

埃拉托斯特尼筛法 (Sieve of Eratosthenes)，这个算法的基本思想是通过逐步标记出合数，从而找出所有的素数。

In [6]:

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    return [p for p in range(2, n + 1) if is_prime[p]]

In [7]:

print(f"100 以内的所有素数：{sieve_of_eratosthenes(100)}")

100 以内的所有素数：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

最大公约数

欧几里得算法是一种用于计算两个整数最大公约数 (GCD) 的经典算法。它的基本思想是利用以下性质：两个数的最大公约数等于其中较小的数与两数相除后余数的最大公约数。

In [8]:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

In [9]:

num1 = 48
num2 = 18
result = gcd(num1, num2)
print(f"{num1} 和 {num2} 的最大公约数是：{result}")

48 和 18 的最大公约数是：6

二分查找

二分查找是一种高效的查找算法，适用于在已排序的数组中查找特定元素。它通过将搜索范围不断减半来快速定位目标元素，从而显著减少查找时间。

In [10]:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

In [11]:

for i in range(7):
    print(i, "=>", binary_search([2, 3, 4, 5], i))

0 => -1
1 => -1
2 => 0
3 => 1
4 => 2
5 => 3
6 => -1

斐波那契数列

斐波那契数列是一个经典的数列，其定义如下：第一个数是 0，第二个数是 1。从第三个数开始，每个数都是前两个数的和。用数学公式表示为：

$F (0) F (1) F (n) am p; = 0 am p; = 1 am p; = F (n - 1) + F (n - 2), n \geq 2$

In [12]:

def fib1(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

In [13]:

def fib2(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib2(n - 1) + fib2(n - 2)

In [14]:

def fib3(n):
    fibs = [0, 1]
    for i in range(2, n + 1):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs[n]

In [15]:

print(fib1(15))
print(fib2(15))
print(fib3(15))

610
610
610

In [16]:

%timeit fib1(15)
%timeit fib2(15)
%timeit fib3(15)

909 ns ± 40.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
246 µs ± 14.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
1.95 µs ± 76.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

fib1 的算法耗时最短。