# The Fourth Dimension Space

## Exploring in The Art Of Programming about Huffman Tree's Creation.

/*数据结构作业之——哈弗曼树的构造以及WPL的计算；

*/

//Get Guidance By Mr ZhangHong
//Student: abilitytao

#include
<iostream>
#include
<cmath>
#include
<cstring>
using namespace std;
#define MAX 10000000

struct node
{

int w;

int p;

int lch;

int rch;
}
huffman[MAX];

int search_min(int l,int r)
{

int min=999999999;

int mark=0;

int i;

for(i=l;i<=r;i++)

{

if(huffman[i].w<min&&huffman[i].p==0)

{
min
=huffman[i].w;
mark
=i;
}

}

return mark;

}

int search_second_min(int l,int r)
{

int min=search_min(l,r);

int secondmin=999999999;

int mark=0;

int i;

for(i=l;i<=r;i++)

{

if(huffman[i].w>=huffman[min].w&&huffman[i].w<=secondmin&&huffman[i].p==0&&i!=min)

{
secondmin
=huffman[i].w;
mark
=i;

}

}

return mark;
}

int main()
{

int n;

int i;

int num;

for(i=1;;i++)

{

scanf(
"%d",&n);
huffman[i].w
=n;
huffman[i].p
=0;
huffman[i].lch
=0;
huffman[i].rch
=0;

if(n==0)

break;
}

num
=i-1;

int pos=num;

for(i=1;i<=num-1;i++)

{

int max_mark=search_min(1,i+num-1);

int secondmax_mark=search_second_min(1,i+num-1);

++pos;
huffman[pos].w
=huffman[max_mark].w+huffman[secondmax_mark].w;
huffman[pos].p
=0;
huffman[pos].lch
=secondmax_mark;
huffman[pos].rch
=max_mark;
huffman[max_mark].p
=pos;
huffman[secondmax_mark].p
=pos;
}

printf(
"这棵树的WPL为：%d\n",huffman[pos].w);
system(
"pause");

return 0;
}

posted @ 2009-03-23 20:57 abilitytao 阅读(1103) | 评论 (0)编辑 收藏

## POJ 3364-Black and white painting 简单数学题

#include<cstdio>
int main()
{
unsigned
int n,m,c;

while(scanf("%d%d%d",&n,&m,&c))

{

if(n==0&&m==0&&c==0)

break;

if(c==1&&(n-7)%2==1&&(m-7)%2==1)
printf(
"%d\n",((n-7)*(m-7)+1)/2);

else
printf(
"%d\n",(n-7)*(m-7)/2);
}

}

posted @ 2009-03-21 17:31 abilitytao 阅读(370) | 评论 (0)编辑 收藏

## 商人过河问题的Matlab实现（转）

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)=[];

posted @ 2009-03-21 01:09 abilitytao 阅读(3334) | 评论 (0)编辑 收藏

## POJ 3512-Incidental Points 要选择合适的算法，否则容易超时

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

posted @ 2009-03-21 00:48 abilitytao 阅读(1154) | 评论 (5)编辑 收藏

## 运算符重载的简单研究

#include<iostream>
using namespace std;

class plural
{
private:

int x;

int y;
public:
plural()

{

x
=0;
y
=0;
}

plural(
int a,int b)

{

x
=a;
y
=b;
}

void print();
plural
operator +(const plural &n);
plural
operator -(const plural &n);
friend ostream
& operator <<(ostream &os,const plural &ob);
}
;

void plural::print()
{

cout
<<x<<' '<<y<<endl;

}

plural plural::
operator +(const plural &n)
{

plural temp;
temp.x
=x+n.x;
temp.y
=y+n.y;

return temp;
}

plural plural::
operator- (const plural &n)
{
plural temp;
temp.x
=x-n.x;
temp.y
=y-n.y;

return temp;

}

ostream
& operator<<(ostream &os,const plural &n)
{
os
<<ob.x<<' '<<ob.y<<endl;

return os;
}

//////////////////////////////////////////////////////////////////////////

int main ()
{

plural a(
3,7);
plural b(
4,10);
plural temp
=a+b;
cout
<<temp;

return 0;
}

posted @ 2009-03-18 00:01 abilitytao 阅读(156) | 评论 (0)编辑 收藏

## 已知树的前序遍历和中序遍历，求后序遍历的方法（转）

