The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

#

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

 

/*数据结构作业之——哈弗曼树的构造以及WPL的计算;
给出叶子结点的权值,然后求出其WPL 
程序中出现的叶子结点均为正数,并以0结束
*/

//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 简单数学题

本题的题意很简单 :先去掉顶部的7行以及左侧的7列,然后求出剩下的棋盘中有多少个白色方格。
不过有意思的是,我刚开始看这道题的时候居然第一反应是DFS...
#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)=[];


这个代码比我上回写的C++代码短很多。。。。。。看来还是Matlab强大丫 一定要尽快学会才行 :-)

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

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

这道题可以算是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;
}


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

运算符重载的简单研究

在这里值得一提的是 我开始用VC6.0编译这段程序 居然出现编译错误 后来用2005却可编译成功,看来VC6.0对运算符重载的支持还不够完善,看来以后要少用6.0了。(记得它对STL也缺乏支持O(∩_∩)O~)

#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深度优先搜索

以前做过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;
}




 

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)编辑 收藏

仅列出标题
共42页: First 34 35 36 37 38 39 40 41 42