IT,软件
Blog日历

<< 2019 十一月 >>
27 28 29 30 31 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

栏目分类
博客登录
用户:
密码:
最新文章
最新评论
访客留言
在这给我留言吧 >>
友情博客
标签列表
补码 反码 原理 解析 命题逻辑 自动化 JKD5.0 泛型
博客搜索
博客音乐
日志存档
·2006-10 ( 2 )
·2006-9 ( 6 )
·2005-12 ( 1 )
友情链接
统计信息
访问:20402 次
日志:-237篇
评论:0 个
留言:0 个
建站时间:2005-10-3
博客成员
boater 管 理 员





IT,软件
深圳南山
Email:weilai2@163.com

首页 | 留言板 | 注册 | 加为友情博客
今日心情

2006-10-23 星期一(Monday) 晴
几个sql语句

一、逐级向上汇总:
数据表tree,其中code字段表明了在树形结构中该结点的路径,leaf字段指出该结点是否叶子结点,acoumt指出了叶结点的数值。要求写一sql语句统计出各结点所下辖的叶子结点所有数值之和。
create table tree (code varchar(20),leaf int,amount int )
insert into tree values('1001',0,0)
insert into tree values('10011001',0,0)
insert into tree values('100110011001',1,50)
insert into tree values('1002',0,0)
insert into tree values('10021001',0,0)
insert into tree values('100210011001',1,50)
insert into tree values('1003',0,0)
insert into tree values('10031001',0,0)
insert into tree values('10011002',0,0)
insert into tree values('100110021001',1,25)
select * from tree order by code

sql语句如下:
select T.code,amount=(select sum(amount) from tree where code like T.code+'%' and leaf=1)
from tree T.

二、
表a如下:
id . .name . . ...province
1. . . . bear.. . shang xi
2. . . . smith. . hu bei
3. . . . tom. . . bei jing
4. . . . fox. . . hong kong
5. . . . mike. . shang hai
6. . . . jack. . xin jiang
表b是对表a按id值进行的分组:
group2 id1. id2.. id3 . id4
1001. ..2. .4. .. 5.. NULL
1002. ..1. .NULL..NULL NULL
1003. ..3.. 6. .. NULL.NULL

编写一sql使其输出以下内容,其中每一行左侧系group2的值,右侧系对应id的name,province对,各对间以'/'号分隔。
1001 smith hu bei/fox hong kong/mike shang hai
1002 bear shang xi
1003 tom bei jing/jack xin jiang

答案:
select * from a
select * from b
select b.group2,
isnull(a1.name+a1.province+'/','')+
isnull(a2.name+a2.province+'/','')+
isnull(a3.name+a3.province+'/','')+
isnull(a4.name+a4.province,'') as nameAndProvince
from b
left outer join a a1 on b.id1=a1.id
left outer join a a2 on b.id2=a2.id
left outer join a a3 on b.id3=a3.id
left outer join a a4 on b.id4=a4.id



boater 发表于 2006-10-23 22:37 | 分类:未分类 | 评论: 0 | 浏览:470 | 送小红花 推荐指数:0

2006-10-11 星期三(Wednesday) 晴
反码和补码技术是怎样被提出的?

======================1.预备知识。==================
注意:此处的'=='是相等的意思。'='是赋值的意思。
在机器世界里:
正数的最高位是符号位0,负数的最高位是符号位1。
对于正数:反码==补码==原码。
对于负数:反码==除符号位以外的各位取反。
     补码==反码+1.
     原码==补码-1后的反码==补码的反码+1。(读完本文后,应该能够直观地认识到本式的正确性)

可以轻易发现如下规律:
自然计算 :a-b==c.
计算机计算:a-b==a+b的补码==d.
c的补码是d.
通过此法,可以把减法运算转换为加法运算。

所以补码的设计目的是:
1.使符号位能与有效值部分一起参加运算,从而简化运算规则.
2.减运算转换为加运算,进一步简化计算机中运算器的线路设计.

=====================2.灵感由来。=================

概念定义:
还记得初中数学里的“补角”的概念吧。
两数之和等于100时,这两个数叫做互为“补数”,100称做“和数”。
如果B+C==100,则
A-B==A-(100-C)==A+C-100.
可以肯定:A-B=A+B的补数-和数。

