㈠ 关于回溯法c语言
具体你的算法我没仔细看，但是没有输出是因为肢老羡你的起始循含纳环条件不满足，l=1; 紧接着while(l<历拍0)肯定是不会进入循环的。
㈡ 回溯法的用回溯法解题的一般步骤
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解贺腔空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯法C语言举例
八皇后问题是能用回溯法解决的一个经典问题。
八皇后问题是一个古老而着名的问题。该问销差题是十九世纪着名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上禅斗衫的状态 ：
a[] a[i]=0表示第i行上还没有皇后；
b[] b[i]=0表示第i列反斜线/上没有皇后；
c[] c[i]=0表示第i列正斜线上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号之和相同；同一正斜线上的方格的行号与列号之差均相同，这就是判断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，准备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第m列回溯到m-1列时，并准备调整第m-1列的皇后配置时，清除在数组a[],b[]和c[]对应位置的值都为1来确定。 #include<stdio.h>
#include<stdlib.h>
#define Queens 8
int a[Queens+1]; //八皇后问题的皇后所在每一行位置，从1开始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are:
);
while(not_finish) //not_finsh=1:处理未结束
{
while(not_finish && i<Queens+1) //处理未结束
{
for(flag=1,k=1;flag && k<i;k++)//判断是否有多个皇后在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判断是否有多个皇后在对角线
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重设第i个元素
{
if(a[i]==a[i-1]) //若a[i]的值已经已经一圈追上a[i-1]的值
{
i--; //退回一步 重新试探处理前一个元素
if(i>1 && a[i]==Queens)
a[i]=1; // 当a[i]为 Queens时 将a[i]的值重置
else
if(i==1 && a[i]==Queens)//当第一未位的值达到Queens时结束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i<=Queens) //若前一个元素的值为Queens
if(a[i-1]==Queens)
a[i]=1;
else //否则元素为前一个元素的下一个值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]::
[%2d]:,count);
for(k=1;k<=Queens;k++) //输出结果
printf(%d,a[k]);
if(a[Queens-1]<Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procere try(k:integer);
var
i:integer;
begin
if k>n then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)&&(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通过路径用数字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></n;j++)>
printf(%d,mase[i][j]);
printf(
);
}
system(pause);
return 0;
}
回溯法解决迷宫问题PASCAL语言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procere search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.
㈢ 求完全背包问题的代码(C语言或C++版)或算法
背包问题小结- []2006-07-28
做到背包问题觉得很有意思，写写看看。
完全背包问题可以用贪心算法。
代码如下：
program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;
procere choose;
var i,j:integer;
begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;
begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];
close(input);
choose;
writeln(x:5:2);
end.
编得不是很好 ^-^ 献丑了。
我来说说0/1背包问题。
状态：当前物品n
算符：j=0（当前物品不放入背包） 或 j=1（当前物品放入背包）
这就很好说了，还是把yes函数一改，问题OK了。
代码如下：
program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始数据}
s:array[1..maxn] of integer;{当前的状态}
r:array[1..maxn] of integer;{当前的总质量}
m:integer;{背包容量}
max:integer;{物品个数}
procere try(n:integer);
var j:integer;
{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}
begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最优解}end
end else
begin
if r[n-1]>m then exit;{已超过背包总容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;
begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.
用yes 函数要从头到当前求已装入背包物品的总质量，时间效率不高。所以我们引入r[n]数组来记录当前背包总质量（很好用！）注意用r[n-1]>m来做剪枝，以再次提高时间效率。
DC跟我说可以用二进制解此类问题。我觉得很有创意，也说说。比如8个物品，每个物品有0/1两种状态所以我们从(00000000)(二进制 )到（11111111）（二进制）循环即可。然后在分离十进制数对应起来即可。但在实际的操作中发现效率比回溯还低，我想有两方面的原因：1、显而易见，不可能做剪枝。2、每一次结果都要从1到8求和十效率降低。不过这确实是一种很新颖的算法。
㈣ 回溯算法，用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语言中的回溯法，举一个简单的小例子，说明回溯法的运行过程！
求子串位置
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语言汉诺塔问题代码不明白之处
哈哈，给你解释下
首先你得明白这是用函数递归调用的方法，递归就不用我说磨滚了，看代码
void hanoi(int n,char one,char two,char three)
{
void move(char x,char y);
if(n==1)
move(one,three);
//这个if语句，当盘子只有一个的时候，当然直接从第一根柱子(one)移到第//三根柱子(three)上就OK了,move(one,three)就这个意思！
else
{
hanoi(n-1,one,three,two);//当有n个盘子，按照递归法，调用hannoi,先把//上面的n-1个盘子从第一根柱子(one)借助第三根柱子(three)移到第二根柱瞎宏//子上(two)。
move(one,three);//上面已把n-1个盘子移到第磨游册二根柱子上了，再将第一根柱//子剩下的一个盘子也就是最大的盘子从one移到three,明白?
hanoi(n-1,two,one,three);
/*移动好了最大的一个盘子，剩下n-1个盘子在two上，这时我们可以把第二根柱子与第一个柱//子的位置交换下，也就是标号为two的排第一，one排第二，three排第三。
这里的hanoi(n-1,two,one,three)对应
void hanoi(int n,char one,char two,char three)，只是盘子变成n-1
个,标号为two的柱子排第一了,下面要做的就是把two上上面的n-2个盘子借助three移到one上，再把剩下的一个移到第三个，再调换one 和two位置。
如此重复！注意转换位置只是我们头脑中的想象，程序本身没有转换柱子位置,编程完全按照标号（one two three）来实现的，我这样写只是便于理解递归过程,不知道是否理解?*/
}
}
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
/*move 函数只是起到一个打印步骤的作用，one对应‘A’，。。，比如move(one,two),就会打印出A-->B */
上面有些是我自己理解时的一些想法，希望能帮到你，实际你把代码对照算法多看几次就OK了，很容易的，理解了自己都可以写出来
㈦ 求助 ！C语言OJjzxx1076怎么做，想半天了
这个问题？
1076. 小F的苹果树
Description
小F有一颗苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
2 5
/
3 4
/
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数冲行氏量，求出最多能留住多少苹果。
Input Format
第1行2个数，N和Q(1≤Q≤N1≤Q≤N,1 < N < 101)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。第1行2个数，N和Q(1≤Q≤N1≤Q≤N,1 < N < 101)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
这题目就是根据输入创建树形结构带隐（每个结构有2个链表指针分别指向2个儿子节点）。
所谓的计算苹果数量，就是遍历所有节点（除了根节点），检查其苹果数量和其两个儿子的苹果数量总和，找出最大的散散Q个节点（可以按照数量和排序），最后把这几个节点的数量和加在一起就是可以保留的最多苹果数量。
㈧ 算法编程：用c语言实现
解决这类问题可以使用 回溯 算法，代码如下：
#include<stdio.h>
#include<stdlib.h>
#defineM6//候选数字个数
#defineN5//组合后数字位数
intcheck(intresult[],inti)
{
for(intj=0;j<N;j++)
if(result[j]==i)
return0;
return1;
}
intlist(intnumbers[],intl,intresult[],intcount)
{
if(l>=N){
//将各位数组合成一个数
intnum=0;
for(inti=0;i<N;i++){
num=num*10+numbers[result[i]];
}
//判断这个数是否能被75整除
if(num%75==0){
printf("%d ",num);
count++;
}
returncount;
}
for(inti=0;i<M;i++){
if(!check(result,i)){
continue;
}
result[l]=i;
count=list(numbers,l+1,result,count);
result[l]=-1;
}
returncount;
}
intmain()
{
intnumbers[M]={1,2,5,7,8,9};
intresult[N]={-1,-1,-1,-1,-1};
intcount=list(numbers,0,result,0);
printf("共有%d个 ",count);
system("pause");
return0;
}
运行结果：
㈨ c语言回溯算法
if(n==7||a[n+1][i]!=1&&a[n+1][i+1]!=1&&a[n+1][i-1]!=1)
这行的代码是判断是否可以放皇后的句子。如果可以就将所在位置置 1 。后面也就是这做孝样做判断的。这个程序应当有问题，其中try应当是C语言中一个关键字啊，不森禅可以这么用。
就我纯春稿的看法：八皇后的问题应当用递归加回溯会都到更好的代码，我写过，不过也快忘了。
㈩ C语言解决八王后问题：好像是绝妙算法，却跑不出来
没人会帮你改誉春，以后也是这样滴哪虚含李笑嘿嘿。。
这个八皇后如果回溯剪枝不优化的话，用清华大学刘汝佳的算法：位处理这样会很快，一般的应该可以算到n=11，LRJ的算法可以到n=13?我印象中是这样的。