怎样用递归寻找所有路径算法？？？？？？？？？？？？？赐教！
这些天学递归，碰到这个例子，好些天不得其解，望知情者告知，当天重谢！！！
1--3--5--7--9
|\ |\ |\ |\ |
0--2--4--6--8
输出0->n(1<=n&&n<=9)的所有路径，
由低位到高位 如0->2：0-->2
0-->1-->2
谢谢！
问题点数：100、回复次数：28Top
1 楼mmmcd（超超）回复于 2004-04-04 11:27:05 得分 7
看看效果，
随手改了一个没调试
#define MAX 10
#include <stdio.h>
int path[MAX]={0};
int n;
void f(int i,int j)
{
int k;
if(j==n)
{
for(k=1;k<=i;k++)
{
printf("-->%d ",path[k]);
}
printf("\n");
}
if(j>=n)return;
for(k=path[i]+1;k<=path[i]+2;k++)
{
path[i+1]=k;
f(i+1,k);
}
}
void main()
{
int n;
path[0]=1;
while(scanf("%d",&n)==1)
{
printf("0");
f(0,0);
}
getchar();
}
Top
2 楼onethousand（越来）回复于 2004-04-04 14:45:11 得分 0
编译链接没错误，语法拽！
结果不正确
没有输出！！
高手可否再看一下???
高分伺候！！Top
3 楼onethousand（越来）回复于 2004-04-04 14:47:45 得分 0
我希望看到递归的结果，最好有C++示例。
Top
4 楼aheadyes（）回复于 2004-04-04 14:50:53 得分 12
#define N 6
#include <stdio.h>
int used[N]={0};
void output()
{
int i;
for(i=0;i<=N;i++) if(used[i]&&used[N-1]==1)printf("%d--> ",i);
printf("\n");
}
void f(int i)
{
if(i>=N)
{
output();
return;
}
used[i]=1;
f(i+1);
if(i+2<=N)
{
f(i+2);
used[i]= 0;
}
else
used[i] = 0;
}
void main()
{
f(0);
getchar();
}
Top
5 楼aheadyes（）回复于 2004-04-04 15:03:20 得分 0
更为正确的如下:)
#define N 4
#include <stdio.h>
int used[N+1]={0};
void output()
{
int i;
for(i=0;i<N;i++) if(used[i]&&used[N]==1)printf("%d--> ",i);
if(used[N]==1) printf("%d",i);
printf("\n");
}
void f(int i)
{
if(i>=N+1)
{
output();
return;
}
used[i]=1;
f(i+1);
if(i+2<N+1)
{
f(i+2);
used[i]= 0;
}
else
used[i] = 0;
}
void main()
{
f(0);
getchar();
}
Top
6 楼onethousand（越来）回复于 2004-04-04 15:19:09 得分 0
我希望看到能输出0--9之间每个数字的的所有路径，
如：0-1；0-2；0-3；0-4；......0-9；的路径
其中比如0-2：又有0->2;0->1->2两条。
上面的兄台好像没有完全理解我的意思。
Top
7 楼onethousand（越来）回复于 2004-04-04 15:20:22 得分 0
不够已经很接近了，待我慢慢参考.
谢谢！Top
8 楼aheadyes（）回复于 2004-04-04 15:27:29 得分 0
上面的只是0-N的路径;
如果你要：0-1；0-2；0-3；0-4；......0-9；的路径
那么加个循环不就得了:)
Top
9 楼aheadyes（）回复于 2004-04-04 15:30:25 得分 0
void main()
{
for(int i=0; i<=N; i++)
f(i);
getchar();
}Top
10 楼onethousand（越来）回复于 2004-04-04 15:59:45 得分 0
好像不太符合要求
即时N=9时
也不能输出所有的路径。Top
11 楼aheadyes（）回复于 2004-04-04 17:09:54 得分 0
呵呵 上面的是求出i-n(0=<i<= n)的路径
原来你是要求
0-1；0-2；0-3；0-4；......0-9；的路径呀:)
#include <stdio.h>
void f(int i,int used[],int N)
{
if(i>=N+1)
{
int i;
for(i=0;i<N;i++)
if(used[i]&&used[N]==1) printf("%d--> ",i);
if(used[N]==1) printf("%d",i);
printf("\n");
return;
}
used[i]=1;
f(i+1,used,N);
if(i+2<N+1)
{
f(i+2,used,N);
used[i]= 0;
}
else
used[i] = 0;
}
void main()
{
int used[9]={0};
for(int i=1; i<=9; i++)
f(0,used,i);
getchar();
}
全部满足条件:) 给分 @_@
Top
12 楼onethousand（越来）回复于 2004-04-04 18:24:02 得分 0
@_@
不好意思，不正确，不能给分
N=9时
显然缺少0->1->2->3->4->5->6->7->8->9
这条路径Top
13 楼aheadyes（）回复于 2004-04-04 18:42:08 得分 10
看清楚点, 没有吗? 你确定. 我运行的时候有啊Top
14 楼chenzhichao2008（陈智超）回复于 2004-04-05 16:35:48 得分 0
楼上的你的程序确实还没找到所有的解
你把9改为4或者3你就知道了Top
15 楼liangbch（宝宝）回复于 2004-04-05 17:36:47 得分 8
我的程序应该没有问题，在vc6.0下调试通过。
#include "stdafx.h"
#define POINT_COUNT 10
void printPath(int a[],int n)
{
int i;
for ( i=0;i<n;i++)
{
printf("%d",a[i]);
if (i <=n-2)
printf("->");
}
printf("\n");
}
void searchCore(int a[],int count,int end)
{
int beg,i;
if ( a[count-1]==end)
{
printPath(a,count);
return;
}
else
{
beg=a[count-1];
for ( i=beg+1;i<=end;i++)
{
a[count]=i;
searchCore(a,count+1,end);
}
}
}
void searchPath(int beg,int end)
{
int pointArr[POINT_COUNT];
pointArr[0]=beg;
searchCore(pointArr,1,end);
}
int main(int argc, char* argv[])
{
searchPath(0,9);
return 0;
}
Top
16 楼onethousand（越来）回复于 2004-04-05 20:59:06 得分 0
这边没人通过，
http://expert.csdn.net/Expert/topic/2923/2923615.xml?temp=.4314234
上面的兄台，头文件错了，改成stdio.h后，也是运行不对，能0->9吗？Top
17 楼chenzhichao2008（陈智超）回复于 2004-04-06 06:50:31 得分 5
这应该总共有88条路(0-9)Top
18 楼liangbch（宝宝）回复于 2004-04-06 13:03:51 得分 0
to onethousand:
是编译不过呢，还是运行结果不对呢？
如果是编译不过，请在vc下作这样的设置：
1.将 #include stdafx.h 改为
#include "stdlib.h"
#include "stdio.h"
2. 点击 project->setting 菜单，设置 C/C++ -> Category 中的 Precompiled Headers 为Not using precompiled headers.
Top
19 楼onethousand（越来）回复于 2004-04-07 12:30:13 得分 0
to 宝宝
是这样的，比如说求0->9的路径；
不可能有这条路径:0—>9；就像我上面画的图，要经过其他数字。最短的也就是0—>2->4->6->8->9;或0->1->3->5->7->9.
不好意思，可能是我说得不够清楚Top
20 楼liangbch（宝宝）回复于 2004-04-07 13:05:46 得分 0
哦，我明白了，这样的话，程序就需要更加复杂一些，首先得建立一个10*10的矩阵，用来表示那些路径是相同的，那些路径是不相同的。在递归程序中，添加节点时加一些判断，只有路径试连同时，才可以增加节点，程序等有空儿时写。Top
21 楼sogald_2001（纳兰无忌）回复于 2004-04-07 14:00:51 得分 15
不用递归行不？
上面有递归算法了，下面这个不是递归算法：
#include <vector>
#include <algorithm>
#include <iostream>
/*
起点为0，终点为n
考虑通路 0 -> 1 -> 2 -> ... -> n-1 -> n
算法：
第i次扫描，保持前面从 0-i的路径不变，判断是否有从i到i+2的不同于i-> i+1 -> i+2 的其它路径，如有
不妨设为V，则路径 0-> 1- >...-> i-1 -> V -> i+3->...-> n为一条新路径, 由于i 和 i+2 直接有边连接
所以V总存在，且仅一条.
i 从0 到 n-2
*/
void Path(int n)
{
typedef std::vector<int> path_type;
typedef std::vector<path_type> paths_type;
path_type basic;
for(int i=0; i < n+1; ++ i)
basic.push_back(i);
paths_type path_set;
path_set.push_back(basic);
//依次从0-N中取出一个点j ( j = 1,2 ... n-1)
for(i=1; i < n; ++ i)
{
path_type new_path(basic);
new_path.erase(std::remove(new_path.begin(), new_path.end(), i)) ;
path_set.push_back(new_path);
}
std::ostream_iterator<int> output(std::cout, " ");
for(paths_type::const_iterator citer = path_set.begin(); citer != path_set.end(); ++ citer)
{
std::copy( citer->begin(), citer->end(), output);
std::cout << std::endl;
}
}
另外一种方法：
看成一个图，数字为顶点，从小数字到大数字是一条有向边，问题转化为在一个有向图中寻求两个顶点间的路径集合问题，这可以利用成熟的图的搜索算法。
Top
22 楼gudfen（帝波微）回复于 2004-04-07 14:20:29 得分 15
#include "stdafx.h"
#include "iostream.h"
#include <stdio.h>
void print(int i){
if(i==0)
cout<<"0";
if(i==1)
cout<<"0-->1";
if(i>1)
{
print(i-1);cout<<"-->"<<i<<endl;
print(i-2);cout<<"-->"<<i<<endl;
}
}
void main(){
int no;
cout<<"Input the destination :";
cin>>no;
print(no);
}
为什么不对？Top
23 楼privet（阿朱）回复于 2004-04-07 22:30:48 得分 18
应自下到上递归,以下是我的递归算法
#include <iostream.h>
int a[9]; //记录走国的数字
int N=0; //记录走过的步数
int m=0; //记录得到的走法数
void print() //输出函数
{for(int i=0;i<N-1;i++)
cout<<a[i]<<"-->";
cout<<a[N-1]<<endl;
m++;}
void recur(int i,int n) //递归函数
{
a[N++]=i;
if(n==i) { print();return;}
recur(i+1,n); //向前一步
N--; //回退
if(i+2<=n)
{recur(i+2,n); //向前二步
N--;} //回退
}
main() //主函数
{ int b,e;
cout<<"Please input begin integer:"<<endl;
cin>>b;
cout<<"Please input end integer:"<<endl;
cin>>e;
recur(b,e);
cout<<"The number of roads is "<<m;
}Top
24 楼privet（阿朱）回复于 2004-04-07 22:33:40 得分 0
路的条数的递推式是:A[n]=A[n-1]+A[n-2}
A[1]=1,A[2]=2,
计算得A[9]=55
Top
25 楼mmmcd（超超）回复于 2004-04-08 12:13:48 得分 5
还是上面一楼那个程序，VC6下调了一下
#define MAX 10
#include <stdio.h>
int path[MAX]={0};
int n;
void f(int i,int j)
{
int k;
if(j==n)
{
printf("0");
for(k=1;k<=i;k++)
{
printf("-->%d",path[k]);
}
printf("\n");
}
if(j>=n)return;
for(k=path[i]+1;k<=path[i]+2;k++)
{
path[i+1]=k;
f(i+1,k);
}
}
void main()
{
//int n; 注释掉
path[0]=0;
while(scanf("%d",&n)==1)
{
f(0,0);
}
getchar();
}
9
0-->1-->2-->3-->4-->5-->6-->7-->8-->9
0-->1-->2-->3-->4-->5-->6-->7-->9
0-->1-->2-->3-->4-->5-->6-->8-->9
0-->1-->2-->3-->4-->5-->7-->8-->9
0-->1-->2-->3-->4-->5-->7-->9
0-->1-->2-->3-->4-->6-->7-->8-->9
0-->1-->2-->3-->4-->6-->7-->9
0-->1-->2-->3-->4-->6-->8-->9
0-->1-->2-->3-->5-->6-->7-->8-->9
0-->1-->2-->3-->5-->6-->7-->9
0-->1-->2-->3-->5-->6-->8-->9
0-->1-->2-->3-->5-->7-->8-->9
0-->1-->2-->3-->5-->7-->9
0-->1-->2-->4-->5-->6-->7-->8-->9
0-->1-->2-->4-->5-->6-->7-->9
0-->1-->2-->4-->5-->6-->8-->9
0-->1-->2-->4-->5-->7-->8-->9
0-->1-->2-->4-->5-->7-->9
0-->1-->2-->4-->6-->7-->8-->9
0-->1-->2-->4-->6-->7-->9
0-->1-->2-->4-->6-->8-->9
0-->1-->3-->4-->5-->6-->7-->8-->9
0-->1-->3-->4-->5-->6-->7-->9
0-->1-->3-->4-->5-->6-->8-->9
0-->1-->3-->4-->5-->7-->8-->9
0-->1-->3-->4-->5-->7-->9
0-->1-->3-->4-->6-->7-->8-->9
0-->1-->3-->4-->6-->7-->9
0-->1-->3-->4-->6-->8-->9
0-->1-->3-->5-->6-->7-->8-->9
0-->1-->3-->5-->6-->7-->9
0-->1-->3-->5-->6-->8-->9
0-->1-->3-->5-->7-->8-->9
0-->1-->3-->5-->7-->9
0-->2-->3-->4-->5-->6-->7-->8-->9
0-->2-->3-->4-->5-->6-->7-->9
0-->2-->3-->4-->5-->6-->8-->9
0-->2-->3-->4-->5-->7-->8-->9
0-->2-->3-->4-->5-->7-->9
0-->2-->3-->4-->6-->7-->8-->9
0-->2-->3-->4-->6-->7-->9
0-->2-->3-->4-->6-->8-->9
0-->2-->3-->5-->6-->7-->8-->9
0-->2-->3-->5-->6-->7-->9
0-->2-->3-->5-->6-->8-->9
0-->2-->3-->5-->7-->8-->9
0-->2-->3-->5-->7-->9
0-->2-->4-->5-->6-->7-->8-->9
0-->2-->4-->5-->6-->7-->9
0-->2-->4-->5-->6-->8-->9
0-->2-->4-->5-->7-->8-->9
0-->2-->4-->5-->7-->9
0-->2-->4-->6-->7-->8-->9
0-->2-->4-->6-->7-->9
0-->2-->4-->6-->8-->9
Top
26 楼gudfen（帝波微）回复于 2004-04-08 15:48:53 得分 0
谢谢阿朱Top
27 楼liangbch（宝宝）回复于 2004-04-08 19:20:54 得分 5
增加了路径的判断，应该完整的回答了楼主的问题。
#include "stdlib.h"
#include "stdio.h"
//1--3--5--7--9
//|\ |\ |\ |\ |
//0--2--4--6--8
//注意: const 关键字在C++中广泛使用，它可以增加程序的安全性，如果你对const不了解可以从程序中删除const,程序功能依然正确
#define POINT_COUNT 10
void printPath(int a[],int n)
{
int i;
for ( i=0;i<n;i++)
{
printf("%d",a[i]);
if (i <=n-2)
printf("->");
}
printf("\n");
}
void searchCore(const char connectionMatrix[10][10],int a[],int count,int end)
{
int beg,i;
if ( a[count-1]==end)
{
printPath(a,count);
return;
}
else
{
beg=a[count-1];
for ( i=beg+1;i<=end;i++)
{
if ( connectionMatrix[beg][i] > 0 ) //从beg到i有路可走
{
a[count]=i;
searchCore(connectionMatrix,a,count+1,end);
}
}
}
}
void searchPath(int beg,int end)
{
//各个节点是否有路可走的矩阵表示，
//connectionMatrix[i][j]:表示从 i 到 j是否有路可走，1:有路可走，0:不能走,
// 如果各个节点的路径不是题目中要求的样子,只需要修改connectionMatrix 即可
const char connectionMatrix[10][10]=
{
{0,1,1,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,0,1,1,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0},
{0,0,0,0,0,1,1,0,0,0},
{0,0,0,0,0,0,1,1,0,0},
{0,0,0,0,0,0,0,1,1,0},
{0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0}
};
int pointArr[POINT_COUNT];
pointArr[0]=beg;
searchCore(connectionMatrix,pointArr,1,end);
}
int main(int argc, char* argv[])
{
searchPath(0,9);
return 0;
}
Top
28 楼mysword（一怒拔剑）回复于 2004-04-08 20:21:36 得分 0
为什么这么简单的问题要有这么多人回答？
Top