把这个方法引入机器世界:
设int是8位整数(最高位是符号位),和数H是9位:1 0000 0000.
a,b是任意两int.
显然,a+a的补码==H,H溢出那个最高位之后就剩下了int值0.
①.输入a-b,
②.机器将a-b化个装后喂给加法器:(a的补码)+(-b的补码),它等于c.
不要忘了,c是一个补码.
③.输出:c的原码.

赋值A=a,B=b后,比较一下:
a-b==(a的补码)+(-b的补码)==c.//此处的c是补码形式。
A-B==A+B的补数-和数==C.//此处的C是数字,可以认为它就是原码形式。
if(C>=0) C==c==c的原码;('=='是相等的意思,并非赋值)
else C==c的原码;

这个“补码”中的“补”,跟初中学的那个“补”是一个意思。
数学中的概念名称真还不是随便定义的,比如“数理逻辑”,故名思义就是:用“数学语言”来理清“逻辑”。
end.



boater 发表于 2006-10-11 22:15 | 分类:软件 | 评论: 0 | 浏览:4043 | 送小红花 推荐指数:0

2006-9-11 星期一(Monday) 晴
命题逻辑的自动化解析

恐怖主义是邪恶的。---9.11


有时候会撞到纯逻辑的推理题,如果能用机器求解的话,事情就会变得相对容易些。人脑必竟是肉做的,跑得过机器吗?
有些推理题是可以自动化解析的。偶(部分地)实现了这个梦想。
1.对命题公式最为机械的解析方式是生成其真值表,以遍历各变元所有可能的结果取值之组合,以及该组合情形下的命题公式的真假。但这可能会造成大量运算,故采用它法。
2.我个人习惯于通过在纸面上画出逻辑树来最终生成各分支均为真的树来。操作中发现:逻辑树产生了大量的分支,若以有向图的形式来表示逻辑分支更为可取。
3.在图中,每一个命题(复合命题,简单命题或命题变元)用一个结点表示
初始状态时,解析代表整个命题公式的结点n。设n=a->^b.当发现其不是变元(有待进一步解析)时,
  将其扩展为平行式:
    a---^b
   ^a--- b
   ^a---^b
  平行式右侧之子系其左侧之变元。左侧ni之子系ni.son.
  然后,以递归方式(以上所述)依次解析平行式右侧之命题。
4.第3步说明了递归解析的方式,在解析中需注意以下几点:
  a.对图结点的遍历与对图中路径的遍历是不同的概念。
  b.一个结点可能系多条路径的交叉点。
  c.若当前结点系变元时,需立即判断在当前逻辑分支中加入此变元后,逻辑上是否归谬(通过全局变量path来判断)。若归谬,需在结点中记录使其归谬时的路径信息(万不可将其删除之)。
  d.当结点无子可遍历或结点归谬时,回退一步。(path.pop()),否则path.push(n);当结点无父时,将其加入root.
5.解析的最终结果是一个图结构。root中存放着图中若干个遍历的起始结点。依次对其中的结点深度优先遍历(遍历时需抛弃已归谬的路径),遍历所得的每一条路径系一个可行的解(即:析取范式中的一个合取项).


(尚未实现对谓词逻辑的解析。)


========================
问题就这样解决了,我们可轻易地加入一点代码,使其实现相关功能。


以下推理题及其解答均系程序自动生成:
a,b,c,d,f,g,h,i,j,k,l,m,n,p,q,r,t 17 个人想进行围棋赛,关于谁参加比赛,下列几个判断是正确的:
1:要么m和r都参加,要么m和r都不参加,
2:要么c参加h不参加,要么c不参加,h参加,
3:不可能q不参加且d参加,
4:要么j和i都参加,要么j和i都不参加,
5:q和r至少有一个不参加,
6:要么d和f都参加,要么d和f都不参加,
7:若t参加,则m必定参加,
8:不可能n不参加且d参加,
9:要么c和f都参加,要么c和f都不参加,
10:若i不参加,则a必定也不参加,
11:要么k参加b不参加,要么k不参加,b参加,
12:不可能j不参加且i参加,
13:要么l参加h不参加,要么l不参加,h参加,
14:要么p参加j不参加,要么p不参加,j参加,
15:不可能g参加且i不参加,
16:要么a参加j不参加,要么a不参加,j参加,
17:不可能n参加且j不参加,
18:g参加,h不参加,
19:要么q,f都参加,要么q,f都不参加,
20:不可能a参加且p不参加,
21:a,b,c,d中至少有一个不参加,
请找出谁参加了比赛。


