信息学奥赛中的基本算法(回溯法)如果上期的“百钱买百鸡”中鸡的种类数是变化的,用枚举法就无能为力了,这里介绍另一种算法——回溯法。回溯基本思想回溯法是一种既带有系统性又带有跳跃性的搜索法,它的基本思想是:在搜索过程中,当探索到某一步时,发现原先的选择达不到目标,就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的,而每个步骤都有若干种可能的分支,为了完成这一过程,需要遵守某些规则,但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。例1、从N个自然数(1,2,…,n)中选出r个数的所有组合。算法分析:设这r个数为a1,a2,…ar,把它们从大到小排列,则满足:(1)a1>a2>…>ar;(2)其中第i位数(1<=i<=r)满足ai>r-i;我们按以上原则先确定第一个数,再逐位生成所有的r个数,如果当前数符合要求,则添加下一个数;否则返回到上一个数,改变上一个数的值再判断是否符合要求,如果符合要求,则继续添加下一个数,否则返回到上一个数,改变上一个数的值……按此规则不断循环搜索,直到找出r个数的组合,这种求解方法就是回溯法。如果按以上方法生成了第i位数ai,下一步的的处理为:(1)若ai>r-i且i=r,则输出这r个数并改变ai的值:ai=ai-1;(2)若ai>r-i且i≠r,则继续生成下一位ai+1=ai-1;(3)若ai<=r-i,则回溯到上一位,改变上一位数的值:ai-1=ai-1-1;算法实现步骤:第一步:输入n,r的值,并初始化;i:=1;a[1]:=n;第二步:若a[1]>r-1则重复:若a[i]>r-i,①若i=r,则输出解,并且a[i]:=a[i]-1;②若i<>r,则继续生成下一位:a[i+1]:=a[i]-1;i:=i+1;若a[i]<=r-i,则回溯:i:=i-1;a[i]:=a[i]-1;第三步:结束;程序实现varn,r,i,j:integer;a:array[1..10]ofinteger;beginreadln(n,r);i:=1;a[1]:=n;repeatifa[i]>r-ithen{符合条件}ifi=rthen{输出}beginforj:=1tordowrite(a[j]:3);writeln;a[i]:=a[i]-1;endelse{继续搜索}begina[i+1]:=a[i]-1;i:=i+1;endelse{回溯}begini:=i-1;a[i]:=a[i]-1;end;untila[1]=r-1;end.下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。例2数的划分(noip2001tg)问题描述整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。1,1,5;1,5,1;5,1,1;问有多少种不同的分法。输入:n,k(6
=ai,则添加下一个元素ai+1;(3)如果i=a[i]则继续搜索;②若sum=a[i]then{判断是否回溯}begininc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜}elsebegindec(i);inc(a[i]);sum:=sum+a[i+1]-1;end;{回溯}end;untila[1]>nk;writeln(t);end.回溯法是通过尝试和纠正错误来寻找答案,是一种通用解题法,在NOIP中有许多涉及搜索问题的题目都可以用回溯法来求解。