两栏

Microsoft Beta 微软测试网站通行证: Beta ID的列表~~~

Posted by 超级苍蝇 on Oct 13, 2005 in 随风~

https://beta.microsoft.com

 
两栏

Google搜索技巧2005版 (转)

Posted by 超级苍蝇 on Oct 11, 2005 in 随风~

文中涉及的样例往往需要你在 google 英文页面 或者选中 搜索所有网页

 .

 注意:文中[]符号是为了突出关键词,在实际搜索中是不包含的;本文采用的是意译;本译文已经征得作者许可;本译文可任意转载,请保留本文的头信息

  1. 双引号可以用减号代替,比如搜索["like this"]与搜索[like-this]是一个效果

  2. Google不会处理一些特殊的字符,比如[#](几年前还不行,现在可以了,比如搜索[c#]已经可以搜到相应的结果),但是还有一些字符它不认识,比如搜索[t.]、[t-]与[t^]的结果是一样的

  3. Google充许一次搜索最多32个关键词

  4. 在单词前加~符号可以搜索同义词,比如你想搜索[house],同时也想找[home],你就可以搜索[~house]

  5. 如果想得到Google索引页面的总数,可以搜索[* *]

  6. Google可以指定数字范围搜索。搜索[2001..2005]相当于搜索含有2001、2002直到2005的任意一个数的网页

  7. 搜索[define:css]相当于搜索css的定义,这招对想学习知识的人很有效;也可以用[what is css]搜索;对中文来说,也可以用[什么是css]之类的

  8. Google有一定的人工智能,可以识别一些简单的短语如[whenwas Einstein born?]或[einstein birthday]

  9. 通过[link:]语法,可以寻找含有某个链接的网页,比如[link:blog.outer-court.com]将找到包括指向 blog.outer-court.com超级链接的网页(最新的Google Blog Search也支持这个语法),但是Google并不会给出所有的包含此链接的网页,因为它要保证pagerank算法不被反向工程(呵呵,可以参见那两个Google创始人关于pagerank的论文,可下载)

  10. 如果在搜索的关键词的最后输入[why?],就会在结果中出现链接到Google Answers的链接http://answers.google.com ,在里面可以进行有偿提问

  11. 现在出现了一种兴趣活动,叫做Google Hacking,其内容是使用Google搜索一些特定的关键词,以便找到有漏洞的、易被黑客攻击的站点。这个网站列出了这些关键词:Google Hacking Database( http://johnny.ihackstuff.com/index….ule=prodreviews )

12. 在Google 中输入一组关键词时,默认是“与”搜索,就是搜索包含有所有关键词的网页。如果要“或”搜索,可以使用大写的[OR]或 [|],使用时要与关键词之间留有空格。比如搜索关键词[Hamlet (pizza | coke)],是让Google搜索页面中或页面链接描述中含有Hamlet,并含有pizza与coke两个关键词中任意一个的网页。

  13. 并非所有的Google服务都支持相同的语法,比如在Google Group中支持 [insubject:test]之类的主题搜索。可以通过高级搜索来摸索这些关键词的用法:进入高级搜索之后设置搜索选项,然后观察关键字输入窗口中的关键字的变化

  14. 有时候Google懂得一些自然语言,比如搜索关键词[goog], [weather new york, ny], [new york ny]或[war of the worlds],此时Google会在搜索结果前显示出一个被业内称为“onebox”的结果,试试看吧!

  15. 并非所有的Google都是相同的,它因国家版本(或是说语言版本)而异。在US版下,搜索[site:stormfront.org]会有成千上万的结果,而在德语版下,搜索[site:stormfront.org]的结果,嗯,自己看吧。Google的确与各国政府有内容审查协议,比如德国版,法国版(网页搜索),中国版Google新闻

  16. 有时候Google会提示你搜索结果很烂,比如你搜索关键词[jew]试试,Google会告诉你它给出的搜索结果很烂,然后给你一个解释:http://www.google.com/explanation.html

  17. 以前,搜索某些关键词如[work at Google] 时会看到Google给自己打的广告。可以去http://www.google.com/jobs/了解Google的工作

  18. 对于一些“Googlebombed”(大概意思是指Google搜索的结果出问题了)的关键词,会有一个广告链接到:http: //googleblog.blogspot.com/2005/09/googlebombing-failure.html (中国大陆需要代理才能访问)。比如搜索[failure],第一条是美国布什总统介绍

  19. 虽然现在Google还没有支持自然语言,但这里有一段录像显示了支持自然语言的搜索引擎的使用效果:http://blog.outer-court.com/videos/googlebrain.wmv

  20. 有人说在Google中搜索[president of the internet],其结第一条表明了president of the internet是谁,我也是这么认为的,而且你还可以使用这个logo支持本文作者:http://blog.outer- court.com/files/president.gif

  21. Google现在不再有“stop words”(被强制忽略的关键词),比如搜索 [to be or not to be], Google返回的结果中间还列有相关的完整短语搜索结果

  22. 在Google 计算器(http://www.google.com/help/features.html#calculator )中有个彩蛋:输入[what is the answer to life, the universe and everything?]时,会返回42。(关键词翻译过来的意思是指“生命、宇宙和一切的答案”,这是一个著名科幻小说中的情节,详情参见http: //en.wikipedia.org/wiki/The_Answer_to_Life,_the_Universe, _and_Everything)。试试吧,哈哈

  23. 你可以在搜索时使用通配符[*],这在搜索诗词时特别有效。比如你可以搜一下["love you twice as much * oh love * *"] 试试

  24. 同样,你的关键词可以全部都是通配符,比如搜索["* * * * * * *"]

  25. www.googl.com是在输错网址后的结果,也是个搜索网站,但搜索结果与Google完全不同。而且此网站也赚Google的钱,因为它使用Google AdSense

  26. 如果你想把搜索结果限制在大学的网站之中,可以使用[site:.edu]关键词,比如[c-tutorial site:.edu],这样可以只搜索以edu结尾的网站。你也可以使用Google Scholar来达到这个目的。也可以使用[site:.de]或[site:.it]来搜索某个特定国家的网站12. 在Google 中输入一组关键词时,默认是“与”搜索,就是搜索包含有所有关键词的网页。如果要“或”搜索,可以使用大写的[OR]或 [|],使用时要与关键词之间留有空格。比如搜索关键词[Hamlet (pizza | coke)],是让Google搜索页面中或页面链接描述中含有Hamlet,并含有pizza与coke两个关键词中任意一个的网页。

 
5

中文搜索引擎技术揭密:中文分词

Posted by 超级苍蝇 on Oct 9, 2005 in 随风~

中文搜索引擎技术揭密:中文分词

文字内容转载自sunsou 图片来源:baidu


什么是中文分词 

  众所周知,英文是以词为单位的,词和词之间是靠空格隔开,而中文是以字为单位,句子中所有的字连起来才能描述一个意思。例如,英文句子I am a student,用中文则为:“我是一个学生”。计算机可以很简单通过空格知道student是一个单词,但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词,就是中文分词,有些人也称为切词。我是一个学生,分词的结果是:我是一个学生。 

中文分词和搜索引擎

  中文分词到底对搜索引擎有多大影响?对于搜索引擎来说,最重要的并不是找到所有结果,因为在上百亿的网页中找到所有结果没有太多的意义,没有人能看得完,最重要的是把最相关的结果排在最前面,这也称为相关度排序。中文分词的准确与否,常常直接影响到对搜索结果的相关度排序。笔者最近替朋友找一些关于日本和服的资料,在搜索引擎上输入“和服”,得到的结果就发现了很多问题。下面就以这个例子来说明分词对搜索结果的影响,在现有三个中文搜索引擎上做测试,测试方法是直接在Google(http://www.google.com)、百度(http://www.baidu.com)、中搜(http://www.zhongsou.com)上以“和服”为关键词进行搜索:在Google上输入“和服”搜索所有中文简体网页,总共结果507,000条,前20条结果中有14条与和服一点关系都没有。在第一页就有以下错误:
  “通信信息报:瑞星以技术和服务开拓网络安全市场”
  “使用纯HTML的通用数据管理和服务- 开发者- ZDNet …”
  “陈慧琳《心口不一》化妆和服装自己包办”
  “::外交部:中国境外领事保护和服务指南(2003年版) …”
  “产品和服务”等等。第一页只有三篇是真正在讲“和服”的结果。
在百度上输入“和服”搜索网页,总共结果为287,000条,前20条结果中有6条与和服一点关系都没有。在第一页有以下错误:
  “福建省晋江市恒和服装有限公司系独资企业”
  “关于商品和服务实行明码标价的规定”
  “青岛东和服装设备”
  在中搜上输入“和服”搜索网页,总共结果为26,917条,前20条结果都是与和服相关的网页。
  这次搜索引擎结果中的错误,就是由于分词的不准确所造成的。通过笔者的了解,Google的中文分词技术采用的是美国一家名叫Basis Technology(http://www.basistech.com)的公司提供的中文分词技术,百度使用的是自己公司开发的分词技术,中搜使用的是国内海量科技(http://www.hylanda.com)提供的分词技术。由此可见,中文分词的准确度,对搜索引擎结果相关性和准确性有相当大的关系。

中文分词技术 

  中文分词技术属于自然语言处理技术范畴,对于一句话,人可以通过自己的知识来明白哪些是词,哪些不是词,但如何让计算机也能理解?其处理过程就是分词算法。
  现有的分词算法可分为三大类:基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。

  1、基于字符串匹配的分词方法

   这种方法又叫做机械分词方法,它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配,若在词典中找到某个字符串,则匹配成功(识别出一个词)。按照扫描方向的不同,串匹配分词方法可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况,可以分为最大(最长)匹配和最小(最短)匹配;按照是否与词性标注过程相结合,又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下:
   1)正向最大匹配法(由左到右的方向);
   2)逆向最大匹配法(由右到左的方向);
   3)最少切分(使每一句中切出的词数最小)。
   还可以将上述各种方法相互组合,例如,可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点,正向最小匹配和逆向最小匹配一般很少使用。一般说来,逆向匹配的切分精度略高于正向匹配,遇到的歧义现象也较少。统计结果表明,单纯使用正向最大匹配的错误率为1/169,单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统,都是把机械分词作为一种初分手段,还需通过利用各种其它的语言信息来进一步提高切分的准确率。     一种方法是改进扫描方式,称为特征扫描或标志切分,优先在待分析字符串中识别和切分出一些带有明显特征的词,以这些词作为断点,可将原字符串分为较小的串再来进机械分词,从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来,利用丰富的词类信息对分词决策提供帮助,并且在标注过程中又反过来对分词结果进行检验、调整,从而极大地提高切分的准确率。
   对于机械分词方法,可以建立一个一般的模型,在这方面有专业的学术论文,这里不做详细论述。

 2、基于理解的分词方法

   这种分词方法是通过让计算机模拟人对句子的理解,达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析,利用句法信息和语义信息来处理歧义现象。它通常包括三个部分:分词子系统、句法语义子系统、总控部分。在总控部分的协调下,分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断,即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性,难以将各种语言信息组织成机器可直接读取的形式,因此目前基于理解的分词系统还处在试验阶段。

 3、基于统计的分词方法

   从形式上看,词是稳定的字的组合,因此在上下文中,相邻的字同时出现的次数越多,就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计,计算它们的互现信息。定义两个字的互现信息,计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时,便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计,不需要切分词典,因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性,会经常抽出一些共现频度高、但并不是词的常用字组,例如“这一”、“之一”、“有的”、“我的”、“许多的”等,并且对常用词的识别精度差,时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典(常用词词典)进行串匹配分词,同时使用统计方法识别一些新的词,即将串频统计和串匹配结合起来,既发挥匹配分词切分速度快、效率高的特点,又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。
  到底哪种分词算法的准确度更高,目前并无定论。对于任何一个成熟的分词系统来说,不可能单独依靠某一种算法来实现,都需要综合不同的算法。笔者了解,海量科技的分词算法就采用“复方分词法”,所谓复方,相当于用中药中的复方概念,即用不同的药才综合起来去医治疾病,同样,对于中文词的识别,需要多种算法来处理不同的问题。

分词中的难题


  有了成熟的分词算法,是否就能容易的解决中文分词的问题呢?事实远非如此。中文是一种十分复杂的语言,让计算机理解中文语言更是困难。在中文分词过程中,有两大难题一直没有完全突破。

 1、歧义识别

  歧义是指同样的一句话,可能有两种或者更多的切分方法。例如:表面的,因为“表面”和“面的”都是词,那么这个短语就可以分成“表面 的”和“表 面的”。这种称为交叉歧义。像这种交叉歧义十分常见,前面举的“和服”的例子,其实就是因为交叉歧义引起的错误。“化妆和服装”可以分成“化妆 和 服装”或者“化妆 和服 装”。由于没有人的知识去理解,计算机很难知道到底哪个方案正确。

 交叉歧义相对组合歧义来说是还算比较容易处理,组合歧义就必需根据整个句子来判断了。例如,在句子“这个门把手坏了”中,“把手”是个词,但在句子“请把手拿开”中,“把手”就不是一个词;在句子“将军任命了一名中将”中,“中将”是个词,但在句子“产量三年中将增长两倍”中,“中将”就不再是词。这些词计算机又如何去识别?

  如果交叉歧义和组合歧义计算机都能解决的话,在歧义中还有一个难题,是真歧义。真歧义意思是给出一句话,由人去判断也不知道哪个应该是词,哪个应该不是词。例如:“乒乓球拍卖完了”,可以切分成“乒乓 球拍 卖 完 了”、也可切分成“乒乓球 拍卖 完 了”,如果没有上下文其他的句子,恐怕谁也不知道“拍卖”在这里算不算一个词。

 2、新词识别

   新词,专业术语称为未登录词。也就是那些在字典中都没有收录过,但又确实能称为词的那些词。最典型的是人名,人可以很容易理解句子“王军虎去广州了”中,“王军虎”是个词,因为是一个人的名字,但要是让计算机去识别就困难了。如果把“王军虎”做为一个词收录到字典中去,全世界有那么多名字,而且每时每刻都有新增的人名,收录这些人名本身就是一项巨大的工程。即使这项工作可以完成,还是会存在问题,例如:在句子“王军虎头虎脑的”中,“王军虎”还能不能算词?   
   新词中除了人名以外,还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题,而且这些又正好是人们经常使用的词,因此对于搜索引擎来说,分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。

中文分词的应用


  目前在自然语言处理技术中,中文处理技术比西文处理技术要落后很大一段距离,许多西文的处理方法中文不能直接采用,就是因为中文必需有分词这道工序。中文分词是其他中文信息处理的基础,搜索引擎只是中文分词的一个应用。其他的比如机器翻译(MT)、语音合成、自动分类、自动摘要、自动校对等等,都需要用到分词。因为中文需要分词,可能会影响一些研究,但同时也为一些企业带来机会,因为国外的计算机处理技术要想进入中国市场,首先也是要解决中文分词问题。在中文研究方面,相比外国人来说,中国人有十分明显的优势。

  分词准确性对搜索引擎来说十分重要,但如果分词速度太慢,即使准确性再高,对于搜索引擎来说也是不可用的,因为搜索引擎需要处理数以亿计的网页,如果分词耗用的时间过长,会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说,分词的准确性和速度,二者都需要达到很高的要求。目前研究中文分词的大多是科研院校,清华、北大、中科院、北京语言学院、东北大学、IBM研究院、微软中国研究院等都有自己的研究队伍,而真正专业研究中文分词的商业公司除了海量科技以外,几乎没有了。科研院校研究的技术,大部分不能很快产品化,而一个专业公司的力量毕竟有限,看来中文分词技术要想更好的服务于更多的产品,还有很长一段路。 
 
 
 

 
两栏

我用本本装苹果操作系统 – MAC OS X x86 试用

Posted by 超级苍蝇 on Oct 8, 2005 in 随风~
几经周折,我终于在我的DELL I6000上装上了苹果操作系统 – MAC OS X ,而且建立了多系统引导~~
先来看几张图

 
12

回忆 – Baidu百度编程大赛

Posted by 超级苍蝇 on Oct 8, 2005 in 随风~

第一题不很复杂,一般人唰唰唰的几分钟就出来了~~~

第二题求重叠区间大小,数据量很大,题目从文件读入数据,"该文件的行数在1到1,000,000之间",看似很恐怖,但是题目没有时间要求,就不用怕Time Limit Exceeded ,加之当时做题时间也不够了,所以用了最垃圾的算法,直接求。据说,测试数据很弱~~以至于那些想了很好算法,或者用了hash的人貌似很是吃亏~

第三题字符串替换,也是数据量很大,很有百度特色:-P。这题就是把读入的串排排序,然后替换就行了,在没有时间空间要求的情况下,难度不大。

第四题低频词过滤,同样数据量很大,还需要有大规模数据调动的能力。由于是机器调试,所以输出格式不能错一点。

此处只讨论竞赛题目本身……

网上决赛就有点难度了,第一题站点统计。

  第一题(共两题100分)站点统计(50分)
题目描述:
一个Internet站点集合,可以用如下的方式来描述站点和站点之间的链接引用关系:
    s 1 2 3 4
    1 / 4 0 3
    2 3 / 4 5
    3 2 2 / 2
    4 6 1 4 /
其中与s(site)同行和同列的数字都表示站点号,其他每个数字表示一个站点到另一个站点的超文本链接数。如果站点A有到另一个站点B的直接链接或间接(指通过一个或多个直接链接)链接,则称站点A有到站点B的访问关系,或称站点B可以被站点A访问到。例如,上面描述了一个有4个站点链接关系的站点集合,第一行 / 4 0 3 表示站点1到站点1,2,3,4的超文本链接数。
请编写程序:
1) 将一个有N个站点的集合划分成满足下面所有条件的站点子集(这些子集的union组成了该N个站点集合):
    a) 当任一子集中的站点数大于1时,该子集内至少存在一个站点有到该子集内所有其他站点的访问关系;
    b) 当任一子集中的站点数大于1时,该子集内的任一站点至少可以被该子集内的某一站点访问到;
    c) 两个不同子集中的任意两个站点之间不存在任何访问关系。
