【python基础算法编程】

一、Python中如何进行倒序处理

在 Python 中，可以使用多种方法来对列表、字符串或其他可迭代对象进行倒序处理。

在 Python 中，通常更倾向于使用内置的reversed() 函数或切片[::-1]操作来实现这种操作，因为它们更简洁和高效

1、使用切片

：对于列表和字符串，可以使用切片操作来获取倒序的结果。

具体来说，使用 [::-1] 语法可以从最后一个元素开始，到第一个元素结束，步长为 -1

a_list = [1, 2, 3, 4, 5]
b_list = my_list[::-1]
print(b_list)  # Output: [5, 4, 3, 2, 1]


my_string = "hello"
reversed_string = my_string[::-1]
print(reversed_string)  # Output: "olleh"

关于切片

和range（）函数有点像

切片（Slicing）是一种用于从序列（如字符串、列表、元组）中提取子序列的方法。它允许你通过指定起始和结束索引来选择序列的一部分。

基本语法是 sequence[start:stop:step]，其中：

1、sequence 是你要进行切片的原始序列。
2、start 是切片的开始索引（包含在内）。如果省略，则默认为 0。
3、stop 是切片的结束索引（不包含在内）。如果省略，则默认为序列的末尾。
4、step 是切片的步长。如果省略，则默认为 1。


以下是一些示例来更好地理解切片：

1. 基本用法
my_list = [1, 2, 3, 4, 5]
print(my_list[1:4])  # 输出 [2, 3, 4]
在这个例子中，我们从索引 1 开始，到索引 4 结束（不包括索引 4），因此结果是 [2, 3, 4]。

2. 省略 start 或 stop
my_list = [1, 2, 3, 4, 5]
print(my_list[:3])  # 输出 [1, 2, 3]
print(my_list[2:])  # 输出 [3, 4, 5]
在第一个例子中，我们省略了 start，所以从索引 0 开始切片。第二个例子中，我们省略了 stop，所以切片到序列的末尾。

3. 使用负索引
my_list = [1, 2, 3, 4, 5]
print(my_list[-3:])  # 输出 [3, 4, 5]
负索引从序列的末尾开始计算。因此，-3 表示从倒数第三个元素开始切片。

4. 使用步长
my_list = [1, 2, 3, 4, 5]
print(my_list[::2])  # 输出 [1, 3, 5]
在这个例子中，我们使用步长 2，所以结果是原始序列的每隔一个元素。

5. 切片字符串
my_string = "Hello, World!"
print(my_string[1:5])  # 输出 "ello"
切片也可以应用于字符串。这个例子中，我们从索引 1 开始，到索引 5 结束（不包括索引 5），所以结果是 "ello"。

切片是 Python 中一个非常强大和灵活的工具，可以帮助你轻松地处理各种类型的序列数据。

2、reversed() 函数

reversed() 函数可以接受一个可迭代对象并返回一个反转的迭代器

a_list = [1, 2, 3, 4, 5]
b_list = list(reversed(my_list))
print(b_list)  # Output: [5, 4, 3, 2, 1]

a_string = "hello"
b_string = "".join(reversed(a_string))
print(b_string)  # Output: "olleh"

3、sorted() 函数

虽然不太直观，但可以使用 sorted() 函数并指定 reverse=True 来对列表进行倒序排序。

my_list = [1, 2, 3, 4, 5]
reversed_list = sorted(my_list, reverse=True)
print(reversed_list)  # Output: [5, 4, 3, 2, 1]

4、使用循环：

可以使用循环从最后一个元素开始，逐个访问每个元素，直到第一个元素。

my_list = [1, 2, 3, 4, 5]
reversed_list = []
for i in range(len(my_list)-1, -1, -1):
    reversed_list.append(my_list[i])
print(reversed_list)  # Output: [5, 4, 3, 2, 1]

使用 for 循环来遍历 my_list 中的元素。
循环的迭代变量 i 的初始值是 len(my_list)-1，即列表中最后一个元素的索引（因为 Python 的索引从 0 开始）。
循环的终止条件是 i 小于等于 0，步长是 -1，这意味着每次迭代 i 的值会减少 1，直到达到 0。



