【c++入门（2）】搜索1

搜索和枚举
谈区别，枚举解决的是你知道有几层循环，才能去一个一个地去列举一种方案，接着进行操作。而在不知道循环层数的情况下，暴力枚举是解决不了问题的，难道写一个：

if(n==1)for()
if(n==2)for()for()
.......
if(n==∞)for()for()for()......

这肯定是b行的，所以搜索是可以考虑的，在有一些题目中需要DP，但是搜索解决的题目不一定DP就能派上用场，然而每一个DP都可以用递归的形式写。

我们这次解决的问题都是方案数一类的问题，就像是一棵树，每一个树杈都会分出几个新的节点(树杈)。接着如果能走到头就算做一种方案，在有些题目中需要去重。
练习T1

题目描述

问题描述

任何一个自然数n，总可以拆分成若干自然数（不包含0）之和。输出可以拆分的方案数。
4有8种划分
输入样例
4
输出样例
8
样例说明

4=1+1+1+1

4=1+1+2

4=1+2+1

4=1+3

4=2+1+1

4=2+2

4=3+1;

4=4;

数据范围

N<=100 

思路，从最开始的节点分出当前的第1个数为1、2、3的3种情况的分支，接着3种情况也同样，直到数被分完，算一种方案。
示意图，假设N=3：
代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
 
using namespace std;
 
int cnt=0;
void doit(int x)
{
    if(x==0){   //全部分完，算一种可行方案
        cnt++;
        return;
    }
    for(int i=1;i<=x;i++)doit(x-i);   //枚举当前这个数可以是几，接着进入下一层doit，一直往后推，直到方案成立 cnt++
    return;
}
 
int main()
{
 
 
    int n;
    cin>>n;
    doit(n);
    cout< 
练习T2
 
题目描述

 N个乒乓球，分成各不相同若干份，求有多少分解方案。

 例如：

5=1+4

5=2+3

共计2种方案。



4=1+3

共计1种方案，因为2+2不合题意。



输入
一个正整数 N。	
输出
一个正整数，表示方案数。	
样例输入

5

样例输出

2

提示
N<=100

 
代码如下：
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
  
using namespace std;
  
int cnt=0;
void doit(int x,int t)
{
    if(x==0){
        cnt++;
        return;
    }
    int i;
    for(i=t+1;i<=x;i++)doit(x-i,i);
    return;
}
  
int main()
{
  
  
    int n;
    cin>>n;
    for(int i=1;i<=n/2;i++)doit(n-i,i);
    cout< 
三 <再看搜索与枚举>
 搜索的时间复杂度和枚举相比谁更优呢？
 一般是搜索，虽然有些水T可以用枚举优化接近搜索。
 搜索是可以达到一遍过的效果，在我们刚才画的图中，没有一个方案是碰钉子的。代码中的if(x==0)不是在判断当前的方案是否合法，其实是在判断是否分完，因为for(int i=1;i<=x;i++)已经注定了搜索到最后的每一种方案都是合法的。
 搜索因为是递归形式所以每一层循环都相当于套在了另一层循环里，虽然感觉搜素和枚举的区别就是在与搜索只不过是把循环的代码省掉了。但是其实不一样的是，搜索正因为它的这种嵌套的形式，所以他才可以回到上一个节点继续搜索答案，而不是重新推。
 
 
dm_n分k