答案是:
参加者:d,c,g,l,b,q,i,f,j,n;不参加者:t,p,m,h,r,a,k


哼哼,有点意思...


 




boater 发表于 2006-10-10 20:01 | 分类:软件 | 评论: 0 | 浏览:368 | 送小红花 推荐指数:0

2006-9-22 星期五(Friday) 晴
其它

###
我就这命——和地质工作者一样,善于发现、无力开掘。


###
百足之虫,虽死不僵:僵,扑也’。意思是说,一百多条腿的虫子,比如蜈蚣、蚰蜒什么的,死了以后因为腿多支撑着躯体不会扑倒。


###
酒吧里放的是玛丽凯洛的歌曲,忧郁伤感的音调恍如隔世的安魂曲催眠着美丽的夜色。我喜欢玛丽凯洛,并不是因为她性感,只是因为她的歌声有时候懒洋洋的抚摩你,象初恋的爱人那样令你心醉;有时候冷冰冰的拒绝你,象大学时系里最美的姑娘永远不让你靠近。就着歌声下酒,就着歌声起舞,就着歌声晾晒阴郁的感情,安静的夜里,除了各自品尝心事,谁会惦记性感的玛丽凯洛呢?
摘自《支离破碎的北京往事》
http://www1.tianya.cn/new/Publicforum/Content.asp?idWriter=0&Key=0&strItem=free&idArticle=188468&flag=1


###
依我看,北大教授阿忆为走穴作辩解而老实公开自己的工资收入,其实是不应该受到炮轰的。我国教育行业的平均年薪为26661元,在其调查的30多个行业中倒数第三,仅相当于电信行业平均工资的46%。其实国内硕士的平均年薪为66078元,副教授全国的平均水平却不超过45000元。反观国外,以美国的加州大学伯克利分校的助教为例,1999年其平均薪资水平为每年73200美元,远高于其它行业如当时最热门的IT工程师。显然,北大教授的工资收入与北京的消费水平不相称,这样对于留住人才完全没好处!
依他看,北大阿忆公布的支出中一小半都是用于子女教育。这说明北大教授们也是知道教育负担之重的。可是,他们的亲身感受并没有转化为对民生之痛的关注和进言,而只是化为“搞外快”的动力而已。甚至于,他们一方面对中学的“苛捐杂税”不满,一方面却又对高校的高额收费不发一言。他们是中学高收费的抨击者,却同时又是高校高收费的受益者。他们的痛感仅限于私人利益,而没有上升为民生之痛。被人宰时喊活不下去,宰人时恨不得再来一刀,这种人格分裂征兆,让人如何能接受“北大教授哭穷”?


###
音乐有三层基本的共振效应和一层社会效应,一层信息效应。
  1). 物理层次的共振效应:声音的震动频率与细胞体的本征频率或本征频率的n次谐波相接近,使细胞体质产生轻度共振;使人产生一种舒服的感觉。悦耳的声音会使人有一种舒适、安逸感,音律的变化使人的身体有一种充实,流畅的感觉,这就是声音的物理层次的共振效应。它活化了体内的细胞,加快了血液的流动,使得血液在血管中的流动更加流畅了,使得细胞和体液活化程度加强,激活了人的物理层次的生命潜能。----毕家祥  ……


###
          狂暴的007主题曲
  
  我知道如何去伤害。
  我知道如何去倾听。
  我知道该展示什么。
  也知道该掩饰什么。
  我知道何时开口。
  我也知道何时去接触。
  没人会因为欲望过多而死。
  世界并不完美(并不能让人满足)!
  但却有一个如此完美的开端。
  亲爱的人!
  要是你足够坚强。
  我们就能一起分享这个世界。
  我辈中人。
  知道如何去生存。
  生活有何意义,
  如果我们不能感受人生?
  我知道何时该接吻。
  我也知道何时该去杀戮。
  我们得不到的一切。
  别人也休想得到。


###
http://www.xj010.com/bbs/ShowPost.asp?ThreadID=11229
汽车又平稳地行驶在山路上,女司机掠了一下头发,按响了录音机。 车快到山顶,拐过弯去就要下山了,车左侧是劈山开的路,右侧是百丈悬崖。汽车悄悄地加速了,女司机脸上十分平静,双手紧握着方向盘,眼睛里淌出晶莹的泪水。 ……


