前面教程汇总

第一讲

算法入门教程（一、模拟）

第二讲

算法入门教程（二、枚举）

第三讲

算法入门教程（三、递推与递归）

第四讲

算法入门教程（四、分治）

第五讲

算法入门教程（五、贪心）

试探

试探法也叫回溯法，试探法的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。

如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

试探法算法基础

使用试探算法解题的基本步骤如下所示。

1. 针对所给问题，定义问题的解空间。
2. 确定易于搜索的解空间结构。
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

试探法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。

例题与解

例题1：P2089 烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克，任意烤鸡的美味程度为所有配料质量之和。

现在，Hanke 想要知道，如果给你一个美味程度 $n$ ，请输出这 $10$ 种配料的所有搭配方案。

输入格式

一个正整数 $n$，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束，$10$ 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 $0$。

样例 #1

样例输入 #1

11

样例输出 #1

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

提示

对于 $100\%$ 的数据，$n\le 5000$。

C++解（暴力枚举）

#include<iostream>  
using namespace std;  
int main()  
{  
    int a,b,c,d,e,f,g,h,i,j,in,x=0;  
    cin>>in;  
    for (a=1;a<=3;a++)  
    {  
        for (b=1;b<=3;b++)  
        {  
            for (c=1;c<=3;c++)  
            {  
                for (d=1;d<=3;d++)  
                {  
                    for (e=1;e<=3;e++)  
                    {  
                        for (f=1;f<=3;f++)  
                        {  
                            for (g=1;g<=3;g++)  
                            {  
                                for(h=1;h<=3;h++)  
                                {  
                                    for (i=1;i<=3;i++)  
                                    {  
                                        for (j=1;j<=3;j++)  
                                        {  
                                            if (a+b+c+d+e+f+g+h+i+j==in)  
                                            {  
                                                x++;  
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
    cout<<x<<endl;  
    for (a=1;a<=3;a++)  
    {  
        for (b=1;b<=3;b++)  
        {  
            for (c=1;c<=3;c++)  
            {  
                for (d=1;d<=3;d++)  
                {  
                    for (e=1;e<=3;e++)  
                    {  
                        for (f=1;f<=3;f++)  
                        {  
                            for (g=1;g<=3;g++)  
                            {  
                                for(h=1;h<=3;h++)  
                                {  
                                    for (i=1;i<=3;i++)  
                                    {  
                                        for (j=1;j<=3;j++)  
                                        {  
                                            if (a+b+c+d+e+f+g+h+i+j==in)  
                                            {  
                                                cout<<a<<" ";  
                                                cout<<b<<" ";  
                                                cout<<c<<" ";  
                                                cout<<d<<" ";  
                                                cout<<e<<" ";  
                                                cout<<f<<" ";  
                                                cout<<g<<" ";  
                                                cout<<h<<" ";  
                                                cout<<i<<" ";  
                                                cout<<j<<endl;  
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
}  

C++解（递归）

#include<iostream>
using namespace std;
int n,kind=0,m1[10000][10],m2[10];
void peiliao(int total,int a){
    if (a==10){
        if (total==n) {
            for (int j=0;j<10;j++) m1[kind][j]=m2[j];
            kind++;
        }
    }
    else if (total>=n); //小小优化一下 
    else
      for (int i=1;i<=3;i++){
          m2[a]=i;
          peiliao(total+i,a+1);
      }
}
int main(){
    cin>>n;
    peiliao(0,0);
    cout<<kind<<endl;
    for (int j=0;j<kind;j++){
      for (int i=0;i<10;i++) cout<<m1[j][i]<<" ";
     cout<<endl; 
    }
    return 0;
}

C++解（回溯）

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans1,ans2[10001][11],sum,a[11];
void trys(int t,int m)//t代表当前的尝试的调料。m代表当前美味程度
{
    if (t>10) 
    {
        if (m==n) //如果美味程度与猪猪的要求相等 
        {
            ans1++;//统计方案总数 
            for (int i=1;i<=10;i++)
            ans2[ans1][i]=a[i];//存入答案的数组 
        }
        return ;
    }
    for (int i=1;i<=3;i++)
    {
        if (m+i>n) break;//如果超过了要求，那么后面的就可以直接忽略 
        a[t]=i;//储存答案 
        trys(t+1,m+i);//查看下一种调料 
        a[t]=0;//状态恢复 
    }
}
int main()
{
    cin>>n;
    trys(1,0);//从第一种调料开始尝试，美味程度为0 
    cout<<ans1<<endl;
    for (int i=1;i<=ans1;i++)
    {
        for (int j=1;j<=10;j++)
            cout<<ans2[i][j]<<" ";
        cout<<endl;
    }//输出结果 
    return 0;
} 

C++解（深搜 + 剪枝）

#include<iostream>
#include<cstring> 
using namespace std;
int n;
int ans=0,a[11],b[50000][11];
void init()
{
    scanf("%d",&n);
    memset(a,0,sizeof(a));
}
void search(int dep,int fsum)
{
    if(dep>10)
    {  
        int num=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10];
        if(num==n)
        {
            ans++;
            for(int i=1;i<=10;i++)
               b[ans][i]=a[i];
        }
        return;
    }
    for(int i=1;i<=3;i++)
    {
        if(fsum+i>n) break;
        a[dep]=i;
        search(dep+1,fsum+i);
        a[dep]=0;
    }    
}
int main()
{  
   init();
   search(1,0);
   cout<<ans<<"\n";
   for(int i=1;i<=ans;i++)
      {
            for(int j=1;j<=10;j++)
              cout<<b[i][j]<<" ";
             cout<<"\n";
      }
    return 0;
}

Pascal解

type data=array [1..10] of longint;
var
 n,i,j:longint;
 ans:array [0..10000] of data;
 t:data;

procedure search(d:longint;a:data);//a储存当前配料情况
var
 sum,i:longint;
begin
 if d=10 then
  begin
   sum:=0;
   for i:=1 to 10 do inc(sum,a[i]);//统计配料质量之和
   if sum=n then
    begin
     inc(ans[0,1]);
     ans[ans[0,1]]:=a;
    end;
   exit;
  end;
 a[d+1]:=1;
 search(d+1,a);
 a[d+1]:=2;
 search(d+1,a);
 a[d+1]:=3;
 search(d+1,a);
end;

begin
 read(n);
 search(0,t);
 writeln(ans[0,1]);
 for i:=1 to ans[0,1] do
 begin
  for j:=1 to 10 do write(ans[i,j],' ');
  writeln;
 end;
end.

例题2：P1036 [NOIP2002 普及组] 选数

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots ,x_n$，以及 $1$ 个整数 $k$（$k<n$）。从 $n$ 个整数中任选 $k$ 个整数相加，可分别得到一系列的和。例如当 $n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$（$1\le n\le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots ,x_n$（$1\le x_i\le 5\times 10^6$）。

输出格式

输出一个整数，表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

提示

【题目来源】

NOIP 2002 普及组第二题

C++解

#include<iostream>
#include<cmath>
using namespace std;
int x[20],n,k;//依照题目所设
bool isprime(int n){//判断是否质数
    int s=sqrt(double(n));
    for(int i=2;i<=s;i++){
        if(n%i==0)return false;
    }
    return true;
}
int rule(int choose_left_num,int already_sum,int start,int end){
//choose_left_num为剩余的k，already_sum为前面累加的和，start和end为全组合剩下数字的选取范围；调用递归生成全组合，在过程中逐渐把K个数相加，当选取的数个数为0时，直接返回前面的累加和是否为质数即可
    if(choose_left_num==0)return isprime(already_sum);
    int sum=0;
    for(int i=start;i<=end;i++){
        sum+=rule(choose_left_num-1,already_sum+x[i],i+1,end);
    }
    return sum;
}
int main(){
    cin>>n>>k;
    for(int i =0;i<n;i++)cin>>x[i];
    cout<<rule(k,0,0,n-1);//调用递归解决问题
}

Pascal解

var n,k,i,j,s,sum:longint;  
    a:array [1..20] of longint;  
    b:array [1..20] of boolean;  
    c:array [1..200] of longint;   
function pd(ss:longint):boolean;  //判断是否为质数
var i:longint;  
    f:boolean;  
begin  
    pd:=true;  
    for i:=2 to trunc(sqrt(s)) do  
    if ss mod i=0 then pd:=false;  
end;  
procedure try(t,x:longint);  //深搜部分
var i,j,l:longint;  
    f:boolean;  
begin  
    for i:=x+1 to n do  
    if b[i] then  
    begin  
        b[i]:=false;  
        inc(s,a[i]);  
        if (t=k) then  
        begin  
            if (pd(s))then inc(sum);  
        end else  try(t+1,i);  
        b[i]:=true;  
        dec(s,a[i]);  
    end;  
end;  
begin  
    read(n,k);  
    sum:=0;  
    for i:=1 to n do  
    read(a[i]);   
    fillchar(b,sizeof(b),true);  
    fillchar(c,sizeof(c),0);  
    try(1,0);  
    write(sum);  
end.  

Python解

#加载包,numpy用于简化计算，combination用于组合
#numpy需要单独安装：pip3 install numpy
import numpy as np
from itertools import combinations
#输入和定义变量
nums_len,sum_nums = map(int,input().split())
nums = list(map(int,input().split()))
count = 0
array_sum = 0
#定义一个筛选素数的函数,时间复杂度为√n/3
def prime_number(number):
    if number <=3:
        return True
    elif number % 2 == 0 or number % 3 ==0:
        return False
    else:
        i = 5
        while i * i <= number:
            if number % i  == 0 or number % (i+2) == 0:
                return False
            i += 6
    return True
#遍历所有组合
for tem_combin in combinations(nums,sum_nums):
    #将组合转化为数组
    array = np.array(tem_combin)
    #数组求和
    array_sum = array.sum()
    #如果为素数，就计数
    if prime_number(array_sum):
        count += 1
print(count)

本文完。关于试探（回溯）算法的题还有很多，可以在洛谷上刷。本文由于代码有一些已经加了注释，所以就不在文章里说明了，如果不懂，欢迎在评论区留言。