2026年掌握noip竞赛中的递归与分治思想

2026年掌握noip竞赛中的递归与分治思想递归与分治思想应用题（共5题，总分40分）第1题（6分）——递归基础应用：斐波那契数列的递归实现题目：编写一个递归函数，计算斐波那契数列的第n项（n≥1）。斐波那契数列的定义如下：-F(1)=1-F(2)=1-F(n)=F(n-1)+F(n-2)（n>2）要求：1.若输入n≤0，函数需返回"输入错误"；2.递归过程中需避免重复计算（例如，使用记忆化技术）。示例：输入：5→输出：5输入：10→输出：55第2题（8分）——分治思想应用：快速排序算法实现题目：实现快速排序算法，要求：1.选择数组的最后一个元素作为基准（pivot）；2.将数组划分为小于基准和大于基准的两部分，分别递归排序；3.输出排序后的数组。要求：-递归终止条件为子数组长度≤1；-不允许使用额外的存储空间（原地排序）。示例：输入：[3,6,8,10,1,2,1]→输出：[1,1,2,3,6,8,10]第3题（7分）——递归与分治结合：二分搜索优化题目：给定一个有序数组nums和一个目标值target，实现二分搜索。要求：1.使用递归实现，返回目标值的索引（若不存在则返回-1）；2.优化递归调用次数，避免不必要的比较。示例：输入：nums=[1,2,3,4,5,6,7],target=4→输出：3输入：nums=[1,2,3,4,5],target=6→输出：-1第4题（9分）——分治思想应用：归并排序算法实现题目：实现归并排序算法，要求：1.将数组递归划分为两半，分别排序；2.合并两个有序子数组；3.输出排序后的数组。要求：-不允许使用额外的存储空间（尽可能优化空间复杂度）；-递归终止条件为子数组长度≤1。示例：输入：[12,11,13,5,6,7]→输出：[5,6,7,11,12,13]第5题（10分）——递归与分治综合应用：汉诺塔问题题目：实现汉诺塔问题的递归解法，要求：1.将n个盘子从源柱子（src）移动到目标柱子（dest），辅助柱子（aux）作为中间过渡；2.每次只能移动一个盘子，且大盘子不能放在小盘子上面；3.输出移动步骤（例如："移动盘子1从A到B"）。示例：输入：n=3,src='A',dest='C',aux='B'→输出："移动盘子1从A到C""移动盘子2从A到B""移动盘子1从C到B""移动盘子3从A到C""移动盘子1从B到A""移动盘子2从B到C""移动盘子1从A到C"答案与解析第1题答案与解析答案：pythondeffib(n,memo={}):ifn<=0:return"输入错误"ifninmemo:returnmemo[n]ifn==1orn==2:return1memo[n]=fib(n-1,memo)+fib(n-2,memo)returnmemo[n]解析：1.使用`memo`字典存储已计算的结果，避免重复递归；2.输入校验确保n为正整数；3.递归基为n=1或n=2时返回1，其他情况递归计算。第2题答案与解析答案：pythondefquick_sort(arr,low,high):iflow<high:pivot=arr[high]i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]quick_sort(arr,low,i)quick_sort(arr,i+2,high)returnarr解析：1.选择基准为最后一个元素；2.划分数组，将小于基准的元素移到左侧，大于基准的移到右侧；3.递归对左右子数组排序。第3题答案与解析答案：pythondefbinary_search(nums,target,left,right):ifleft>right:return-1mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]>target:returnbinary_search(nums,target,left,mid-1)else:returnbinary_search(nums,target,mid+1,right)解析：1.递归二分搜索的核心是不断缩小搜索范围；2.终止条件为`left>right`（无解）；3.优化通过直接返回子数组索引，避免不必要的全局遍历。第4题答案与解析答案：pythondefmerge_sort(arr,left,right):ifleft<right:mid=(left+right)//2merge_sort(arr,left,mid)merge_sort(arr,mid+1,right)merge(arr,left,mid,right)returnarrdefmerge(arr,left,mid,right):temp=[]i,j=left,mid+1whilei<=midandj<=right:ifarr[i]<=arr[j]:temp.append(arr[i])i+=1else:temp.append(arr[j])j+=1whilei<=mid:temp.append(arr[i])i+=1whilej<=right:temp.append(arr[j])j+=1arr[left:right+1]=temp解析：1.递归将数组划分为两半并分别排序；2.合并步骤将两个有序子数组合并成更大的有序数组；3.空间复杂度优化通过原地修改数组（需额外临时空间）。第5题答案与解析答案：pythondefhanoi(n,src,dest,aux):ifn==1:print(f"移动盘子1从{src}到{dest}")returnhanoi(n-1,src,aux,dest)print(f"移动盘子{n}从{src}到{dest}")hanoi(n-1,aux,