Dfs学习经验（纸上运行理解DFS）【两道题】
首先我想吐槽的是，在CSDN上搞了好久还是不能发博客，就是点下发表丝毫反应都没有的，我稍微百度了几次还是没有找到解决方法，在CSDN的BBS上也求助过管理员但是没有收到答复真是烦躁，导致我新生入学以来没能很好的在博客上记录点什么，有些想法只是在脑中灵光一现然后事后就不好想起来了。后来发现了除了CSDN还有ITeye、cnblogs等一些其他优秀的博客网站…。废话不多说了，现在开始吧。
背景：在大一上学期的第六次C语言课后练习中碰到了这样一题
放苹果（POJ1664）
题目描述
把M个同样的苹果放在N个同样的盘子里，允许有盘子空，问共有多少种不同分法
注意：5,1,1和1,5,1是同一种。
输入
第一行是测试数据数目t（0~20），以下t行均包含两个整数M,N，空格分开。
1<=M,N<=10;
输出
对每行数据，输出相应的k。
样例输入
1
7 3
样例输出
8
审题思考：
在经过小范围数据的纸上运行后，发现了这么一个规律：
0 0 0
0 0 7 OK
0 1 1
0 1 6 OK
0 2 2
0 2 5 OK
0 3 3
0 3 4 OK
0 4 4
0 5 5
0 6 6
0 7 7
1 1 1
1 1 5 OK
……
于是，按照这个规律，我试着这么写：
当M=7,N=3的时候：
1 if(N==3)
2 {
3 for(i=0;i<M;i++)
4 {
5 for(j=i;j<M;j++)
6 {
7 for(k=j;k<=M;k++)
8 {
9 if((i+j+k)==M)
10 {
11 ti++;
12 break;
13 }
14 }
15 }
16 }
17 printf("%d\n",ti);
18 }
同理，N在1-10这10个数中，都可以利用此种多重FOR循环嵌套进行搜索判断
按照这种规律，我完整的写了一遍这题，但是发现提交上去WA
以下是我完整的代码：
#include<stdio.h>
int main()
{
int n,i,j,k,M,N,ti,i4,i5,i6,i7,i8,i9,i10;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
ti=;
scanf("%d%d",&M,&N);
if(N==)
printf("1\n");
if(N==)
{
for(j=;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((j+k)==M)
{
ti++;
break;
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i=;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i+j+k)==M)
{
ti++;
break;
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i4=;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i5=;i5<M;i5++)
{
for(i4=i5;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i5+i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i6=;i6<M;i6++)
{
for(i5=i6;i5<M;i5++)
{
for(i4=i5;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i6+i5+i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i7=;i7<M;i7++)
{
for(i6=;i6<M;i6++)
{
for(i5=i6;i5<M;i5++)
{
for(i4=i5;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i7+i6+i5+i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i8=;i8<M;i8++)
{
for(i7=;i7<M;i7++)
{
for(i6=;i6<M;i6++)
{
for(i5=i6;i5<M;i5++)
{
for(i4=i5;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i8+i7+i6+i5+i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i9=;i9<M;i9++)
{
for(i8=;i8<M;i8++)
{
for(i7=;i7<M;i7++)
{
for(i6=;i6<M;i6++)
{
for(i5=i6;i5<M;i5++)
{
for(i4=i5;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i9+i8+i7+i6+i5+i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
}
}
}
}
}
printf("%d\n",ti);
}
if(N==)
{
for(i10=;i10<M;i10++)
{
for(i9=;i9<M;i9++)
{
for(i8=;i8<M;i8++)
{
for(i7=;i7<M;i7++)
{
for(i6=;i6<M;i6++)
{
for(i5=i6;i5<M;i5++)
{
for(i4=i5;i4<M;i4++)
{
for(i=i4;i<M;i++)
{
for(j=i;j<M;j++)
{
for(k=j;k<=M;k++)
{
if((i10+i9+i8+i7+i6+i5+i4+i+j+k)==M)
{
ti++;
break;
}
}
}
}
}
}
}
}
}
}
}
printf("%d\n",ti);
}
}
}
return ;
}
但是对于用这种方法解决这题我并不是很满意，虽然不知道为什么WA了。
在查阅了相关资料后发现可以利用DFS的方式
这里有一段关于解决这题的DFS相关函数：
//代码来西电ACMPPT
void dfs(long k, long w) //初始k=1,w=0; k表示现在已用几个盘子,w表示已经放了几个苹果
{
long i,u;
if (k==m) //当最后一个盘子被放置苹果的时候我们进行判断
{
if (n-w>=s[k-])
{
s[k]=n-w;
z=z+;
}
return;
}
for (i=;i<=n;i++)
if (i>=s[k-]) //如果当前放置的苹果个数大于前一个盘子继续放置
{
w=w+i;
s[k]=i; k=k+;
dfs(k,w);
w=w-i;
k=k-;
}
}
当初看到这段简短的代码，我只是一眼看出了这是与递归相关的函数
花了一段时间纸上运行后（在纸上写出详细步骤）
大致写出我的纸上运行内容：
以实例输入为5个苹果，3个盘子
Start: k=1,w=0
第一次进入DFS函数
W=0,s[1]=0,k=2;
第二次进入DFS函数
W=0,s[2]=0,k=3;
第三次进入DFS函数
S[3]=5,z=z+1;
退出第三次进入的DFS函数，返回第二次进入的DFS函数
I=1,w=1,s[2]=1,k=3
第三次进入DFS函数
S[3]=4,z=z+1;
退出第三次进入的DFS函数，返回第二次进入的DFS函数
W=0,k=2;
I=2,w=1,s[2]=2,k=3;
第三次进入DFS函数
S[3]=3,z=z+1
退出第三次进入的DFS函数，返回第二次进入的DFS函数
！暂停
在此，我们已经得到三组答案数据，即 0 0 5、 0 1 4和 0 2 3
并且得到Z=3；
那么按照这个规律，我们可以得出一共会有七组答案数据：
0 0 7
0 1 6
0 2 5
0 3 4
1 1 5
1 2 4
1 3 3
2 2 3
在此，我们已经可以利用DFS的方法解决这道题目，当然
这样解决的效率并不是很高，所有需要剪枝
优化的代码为：
//代码来自西电ACMPPT
void dfs(long k, long w)
{
long i,u;
if (k==m)
{
if (n-w>=s[k-])
{
s[k]=n-w;
z=z+;
}
return;
}
for (i=;i<=n;i++)
if ((i>=s[k-])&&((n-w)/(m-k)>=s[k-])) //优化剪枝部分
{
w=w+i;
s[k]=i;
k=k+;
dfs(k,w);
w=w-i;
k=k-;
}
}
到此为止，本题结束，但是我还想再提一题：
问题 C: 伯努利装错信封问题-综合[难]
时间限制: 30 Sec 内存限制: 128 MB
提交: 417 解决: 199
[提交][状态][讨论版]
题目描述
某人写了n封信，同时为每一封信写1个信封，共n个信封。如果把所有的信都装错了信封，问共有多少种？（这是组合数学中有名的错位问题。著名数学家伯努利(Bernoulli)曾最先考虑此题。后来，欧拉对此题产生了兴趣，称此题是“组合理论的一个妙题”，独立地解出了此题）
试编程求出完全装错情形的所有方式及其总量s。例如，输入n=3，即有3封信需要装入信封，完全装错的一种方式可以表示为312，表示第1封信装入第3个信封，第2封信装入第1个信封，第3封信装入第2个信封。对于n=3，完全装错的方式共有2种，分别是312和231.
输入
输入一个正整数n(2<=n<=6)
输出
输出完全装错情形的所有方式以及装错方式的总量s (每行输出5种方式，一行中的相邻两种方式之间用1个空格隔开。装错方式输出时，从小到大排列，见输出样例)。
样例输入
4
样例输出
2143 2341 2413 3142 3412
3421 4123 4312 4321
s=9
审题思考：
解决这道题目可以利用DFS。
的回答后，我对代码进行了适当解释和修改，以下是完整代码：
//代码改编自百度知道
#include<stdio.h>
#include<stdlib.h>
int printed,ti=;
void draw(int* a,int k)//输出函数
{
int i;
for(i=;i<k;i++)
printf("%d",a[i]);
printf(" ");
if(ti!=)
ti++;
if(ti==)
{
printf("\n");
ti=;
}
}
void Settle(int *a,int iStep,int k)//函数调用值为：a,0,k
{
int i;
for(i=;i<iStep-;i++)
if(a[iStep-]==a[i]) return;//判断序号为（iStep-1)的信是否同序号为i的信放入同一个信箱，否则将函数返回
if(iStep==k)
{
draw(a,k);
printed++;
}
for(i=;i<=k;i++)
{
if(i==iStep+) continue;//判断序号i信是否放到的是i信封，是则继续下一步
a[iStep]=i;
Settle(a,iStep+,k);
}
}
int main()
{
int* a;
int k;
scanf("%d",&k);
a=(int*)calloc(k,sizeof(int));//在内存的动态存储区中分配k个长度为int大小的连续空间
Settle(a,,k);
printf("\ns=%d",printed);
return ;
}
a=(int*)calloc(k,sizeof(int));//在内存的动态存储区中分配k个长度为int大小的连续空间
/*
它的意思是a为一块长度为k*sizeof(int) = 4k的内存块，可以存储k个int型变量，这个内存块就相当于一个int数组
也就是等价于
int a[k]; // 注意：此时a的内存在堆栈（Stack）上面
不同的是，你所询问的这句，申请的这块内存区域是动态申请的，属于堆（heap）上面的空间。 calloc是一个C语言函数
函数名: calloc
void *calloc(unsigned n,unsigned size)；
功 能: 在内存的动态存储区中分配n个长度为size的连续空间，函数返回一个指向分配起始地址的指针；如果分配不成功，返回NULL。
跟malloc的区别：
calloc在动态分配完内存后，自动初始化该内存空间为零，而malloc不初始化，里边数据是随机的垃圾数据。
用 法: void *calloc(unsigned n,unsigned size)；
头文件：stdlib.h或malloc.h
*/
为了解读这串代码我同样在纸上运行了一小段数据帮助理解
以下是我在纸上运行的过程：
以输入N=4 为例
第一次调用settle函数
a : 空 空 空 空 , istep=0,k=4;
i=1,i=2,a[0]=2;
第二次调用settle函数
a : 2 空 空 空 , istep=1,k=4;
i=1,a[1]=1
第三次调用settle函数
a : 2 1 空 空 , istep=2,k=4;
i=1,a[2]=1;
第四次调用settle函数
a : 2 1 1 空 , istep=3,k=4;
i=0,i=1,a[1]=a[2]
函数返回
第三次调用settle函数
a : 2 1 空 空 , istep=2,k=4;
i=2,a[2]=2
第四次调用settle函数
a : 2 1 2 空 , istep=3,k=4;
i=0,a[2]=a[0]
函数返回
第三次调用settle函数
a : 2 1 空 空 , istep=0,k=4;
………(省略数步骤)
第五次调用settle函数
a : 2 1 4 3 , istep=4,k=4;
输出2143
经过这样的纸上运行后，发现DFS在编写程序上以递归的形式，可以通过简短的代码解题
但是面临的问题是：
1、 代码难写，不好控制终止等条件
2、 执行效率低（目前我对剪枝的原理还不是很懂）
总结：
相比于我曾经完全利用的多重FOR循环嵌套语句，DFS递归的方式更体现出了程序的严密和递归的好处
最新文章
- slf4j的简单介绍
- uva10375 Choose and Divide(唯一分解定理）
- 将Java应用程序打包成可执行的Jar包
- Linux 下子线程 exit code 在主线程中的使用
- linux下创建管理员组&nbsp;使用&nbsp;su&nbsp;-&nbsp;命令
- 深入NGINX：我们如何设计它的性能和扩展性
- Commons JXPath - Modifying Object Graphs
- OK335xS tmp75 Qt 温度读取
- 简单的背包问题（入门）HDU2602 HDU2546 HDU1864
- java String 去除空格
- 初次使用cocoapods注意事项
- Caused by: java.lang.ClassNotFoundException: com.mchange.v2.c3p0.ComboPooledDataSource
- Ext JS学习第十天 Ext基础之动态加载JS文件（补充）
- Hibernate主键生成方式之hilo
- LVS-DR实现web调度模式
- [Python] 文科生零基础学编程系列三——数据运算符的基本类别
- 剑指Offer_12_矩阵中的路径(参考问题:马踏棋盘)
- VS2010+OpenCV3.4.1+zbar 64位
- Vue在MVC中的进行前后端的交互
- fillder---工具栏隐藏/显示