my_string = "hello"
reversed_string = ""
for char in my_string[::-1]:
    reversed_string += char
print(reversed_string)  # Output: "olleh"

在 Python 中，range() 函数是一个非常有用的工具，用于生成一系列整数。

它通常用于 for 循环中，以便对某个范围内的整数进行迭代。包括倒序处理

range() 函数可以接受一到三个参数：start, stop, 和 step。

start：指定序列的起始值。默认情况下，起始值为 0。

stop：指定序列的终止值。序列生成器将生成从 start 到 stop-1 的所有整数。stop 值本身不包含在生成的序列中。

step：指定序列中相邻两个元素之间的差值。默认步长为 1。



下面是一些使用 range() 函数的示例：

range(5)：生成一个从 0 到 4 的序列，等同于 [0, 1, 2, 3, 4]。
range(1, 5)：生成一个从 1 到 4 的序列，等同于 [1, 2, 3, 4]。
range(0, 10, 2)：生成一个从 0 到 8 的序列，步长为 2，等同于 [0, 2, 4, 6, 8]。
range(5, 0, -1)：生成一个从 5 到 1 的序列，步长为 -1，等同于 [5, 4, 3, 2, 1]。

step 为-1，表示，start 每次-1

二、冒泡排序的Python实现

bubble_sort() 函数接受一个列表作为参数，并对其进行排序。它使用两个嵌套的循环来遍历列表并进行元素交换。外层循环控制排序的轮数，内层循环比较相邻的元素并交换它们。

请注意，冒泡排序的时间复杂度为 O(n^2)，因此它不适合大规模的数据排序

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Last i elements are already in place
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("Sorted array is:", my_list)

三、斐波那契数列，求第N位的数据，利用Python实现

斐波那契数列是一个经典的数学序列，其中每个数字都是前两个数字的和。

斐波那契序列以0和1开头，然后每个后续数字都是前两个数字的和。

1、方法一：递归

递归是一种直接的方法来计算斐波那契数列，但对于较大的 N 值，它会非常慢，因为它会重复计算相同的子问题。