###
陌生男子把女儿扔下人行天桥……据了解,彭女士26岁,来自湖南湘潭,丈夫任先生是四川人,在广州打工,33岁,月入约2000元。受害的女儿任湘3岁,前天,她刚在广州上了第一天幼儿园。……小任湘脑部受到剧烈撞击,右脑太阳穴部位已明显凹陷,两边不对称,从拍片结果看,其头骨有多处裂缝,有无生命危险尚难定论。据彭女士称,与行凶男子素不相识。


###
北京数人与陌生人闹市拥抱 1小时后被警察带走,为什么?
http://www.ce.cn/xwzx/shgj/gdxw/200610/29/t20061029_9176325.shtml




#matrix::
《黑客帝国》——WHO AM I ?
http://www.tianya.cn/new/Publicforum/content.asp?idwriter=3960966&key=0&idArticle=588571&strItem=no04&flag=1#Bottom
尼奥和设计师的这段对话可以说深奥之极,我在反复琢磨之后终于明白设计师到底告诉尼奥些什么,首先,我们得出一个振聋发聩的结论,锡安也是假的,也是设计师设计的一个 Matrix 而已,莫非斯他们并没有得到真正的自由,他们仍然活在 Matrix 中而并不自知。人类自他们出生的时候,Matrix 分配每个人一个角色.
99% 的人接受这个角色,让这个角色控制他们的大脑。所以与其说这些人是人,还不如说他们只有一个附着在生命体上的一段意识而已,这段意识被 Matrix 所左右。他们没有自主的意识,取而代之控制大脑的是由 Matrix 编写的具有人类意识特征的程序,由于这些人愿意接受分配给他们任何角色,所以他们可以被特工控制思想,被 Smith 复制。
另外 1% 的人他们自主的潜意识如此的强,他们不愿接受 Matrix 分配给的角色,并且能隐约感到有些地方不对劲,开始思考自身存在的方式,这种对 Matrix 分配过来的角色不兼容性,如果不进行控制会导致系统的不稳定和崩溃。因此编写 Matrix 的设计师,编写了一套不同于 Matrix 的另一个系统模拟程序,为了诉说的方便我把他称之为 Matrix2,并给那些自主意识很强的人编写了另外的角色,这些人指的就是片中莫非斯,崔尼悌等叛军。




boater 发表于 2006-09-22 08:51 | 分类:非软件 | 评论: 0 | 浏览:277 | 送小红花 推荐指数:0

2006-9-20 星期三(Wednesday) 晴
JDK5.0的泛型,小例子

以下只是简单举例,权威资料请参见http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
1.
以下代码:
List strList = new ArrayList(); //1
List objList = strList; //2编译错误。
objList.add(new Object()); // 3
String s = strList.get(0); // 4: attempts to assign an Object to a String!
为了防止第4行情况的发生,第2行便会阻止编译。
因为第2行会让人想到向上转型的概念,但这样做的话,第4行的向下转型就可能失败,因为第3行使得strList的属性发生了质变,这是不允许的。

2.
事先并不知c是什么类型,就贸然执行c.add是不对的:
Collection c = new ArrayList();
......
c.add(new Object()); // compile time error
c.get(1);//ok.

再看一个例子:
public void addRectangle(List shapes) {
   System.out.println(shapes.get(0).toString());//ok.
   shapes.add(0, new Rectangle()); //2, compile-time error!
}
为什么出错?因为?代表着某个确定的Shape的子类,但并不保证?的具体类型就是Rectangle.就这样贸然地给shapes增加一个Rectangle是不安全的。


3.
现在我想把一个数组装填到一个集合中去,由上面的示例可知,下面代码是错误的:
static void fill(Object[] a, Collection c) {
    for (Object o : a) {
       c.add(o); // compile time error
    }
}
由最开始的介绍可知,下面的代码也很糟糕,因为它不能接受成员类型为Object子类型的参数:
static void fill(Object[] a, Collection c) {
    for (Object o : a) {
       c.add(o); // compile time error
    }
}
使用下面的代码可以解决这个问题:
 public static void fill(T[] arr, Collection col) {
  for (T o : arr)
   col.add(o); // correct
 }