摘要: /**//*    树中已知先序和中序求后序。      如先序为：abdc,中序为：bdac .      则程序可以求出后序为：dbca 。此种题型也为数据结构常考题型。    ...  阅读全文

posted @ 2009-03-17 18:20 abilitytao 阅读(7259) | 评论 (0)编辑 收藏

## 数据结构作业之二叉树左右子树交换+二叉树高度计算(写的不好还请大家多多指点）

//数据结构作业之二叉树左右子树交换+二叉树高度计算
//学生：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;
}

//////////////////////////////////////////////////////////////////////////

posted @ 2009-03-17 18:08 abilitytao 阅读(2944) | 评论 (4)编辑 收藏

## 数据结构作业——三元矩阵相加

//数据结构作业 三元组矩阵相加C=A+B;
//由于时间所限 这里仅考虑算法内核 不考虑软件容错及外包界面的工作
#include<algorithm>
#include
<cmath>
#include
<cstdio>
#include
<iostream>
#include
<cstring>
using namespace std;
#define  MAXSIZE 10000

struct triple
{

int x,y;

int val;
}
;

struct tripletable
{

triple data[MAXSIZE];

int len,wide,num;
}
;

tripletable a,b;

int result[MAXSIZE][MAXSIZE];

int main ()
{

int i,j;

int p;

cout
<<"                        数据结构作业之 三元组矩阵相加C=A+B ";
cout
<<"                                                                 ——by abilitytao (指导老师：Mr Zhang Hong)"<<endl<<endl;
cout
<<"请输入第一个矩阵的长:";
cin
>>a.len;
cout
<<"请输入第一个矩阵的宽:";
cin
>>a.wide;
cout
<<"请输入矩阵a:"<<endl;
p
=1;
a.num
=0;

for(i=1;i<=a.wide;i++)

{

for(j=1;j<=a.len;j++)

{

int temp;
cin
>>temp;

if(temp!=0)

{
a.data[p].x
=i;
a.data[p].y
=j;
a.data[p].val
=temp;
p
++;
a.num
++;
}

}

}

cout
<<endl<<endl<<"ATTENTION:由于本程序不考虑容错，请确保两个矩阵的长宽相等"<<endl<<endl<<endl;
cout
<<"请输入第二个矩阵的长:";
cin
>>b.len;
cout
<<"请输入第二个矩阵的宽:";
cin
>>b.wide;
cout
<<"请输入矩阵b:"<<endl;
p
=1;
b.num
=0;

for(i=1;i<=b.wide;i++)

{

for(j=1;j<=b.len;j++)

{

int temp;
cin
>>temp;

if(temp!=0)

{
b.data[p].x
=i;
b.data[p].y
=j;
b.data[p].val
=temp;
p
++;
b.num
++;
}

}

}

for(i=1;i<=a.num;i++)

{

result[a.data[i].x][a.data[i].y]
+=a.data[i].val;
}

for(i=1;i<=b.num;i++)

{
result[b.data[i].x][b.data[i].y]
+=b.data[i].val;
}

cout
<<"矩阵相加的结果是:"<<endl;

for(i=1;i<=a.wide;i++)

{

for(j=1;j<=a.len;j++)

{

cout
<<result[i][j]<<' ';

}

cout
<<endl;

}

system(
"pause");

return 0;

}

posted @ 2009-03-16 13:15 abilitytao 阅读(572) | 评论 (0)编辑 收藏

## POJ 1111-Image Perimeters DFS深度优先搜索

if(visit[i][j]==0)了，因为压栈的元素必须是没有考察过的X结点；当然这只不过是基于自己的个人习惯而已，我想，即使你不判断压栈元素，应该也能做出来吧，只不过这样似乎并不符合我们的思维习惯而已；

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

posted @ 2009-03-12 20:47 abilitytao 阅读(1857) | 评论 (1)编辑 收藏

## POJ-1321 棋盘问题—即简化版八皇后问题(dfs深度优先搜索+回溯）

//参考了网络上牛人的代码
#include <iostream>
#include
<algorithm>
using namespace std;

bool row[9];
bool line[9];
bool map[9][9];
int ans;
int sum;
int n,k;

bool check(int i,int j)
{

if(map[i][j]&&row[i]&&line[j])return 1;

else return 0;
}

void dfs(int r)
{

if(sum==k){ans++;return;}

if(r==n+1)return;

for(int i=1;i<=n;i++)

{

if(check(r,i))

{
row[r]
=0;line[i]=0;
sum
++;
dfs(r
+1);
sum
--;
row[r]
=1;line[i]=1;
}

}

dfs(r
+1);
}

int main()
{

int i,j;

char c;

while(cin>>n>>k)

{

if(n==-1&&k==-1)

break;
sum
=0;
ans
=0;

for(i=1;i<=n;i++)

{
getchar();
row[i]
=1;line[i]=1;

for(j=1;j<=n;j++)

{
scanf(
"%c",&c);

if(c=='#')map[i][j]=1;

else map[i][j]=0;
}

}

dfs(
1);
cout
<<ans<<endl;
}

system(
"pause");

return 0;
}

posted @ 2009-03-07 17:44 abilitytao 阅读(1889) | 评论 (1)编辑 收藏