7.29 黄昏时刻
(一) 全排列
建模：
给了数字n 代表从1-n 个数全排列
思路：
1. 输入n，如果n值为‘0’，则退出程序
2. vis[i] 保存 是否对第i个数字进行访问
3. dfs 遍历1-n 个数字的全排列，若重复访问，则越过。直到最终访问结束输出访问的的结果。之后回溯删掉对数字的访问。
优化：
none
代码：
#include <stdio.h>
#include <string.h> int a[] ,n, vis[]; void dfs(int s) {
int i;
//如果dfs 次数为n,则输出a数组的内容
if(s == n) {
for(i = ; i < n; i++)
printf("%-5d", a[i]); // -5 是格式化输出左对齐
printf("\n");
return;
}
//遍历 1- n 如果访问过则继续循环呗
for(i = ; i <= n; i++) { if(vis[i]) continue;
vis[i] = ; //标记节点被访问过
a[s] = i; //在a 数组存取全排列的数字
dfs(s+); //深搜
vis[i] = ; //回溯操作，删掉节点访问痕迹
}
} int main() {
while() {
scanf("%d", &n);
if(!n) break;
memset(vis, , sizeof(vis));
dfs();
}
return ;
}
(二)全组合
建模：
给了数值n 对n 进行组合，并打印出。
思路：
1.输入n , 如果n不存在 返回。
2.dfs 找出n个数字的组合，用‘0’,‘1’标记法判断一个数字是否存在，并且对存在或者不存在依次进行递归。
3.若dfs次数>n，则输出组合的结果。
代码：
#include <stdio.h>
int n, a[];
void dfs(int s) {
int i;
//输出排列后的结果
if(s > n) {
for(i = ; i <= n; i++) {
if(a[i])
printf("%-5d ", i);
}
return;
}
//对a[s]的存在亦或是不存在的两种情况进行递归。
a[s] = ;
dfs(s+);
a[s] = ;
dfs(s+);
}
int main() {
while() {
scanf("%d", &n);
if(!n) break;
dfs();
}
return ;
}
(D89) The settlers of catan
建模：
已知n 个点，m 条边，输入两个点来构成一条边，构成一副无向图，两点之间可以有多条边，从任意一个点搜索，要求每条边只能经过一次，找到最长的路径。
思路：
1.输入点的个数n, 边的个数m，并且初始化存整个无向图的二维数组w
2.存边进入二维数组W
3.对所有点进行dfs搜索，如果路径最长则更新max
4.dfs找出所有存在的边，并且记录路径的长度
代码：
#include <stdio.h>
#include <string.h>
#define N 26 int w[N][N],max,n; //w[N][N] 存入整个图，w[i][j]=x 代表i到j有x条边 void dfs(int,int); int main()
{
int m,sum;
int a,b,i;
while()
{
scanf("%d%d",&n,&m);
if(!m && !n)
break; memset(w,,sizeof(w)); //初始化 for(i=;i<m;i++)
{
scanf("%d%d",&a,&b);
w[a][b]++; //无向图
w[b][a]++;
} max=;
for(i=;i<n;i++)
{
sum=; //把每个点作为出发点，对每一个点进行搜索
dfs(i,sum);
}
printf("%d\n",max);
}
return ;
} void dfs(int a,int sum) // a 为当前探索到哪一个节点，sum为当前探索到的路径长度
{
int i;
if(sum>max) //更新当前搜索到的最长路径
max=sum;
for(i=;i<n;i++)
{
if(w[a][i])
{
w[a][i]--; w[i][a]--; //用去一条边
dfs(i,sum+); // 进行下一层递归
w[a][i]++; w[i][a]++; //回溯到上一层 }
}
return;
}
(A38) A long stick
建模：
给了n个棍子的长度， 和b的值
找出一些棍子链接起来得到长度length， length >= b, length尽量接近b
思路：
1. min为结果， 初始化为所有棍子的长度和。
2. dfs找出这堆棍子的组合， 判断每一种组合所得到的长度sum， sum与min相比， 如果sum比min更优， 更新min为sum
优化：
1. 剪枝
a) 在当前搜索到的状态下， 假设剩下的棍子全部装完， 得到的结果 < b， 则可以剪枝.
b) 当搜索到的sum >= b时， 判断sum 与 min， 然后剪枝
2. 排序, 将棍子长度逆序排序， 在搜索的过程中， sum的增长速度会更快， 也可以提高剪枝效率。
未优化的代码：
#include <stdio.h> int n, b;
int len[];
int min; void dfs(int ,int); int main() {
int t, i;
scanf("%d", &t);//输入t次后结束
while(t--) { scanf("%d%d", &n, &b);//n为小棍子数目，b为拼接后的长度最接近的值
min = ;//拼接后趋近的结果
for(i = ; i < n; i++) {//输入n组小棍子长度
scanf("%d", &len[i]);
min += len[i];
} dfs(,);//递归求最接近b长度的若干根棍子合起来的长度值
printf("%d\n", min);//输出结果
} return ;
} void dfs(int sum, int i) { if(min == b) //假如拼接后的长度min 刚好为b 则返回
return;
if(sum >= b) {//如果棍子拼接的长度刚好>=b 如果比之前拼接的长度更接近于b，就更新min
if(sum < min)
min = sum;
return;
}
if(i == n) return;//避免死递归判断假如存在n的情况
dfs(sum+len[i], i+);//如果存在第i根棍子，往下搜索求和
dfs(sum, i+);//假设不存在第i根棍子，继续搜索求和
}
剪枝后的优化：
#include <stdio.h>
#include <string.h> int n, b;
int len[], s[];
int min; void dfs(int sum, int i); int main() {
int t, i;
scanf("%d", &t);
while(t--) { scanf("%d%d", &n, &b);
min = ;
memset(s, , sizeof(s));
for(i = ; i < n; i++) {
scanf("%d", &len[i]);
min += len[i];
}
for(i = n-; i > -; i--) //记录最后一根棍子 to 第i根棍子 的总长度
s[i] = s[i+] + len[i]; dfs(,);
printf("%d\n", min);
}
return ;
} void dfs(int sum, int i) {
if(min == b)
return;
if(sum >= b) {
if(sum < min)
min = sum;
return;
}
if(i == n) return;
if(sum+len[i]+s[i+] >= b ) //剪枝
dfs(sum+len[i], i+);
if(sum+s[i+] >= b) //剪枝
dfs(sum, i+); }
剪枝排序后的优化：
#include <stdio.h>
#include <string.h>
#include <stdlib.h> int n, b;
int len[], s[];
int min; void dfs(int sum, int i); int cmp(const void *a,const void *b)
{
return *(int *)b-*(int*)a;
} int main() {
int t, i;
scanf("%d", &t);
while(t--) { scanf("%d%d", &n, &b);
min = ;
memset(s, , sizeof(s));
for(i = ; i < n; i++) {
scanf("%d", &len[i]);
min += len[i];
} qsort(len,n,sizeof(len[]),cmp); for(i = n-; i > -; i--) //记录最后一根棍子 to 第i根棍子 的总长度
s[i] = s[i+] + len[i]; dfs(,);
printf("%d\n", min);
}
return ;
} void dfs(int sum, int i) {
if(min == b)
return;
if(sum >= b) {
if(sum < min)
min = sum;
return;
}
if(i == n) return;
if(sum+len[i]+s[i+] >= b ) //剪枝
dfs(sum+len[i], i+);
if(sum+s[i+] >= b) //剪枝
dfs(sum, i+); }
DFS 题目 用到的DFS函数:
// The Settlers of Catan V1 void dfs(int a,int sum)
{
int i;
if(sum>max) max=sum;
for(i=;i<n;i++) if(w[a][i]){
w[a][i]--; w[i][a]--;
dfs(i,sum+);
w[a][i]++; w[i][a]++;
} return;
}
// The Settlers of Catan V2
void dfs(int u, int num){
int flag;
for(int v=; v<n; ++v){
if(G[u][v] && !vis[u][v]){
if(G[u][v] != ){
flag = ;
vis[u][v] = ;
vis[u][v] = ;
G[u][v] --;
G[v][u] --;
}
else {
vis[u][v] = ;
vis[v][u] = ;
}
dfs(v, num+);
if(flag == ){
G[u][v]++;
G[v][u]++;
}
flag = ;
vis[u][v] = vis[v][u] = ;
}
}
if(num > maxNum) maxNum = num;
}
// A long stick void dfs(int sum,int i)
{
int j;
sum-=stick[i];
if(sum<length || min==length)
return; if(sum<min)
min=sum; for(j=i+;j<=n;j++)
dfs(sum,j);
}
// repeatless V1 void dfs(int dep)
{
int i;
if (dep==)
{
int tmp=d[];
for (i=;i<=;i++) tmp=tmp*+d[i];
T++;
f[T]=tmp;
return;
}
if (T>) return;
for (i=;i<=;i++)
if (s[i]==)
{
d[dep+]=i;
sum+=i;
if (sum) s[i]++;
dfs(dep+);
if (sum) s[i]--;
sum-=i;
}
}
// repeatless V2 author : ZSX void recursion( int k )
{
if( bl == )
return ;
int i, j;
int a, b;
if( p == k )
{
int sum = ;
int temp;
for( i=; i<p; i++ )
{
temp = ;
for( j=; j<p-i-; j++ )
temp *= ;
sum += temp*buffer[i];
}
if( q <= )
array[q++] = sum;
else
bl = ;
}
else
{
for( a=; a<=; a++ )
if( flag[a] == && (p != || a!=) )
{
flag[a] = ;
buffer[p++] = a;
recursion( k );
flag[a] = ;
p--;
}
}
}
// 全排列
void dfs(int s, int n) {
int i;
if(s == n) {
for(i = ; i < n; i++)
if(i==) printf("%d", a[i]);
else printf(" %d", a[i]);
printf("\n");
return;
}
for(i = ; i <= n; i++) {
if(vis[i]) continue;
a[s] = i;
vis[i] = ;
dfs(s+, n);
vis[i] = ;
}
}