本文目录一览：
- 1、求大神给这个程序做个详细的注释 C语言 回溯法 任务分配问题
- 2、C语言中回溯法的问题
- 3、求C语言中的回溯法，举一个简单的小例子，说明回溯法的运行过程！
- 4、回溯算法，用c语言实现
- 5、求助，用C语言并用回溯算法编写的有关蛇吃苹果走迷宫的程序，题目如下：
求大神给这个程序做个详细的注释 C语言 回溯法 任务分配问题
这个题目分解一下，就是将n个数据排列组合，数学算法可以得到种数为A(n,n)=n!
然后在这n!种可能种找到花费最少的那一种就行了。
以下是我写的程序，验证了一下，好像没有什么问题，你看看。
#include stdio.h
int best,last;
int b[20],c[20],d[20],a[20][20];
void get_best(int n)
{
int j,k;
last = 0;
for(j=0;jn;j++)
last += a[j][c[j]];
if(best == 0)
{
best = last;
for(k=0; kn; k++)
d[k] = c[k];
}
else
{
if(last best)
{
best = last;
for(k=0; kn; k++)
d[k] = c[k];
}
}
}
void f(int n,int count)
{
int i,t,j;
if(n == 1)
{
c[count] = b[0];
get_best(count+1);
}
else
{
for(i=0; in; i++)
{
t = b[i];
b[i] = b[n-1];
b[n-1] = t;
c[count] = t;
f(n-1,count+1);
t = b[i];
b[i] = b[n-1];
b[n-1] = t;
}
}
}
int main()
{
int i,j;
int n;
printf("请输入作业数：");
scanf("%d",n);
printf("作业分配给不同工人所需费用:\n");
for(i=0;in;i++)
{
b[i] = i;
c[i] = -1;
d[i] = -1;
for(j=0;jn;j++)
scanf("%d",a[i][j]);
}
best = last = 0;
f(n,0);
printf("最小总费用为：%d\n", best);
for(i=0;in;i++)
{
printf("第%d人分：",i+1);
printf("第%d工作. ", d[i]+1);
printf("金钱为：%d\n",a[i][d[i]]);
}
puts("\n");
return 0;
}
C语言中回溯法的问题
不能删的，你不会出错可能是编译器的问题，要不你重新写一次把a[--i]++删掉试下。它最后是输出几个后进入死循环。
else的功能是当if条件不符合时（即r个a[]无法再排下去，一般是a[r-1]=m,a[r-2]=m-1……）
比如m=10,r=3
当输出1 2 10时，它接下来输出的是1 3 4，即a[1]从2到3就是else的a[--i]++（即a[--2]++）执行的。
当最后时输出：8 9 10执行两次a[--i]++(a[--2]++,a[--1]++)这样i=0实现断开while(1)这是很重要的。
求C语言中的回溯法，举一个简单的小例子，说明回溯法的运行过程！
求子串位置
int Index(SString S, SString T, int pos) {
// 返回子串T在主串S中第pos个字符之后的位置。
// 若不存在，则函数值为0。
// 其中，T非空，1≤pos≤StrLength(S)。
int i = pos;
int j = 1;
while (i = S[0] j = T[0]) {
if (S[i] == T[j]) { // 继续比较后继字符
++i;
++j;
} else { // 指针后退重新开始匹配
i = i-j+2;
j = 1;
}
}
if (j T[0]) return i-T[0];
else return 0;
} // Index
回溯算法，用c语言实现
这个算法应该不难，基本和全排列的算法类似，只不过判断条件不是n=1， 而是在判断已经取得的数的和=M为终止条件。
具体的算法，我给个大概流程吧
int lst[N]; //保存选取的数
int index = 0; //lst中最后的一个数的位置
func(W, N)
{
if(N == 0) //遍历完毕 返回
return;
for(i=0 to N)
{
if( W[i][1] != -1 ) //判断是否已经读取当前值
{
lst[index++] = W[i][0] //当前值加入到保存数组
W[i][1] = -1; //设置当前值已经读取，不可再读
if(check() == 0)
{
func(W, N-1); //大小不够M，继续往下读
}
else if(check() == 1)
{
print(lst); //和为M，输出
}
lst[--index] = 0; //回溯，寻找下一组解
W[i][1] = 0;
}
}
}
check()
{
if(sum(lst) W)
return -1;
if(sum(lst) W)
return 0;
return 1;
}
求助，用C语言并用回溯算法编写的有关蛇吃苹果走迷宫的程序，题目如下：
/*
* snake
*/
#include stdio.h
#include stdlib.h
#include string.h
#define DEBUG 0
#define printpos() \
printf("File: %s\tLine: %d\n", __FILE__, __LINE__); fflush(stdout);
#define CALLOC(ARRAY, NUM, TYPE) \
ARRAY = (TYPE*) calloc(NUM, sizeof(TYPE)); \
if (ARRAY == NULL) { \
printf("File: %s, Line: %d: ", __FILE__, __LINE__); \
printf("Allocating memory failed.\n"); \
exit(0); \
}
#define REALLOC(ARRAY, NUM, TYPE) \
ARRAY = (TYPE*) realloc(ARRAY, (NUM)*sizeof(TYPE)); \
if (ARRAY == NULL) { \
printf("File: %s, Line: %d: ", __FILE__, __LINE__); \
printf("Allocating memory failed.\n"); \
exit(0); \
}
const int START = -1;
const int HOME = -2;
#if DEBUG
int m=4, n=4;
int a[4][4] = {{7, 0, 4, 18}, {4, 0, 1, 1}, {15, 7, 11, -1}, {0, 12, -2, 0}};
#else
int m=0, n=0;
int **a=NULL;
#endif
struct pos {
int x;
int y;
};
typedef struct pos pos;
struct node {
pos p;
int mv;
int n;
};
typedef struct node node;
const pos mv[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
/*
* get m, n, a and check them
*/
int setup()
{
int nstart=0, nhome=0;
int i, j;
#if DEBUG
#else
//get the dimension of the matrix and allocate memory
printf("Please input the number of rows of the matrix: ");
scanf("%d", m);
if (m=0) {
printf("Number of rows must be greater than 0.\n");
exit(0);
}
a = (int**) calloc(m, sizeof(int*));
if (a == NULL) {
printf("Allocate memory failed.\n");
exit(1);
}
printf("Please input the number of columns of the matrix: ");
scanf("%d", n);
if (n=0) {
printf("Number of columns must be greater than 0.\n");
exit(0);
}
for (i=0; im; i++) {
a[i] = (int*) calloc(n, sizeof(int));
if (a[i] == NULL) {
printf("Allocate memory failed.\n");
exit(1);
}
}
//get the matrix
printf("Please input the matrix, entities seperated by blank:\n");
for (i=0; im; i++) {
for (j=0; jn; j++) {
scanf("%d", a[i][j]);
}
}
#endif
//check the matrix
for (i=0; im; i++) {
for (j=0; jn; j++) {
if (a[i][j] == START) {
nstart++;
if (nstart 1) {
printf("More than 1 starting point.\n");
exit(0);
}
} else if (a[i][j] == HOME) {
nhome++;
if (nhome 1) {
printf("More than 1 home point.\n");
exit(0);
}
} else if (a[i][j] 0) {
printf("a[%d][%d] = %d has no meaning.\n", i, j, a[i][j]);
exit(0);
}
}
}
if (nstart == 0) {
printf("No starting point.\n");
exit(0);
}
if (nhome == 0) {
printf("No home point.\n");
exit(0);
}
//output the matrix
printf("The matrix (%d X %d):\n", m, n);
for (i=0; im; i++) {
for (j=0; jn; j++) {
printf("%d\t", a[i][j]);
}
printf("\n");
}
return 0;
}
int solve(node** optpath)
{
pos dest; //destinating point
node* curpath = NULL; //current path
node** sol = NULL;
int nsol = 0;
int nsteps; //number of steps
int i, j;
int curmv = -1;
int sucmv = 0; //sucessfully moved
int sum;
int maxsum=0;
//setup starting point
for (i=0; im; i++) {
for (j=0; jn; j++) {
if (a[i][j] == START) {
dest.x = i;
dest.y = j;
break;
}
}
}
nsteps = 0;
CALLOC(curpath, nsteps+1, node);
curpath[0].p.x = dest.x;
curpath[0].p.y = dest.y;
curpath[0].mv = -1;
a[dest.x][dest.y] = 0;
curmv = 0;
while (1) {
for (sucmv=0, curmv=curpath[nsteps].mv+1; curmv4; curmv++) {
dest.x = curpath[nsteps].p.x + mv[curmv].x;
dest.y = curpath[nsteps].p.y + mv[curmv].y;
if (dest.x 0 || dest.x = m || dest.y 0 || dest.y = n) {
curpath[nsteps].mv = curmv;
continue;
}
if (a[dest.x][dest.y] == 0) {
curpath[nsteps].mv = curmv;
continue;
}
nsteps++;
REALLOC(curpath, nsteps+1, node);
curpath[nsteps].p.x = dest.x;
curpath[nsteps].p.y = dest.y;
curpath[nsteps-1].mv = curmv;
curpath[nsteps].mv = -1;
curpath[nsteps].n = a[dest.x][dest.y];
a[dest.x][dest.y] = 0;
sucmv = 1;
break;
}
if (sucmv) {
if (curpath[nsteps].n == HOME) {
nsol++;
REALLOC(sol, nsol, node*);
CALLOC(sol[nsol-1], nsteps+1, node);
memcpy(sol[nsol-1], curpath, (nsteps+1)*sizeof(node));
//back
a[curpath[nsteps].p.x][curpath[nsteps].p.y] = curpath[nsteps].n;
nsteps--;
if (nsteps == -1 curpath[0].mv == 3) break;
REALLOC(curpath, nsteps+1, node);
} else {
continue;
}
} else {
a[curpath[nsteps].p.x][curpath[nsteps].p.y] = curpath[nsteps].n;
nsteps--;
if (nsteps == -1 curpath[0].mv == 3) break;
REALLOC(curpath, nsteps+1, node);
}
}
//printf("number of solutions: %d\n", nsol);
for (maxsum=0, i=0; insol; i++) {
//printf("Solution %d \n", i);
//printf("\tPath: ");
sum = -1*HOME;
for (j=0; ; j++) {
//printf("(%d, %d)\t", sol[i][j].p.x, sol[i][j].p.y);
sum += sol[i][j].n;
if (sol[i][j].mv == -1) break;
}
//printf("\n\tSum of apples: %d\n", sum);
if (summaxsum) {
maxsum = sum;
*optpath = sol[i];
}
}
return 0;
}
int output(node* path)
{
int i=0, sum=0;
printf("Path: ");
sum = -1*HOME;
for (i=0; ; i++) {
printf("(%d, %d)\t", path[i].p.x, path[i].p.y);
sum += path[i].n;
if (path[i].mv == -1) break;
}
printf("\nSum of apples: %d\n", sum);
return 0;
}
int main()
{
node* path=NULL;
setup();
solve(path);
output(path);
return 0;
}
编译、链接、运行程序，输入与输出如下：
:!gcc -Wall tmp.c -o tmp
:! ./tmp
Please input the number of rows of the matrix: 5
Please input the number of columns of the matrix: 5
Please input the matrix, entities seperated by blank:
1 7 9 7 0
-2 8 10 8 7
0 10 8 2 -1
4 3 0 7 0 9
1 2 5 1 0 7
The matrix (5 X 5):
1 7 9 7 0
-2 8 10 8 7
0 10 8 2 -1
4 3 0 7 0
9 1 2 5 1
Path: (2, 4) (1, 4) (1, 3) (0, 3) (0, 2) (1, 2) (2, 2) (2, 3) (3, 3) (4, 3) (4, 2) (4, 1) (4, 0) (3, 0) (3, 1) (2, 1) (1, 1) (0, 1) (0, 0) (1, 0)
Sum of apples: 108
:!gcc -Wall tmp.c -o tmp
:! ./tmp
Please input the number of rows of the matrix: 4
Please input the number of columns of the matrix: 4
Please input the matrix, entities seperated by blank:
7 0 4 18
4 0 1 1
15 7 11 -1
0 12 -2 0
The matrix (4 X 4):
7 0 4 18
4 0 1 1
15 7 11 -1
0 12 -2 0
Path: (2, 3) (1, 3) (0, 3) (0, 2) (1, 2) (2, 2) (2, 1) (3, 1) (3, 2)
Sum of apples: 54
