The Fourth Dimension Space

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

#

Reverse Polish Notation-我的原创题目

Reverse Polish Notation


Time Limit: Nolimit


 


Memory Limit: 65536K



Description


标准的表达式如"A+B",在数学上学名叫中缀表达式(Infix Notation),原因是运算符号在两个运算对象的中间。相对应的还有前缀表达式(Prefix Notation),如:"+ - A * B C D",转换成中缀表达式为:"A - B * C + D";后缀表达式(Postfix Notation),比如前所述的中缀表达式转换为后缀表达式为:"A B C * - D +"。为了纪念波兰数学家鲁卡谢维奇(Jan Lukasiewicz),前缀表达式被称作波兰表达式,后缀表达式称为逆波兰表达式(Reverse Polish Notation)。
后缀表达式的优点是显而易见的,编译器在处理时候按照从左至右的顺序读取逆波兰表达式,遇到运算对象直接压入堆栈,遇到运算符就从堆栈提取后进的两个对象进行计算,这个过程正好符合了计算机计算的原理。
后缀表达式比前缀表达式更加易于转换,并且它的最左面一定为数字,这一点在实际编程的时候就会体会到它的好处了。
逆波兰表达式有一个更大的优点,就是拆括号,根据运算符的级别将中缀表达式转换成逆波兰表达式后,运算顺序就已经替代了运算符的级别,这样也避免了括号提高运算级别的特殊处理。
事实上,人的思维方式很容易固定~~!正如习惯拉10进制。就对2,3,4,8,16等进制不知所措一样~~!人们习惯的运算方式是中缀表达式。而碰到前缀,后缀方式。。迷茫其实仅仅是一种表达式子的方式而已(不被你习惯的方式)我这里教你一种也许你老师都没跟你讲的简单转换方式一个中缀式到其他式子的转换方法~~这里我给出一个中缀表达式~a+b*c-(d+e)
第一步:按照运算符的优先级对所有的运算单位加括号
~
        式子变成拉:
((a+(b*c))-(d+e))
第二步:转换中缀与后缀表达式

        后缀:把运算符号移动到对应的括号后面
        则变成拉:((a(bc)*)+(de)+)-
        把括号去掉:abc*+de+-  后缀式子出现

发现没有,前缀式,后缀式是不需要用括号来进行优先级的确定的。
现在,你需要用计算机来实现这一过程,怎么样,是否有兴趣一试呢?如果答案是肯定的话,Let‘s go!

 


Input


按照人们日常的输入习惯,请输入一个带浮点型带括号的中缀表达式(不需要添加等号)。


输入的算式可以包含整数,小数,+,-,*,/,(,)这几种类型,


当然,为了体现和谐社会的客观要求及人文关怀,你可以假设这个算式的总字符长度小于100字节。


Output


输出与此中缀表达式对应的逆波兰表达式,为了区分数字,请将数字与数字或字符与字符以空格隔开。


最后一个字符后不需要添加空格,各组测试数据之间请用空行隔开。(输出到文件尾)


Sample Input


1.5+2.5*3-4+5


1*2+3/4


Sample Output


1.5 2.5 3 * + 4 5 + -

 


 


1 2 3 + * 4 /


Source


Weitao(伟涛) 's first submitting problem for njust ACM team;

 

posted @ 2009-02-19 13:02 abilitytao 阅读(1128) | 评论 (0)编辑 收藏

POJ 1088 动态规划之经典问题——滑雪

动态规划之经典问题——滑雪解题报告

                                           

原题链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1088

Description

Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

Sample Output

25

个人心得:记得前段时间曾经做过一个求最长下降子序列的题(相信大家都做过该题,故不另附原题),如果说说那道题是dp问题的基础,那么这道题就可以称得上是求最长下降子序列的变种或者更确切的说是一种升华!

对比来看,前者是求最长下降子序列在一维条件下的解,而1088滑雪这道题则是将此下降问题至于二维平面的背景下。相信弄明白这道题是非常有必要的,因为它不仅升华了我们对该类问题的理解,而且能启发我们用同样的思维方式去解决更多动态规划的问题。

 

 

