#
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;
}