、T[],可以用来表达各个参数类型之间的关系。上面方法中的T表示了这样一种关系:arr和col必需具有相同的成员类型。

end.




boater 发表于 2006-09-20 19:54 | 分类:软件 | 评论: 0 | 浏览:212 | 送小红花 推荐指数:0

2006-9-8 星期五(Friday) 晴
自动机VS正则式引擎

    本文适用于对自动机有所了解的朋友。

    图的概念太笼统了,我们可以把NFA理解成一颗畸形的树。总体来讲,它有根(初始结点),有叶子(终止结点),但在根与叶子之间,的局部范围内的结点之间,可能会有些循环关系。但在同一分支中的任意二循环体(具有循环结构的部分)之间要么是包含关系,要么是前后承接的关系。NFA就是这样一颗“树”。
也可能是因为NFA把图或树的概念给掩盖了,以至于看不见事物的本来面目。不防试着把NFA,什么x文法,y方法的概念扔到篓子里边儿去,直接把“图”,“树”拿过。画图、画树、画半图半树……然后用程序流程去实现它们。说白了不过一张图,小学生的水彩画红兰白绿,枝枝叉叉,比它繁杂多了!

无聊,写个自动机吧……从构思到编码耗去10天,一个简易的Demo(1.5k行)出炉了。

下面是我提取的程序注释,该程序是一个简易的正则式引擎。如果谁想要,请留Email,顶我贴。

 ==========================a(\w{2,5}|(\D-[^a-g]+)?)*
 功能:
 1. NFA compile(String pattern);根据模式串生成自动机。
 2. boolean match(String input);//匹配输入串。
 3. void print(NFA n);输出自动机状态表,用于调度。
 4. DFA nfa2dfa(NFA nfa); 非确定性自动机到确定性自动机的转换。
 5.
 ==========================
 算法及约定:
   pi是正则式,其中i是p的数量词(重复限制值),当i为空时,p的数量为默认值1。
   p是普通或特殊字符,形如:a,x,\d,\D...等;i形如?,+,*,{2,3}等。
   正则式的n次重复也是正则式。
   圆括号所包括的内容是匹配子组。
   方括号所包括的内容是一个模式,如[^xb-d]表示除x和b~d外的任意一个字符。
   在字符'|'两边的子模式是并列关系的可选子模式.
 0.将(...){2,3}分解成3个结点:①'(' ②'...' ③'){2,3}'.
   将[...]{2,3}分解成3个结点:①'[' ②'...' ③']{2,3}'.
 1.词汇:
   准结点 :指尚未被确是否需要进一步对其分解的结点。
   brance:分支,如..(abc|def)...中的abc,def均是'('的可选的分支(后继)。
   空边转向:
     即在空输入下亦自动产生的转向。结点若存在空边转向的条件,无论当前输入空或非空,均可转向。
 2.所有的结点生成动作均在nextNodes(NFA nfa,Node pre)或traverseWhenCompile(NFA nfa, Node pre)中进行。
 3.一个模式可分前后两部分,后面部分指出了模式的重复次数。若无后部,则不重复。
 4.路径分为单支路径、分支路径,分支路径均以'|'分隔。所有分支路径的父结点必是'('.
    如在...(a|b|c)中,a,b,c之父必是'('.
 5.当遇见方括号结点时,对其后继结点(对应着括号中的内容)用方法NFA.squareBracketMatch(..)进行匹配。
 6.当结点存在后继为'('的结点时,'('必是其唯一后继。
   当'(...){2,3}'被一步解析后,会得到三个结点:a.'(' ; b.'...'; c.'){2,3';
   对于结点']..'或')..',其循环次数限制值所致的转向node.inf信息在所有的相关分支汇合之后(亦即被解析之后)方予以追加。
 7.可以给正则式追加模式,因此也可以给自动机追加自动机。
   新生的转向后集合可能有重复内容,但最终由maybeStatus(HashSet)接受,自然消除重复。
 9.当前结点的转向集合亦应包含其空转向.
   '('的前趋有到'('的空转向,')'的前趋有到')'的空转向。
   '['的前趋有到'['的空转向,']'的前趋有到']'的空转向。
  
 10.对于正则式'a(\w{2,5}|(\D-[^a-g]+)?)*',按照如下方式生成其自动机:
    自动机起始结点为'-1'.
    子模式与结点一一对应。从左至右扫描串,获取一个子模式后,立即产生一个结点n,结点id为该子模式在模式串
