#
function foot=chouxiang
%%%%%%%%%%%%%%%%%%%%%% 程序开始需要知道商人数，仆人数，船的最大容量
n=input('输入商人数目:');
nn=input('输入仆人数目:');
nnn=input('输入船的最大容量:');
if nn>n
n=input('输入商人数目:');
nn=input('输入仆人数目:');
nnn=input('输入船的最大容量:');
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成
jc=1; % 决策向量存放在矩阵“d”中，jc为插入新元素的行标初始为1
for i=0:nnn
for j=0:nnn
if (i+j<=nnn)&(i+j>0) % 满足条件 D=
{(u,v)|1<=u+v<=nnn,u,v=0,1,2}
d(jc,1:3)=[i,j 1]; %生成一个决策向量后立刻将他扩充为三维（再末尾加“1”）
d(jc+1,1:3)=[-i,-j,-1]; % 同时生成他的负向量
jc=jc+2; % 由于一气生成两个决策向量,jc指标需要往下移动两个单位
end
end
j=0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 状态数组生成
kx=1; % 状态数组存放在矩阵“A”中，生成方法同决策生成
for i=n:-1:0
for j=nn:-1:0
if ((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))
% (i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))为可以存在的状态的约束条件
A(kx,1:3)=[i,j,1]; % 生成状态数组集合D`
A(kx+1,1:3)=[i,j,0];
kx=kx+2;
end
end
j=nn;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 将状态数组生成抽象矩阵
k=(1/2)*size(A,1);
CX=zeros(2*k,2*k);
a=size(d,1);
for i=1:2*k
for j=1:a
c=A(i,:)+d(j,:) ;
x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ;
v(i,x)=1; % x为空不会改变v的值
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% dijstra方法
x=1; y=size(A,1);
m=size(v,1);
T=zeros(m,1);
T=T.^-1;
lmd=T;
P=T;
S=zeros(m,1);
S(x)=1;
P(x)=0; lmd(x)=0;
k=x;
while(1)
a=find(S==0);
aa=find(S==1);
if size(aa,1)==m
break;
end
for j=1:size(a,1)
pp=a(j,1);
if v(k,pp)~=0
if T(pp)>(P(k)+v(k,pp))
T(pp)=(P(k)+v(k,pp));
lmd(pp)=k;
end
end
end
mi=min(T(a));
if mi==inf
break;
else
d=find(T==mi);
d=d(1);
P(d)=mi;
T(d)=inf;
k=d;
S(d)=1;
end
end
if lmd(y)==inf
foot='can not reach';
return;
end
foot(1)=y;
g=2; h=y;
while(1)
if h==x
break;
end
foot(g)=lmd(h);
g=g+1;
h=lmd(h);
end
foot=A(foot,:);
foot(:,3)=[];
这个代码比我上回写的C++代码短很多。。。。。。看来还是Matlab强大丫 一定要尽快学会才行 :-)
这道题可以算是1118,2780的升级版，因为更容易超时了 O(∩_∩)O~
题目的意思很简单，给你许多点，然后让你求出在同在一条直线上的点最多有多少个。
这道题做了2个小时，开始用了暴搜的方法（那个方法不用考虑斜率不存在的情况），超时了，汗~后来改成计算斜率的方法才过的 方法如下：
单独考虑斜率不存在的情况，把所有的点按照x的大小排序，算出x相同的点最多有多少个，保存到max1里；
然后考虑斜率存在的情况，考虑一个定点，把它和其它直线的斜率都算出来，排序，然后再计算相同的斜率最多有多少个，每个点都这样算一遍，取最大值中的最大值，存在max2中；
最后比较max1和max2+1（注意max2我们是用斜率算的，它代表max2+1个点）取较大值输出即可；
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node {
int x;
int y;
}set[1001];
int cmp(const void *a,const void *b)
{
struct node*c=(node *)a;
struct node*d=(node* )b;
return c->x-d->x;
}
char temp[100];
double slope[10001];
int main ()
{
int n;
int i,j,k;
int testcase;
testcase=0;
int max1;
int max2;
int pos;
int tempmax2;
for(testcase=1;;testcase++)
{
pos=0;
while(gets(temp))
{
if(temp[0]=='-'&&temp[1]=='-')
break;
pos++;
sscanf(temp,"%d%d",&set[pos].x,&set[pos].y);
}
n=pos;
if(n==0)
break;
int tempmax=1;
max1=0;
qsort(set+1,n,sizeof(set[1]),cmp);
for(i=2;i<=n;i++)
{
if(set[i].x!=set[i-1].x)
tempmax=1;
else
tempmax++;
if(tempmax>max1)
max1=tempmax;
}
max2=0;
for(i=1;i<=n;i++)
{
pos=0;
for(j=1;j<=n;j++)
{
if(i!=j&&set[i].x!=set[j].x)
{
pos++;
slope[pos]=((double)set[j].y-set[i].y)/((double)set[j].x-set[i].x);
}
}
sort(slope+1,slope+1+pos);
tempmax=1;
tempmax2=0;
for(j=2;j<=pos;j++)
{
if(slope[j]!=slope[j-1])
tempmax=1;
else
tempmax++;
if(tempmax>tempmax2)
tempmax2=tempmax;
}
if(tempmax2>max2)
max2=tempmax2;
}
if(max1>max2)
printf("%d. %d\n",testcase,max1);
else
printf("%d. %d\n",testcase,max2+1);
}
return 0;
}
摘要: /**//* 树中已知先序和中序求后序。 如先序为：abdc,中序为：bdac . 则程序可以求出后序为：dbca 。此种题型也为数据结构常考题型。 ...
阅读全文
//数据结构作业之二叉树左右子树交换+二叉树高度计算
//学生：abilitytao 指导老师：Mr ZHANGHONG
//时间:2009年3月17日17:54:33
#include<iostream>
using namespace std;
struct node{
int data;
node *lchild;
node *rchild;
};
void preorder(node *p)
{
if(p!=NULL)
{
cout<<p->data;
preorder(p->lchild);
preorder(p->rchild);
}
}
void inorder(node *p)
{
if(p==NULL)
return ;
inorder(p->lchild);
cout<<p->data;
inorder(p->rchild);
}
void CreatTree(node *&p)
{
int temp;
cin>>temp;
if(temp==0)
{
p=NULL;
return;
}
p=new node;
p->data=temp;
CreatTree(p->lchild);
CreatTree(p->rchild);
}
void change(node *p)
{
if(p==NULL)
return;
node *temp;
temp=p->lchild;
p->lchild=p->rchild;
p->rchild=temp;
change(p->lchild);
change(p->rchild);
}
int count(node *p)//用递归的方法计算树高
{
if(p==NULL)
return 0;
int lhigh=count(p->lchild);
int rhigh=count(p->rchild);
if(lhigh>=rhigh)
return lhigh+1;
else
return rhigh+1;
}//问：可以用全局变量计算树高么？
/**//*int count(node *p)
{
if(p==NULL)
return 0;
else if(count(p->lchild)>=count(p->rchild))
return count(p->lchild)+1;
else count(p->rchild)+1;
}*///错误版树高计算程序 问：到底哪错了？？？个人感觉是递归上出问题了。。。
/**////////////////////////////以下为测试/////////////////////////////int main ()
{
node *tree;
CreatTree(tree);
cout<<"此二叉树的高度为:"<<count(tree)<<endl;
system("pause");
return 0;
}
/**///////////////////////////////////////////////////////////////////////////
以前做过POJ上的3620，题意大概是要你求出相邻的X有多少个，而这个题呢，则是要求你求出整个互相邻接的X所够成的周长；
我个人认为，这两道题有异曲同工之妙。
这道题和3620不同的是，我们不能将所有与X相邻的结点都压栈，而是选择X结点压栈，为什么呢？我想了想，因为此题的周长是在你考察X的基础上向四面八方试探而求出的。你最好是立足与X结点，由于对压栈元素进行了限制，那么在进入dfs递归的时候也就不用大费周章的去判断
if(visit[i][j]==0)了，因为压栈的元素必须是没有考察过的X结点；当然这只不过是基于自己的个人习惯而已，我想，即使你不判断压栈元素，应该也能做出来吧，只不过这样似乎并不符合我们的思维习惯而已；
另外做这个题目的时候还遇到了一个小问题，就是cin.ignore()的使用，再输入r,c,x,y的值之后，由于回车符不可能被整型变量吃掉，所以它会滞留在缓冲区，使得在输入字符时回车符优先进入map数组，而且每一行之后都有一个回车符，所以这个cin.ignore()的位置也是不能改变的。
当让还有个有意思的地方，就是这个题要用向量来存储考察的方向，这样的话一个循环就可以考察完所有的方向，不用费力把所有的方向都写一遍了，这是一个很不错的方法，宜借鉴之；
最后要感谢一下网路上分享代码的大牛们，正是由于参考了你们的代码才使我有所进步；
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAX 100
char map[MAX][MAX];
int visit[MAX][MAX];
int sum;
int r,c;
int path[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
void dfs(int a,int b)
{
visit[a][b]=1;
int i;
for(i=0;i<8;i++)
{
int x=a+path[i][0];
int y=b+path[i][1];
if(x>=1&&x<=r&&y>=1&&y<=c)
{
if(map[x][y]=='X'&&visit[x][y]==0)
dfs(x,y);
else if(map[x][y]=='.'&&(x==a||y==b))
{
sum++;
}
}
else if(x==a||y==b)
sum++;
}
}
int main ()
{
int x,y;
int i,j;
while(scanf("%d%d%d%d",&r,&c,&x,&y))
{
for(i=1;i<=r;i++)
for(j=1;j<=c;j++)
{
visit[i][j]=0;
}
for(i=1;i<=r;i++)
{
cin.ignore();
for(j=1;j<=c;j++)
{
scanf("%c",&map[i][j]);
}
}
sum=0;
if(r==0&&c==0&&x==0&&y==0)
break;
dfs(x,y);
printf("%d\n",sum);
}
return 0;
}