2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 回溯法.doc

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 回溯法如果上期的“百钱买百鸡”中鸡的种类数是变化的，用枚举法就无能为力了，这里介绍另一种算法回溯法。回溯基本思想回溯法是一种既带有系统性又带有跳跃性的搜索法，它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。例1、从N个自然数(1,2,n)中选出r个数的所有组合。算法分析：设这r个数为a1,a2,ar,把它们从大到小排列，则满足：（1） a1a2ar;（2） 其中第i位数(1=ir-i;我们按以上原则先确定第一个数，再逐位生成所有的r个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值按此规则不断循环搜索，直到找出r个数的组合，这种求解方法就是回溯法。如果按以上方法生成了第i位数ai，下一步的的处理为：（1） 若air-i且i=r，则输出这r个数并改变ai的值:ai=ai-1;（2） 若air-i且ir，则继续生成下一位ai+1=ai-1;（3） 若air-1则重复：若air-i，若i=r，则输出解，并且ai:=ai-1;若ir，则继续生成下一位：ai+1:=ai-1; i:=i+1;若 air-i then 符合条件 if i=r then 输出beginfor j:=1 to r do write(aj:3);writeln; ai:=ai-1; endelse 继续搜索begin ai+1:=ai-1; i:=i+1;end else回溯 begin i:=i-1; ai:=ai-1;end; until a1=r-1;end.下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。例2 数的划分（noipxxtg）问题描述 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。输入：n，k (6n=200，2=k=6)输出：一个整数，即不同的分法。样例输入： 7 3输出：4 四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;算法分析：此题可以用回溯法求解，设自然数n拆分为a1,a2,ak,必须满足以下两个条件：（1） n=a1+a2+ak ；（2） a1=a2=ak (避免重复计算)；现假设己求得的拆分数为a1,a2,ai,且都满足以上两个条件,设sum=n-a1-a2-ai,我们根据不同的情形进行处理：（1） 如果i=k,则得到一个解，则计数器t加1，并回溯到上一步，改变ai-1的值；（2） 如果i=ai,则添加下一个元素ai+1；（3） 如果ik且sumai,则说明达不到目标，回溯到上一步，改变ai-1的值；算法实现步骤如下：第一步：输入自然数n,k并初始化；t:=0; i:=1;ai:=1; sum:=n-1; nk:=n div k;第二步：如果a1=ai则继续搜索；若sum=ai then 判断是否回溯begin inc(i);ai:=ai-1;sum:=sum-ai;end继续搜 else begin dec(i); inc(ai); sum:=sum+ai+1-1; end;回溯 end; until a1nk; writeln(t);end.回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在NOIP中有许多涉及搜索问题的题目都可以用回溯法来求解。