中的起始下标。结点用于保存子模式的相关信息及前后继关系(一般来说是左前右后)。
    ')'所对应的结点还应保存跨越多个结点的数量词。
    因为结点的数量词所导致的子模式重复信息是‘有条件的转向',它应当与子模式的前后继关系所产生的转向信息分开存放,分别判断。
    初始时,整个模式pattern就是一个大准结点。经过不断地解析,将会形成一个有起始结点(root)的结点集。这个结点集就是pattern的另一种表现形式:输入及状态转换集。(是吗?)
 11.约定此处的自动机只有一个固定的终结点end,在编译时将实际的终结点空边转向到end即可.
 12.以上的描述可能不够清晰;要理解一个问题还得主要靠自己。
 =========================
 缺点:模块功能抽象得不好,maybeStatus存在冗余状态,大量使用Collection可能使效率低下;语法判断不够严格......Pattern.java是一个借鉴;对递归的运用不够好.

 ==========================
经验:
    模式的自然连接构成更大的模式,自动机也应当方便地实现与其它自动机的连接,当前程序经改良后可以做到这一点。(当连接以后,node.id值会出现重复,这是NFA.nodes所不允许的。这种重复的现象用此法得以消除:第2个自动机的所有id+=第一个模式串的长度。)

    空边转向可能是有前置条件的,并且要重视它对当前可能状态集的影响。

    正则式稍稍写的复杂些,就可看到回溯。此时的匹配就象走迷宫一样,怎样才能走 出去(匹配成功),需要不断地试探着前进,回退,前进,回退……这可能会让初学者一下子理不清头绪,其实象这样一种“探路(试探性匹配)”的操作是容易控制的,在本程序中仅仅引入了“当前可能状态(结点)集”这样一个hashSet就搞定了(需要在匹配的过程中不断地对这个hashSet进行元素的增减操作)。
。这个时候,图就派上用场了:自动机(图)是正则表达式的最易理解,最具有功能上的可扩展性的数据模型。因此,正则式引擎并不直接用正则式字串去匹配输入串,而是先将其信息置入一个图结构(自动机)中去。对于java,这个过程对应着java.utile.regexp包中类的调用:Pattern pat=Pattern.compile(String patternStr);

end.




boater 发表于 2006-09-08 14:05 | 分类:软件 | 评论: 0 | 浏览:589 | 送小红花 推荐指数:0

2006-9-8 星期五(Friday) 晴
编译基础——数学表达式的解析求值的算法小议

使用举例:
double d=Value.doubleOf("pow(2,22-6)");
Value.log(2.2,10);//求以2.2为底10的对数。
Value.loge(2);求2的自然对数。
double[][2] d=Value.doublesOf("12*x -11 100 2");//x from -11 to 100 ,incremnt is 2,output the resultSet.

表达式求值之算法:
1.一个算术表达式(如'-2*-pow(2,3-1)')可划分为下列部分。
   operand  :操作数(数字),当扫描到一个'-'号时,需根据其上下文判断,它是减号还是正负号。
   operator :算术运算符,关系运算符,逻辑运算符。如:+,-,*,/...
   delimeter:界限符,指左右括号或结束符,函数中的逗号等。
   function :函数名.可视其为特殊的运算符。
  运算符和界限符统称为算符。
2.用load(String)函数将表达式各部分(数字,运算符,界限符,函数名)依次装入元素类型为ExpEle 的链。
3.从头到尾扫描链表,
  若找到可对其前后元素(结点)直接求值的操作符结点(+,-,*,/) ,求其值并调整相关的链表结点属性及其前后指向;
  若找到可对其后元素(结点)直接求值的函数结点(ExpEle.att='f'),求其值并调整相关的链表结点属性及其前后指向;
  若均未找到可直接求值的结点,返回链表第一个元素的数据值ExpEle.n,否则重新开始第3步(本步)。
 
4.在扫描中,可以对什么样的函数或运算符所在的上下文(链表中的前后指向)直接解析求值?  当扫描到运算符时,若其前后是数字,且其运算的优先级高于其后运算符的优先级时,可直接对其求值。  当扫描到函数名时,若其上下文中的所有变量均是数字(而非表达式)时,可直接对其求值。
 