题目意思其实很简单,给出一个二维数组,在其中找出一个点,是它能找到一条高度依次下降的路径并使得这条路径最长。

算法:开一个二维数组height记录每个点的高度,一个二维数组len记录每个点能搜索到的最长下降子序列的长度(初始值全为零),一个结构体数组dot line[20000]记录每个点的坐标(x,y)和高度值 h.

先将每个点的记录信息保存在结构体数组中。然后以高度由低到高的顺序排序,初始状态下指针就位于结构体数组的起始位置。

接着顺序的扫描此结构体数组内的信息,因为已经排好序,所以高度是一次递增的,这样做的好处是只需要朝着一个方向搜索,而且还可以有效避免越界的问题。

当指针每指向一个结构体个体时,我们均可以找到该点在height数组里的位置,如果存在任意一个点,在它周围的四个方向上而且高度比该点大且这个任意点的最长下降子序列小于或等于该店的长度。那么这个任意点的最长下降子序列的长度就+1;

等到结构体数组扫描完成,再去遍历len这个二维数组,求出最大值即为所求;

 

 

 

CODE:

 

#include<iostream>

#include
<cmath>

#include
<cstring>

#include
<cstdio>

#include
<algorithm>

using namespace std;

 

 

struct dot//创建一个结构体存储每个点的信息

{

    
int x;

    
int y;

    
int h;

}
;

dot line[
20000]; //将每个点存入该结构体数组

int height[120][120]; //用于存储input

int len[120][120];  //dp数组,存储每个点的最优解

int cmp( const void *a ,const void *b) //快速排序的参考函数

{

 

    
if((*(dot *)a).h>(*(dot *)b).h)

        
return 1;

    
else return -1;

 

}


int main ()

{

    
int m,n;

    cin
>>m>>n;

    
int i,j;

    
int flag=-1;

    
int max=0;

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

    
{

 

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

        
{

            flag
++;

            scanf(
"%d",&height[i][j]);

            line[flag].x
=i;

            line[flag].y
=j;

            line[flag].h
=height[i][j];

        }


    }
 //这个双层循环用来完成数据收集的工作

    qsort(line,m
*n,sizeof(line[0]),cmp); //对结构体的h参数进行排序

    
for(i=0;i<m*n;i++)

    
{

    
if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y+1]&&len[line[i].x][line[i].y]>=len[line[i].x][line[i].y+1])

        
{

            len[line[i].x][line[i].y
+1]=len[line[i].x][line[i].y]+1;

        }


    
if(height[line[i].x][line[i].y]<height[line[i].x+1][line[i].y]&&len[line[i].x][line[i].y]>=len[line[i].x+1][line[i].y])

        
{

            len[line[i].x
+1][line[i].y]=len[line[i].x][line[i].y]+1;

        }


    
if(height[line[i].x][line[i].y]<height[line[i].x][line[i].y-1]&&len[line[i].x][line[i].y]>=len[line[i].x][line[i].y-1])

        
{

            len[line[i].x][line[i].y
-1]=len[line[i].x][line[i].y]+1;

        }


        
if (height[line[i].x][line[i].y]<height[line[i].x-1][line[i].y]&&len[line[i].x][line[i].y]>=len[line[i].x-1][line[i].y])

        
{

            len[line[i].x
-1][line[i].y]=len[line[i].x][line[i].y]+1;

        }


    }
 //动态规划过程

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

    
{

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

        
{

 

           

            
if(len[i][j]>max)

                max
=len[i][j];

        }


    }
 //遍历len数组,求出最大值

    cout
<<max+1<<endl;// 因为初始值是0,所以最后要加一

    
return 0;

}


 

 

最后不得不说,动态规划的确是一个值得研究的问题,相比于递归,他能够节省大量的运行时间。

鉴于现在还处于学习的初级阶段,如果有所不足,还请老师和学长们多多指点.

Thank you~

posted @ 2009-02-19 13:00 abilitytao 阅读(10264) | 评论 (13)编辑 收藏

带括号浮点型计算器final

     摘要: 课程设计一:                                &n...  阅读全文

posted @ 2009-02-19 01:12 abilitytao 阅读(2042) | 评论 (3)编辑 收藏

线性表类——张宏数据结构第一课