2) 裁减这些子集内的站点之间现有的链接关系,使得被裁减后的各子集内的站点依然可以满足上述所有条件,同时使得子集内的站点之间的链接总数相加之和为最小。
假如上面的站点集合是这N个站点集合中的一个子集,它满足了条件a):4可以访问到3,也可以访问到2和1;也满足了条件b):站点4可以被站点3访问到,等等。对该站点集合进行裁减使其仍然满足条件a和b,并使得其链接总数之和为最小的结果为:
    s 1 2 3 4
    1 / 0 0 0
    2 0 / 0 0
    3 2 0 / 2
    4 0 1 4 /
这里,站点4可以访问到站点3和2,站点4也可以访问到站点1(通过站点3间接访问);此外,站点3可以访问到站点4;最小链接总数相加为2+2+1+4=9。
   输入数据:
程序读入已被命名为sites.txt的完全如上所示的N*N矩阵的输入数据文本文件,N不大于10万(N即为行数和列数),输入文件的每一行的列和列之间用一个\t分隔,行和行之间用\n分隔。
   输出数据:
按行输出满足题目要求的每个子集内的站点数以及裁减后的最小链接总数之和,数和数之间都以一个空格分隔。如上述子集和最小链接总数为:
1 2 3 4 9
如果输入数据无满足题目要求的子集存在,则输出NONE。
   评分标准:
在结果正确的前提下,会考虑程序的运行时间。我们会用两个不同的输入数据文件(一个简单一个复杂)进行测试,简单的输入数据产生的程序输出结果如果正确,获该题满分的30%即15分(不处理运行时间,除非因程序错误引起的超时运行);复杂的输入数据产生的程序输出结果如果正确,获50%即25分,运行时间满分为20%即10分,按各自程序的运行时间在所有参赛选手的程序的运行时间中所占位置获得相应比例。请仔细阅读并遵守"输入数据"和"输出数据"中的格式要求,如不符合要求,我们的自动评分程序可能会判定程序不正确。

这是一个图,先要求一个子集,感觉不是很复杂。不过后来事实证明我的算法不对,测试数据居然输出NONE~~~晕倒了。后面貌似是要求这个子集所形成的加权有向图的最短路径。查书发现了Dijkstra算法,编了一下,貌似不对,后来针对这个改了一下,貌似就差不多对了。

不过由于前面结果是NONE,以至于没有用武之地~~~~~~可能题目的意思没搞清楚。

不过这道题,最无良的是题目上说了N不大于10万,以至于我相当长的时间在解决数据存储问题~
后来是综合应用了内存和文件,才使其得以支持10万级数据量。我的做法是一定范围内的数据直接读取至内存,超出的直接读文件,看似兼顾了速度和内存~~

