递归与回溯算法的探索

递归是一种在函数内部调用自身的方法,它可以用来解决许多复杂的问题。回溯算法则是一种通过探索所有可能的候选解来寻找所有解决方案的算法,如果当前路径不可能得到有效的解,算法会回溯到上一步,尝试其他可能的路径。本文将通过几个Python代码示例,介绍递归和回溯算法的基本概念和应用。

阶乘计算

阶乘是所有小于等于该数的正整数的乘积。例如,4的阶乘(记作4!)等于4*3*2*1=24。下面是一个使用递归计算阶乘的Python示例:

def factorial(n): if n > 1: return factorial(n - 1) * n return 1

这个函数通过递归调用自身,每次调用都将n的值减1,直到n为0,此时递归结束,返回1。

π值计算

π是一个无理数,其值可以通过多种方法计算。下面是一个使用递归计算π值的Python示例,它基于Nilakantha级数:

def CalcPiDecimals(opr, preciciendept): if preciciendept < 1: return 0 preciciendept -= 1 return 4/(opr * (opr + 1) * (opr + 2)) - 4/((opr + 2) * (opr + 3) * (opr + 4)) + CalcPiDecimals(opr + 4, preciciendept) print(3 + CalcPiDecimals(2, 500))

这个函数通过递归计算π的十进制部分,最终结果需要加上3。

数独解决

数独是一种逻辑游戏,玩家需要在9x9的网格中填入数字,使得每行、每列以及每个3x3的小方格内的数字都不重复。下面是一个使用回溯算法解决数独问题的Python示例:

import numpy as np sudoku = np.array([ [0, 0, 2, 0, 1, 5, 0, 7, 8], [1, 8, 0, 0, 6, 3, 4, 0, 0], [0, 0, 4, 0, 2, 0, 5, 6, 1], [0, 9, 6, 0, 0, 7, 0, 3, 0], [0, 1, 0, 3, 0, 6, 0, 0, 5], [0, 0, 3, 2, 0, 4, 0, 9, 6], [0, 3, 0, 0, 0, 0, 0, 0, 0], [6, 4, 9, 8, 3, 0, 2, 0, 7], [0, 0, 7, 0, 0, 0, 0, 1, 0] ]) def possible(sudoku, row, col, val): if sudoku[row][col] != 0: return False if val in sudoku[row]: return False for a in range(9): if sudoku[a][col] == val: return False sqr_row = int(int(row) / 3) * 3 sqr_col = int(int(col) / 3) * 3 for r in range(sqr_row, sqr_row + 3): for c in range(sqr_col, sqr_col + 3): if sudoku[r][c] == val: return False return True def solve_Sudoku(sudoku): for row in range(0, 9): for col in range(0, 9): if sudoku[row][col] == 0: for val in range(1, 10): if possible(sudoku, row, col, val): sudoku[row][col] = val if solve_Sudoku(sudoku): return True sudoku[row][col] = 0 return False return True solve_Sudoku(sudoku) print(sudoku)
沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485