本文目錄一覽：
- 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
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/293456.html
微信掃一掃 
支付寶掃一掃 