最终测试时居然只用了5000*5000的数组!!而我读入内存的数据量阈值是4990,真是巨郁闷~~

long getlinks(long a,long b)
{

return (a<4990?(links[a*n+b]==-1?nolink:links[a*n+b]):readlinksdata(a,b));


 //>4990直接通过文件定位读取
}

不过,我连那个简单数据都没过~~(输出NONE了)也就不说什么了。

第二题相对要简单不少~~不过题目说得太含糊了,很多关键地方表述不清楚,没有ACM ICPC题目的严谨,细致。


   第二题(共两题100分)决策系统(50分)
 
   题目描述:
一个智能决策系统可以由规则库和事实库两部分组成,假定规则库的形式为:
    Ri C1 & C2 & … & Cn->A
表示在条件C1,C2,… 和Cn都满足的前提下,结论A成立(即采取行动A);Ri表示这是规则库中的第i条规则。事实库则由若干为真的条件(即命题)所组成。
对一个新的待验证的命题Q,可使用数据驱动或目标驱动两种推理方式之一,来确认它是否可由某规则库和事实库推出:
1) 数据驱动的推理是指从事实库开始,每次试图发现规则库中某条能满足所有条件的规则,并将其结论作为新的事实加入事实库,然后重复此过程,直至发现Q是一个事实或没有任何新的事实可被发现;
2) 目标驱动的推理是指从目标假设Q出发,每次试图发现规则库中某条含该假设的规则,然后将该规则的前提作为子目标,确认这些子目标是否和事实库中的事实相匹配,如果没有全部匹配,则重复此过程,直至发现新的子目标都为真或不能再验证子目标是否为真。
例如,一个规则库为:
    R1 X & B & E -> Y
    R2 Y & D -> Z
    R3 A->X