def fibonacci_recursive(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

# Example usage
n = 10
print(fibonacci_recursive(n))  # Output: 55

2、方法二：迭代

迭代方法更高效，因为它避免了重复计算。它使用一个循环来计算每个斐波那契数字。

def fibonacci_iterative(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        #首先，我们初始化两个变量 a 和 b 分别为斐波那契数列的前两个数字。
        a, b = 0, 1
        for _ in range(2, n+1):
            a, b = b, a + b
        return b

# Example usage
n = 10
print(fibonacci_iterative(n))  # Output: 55

在 Python 中，`_` 是一个特殊的变量名，通常用来表示在特定上下文中不需要使用的变量。
它可以用作任何变量名，通常被用来表示一个"丢弃"或"无用"的变量。

在这个特定的情况下，`_` 是在 `for` 循环中用作循环变量的名称。这个循环变量实际上不被使用，因为我们只需要迭代一定的次数来计算斐波那契数列的第 N 项。使用 `_` 作为变量名是一种惯例，表示我们不关心循环变量的具体值，只关心循环的次数。

如果你想，你也可以使用其他变量名，例如 `i`，来代替 `_`。但是，使用 `_` 是一种常见的做法，可以帮助其他开发者更容易地理解你的代码。

四、判断一个数据是否为回文的Python实现

回文（Palindrome）是一个在前后两端都能读出同样内容的词、短语、数字、或其他序列的特性。换句话说，回文是指正着读和倒着读都一样的序列。

例如，以下都是回文的例子：

单词：“level”, “radar”, “deified”
短语：“A man, a plan, a canal, Panama!”
数字：“121”, “12321”, “10001”

1、使用切片和反转比较

这个函数接受一个字符串 s，然后使用切片 [::-1] 来反转字符串，并将其与原字符串进行比较。如果它们相同，则返回 True，否则返回 False。

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

2、使用循环比较

这个函数使用两个指针，一个从字符串的开头开始，另一个从字符串的结尾开始。然后，它在每次迭代中比较这两个指针所指向的字符是否相等。如果在某个点它们不相等，函数返回 False。如果循环完成而没有发现不相等的字符对，函数返回 True。

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left]!= s[right]:
            return False
        left += 1
        right -= 1
    return True

3、使用递归比较

这个函数使用递归来检查字符串是否为回文。它首先检查字符串的长度是否小于 2，如果是，则返回 True。然后，它比较字符串的第一个和最后一个字符是否相等。如果它们不相等，函数返回 False。否则，函数递归调用自身，传入去掉首尾字符的子字符串。如果递归过程中没有发现不相等的字符对，函数最终返回 True。

def is_palindrome(s):
    if len(s) < 2:
        return True
    if s[0]!= s[-1]:
        return False
    return is_palindrome(s[1:-1])

五、对于1-4这四个数字，能组成互不相同的且无重复的三位数的 数量以及具体数字：

1、使用permutations 函数

itertools 模块中的 permutations 函数是一个生成器函数，用于生成从给定序列中选择指定长度的元素的所有排列。

from itertools import permutations

# 定义数字列表
digits = [1, 2, 3, 4]

# 使用 permutations 函数生成所有可能的三位数
three_digit_numbers = [''.join(p) for p in permutations(digits, 3)]

# 输出结果
print("总共可以组成的三位数数量为：", len(three_digit_numbers))
print("所有可能的三位数：")
for number in three_digit_numbers:
    print(number)

itertools 模块中的 permutations 函数是一个生成器函数，
用于生成从给定序列中选择指定长度的元素的所有排列。
换句话说，它可以给出一个序列中所有可能的排列组合。

这个函数接受两个参数：一个可迭代对象（如列表、元组或字符串）和一个整数，表示要生成的排列的长度。如果不指定第二个参数，默认情况下生成所有可能的排列。

以下是一个简单的例子，展示了如何使用 permutations 函数来生成一个列表中所有可能的两元素排列：

import itertools

my_list = [1, 2, 3]
two_element_permutations = list(itertools.permutations(my_list, 2))

print(two_element_permutations)
输出结果将是：

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]




my_list = [1, 2, 3]
two_element_permutations = list(itertools.permutations(my_list))

print(two_element_permutations)
输出结果将是：

[(1, 2), (1, 2，3), (2, 1，3), (2, 3), (3, 1), (3, 2)]等等

2、三层for循环

count = 0

numbers = []

for i in range(1, 5):
    for j in range(1, 5):
        for k in range(1, 5):
            if i != j and i != k and j != k:  # 确保三个数字互不相同

                count += 1

                numbers.append(i * 100 + j * 10 + k)

print("能组成的互不相同的且无重复的三位数的数量为:", count)

print("具体数字为:", numbers)

六、给定一串整数0-N，和一个0-9的数K，要求返回0-N中数字K出 现的次数。

def count_digit_occurrences(N, K):
    count = 0

    #想遍历到N，就得写到N+1
    for i in range(N+1):
        count += str(i).count(str(K))
    return count

# 示例用法
N = 100
K = 5
result = count_digit_occurrences(N, K)
print(f"在0到{N}之间的整数中，数字{K}出现了{result}次。")

count += str(i).count(str(K))

1、str(i): 将当前整数 i 转换为字符串类型。这是因为我们需要在字符串中查找指定数字的出现次数。
2、str(K): 将指定的数字 K 也转换为字符串类型。这样可以在字符串中进行比较和计数。
3、.count(str(K)): 在 str(i) 这个字符串中，统计 str(K) 出现的次数。count() 方法返回指定子串在字符串中出现的次数。
4、count +=...: 将计算出的出现次数加到变量 count 中。这样，count 就会累加所有整数中指定数字的出现次数。

总的来说，这个语句的作用是遍历给定范围内的每个整数，将其转换为字符串，并统计在这个字符串中指定数字出现的次数。通过累加这些出现次数