晚上花了2个多小时写的,感觉不是很难,下次尝试下写成链表+模板的形式 O(∩_∩)O~

#include<iostream>
#include
<algorithm>
using namespace std;

#define LISTVOLUME 10000


class sqlist
{
private:
    
int a[10001];
    
int lenth;
    
int max;
public:
    sqlist()
    {
        memset(a,
0,sizeof(a));
        lenth
=0;
        max
=LISTVOLUME;


    }
    
void initial();
    
void creat();
    
void print();
    
void inset(int num,int pos);
    
void deletenode(int pos);
    
void sortlist();
    
int size();
    
bool empty();
    
bool full();
    
void findnode(int num);


};


void sqlist::initial()
{
    memset(a,
0,sizeof(a));
    lenth
=0;
    max
=LISTVOLUME;
}
void sqlist::creat()
{

    cout
<<"请顺序键入链表中的数值,用空格隔开,并以'-1'结束"<<endl;
    
int pos=1;
    
int temp;
    
while(cin>>temp)
    {
            
if(temp==-1)
            
break;
        
if(lenth>=LISTVOLUME)
        {

            cout
<<"抱歉,线性表已满,无法输入数据,请重新初始化该数据表"<<endl;
            cout
<<"请问需要重新初始化吗?(Y/N)"<<endl;
            
char temp;
            cin
>>temp;
            
if(temp=='Y'||temp=='y')
            {

                initial();
                creat();
                
break;
            }
            
else
                
break;
        }

    
        a[pos]
=temp;
        pos
++;
        lenth
++;

        

    }

}

void sqlist::print()
{

    
int i;
    
for(i=1;i<=lenth;i++)
    {

        cout
<<a[i]<<' ';

    }
    cout
<<endl;

}

void sqlist::inset(int num, int pos)
{

    
if(lenth>=LISTVOLUME)
    {

        cout
<<"数据表已满,无法添加数据"<<endl;
        
return;
    }
    
if(pos<1||pos>lenth+1)
    {

        cout
<<"您输入的位置不合法,请重新输入(仅需要输入插入的位置):";
        cin
>>pos;
    }
    
int i;
    
for(i=lenth;i>=pos;i--)
    {
        a[i
+1]=a[i];
    }
    a[pos]
=num;
    lenth
++;

}

void sqlist::deletenode(int pos)
{
    
if(pos<1||pos>lenth)
    {

        cout
<<"您输入的位置不合法,请重新输入";
        cin
>>pos;
    }
    
int i;
    
for(i=pos+1;i<=lenth;i++)
    {

        a[i
-1]=a[i];

    }
    a[lenth]
=0;
    lenth
--;
    cout
<<"成功删除"<<pos<<"号结点"<<endl;
}

void sqlist::sortlist()
{

    
int temp;
    cout
<<"请问您需要从小到大排列(键入1)还是从大到小排列(键入-1)"<<endl;
    cin
>>temp;
    
if(temp==1)
        sort(a
+1,a+1+lenth);
    
else if(temp==-1)
    {

        sort(a
+1,a+1+lenth);
        reverse(a
+1,a+1+lenth);

    }
    cout
<<"排序完成"<<endl;
}
int sqlist::size()
{
    
return lenth;
}

bool sqlist::empty()
{

    
if(lenth==0)
        
return true;
    
else
        
return false;
}

bool sqlist::full()
{

    
if(lenth>=max)
        
return true;
    
else
        
return false;

}

void sqlist::findnode (int num)
{

    
int i;
    
for(i=1;i<=lenth;i++)
    {

        
if(a[i]==num)
        {
            cout
<<"该元素位于"<<i<<"号位置"<<endl;
            
return ;
        }


    }
    cout
<<"没有搜索到改元素,请重新查找"<<endl;
}





int main ()
{
    sqlist test;
    
int m,n;
    cin
>>m>>n;
    test.creat();
    test.print();
    test.initial();
    test.creat();
    test.print();
    test.inset(m,n);
    test.sortlist ();
    test.deletenode(
3);
    test.findnode(
3);
    
return 0;

}



posted @ 2009-02-19 00:51 abilitytao 阅读(967) | 评论 (3)编辑 收藏

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