判定规则及其它:
1.将表达式装载到链表的过程中,减号前的元素是数字或操作符或‘(’或函数或前前为null时,减号必属于一个数字。
2.左右括号可能连续出现: -12+(-2*3-(-pow(2,2)));-((-2-3)*4-2)*4
3.数字前后必是运算符或界限符。如pow(2,3+2)
4.'-'may be part of num,may be operator.and it's attribute may be

changed in future.
5.解析求值的过程中,若出现冗余的括号,当除之。
6.此算法避免了递归,因此显得繁琐。不确定是好是坏。
  表达式VS递归:
   a.括号中的内容就是一个子表达式(大至整个表达式,小至一个数字,都可视其在一对括号内)
   b.括号中的内容最终会被解析为一个值,我称其为:'准数'最终会被解析为'数'.
   c.如果一个子表达式是'准数',递归解析之,直到无可解析为止。
  我曾试尝试大面积地引入正则式进行表达式的解析,可节省一多半的工作量,但程序运行速度会慢上不止十倍。
 
7.其它:-2.1E-2中的'E'必须为大写。




boater 发表于 2006-09-08 14:03 | 分类:软件 | 评论: 0 | 浏览:1067 | 送小红花 推荐指数:0

2006-9-8 星期五(Friday) 晴
批处理文本编辑器及其命令集的实现,未完成。

1.批处理文本编辑的需求及意义。
2.技术实现。
3.前景。
有待完成。
......



boater 发表于 2006-09-08 14:01 | 分类:软件 | 评论: 0 | 浏览:154 | 送小红花 推荐指数:0

2005-12-19 星期一(Monday) 晴
从n个元素中取k个元素的所有组合及排列


````````/**
```````` *

```````` * 求m取n的所有组合。
```````` * m个数分别为0,1,2...m-1.
```````` * 算法简述:
```````` * 二个组合,若仅有元素顺序不同,视其为同一个组合。
```````` * 左位系低位,右位系高位。
```````` * 按自然的取法取第一个组合(各数位分别是:0,1,2...n-1),以后的所有组合都经上一个组合变化而来:
```````` * 从右至左,找到有增量空间的位,将其加1,使高于该位的所有位,均比其左邻位大1,从而形成新的组合。
```````` * 若所有位均无增量空间,说明所有组合均已被遍历。
```````` * 使用该方法所生成的组合数中:对任意组合int[] c,下标小的数必定小于下标大的数.
```````` *

```````` */
````````public class Combination {
````````````````int n, m;
````````````````int[] pre;//previous combination.

````````````````public Combination(int n, int m) {
````````````````````````this.n = n;
````````````````````````this.m = m;
````````````````}

````````````````/**
```````````````` * 取下一个组合。可避免一次性返回所有的组合(数量巨大,浪费资源)。
```````````````` * if return null,所有组合均已取完。
```````````````` */
````````````````public int[] next() {
````````````````````````if (pre == null) {//取第一个组合,以后的所有组合都经上一个组合变化而来。
````````````````````````````````pre = new int[n];
````````````````````````````````for (int i = 0; i < pre.length; i++) {
````````````````````````````````````````pre[i] = i;
````````````````````````````````}
````````````````````````````````int[] ret = new int[n];
````````````````````````````````System.arraycopy(pre, 0, ret, 0, n);
````````````````````````````````return ret;
````````````````````````}
````````````````````````int ni = n - 1, maxNi = m - 1;
````````````````````````while (pre[ni] + 1 > maxNi) {//从右至左,找到有增量空间的位。
````````````````````````````````ni--;
````````````````````````````````maxNi--;
````````````````````````````````if (ni < 0)
````````````````````````````````````````return null;//若未找到,说明了所有的组合均已取完。
````````````````````````}
````````````````````````pre[ni]++;
````````````````````````while (++ni < n) {
````````````````````````````````pre[ni] = pre[ni - 1] + 1;
````````````````````````}
````````````````````````int[] ret = new int[n];
````````````````````````System.arraycopy(pre, 0, ret, 0, n);
````````````````````````return ret;
````````````````}
````````}

````````/**
```````` *

```````` * 求m取n的所有排列。
```````` * =========
```````` * 方法一、
```````` * 0~999是有1000个数的数列,它是0~9个数中任取3个数且可重复取值时的所有排列。
```````` * 从中去掉有重复值的排列,即为所求排列集合。即,在不断自增1的过程中:
```````` * 利用hash原理来去除重复取数:hash set is int[100] set,
```````` * 欲取k时,if(set[k]==-1) k非重复,可取,
```````` * else k系重复值,不可取。
```````` * 细节问题则复杂了点,请见代码行中的注释。
```````` * 方法二、
```````` * 此方法仅限于全排列。取全排列时,不断地相邻位翻转来获取新组合。
```````` * 这是上面方法(不断地自增1)的变种。因为翻转取得了增值的效果,且避免了重复取值。
```````` *=========
```````` *每一个排列都是在上一个排列的基础上形成的。
```````` *一定要想清楚进位时的细节判断。
```````` *

```````` */
````````public static class Permutation {
````````````````int n, m;
````````````````int[] pre;//previous combination.
````````````````/**
```````````````` * if(set[i]>-1)表示数值i已被取走并被放置到pre[set[i]]中。
```````````````` * else 数值i尚未被取。
```````````````` */
````````````````int[] set;

````````````````public Permutation(int n, int m) {
````````````````````````this.n = n;
````````````````````````this.m = m;
````````````````}

````````````````public int[] next() {
````````````````````````if (pre == null) {//第一个排列。
````````````````````````````````set = new int[m];
````````````````````````````````pre = new int[n];
````````````````````````````````Arrays.fill(set, -1);
````````````````````````````````for (int i = 0; i < n; i++) {
````````````````````````````````````````pre[i] = i;
````````````````````````````````````````set[i] = i;
````````````````````````````````}
````````````````````````````````int[] ret = new int[n];
````````````````````````````````System.arraycopy(pre, 0, ret, 0, n);
````````````````````````````````return ret;
````````````````````````}
````````````````````````int n1 = n - 1, inc = pre[n1] + 1;
````````````````````````/**
```````````````````````` *

```````````````````````` * 从右至左,找到第一个可以增值且不会出现重复值的位n1。
```````````````````````` * 进位时,左侧位无需考虑右侧位的取值情形,但右侧位必需考虑左侧位
```````````````````````` *的取值情形: 若第n1位与其右侧位有重复值,则不算做重复,因为对于本
```````````````````````` *组合,n1位的右侧位将在n1位被确定之后重新计算。
```````````````````````` * 就好比129中的2进位之后,9将变为0.
```````````````````````` *
```````````````````````` */
````````````````````````while (true) {
````````````````````````````````//if(inc未越界&&(数值inc尚未被取||inc系某个右侧位的值)
````````````````````````````````if (inc < m && (set[inc] == -1 || set[inc] > n1)) {
````````````````````````````````````````break;
````````````````````````````````} else if (inc == m) {
````````````````````````````````````````if (n1 == 0)
````````````````````````````````````````````````return null;//所有位均无值可增,说明所有排列均已遍历完毕。
````````````````````````````````````````inc = pre[--n1] + 1;//当前位若增值则会越界,试探其左邻位。
````````````````````````````````} else {
````````````````````````````````````````inc++;
````````````````````````````````}
````````````````````````}
````````````````````````//找到第一个增值位后,设其值。
````````````````````````set[pre[n1]] = -1;
````````````````````````pre[n1] = inc;
````````````````````````set[inc] = n1;
````````````````````````for (int i = n1 + 1, k = 0; i < n; i++) {
````````````````````````````````//将其右侧各位设为最小的,且不会产生重复位的值。
````````````````````````````````while (k < m && set[k] != -1 && set[k] < i) {
````````````````````````````````````````k++;
````````````````````````````````}
````````````````````````````````if (k >= m)
````````````````````````````````````````return null;
````````````````````````````````if (set[pre[i]] >= i) {
````````````````````````````````````````//pre[i]未被左邻位取走时,置set[pre[i]] = -1;.
````````````````````````````````````````set[pre[i]] = -1;
````````````````````````````````}
````````````````````````````````pre[i] = k;
````````````````````````````````set[k] = i;
````````````````````````}
````````````````````````int[] ret = new int[n];
````````````````````````System.arraycopy(pre, 0, ret, 0, n);
````````````````````````return ret;
````````````````}
````````}



boater 发表于 2005-12-19 22:37 | 分类:软件 | 评论: 0 | 浏览:2125 | 送小红花 推荐指数:0

页码:1/-23   

本站域名:http://boater.blog.tianya.cn/