大致上没看懂kai的思路

typedef vector<City> VCC; //这里不可行，City类没定义，提示错误

kai的想法好，但太复杂，恩……还有就是没有处理哪条路径最长，不过题目好像也有漏洞，就是说，既然两个城市之间可以飞来飞去，就会使程序进入死循环，因为如果有一条路径刚好是在几个城市之间连通了，那可以死循环，要多长路径就有多长，也就是说，这道题其实不完整，我也觉得太难了，难就难在实现路径比较，分支很难处理，如果按照kai的把分支用回推，如果分支太多，就推不了。个人意见，希望高手想个完整一点的方案。

钱已经给了，快告诉我，最好把正确的代码也给出，“空前”的代码运行通不过！晕~~！！

我把代码修改如下：

#include<iostream.h> #include<stdlib.h>

void main() { int count=0; float temp; cout<<"input value of money:"; cin>>temp; int value=int(temp*100); for(int h=0; h<=value/50; h++) for(int q=0; q<=value/25; q++) for(int d=0; d<=value/10; d++) for(int n=0; n<=value/5; n++) for(int p=0; p<=value; p++) if(p+5*n+10*d+25*q+50*h==value) count++; cout<<"There are "<<count<<" ways to make $"<<temp<<endl; system("pause"); }

臭knocker，要是你能给出更优的算法，我再给1000你！

我在1楼给出了我们作业的全部题，有两类，每一类挑一题做，而第一类就是硬币那题，很快就解决了，第二类挑这题，因为觉得这题已经是最简单的了，不过还是难啊，难在怎样实现判断路径长短，因为但遇到分支，如果要先储存在判断，就要另外开一个储存的链(暂时假设用链储存一条路径)，但是如果这样，但下一条不同路径，又要判断刚才那条的城市哪个已经经过，哪个没有经过，然后再来就是对比，设置一个depth变量来比较，最后得出最长路径，还要找出刚才最长的链表，而且如果有N个链表等长，那就更麻烦了！

在字符(地名用字符储存)比较上我也想了N久，到底用char*还是string呢？郁闷了两天才想到，在两个城市的储存上，完全可以用int，就是单个城市名时的数组下标。

我先这样储存单个城市： int N,V; int start=-1; //第一个起点

//下面打开文件，C++方式打开 fstream file1; file1.open("E:\\travel.in"); file1>>N>>V; //取到城市数和通道数 V*=2; //一条通道有两个城市

string *city=new string[N]; //动态申请数组，C++方式 string *route=new string[V]; for(int i=0;i<N;i++) file1>>city[i]; //先把单个城市名储存，string数组

for(int j=0;j<V;j++) { file1>>route[j]; //路径，双数是前一个，单数是后一个 if(j%2==0&&start!=0) //判断如果起点航班存在 start=city[0].compare(route[j]); } file1.close(); //关闭文件，C++方式 if(start!=0) //如果连起点航班都没有就退出，例如Vancouver存在 exit(0);

然后接下来，如果每次都判断string字符串是否一样，就真的很烦，一来代码长，二来cpu也忙，三来我用脑记忆字符也烦，所以干脆把航班表示成数字，例如： 0Vancouver 1Yellowknife 2Edmonton 3Calgary 4Winnipeg 5Toronto 6Montreal 7Halifax 0 2 Vancouver Edmonton 0 3 Vancouver Calgary 3 4 Calgary Winnipeg 4 5 Winnipeg Toronto 5 7 Toronto Halifax 6 7 Montreal Halifax 2 6 Edmonton Montreal 2 1 Edmonton Yellowknife 2 3 Edmonton Calgary

这样一来解决，解决掉比较烦人的问题，就是储存，像kai说的用向量容器储存的确是好，就是用到类和模板，太复杂了，我懒去想，，恩……向量的好处是，当储存越过了数组的边界，系统会自动再加大数组容量，就是说存多少都可以，相对的，删除一个就自动减少容量，很好用，但是在类的嵌套上，用了3个类，我是晕晕，始终觉得太多类只用在工程上，一般算法思维是越简单越好，甚至连函数体也最好用少一点，大致上看得懂kai的第一个类，是要用类链。

kai的思路真的很清晰。不过这句可以不用 typedef vector<City> VCC; 其实写多一点也没关系。 er...写得太抽象，类是很清晰，但实现的时候怎么半？实例化的时候，形成一条链吗？

[此贴子已经被作者于2004-11-20 17:17:16编辑过]

我是想像knocker说的用图来储存，但是又很难，储存是可以，但是遍历的时候就麻烦了。

我再给出用图的邻接矩阵来储存航班之间连通的代码：

//下面动态创建二维数组，C++方式 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

//先给全部元素赋0值 for(i=0; i<N; i++) for(j=0;j<N;j++) connect[i][j]=0;

//下面循环是处理当遇到连通的两个地点，就赋1值 for(int k=0; k<V; k+=2) { for(i=0; i<N; i++) if(!(route[k].compare(city[i]))) break; for(j=0; j<N; j++) if(!(route[k+1].compare(city[j]))) break;

connect[i][j]=connect[j][i]=1; }

