#
function foot=chouxiang
%%%%%%%%%%%%%%%%%%%%%% 程序開(kāi)始需要知道商人數(shù)，仆人數(shù)，船的最大容量
n=input('輸入商人數(shù)目:');
nn=input('輸入仆人數(shù)目:');
nnn=input('輸入船的最大容量:');
if nn>n
n=input('輸入商人數(shù)目:');
nn=input('輸入仆人數(shù)目:');
nnn=input('輸入船的最大容量:');
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 決策生成
jc=1; % 決策向量存放在矩陣“d”中，jc為插入新元素的行標(biāo)初始為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]; %生成一個(gè)決策向量后立刻將他擴(kuò)充為三維（再末尾加“1”）
d(jc+1,1:3)=[-i,-j,-1]; % 同時(shí)生成他的負(fù)向量
jc=jc+2; % 由于一氣生成兩個(gè)決策向量,jc指標(biāo)需要往下移動(dòng)兩個(gè)單位
end
end
j=0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 狀態(tài)數(shù)組生成
kx=1; % 狀態(tài)數(shù)組存放在矩陣“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))為可以存在的狀態(tài)的約束條件
A(kx,1:3)=[i,j,1]; % 生成狀態(tài)數(shù)組集合D`
A(kx+1,1:3)=[i,j,0];
kx=kx+2;
end
end
j=nn;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 將狀態(tài)數(shù)組生成抽象矩陣
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為空不會(huì)改變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)=[];
這個(gè)代碼比我上回寫(xiě)的C++代碼短很多。。。。。。看來(lái)還是Matlab強(qiáng)大丫 一定要盡快學(xué)會(huì)才行 :-)
這道題可以算是1118,2780的升級(jí)版，因?yàn)楦菀壮瑫r(shí)了 O(∩_∩)O~
題目的意思很簡(jiǎn)單，給你許多點(diǎn)，然后讓你求出在同在一條直線上的點(diǎn)最多有多少個(gè)。
這道題做了2個(gè)小時(shí)，開(kāi)始用了暴搜的方法（那個(gè)方法不用考慮斜率不存在的情況），超時(shí)了，汗~后來(lái)改成計(jì)算斜率的方法才過(guò)的 方法如下：
單獨(dú)考慮斜率不存在的情況，把所有的點(diǎn)按照x的大小排序，算出x相同的點(diǎn)最多有多少個(gè)，保存到max1里；
然后考慮斜率存在的情況，考慮一個(gè)定點(diǎn)，把它和其它直線的斜率都算出來(lái)，排序，然后再計(jì)算相同的斜率最多有多少個(gè)，每個(gè)點(diǎn)都這樣算一遍，取最大值中的最大值，存在max2中；
最后比較max1和max2+1（注意max2我們是用斜率算的，它代表max2+1個(gè)點(diǎn)）取較大值輸出即可；
#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;
}
摘要: /**//* 樹(shù)中已知先序和中序求后序。 如先序?yàn)椋篴bdc,中序?yàn)椋篵dac . 則程序可以求出后序?yàn)椋篸bca 。此種題型也為數(shù)據(jù)結(jié)構(gòu)常考題型。 ...
閱讀全文
//數(shù)據(jù)結(jié)構(gòu)作業(yè)之二叉樹(shù)左右子樹(shù)交換+二叉樹(shù)高度計(jì)算
//學(xué)生：abilitytao 指導(dǎo)老師：Mr ZHANGHONG
//時(shí)間: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)//用遞歸的方法計(jì)算樹(shù)高
{
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;
}//問(wèn)：可以用全局變量計(jì)算樹(shù)高么？
/**//*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;
}*///錯(cuò)誤版樹(shù)高計(jì)算程序 問(wèn)：到底哪錯(cuò)了？？？個(gè)人感覺(jué)是遞歸上出問(wèn)題了。。。
/**////////////////////////////以下為測(cè)試/////////////////////////////int main ()
{
node *tree;
CreatTree(tree);
cout<<"此二叉樹(shù)的高度為:"<<count(tree)<<endl;
system("pause");
return 0;
}
/**///////////////////////////////////////////////////////////////////////////
以前做過(guò)POJ上的3620，題意大概是要你求出相鄰的X有多少個(gè)，而這個(gè)題呢，則是要求你求出整個(gè)互相鄰接的X所夠成的周長(zhǎng)；
我個(gè)人認(rèn)為，這兩道題有異曲同工之妙。
這道題和3620不同的是，我們不能將所有與X相鄰的結(jié)點(diǎn)都?jí)簵＃沁x擇X結(jié)點(diǎn)壓棧，為什么呢？我想了想，因?yàn)榇祟}的周長(zhǎng)是在你考察X的基礎(chǔ)上向四面八方試探而求出的。你最好是立足與X結(jié)點(diǎn)，由于對(duì)壓棧元素進(jìn)行了限制，那么在進(jìn)入dfs遞歸的時(shí)候也就不用大費(fèi)周章的去判斷
if(visit[i][j]==0)了，因?yàn)閴簵５脑乇仨毷菦](méi)有考察過(guò)的X結(jié)點(diǎn)；當(dāng)然這只不過(guò)是基于自己的個(gè)人習(xí)慣而已，我想，即使你不判斷壓棧元素，應(yīng)該也能做出來(lái)吧，只不過(guò)這樣似乎并不符合我們的思維習(xí)慣而已；
另外做這個(gè)題目的時(shí)候還遇到了一個(gè)小問(wèn)題，就是cin.ignore()的使用，再輸入r,c,x,y的值之后，由于回車符不可能被整型變量吃掉，所以它會(huì)滯留在緩沖區(qū)，使得在輸入字符時(shí)回車符優(yōu)先進(jìn)入map數(shù)組，而且每一行之后都有一個(gè)回車符，所以這個(gè)cin.ignore()的位置也是不能改變的。
當(dāng)讓還有個(gè)有意思的地方，就是這個(gè)題要用向量來(lái)存儲(chǔ)考察的方向，這樣的話一個(gè)循環(huán)就可以考察完所有的方向，不用費(fèi)力把所有的方向都寫(xiě)一遍了，這是一個(gè)很不錯(cuò)的方法，宜借鑒之；
最后要感謝一下網(wǎng)路上分享代碼的大牛們，正是由于參考了你們的代碼才使我有所進(jìn)步；
#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;
}