Python程序的一些问题

Python程序代码编写及输出
1、字符串的创建及输出（可用顺序存储及链式存储）
2、在字符串创建的基础上实现串的相关运算
3、递归模型的设计及算法的编写

基于new bing的参考回答：
【字符串的相关操作】

class String:
    def __init__(self, str_init):
        self.str = str_init # 创建串对象时初始化

    def connect(self, str2):
        """串连接"""
        return self.str + str2

    def insert(self, index, str_insert):
        """串插入"""
        return self.str[:index] + str_insert + self.str[index:]

    def delete(self, start, end):
        """串删除"""
        return self.str[:start] + self.str[end:]

    def replace(self, sub_str, new_str):
        """串替换"""
        return self.str.replace(sub_str, new_str)

    def find(self, sub_str):
        """串的模式匹配-查找子串"""
        return self.str.find(sub_str)

    def count(self, sub_str):
        """串的模式匹配-计算子串出现的次数"""
        return self.str.count(sub_str)

    def application(self):
        """串的相关应用"""
        # TODO: 添加具体应用


def string_operation(option, s1):
    """
    option:
        1. 串连接
        2. 串插入
        3. 串删除
        4. 串替换
        5. 串的模式匹配-查找子串
        6. 串的模式匹配-计算子串出现的次数
    """

    if option == 1:
        s2 = String(input("请输入第二个要连接的串："))
        s3 = s1.connect(s2.str)
        print("连接后的串为：", s3)
    elif option == 2:
        index = int(input("请输入要插入的位置："))
        sub_str = input("请输入要插入的字符串：")
        s2 = s1.insert(index, sub_str)
        print("插入后的串为：", s2)
    elif option == 3:
        start = int(input("请输入要删除的子串的起始位置："))
        end = int(input("请输入要删除的子串的结束位置："))
        s2 = s1.delete(start, end)
        print("删除后的串为：", s2)
    elif option == 4:
        sub_str = input("请输入要替换的子串：")
        new_str = input("请输入替换后的字符串：")
        s2 = s1.replace(sub_str, new_str)
        print("替换后的串为：", s2)
    elif option == 5:
        sub_str = input("请输入要查找的子串：")
        index = s1.find(sub_str)
        if index == -1:
            print("未找到子串！")
        else:
            print("子串在当前串中的位置为：", index)
    elif option == 6:
        sub_str = input("请输入要计算的子串：")
        count = s1.count(sub_str)
        print("子串在当前串中出现的次数为：", count)
    else:
        print("不支持的操作！")


# 测试主函数
def test_string_operation():
    # 创建字符对象
    s1 = String("hello")

    while True:
        # 打印菜单
        print("\n请选择操作：")
        print("1. 连接两个字符串")
        print("2. 在指定位置插入字符串")
        print("3. 删除指定子串")
        print("4. 替换子串")
        print("5. 查找子串")
        print("6. 计算子串出现的次数")
        print("0. 退出程序")
        print("初始化的字符串是"+s1.str)

        # 获取用户选择
        option = input("请选择菜单上的编号进行操作：")

        if option == "0":
            print("程序已退出。")
            break

        try:
            option = int(option)
        except ValueError:
            print("输入的不是合法的菜单编号，请重新输入！")
            continue

        if 1 <= option <= 6:
            string_operation(option, s1)
        else:
            print("输入的菜单编号不在范围内，请重新输入！")


# 调用测试主函数
test_string_operation()

【单链表的正向反向输出】


class ListNode:
    """
    链表节点类
    """
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    """
    单链表类
    """
    def __init__(self, head=None):
        self.head = head

    def add_node(self, val):
        """
        在链表末尾添加节点
        """
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node

    def print_linked_list(self):
        """
        遍历并正向输出单链表
        """
        current_node = self.head
        while current_node:
            print(current_node.val, end=" ")
            current_node = current_node.next
        print()

    def print_linked_list_reverse(self):
        """
        非递归实现单链表的反向输出
        """
        stack = []
        current_node = self.head
        while current_node:
            stack.append(current_node.val)
            current_node = current_node.next
        while stack:
            print(stack.pop(), end=" ")
        print()

    def print_linked_list_reverse_recursive(self, head=None):
        """
        递归实现单链表的反向输出
        """
        if not head:
            head = self.head
        stack = []
        current_node = head
        while current_node:
            stack.append(current_node.val)
            current_node = current_node.next
        while stack:
            print(stack.pop(), end=" ")
        print()


# 测试
if __name__ == '__main__':
    # 创建链表对象
    linked_list = LinkedList()

    # 添加节点
    linked_list.add_node(1)
    linked_list.add_node(2)
    linked_list.add_node(3)
    linked_list.add_node(4)
    linked_list.add_node(5)

    # 正向输出
    print("正向输出：")
    linked_list.print_linked_list()

    # 反向输出（非递归）
    print("反向输出（非递归）：")
    linked_list.print_linked_list_reverse()

    # 反向输出（递归）
    print("反向输出（递归）：")
    linked_list.print_linked_list_reverse_recursive()

问题1,2没啥补充，对于递归做些补充。递归在解决以下类型的问题时非常有效：
1、问题可分解为较小的子问题：递归适用于那些可以通过将原始问题划分为更小的、相同或相似的子问题来解决的情况。通过递归地解决这些子问题，最终可以解决原始问题。
2、问题具有递归结构：某些问题本身就具有递归结构，即问题的解取决于相同问题类型的更小实例的解。例如，树、图和链表等数据结构的遍历和搜索问题通常使用递归来实现。
3、问题规模可缩小：在递归算法中，问题的规模应该在每一次递归调用中变得更小，接近基本情况。如果问题的规模不能缩小，递归可能会导致无限循环。
常见的递归应用包括阶乘、斐波那契数列、二叉树遍历、图的深度优先搜索等。不过，在某些情况下，使用循环或其他算法可能更加高效和简单。因此，在选择是否使用递归时，需要权衡问题的特点、可读性、性能等因素。
当设计递归模型时，有几个关键方面需要考虑：基本情况（递归的停止条件）、递归步骤和问题规模的缩小。

递归


Fabonacci数列
学过数学的人应该都知道Fabonacci数列，1，1，2，3，5，8，13…，我们可以很容易的写出这个数列的递归公式表示

同样的，根据这个递归公式我们就可以方便的写出递归函数

#Fabonacci数列
def fabonacci(n:int):
'''
        n为输出fabonacci数列的第多少个
    '''
if n <= 1:
return 1
else:
return fabonacci(n-1)+fabonacci(n-2)
 
 
#时间复杂度为O(2^n)  调用过程类比二叉树