事实库为:
    A
    B
    C
    D
    E
如果想知道命题Z是否为真,数据驱动的推理是从A B C D E开始,依次匹配规则R3(得到新事实X),R1(得到新事实Y)和R2,得到Z为真的事实;目标驱动的推理是从假设目标Z开始,依次匹配规则R2(得到新的子目标Y),R1(得到新的子目标X)和R3,得到假设Z为真的结论。
请编写程序正确、高效的实现这两种推理方式。 
   输入数据:
程序需要两个命令行参数:
1) <推理方式>:data|goal,分别表示程序应采用数据驱动的推理或目标驱动的推理;
2) <命题>:如Z。
此外,程序还需读入已被命名为rules.txt的规则库和已被命名为facts.txt的事实库。规则库中的规则可能在千量级,按R1,R2,R3…依次按行排列的,每行一条规则,每条规则都以Ri C1 & C2 & … & Cn->A的形式表示,Ri和C1之间有1个或多个空格,Ci和&之间,Cn和->之间,以及->和A之间可以有0或多个空格。事实库中的各事实之间用1个\n隔开,每行一个事实。
   输出数据:
如果Z能被推理为真,则输出:
TRUE <推理方式:data或goal> <用空格隔开的规则序列:以在所输入的推理方式下,推出该命题为真的规则被激活的顺序排列>
例如:TRUE goal R2 R1 R3
如果Z不能被推理为真,输出:
UNCERTAIN
   评分标准:
在结果正确的前提下,会考虑程序的运行时间。我们会用两组不同的输入数据文件(一个简单一个复杂)进行测试,简单的输入数据产生的程序输出结果如果正确,获该题满分的20%即10分(不处理运行时间,除非因程序错误引起的超时运行);复杂的输入数据产生的程序输出结果如果正确,获40%即20分,运行时间满分为40%即20分,按各自程序的运行时间在所有参赛选手的程序的运行时间中所占位置获得相应比例。两种推理方式各占一半的分数。请仔细阅读并遵守"输入数据"和"输出数据"中的格式要求,如不符合要求,我们的自动评分程序可能会判定程序不正确。
B

这题貌似比较简单一点,不过还是太模糊~

我貌似过了那个15个条件的数据。

最终结果ms是60多名,可能是并列计算的。

 
3

C++可直接使用的排序函数:qsort(),sort()

Posted by 超级苍蝇 on Oct 7, 2005 in 随风~

qsort() 和 sort()

(wysuperfly原创 v1.1)

//基于c++描述 <<将标准 C++ 视为一个新语言>>

使用C++编译器(VC6,G++等)可以使用STL里的sort()函数或者CRT中的qsort()来排序,这么好的函数我居然才知道,真是孤陋阿~总算摆脱整天冒泡的日子了~~~
[注] qsort () 可在任何C/C++编译器里使用。
而sort()函数是标准模板库的的函数可在C++编译器里使用。