七、请用 python 打印出 10000 以内的对称数

对称数特点：数字左右对称，如：1,2,11,121,1221 等

定义回文数函数

def is_palindrome(n):  
    return str(n) == str(n)[::-1]  
  

使用for循环，调用这个回文数函数；

for i in range(10000):  
    if is_palindrome(i):  
        print(i)

八、判断 101-200 之间有多少个素数，并输出所有的素数

素数

素数（Prime Number）是指在大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数。换句话说，一个素数只有两个因子：1和它本身。

例如，2、3、5、7、11、13等都是素数，因为它们不能被除了1和它们本身以外的任何数整除。相反，4、6、8、9等不是素数，因为它们可以被其他数整除。

质数

质数和素数实际上是同义词，都是指大于1的自然数中，除了1和它本身以外，不能被其他自然数整除的数

1、表达式实现

count = 0
for num in range(101, 201):
    if all(num % i!= 0 for i in range(2, int(num**0.5)+1)):
        print(num)
        count += 1
print(f"共有 {count} 个素数。")

解释：

1、我们首先定义一个变量 count，用来统计素数的个数。
2、使用 for 循环遍历从 101 到 200 的所有数字。
3、对于每个数字，使用 all() 函数和生成器表达式来判断它是否是素数。生成器表达式 num % i!= 0 for i in range(2, int(num**0.5)+1) 会检查从 2 到 num 的平方根（向上取整）之间的所有数字是否能整除 num。如果都不能整除，说明 num 是素数。
4、如果 num 是素数，代码将其打印出来，并将 count 加 1。
5、最后，代码输出素数的总个数。

请注意，这个方法的时间复杂度是 O(n√n)，因为对于每个数字，我们都需要检查从 2 到它的平方根之间的所有数字是否能整除它。

range(2, int(num**0.5)+1): 

1、创建一个从 2 到 num 的平方根（向下取整）加 1 的整数序列。这个序列包含了所有可能的因子，因为如果一个数有大于其平方根的因子，那么它一定也有一个小于其平方根的因子。

2、num % i!= 0: 对于序列中的每个整数 i，检查 num 是否能被 i 整除。如果不能，那么这个条件就是 True。

3、all(...)：使用 all() 函数来检查上述条件是否对所有的 i 都成立。如果 num 不能被任何一个 i 整除，那么 all() 函数返回 True，表示 num 是素数；否则返回 False。

简而言之，这个表达式的意思是：如果 num 不能被从 2 到其平方根加 1 的任何整数整除，那么 num 是素数。这个方法是一种常见的素数判定算法

 2、for循环实现

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

count = 0  

for i in range(101, 201):  
    if is_prime(i):  
        print(i)  
        count += 1  

print("There are {} prime numbers between 101 and 200.".format(count))

九、请编写一个完整出程序，完成递归。

def factorial(n):  
    if n == 0 or n == 1:  
        return 1  
    else:  
        return n * factorial(n-1)  
  

n = int(input("请输入一个数字："))  

print("{}! = {}".format(n, factorial(n)))

十、写代码将如下数据从小到大排序，语言不限。（不可以直接使 用 sort（）等排序方法）

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print(data)

我们定义了一个名为 bubble_sort 的函数，它接受一个列表 arr 作为参数，并使用冒泡排序算法对其进行排序。

1、在函数内部，我们首先获取列表的长度 n。
2、然后，我们使用两个嵌套的循环来遍历列表。在外层循环中，我们从第一个元素到倒数第二个元素进行迭代。3、在内层循环中，我们从第一个元素到倒数第二个元素减去当前外层循环的迭代次数进行迭代。
4、在内层循环中，如果当前元素大于下一个元素，我们交换它们的位置。
5、这个过程会把最大的元素“冒泡”到列表的末尾。因此，外层循环的每次迭代都会使得剩余未排序的部分的最大值被移动到正确的位置。
6、最后，我们调用 bubble_sort 函数对给定的数据进行排序，并打印结果。

请注意，冒泡排序的时间复杂度是 O(n^2)