//先把图输出，看看正确否 for(i=0; i<N; i++) { for(j=0; j<N; j++) cout<<connect[i][j]<<" "; cout<<endl; }

[此贴子已经被作者于2004-11-20 17:48:36编辑过]

#include<string> #include<iostream> #include<fstream> using namespace std;

void travel(int matrix[][],int visited[],int i,int n);

void main() { int N,V;

//下面打开文件，C++方式打开 fstream file1; file1.open("E:\\travel.txt"); file1>>N>>V; //取到城市数和通道数 V*=2; //一条通道有两个城市

string *city=new string[N]; //动态申请数组，C++方式 string *route=new string[V];

for(int i=0;i<N;i++) file1>>city[i]; //先把单个城市名储存，string数组

int start=-1; //第一个起点 for(int j=0;j<V;j++) { file1>>route[j]; //路径，双数是前一个，单数是后一个 if(j%2==0&&start!=0) //判断如果起点航班存在 start=city[0].compare(route[j]); }

file1.close(); //关闭文件，C++方式 if(start!=0) //如果连起点航班都没有就退出，例如Vancouver存在 exit(0); //下面动态创建二维数组，C++方式 int **connect=new int*[N]; for(i=0; i<N; i++) connect[i]=new int[N];

//先给全部元素赋0值 for(i=0; i<N; i++) for(j=0;j<N;j++) connect[i][j]=0;

//下面循环是处理当遇到连通的两个地点，就赋1值 for(int k=0; k<V; k+=2) { for(i=0; i<N; i++) if(!(route[k].compare(city[i]))) break; for(j=0; j<N; j++) if(!(route[k+1].compare(city[j]))) break;

connect[i][j]=connect[j][i]=1; }

//先把图输出，看看正确否 for(i=0; i<N; i++) { for(j=0; j<N; j++) cout<<connect[i][j]<<" "; cout<<endl; }

int *visited=new int[N]; travel(connect[0],visited,0,N);

//清除刚才申请的内存，包括之前申请的字符串内存，C++方式 for(i=0; i<N; i++) delete[] connect[i]; delete[] connect; delete[] route; delete[] city; }

void travel(int **matrix,int visited[],int i,int n) { cout<<i<<endl; visited[i]=true; for(int j=0; j<n; j++) if(matrix[i][j]!=0&&matrix[i][j]!=(N+1)&&!visited[j]) travel(matrix[],visited,j,n); }

这个问题，去看看最优化的书就应该能够解决的！这个好像是最短路径问题！在matlab中比较容易解决！ 有个统一的思路的吧！

[此贴子已经被作者于2004-11-20 19:30:11编辑过]

错了，是最长路径的问题，比最短路径难，没有同意思路，我也有最短路径算法。

呵呵，还用说～～～