赫赫,介绍一下:


使用
#include <iostream>
using namespace std;

开头的,可以直接使用这2个函数,而不用额外包含其他头文件。



qsort()    

.

.

应该就是用的快排。貌似是以数据块的方式移动数据,速度较快。

原型:
_CRTIMP void __cdecl qsort (void*, size_t, size_t,int (*)(const void*, const void*));

解释:    qsort ( 数组名 ,元素个数,元素占用的空间(sizeof),比较函数) 
比较函数是一个自己写的函数  遵循 int com(const void *a,const void *b) 的格式。
当a b关系为 >  <  = 时,分别返回正值 负值 零 (或者相反)。
使用a b 时要强制转换类型,从void * 转换回应有的类型后,进行操作。 
数组下标从零开始,个数为N, 下标0-(n-1)。

示例:

int nn[100],n=100;
int com(const void *a,const void *b)
{
    return *(int*)a-*(int*)b;
}   

qsort((void *)nn,n,sizeof(int),com);

相关:

为什麽你必须给予元素个数?(因为阵列不知道它自己有多少个元素)为什麽你必须给予 double 的大小?(因为 qsort 不知道它要排序的单位是 doubles.)为什麽你必须写那个丑陋的、用来比较 doubles 数值的函式?(因为 qsort 需要一个指标指向某个函式,因为它不知道它所要排序的元素型别)为什麽 qsort 所使用的比较函式接受的是 const void* 引数而不是 char* 引数?(因为 qsort 可以对非字串的数值排序)Bjarne Stroustrup

sort()    

.

.

sort()函数是标准模板库的的函数,已经进行了优化,根据情况的不同可以采用不同的算法,所以较快。

在同样的元素和同样的比较条件下,sort()的执行速度都比qsort()要快。另外,sort()是类属函数,可以用于比较任何容器,任何元素,任何条件。

stl_algo.h 里面找到的:
template<typename _RandomAccessIterator>
    void
    __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

只要开始和结束的地址就可以了。模板可以直接使用很多类型。

示例:

1:上面的程序:
sort(nn,nn+n);即可。

2:比较方便的字符串排序:

   char ch[20]="sdasdacsdasdas\0";
   cout<<ch<<endl;
   sort(ch,ch+14);
   cout<<ch<<endl;


Copyright © 2014 SuperFly-超级苍蝇飞飞飞 All rights reserved. Theme by Laptop Geek.