2007年8月15日星期三

ASP.Net 学习之返回上一页的实现方法

返回上一页的这个东东在我们做项目的时候一般是用于填写完表单后确认的时候,有对原来输入的数据进行修改时用的,或者是因为网站为了方便浏览者而有心添加的一个东东,一般这种功能的实现在ASP.net中都是用一个button的控件来实现的,实现的方法有很多,今天恰好在做项目时碰到要用这个东东,我就把能实现" 返回上一页","返回前一页"的几种方法总结了一下,供大家学习之用,请多多指教:0)

其实要实现这个功能主要还是要用到javascript

方法一:
在asp.net的aspx里面的源代码中
<input type="button onclick="javascript:window.history.go(-1);"value="返回上一页">

浅析:这个是用了HTML控件,通过一个onclick的事件,调用了javascript中的一个方法就可以了。这个是最简单的了,也同样适用于静态页面,ASP页面等。

方法二:

利用Reponse.write
如果你对ASP有一定的了解,那么对Response.write这个东东就不会陌生了,方法一是直接有HTML页面中实现,则这个则是在后台环境中实现(这个说法好像不是很规范,呵呵)

Response.write("<script language=javascript>history.go(-2);</script>)

<a href="#" onclick="javascript:history.back();">返回前一页</a>


这里为会么要采用-2的值呢,我个人认为是这样的:因为在asp.net中的页面,当你按下一个button后,由于页面中会实现page.postback的缘故,实际上在这其中是刷新了两次页面,我们要的是第一次的,所以就......


方法三

利用Response.Redirect() 或 server.transfer()


在page_load中加入
if(!IsPostBack)
ViewState["retu"]=Request.UrlReferrer.ToString();

而在在返回按钮事件中
Response.Redirect(ViewState["retu"].ToString());
或Server.Transfer (ViewState["retu"].ToString());


浅析:
Request.UrlReferrer可以获取客户端上次请求的url的有关信息,我们在使用这个的时候最好对其进行一个判断

if(ViewState["UrlReferrer"]!=null)

Response.Redirect(ViewState["UrlReferrer"].ToString();

else
{
Response.write("对不起,当前是最前页码“);


这样才好使一点点喔
}

在使用Request.UrlReferrer时还要注意:
1. 如果上一页面使用document.location方法导航到当前页面,Request.UrlReferrer返回空值
2. 如果有A,B两个页面,在浏览器中直接请求A页面,在A页面的中Page_Load事件中导航到B 页面,则 Request.UrlReferrer返回空。因为 在Page_load事件中页面还未初始化,所以无法记录当前页的信息,导航到b页面也就无法获得上一页面的信息
3. 点击刷新按钮不会改变Request.UrlReferrer



方法四:

这个方法估计很少人用,不过我试了一下,也还很不错喔

在button的onClick事件中输入

this.RegisterClientScriptBlock("e", "<script language=javascript>history.go(-2);</script>");

一样可以 返回到上一页


方法五

这种方法也比较麻烦,不建议大家使用,这个好像是ASP里面的。

<a href=<%=request.servervariable("http_Referre)%>

<asp:image id="imageback" visible = true" imagurl="上一页" runat="server"/></a>

转载:


Powered by ScribeFire.

2007年5月31日星期四

Astar2007 初赛第二阶段题

由于第二场初赛没有参加,所以从NINSTEIN'S BLOG转贴了这场比赛的题目。唉 看看吧~

1.百度时间

Baidu的服务器上使用的不是北京时间,而是Baidu时间。Baidu时间的时分秒与北京时间相同,但是日期与北京时间不同,是用一个正整数表示从2000年1月1日开始经过了几天。



现在就请大家设计一个程序将北京时间转换为百度时间。在本题中,闰年的年份是400的倍数,或者是4的倍数但不是100的倍数。比如2000和8888均为闰年,但6100不是。

输入格式

输入数据的每一行为一个待转化的北京时间(不含空格和TAB),正确的格式包括两种:

一种为:YYYY-MM-DD,(YYYY表示四位数年份,MM为两位月份,DD为两位日期);

另一种为:MM/DD/YYYY,(YYYY表示四位数年份,MM为两位月份,DD为两位日期);

输出格式

每个数据输出一行。如果可以成功转换,输出一个正整数,否则输出Error。

输入样例

2000-01-01

AStar2007

05/26/2007

输出样例

0

Error

2702

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有5个测试数据集,数据1和数据2中的所有日期均能成功转换。所有数据中,每行不超过20个字符,每组数据最多包含100行;

  4. 该题目20分。

2.实习生小胖的百度网页过滤器

百度网页采集器(Baiduspider)每天从互联网收录数亿网页,互联网的网页质量参差不齐。百度的工程师们每天都在改进方法来判断一个网页质量的好 坏,使质量差的网页出现在检索结果中较后的位置。现在实习生小胖想到一个很简单的方法来判断一个网页内容的好坏,方法如下:

1. 利用数据挖掘技术在互联网语料库中挖掘出一批有特点的词汇,分为好词和坏词两种,好词标上正的权重,坏词标上负的权重;

2. 通过好词和坏词词典对每个网页计算网页总权重:从第一个字开始匹配,找到一个好词则加上相应的权重,找到一个坏词则减去相应的权重,下一次匹配将从找到的词末尾的下一个位置开始。

3. 坏词采用正向最短匹配:从当前匹配位置开始的若干连续汉字,如果形成多个坏词,则只计算最短的那个坏词的权重,下一次匹配将从这个最短坏词末尾的下一个位置开始。

4. 好词采取正向最长匹配:从当前匹配位置开始的若干连续汉字,如果形成多个“有效”好词,则只计算最长“有效”好词的权重,下一次匹配从这个最长“有效”好词末尾的下一个位置开始。

5. “无效”好词的定义:好词的一部分本身是一个坏词;或者好词的一部分与后续相邻的若干字组成一个坏词。

现在小胖已经做好了第1步的工作,有一个好词和坏词的列表(词典),但是由于没有对中文文本处理的程序经验,他想请未来的百度之星们帮他完成这个程序。

 

输入格式

输入第一行为一个字符串(网页正文)。从第二行开始为词典,格式为“词 空格 词的权重”。权重为一个带符号32位整数。如果权重为正,则为好词,反之则为坏词;不存在重复的词,不存在权重为0的词。

作为“网页”的字符串中同时包含中文和ASCII字符,每个汉字占2个字节。并非“网页”中的所有字都在词典中。

输出格式

输出仅一行,为网页总权重(答案保证不超过带符号32位整数的范围)。

样例输入

小胖之喷火龙骑士!!

小胖 6

喷火 -1

喷火龙 -1

火龙 -1

龙 4

龙骑 3

龙骑士 2

骑士 -2

士 3

样例输出

7

样例解释

从“网页”中找到的好词为“小胖”和“龙”,坏词为“喷火”和“骑士”。特别要说明一下“龙” 被识别为好词的原因——“喷火”和“喷火龙”均为坏词,按正向最短匹配得到“喷火”,接着往下匹配到好词“龙”、“龙骑”和“龙骑士”,但是由于“骑士” 是坏词,所以“龙骑”、“龙骑士”无效而“龙”是最长的有效好词。注意题目描述中的匹配规则,好词的“有效”和“无效”只考虑该好词的一部分与后续字是否 能够组成坏词,而不考虑和前面的字是否能够组成坏词——样例中的“龙”虽然可以与前面的字组成坏词“喷火龙”和“火龙”,但由于这两个词都是未能匹配成功 的坏词,因此对好词“龙”的词性没有影响,可以累积“龙”的权重。

注意事项

输入数据的中文采用GBK编码。

GBK: 是又一个汉字编码标准,全称《汉字内码扩展规范》。采用双字节表示,总体编码范围为 8140-FEFE,首字节在 81-FE 之间,尾字节在 40-FE 之间,排除xx7F。总计 23940 个码位,共收入 21886 个汉字和图形符号,其中汉字(包括部首和构件)21003 个,图形符号 883 个。

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有10个测试数据集,前7组数据的大小不超过1K字节,数据8和数据9不超过600K字节,数据10的网页正文不超过1M字节。所有数据的词典不超过50,000项,且词典中的词保证由1到5个汉字组成。词典不包含重复的单词;

  4. 该题目20分。

3.Wii游戏开始啦!

为了在紧张的上班时间让员工们轻松些,百度休息室里放置着按摩椅、CD、高尔夫套装和Wii游戏机等休闲用品。其中最受欢迎的当然是游戏机。



Wii游戏机有两个手柄,每个手柄使用两节电池(这两个电池可以是不同的品牌),其中至少一块电池没电时该手柄没电。



工程师们在玩游戏时,总是用最简单的方式更换电池:有手柄没电时把所有没电的电池拿走,一一换上新电池即可(有电的电池总是继续使用)。当有手柄没电且没有新电池可用时才停止玩Wii。



告诉你每个品牌电池的使用时间以及该品牌电池的个数,请计算工程师们玩游戏时间的最小值和最大值。

输入格式

输入第一行为一个正整数n,表示电池的种数。接下来n行,每行两个整数L和F,表示使用时间为L的电池有F个(电池不必成对出现,即F可以是奇数)。

输出格式

输出仅一行,包含两个整数,分别表示工程师们的最短游戏时间和最长游戏时间(短的时间在前)。两个整数之间以空格隔开。

输入样例

3

3 2

5 2

8 2

输出样例

5 8

样例解释

有三对电池,使用时间分别为3小时、5小时和8小时。

方案1:一开始给手柄1使用一对3小时的电池,给手柄2使用一对5小时的电池,则3小时后手柄1没电,换上一对8小时的。再过2小时后,手柄2没电。此时已经没有电池可用了。总时间为5小时。

方案2:一开始给手柄1使用一对8小时的电池,给手柄2使用一对5小时的电池,则5小时后手柄2没电,换上一对3小时的。再过3小时后,手柄1和手柄2同时没电。此时已经没有电池可用了。总时间为8小时。

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过2秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有15个测试数据集,均满足n<=10, L<=200, F的总和不超过30;

  4. 该题目30分。

4.百度的高级搜索方法

你尝试过在百度上使用site inurl语法查询吗? 如果还没有的话可以试一下:)

如输入 site:www.baidu.com inurl:news

则会搜出所有在www.baidu.com站点上的包含"news"子串的url。



现在我们有一个inurl查询列表和一个url列表,你能找出所有至少被查询过一次的url吗?

输入格式

输入第一行是一个整数n,表示一共有n个查询。以下n行每行一个查询。查询的site部分和inurl部分中间恰好用一个空格分割,且每行不包含其他空格。下一行是一个整数m,表示url列表中一共有m个url。以下m行每行一个url。

输出格式

每个url输出一行。如果至少符合一条查询,输出1,否则输出0。

输入样例

3

site:www.baidu.com inurl:/more

site:zhidao.baidu.com inurl:/browse/

site:www.sina.com.cn inurl:www20041223am

7

http://www.baidu.com/more/

http://www.baidu.com/guding/more.html

http://www.baidu.com/events/20060105/photomore.html

http://hi.baidu.com/browse/

http://hi.baidu.com/baidu/

http://www.sina.com.cn/head/www20021123am.shtml

http://www.sina.com.cn/head/www20041223am.shtml

输出样例

1

1

0

0

0

0

1

评分规则

  1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过2秒,否则该用例不得分;

  2. 要求程序能按照输入样例的格式读取标准输入数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;

  3. 该题共有6个测试数据集,数据1,2,3,4,5,6的大小分别约为4K, 750K, 1.5M, 6.5M, 12M, 18M。所有查询和url均合法,url均以http://开头。url和查询中可能包含中文。输入文件的每行不超过256个字节;

  4. 该题目30分




Technorati Tags:



Powered by ScribeFire.

2007年5月29日星期二

很失望的说

Astar2007的初赛结束了。结果很让人失望了~~唉。去年的比赛题还能看得懂,今年的题目就......看来离程序员的距离还是十分遥远的啊~2个小时4道题,结果2个小时一晃就过去了,而题目却一题也没有作o(∩_∩)o暑假~~恶补C,C++,VC++看来是势在必行的了。另外,继续关注复赛和决赛的题目。回去自己练练手了~~唉~~



Technorati Tags:



Powered by ScribeFire.

My Princess

呵呵,My girl。估计没人会说不漂亮吧?嘿嘿
Posted by Picasa

2007年5月28日星期一

Astar2007初赛第一阶段题

1.水果开会时段
每个百度工程师团队都有一笔还算丰裕的食品经费,足够每天购置多种水果。水果往往下午送达公司前台。前台的姐姐们只要看到同时出现五种或以上的水果,就称之为“水果开会”。
从 搜索引擎切词的语法角度,只要两种水果的名字中有一个字相同就属于同样的类别。例如“小雪梨”和“大雪梨”是同一种水果,而“核桃”和“水蜜桃”也被认为 是同一种水果。尤其要指出的是,如果有三种水果x, y, z同时在前台出现,且x和y是同一种水果,y和z也是同一种水果的时候,x和z在此时也被认为是同一种水果(即使x和z并不包含相同的字)。现在前台的姐 姐们想知道,今天是否有“水果开会”——五种或更多的水果同时在前台出现。
输入格式
输入的第一行只有一个整数n,表示购置水果的组数。接下来的n行表示水果的到达时间、取走时间(时间用1200到1900之间的正整数表示,保证取走时间 大于到达时间)。剩下的字符串以空格分割每一种水果。如“1400 1600 雪梨 水蜜桃”,表示下午两点到四点(包含两点和四点这两个时间点),雪梨和水蜜桃会在前台等待开会。每种水果名称由不超过十个汉字组成。
输出格式
输出仅一行,包含一个字符串Yes或No,分别表示今天水果开会与否。
输入样例1
3
1200 1400 雪梨 柠檬
1300 1400 西瓜 苹果
1400 1800 花生 水蜜桃
输出样例1
Yes
输入样例2
3
1200 1400 雪梨 柠檬
1400 1500 哦 大梨 呀
1500 1800 咦 大梨
输出样例2
No
样例解释
在样例1中,时刻1400有六种水果在前台;在样例2中,由于雪梨和大梨在任何时刻都是同一种水果,最多只有四种水果同时在前台。
评分规则
1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;
2. 要求程序能按照输入样例的格式读取数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;
3. 该题共有10个测试数据集,每组数据均满足n<=10,每个时段最多有10个水果,一共不超过50个水果;
4. 该题目20分。

2.大话西游与数字游戏
“叉烧鸡翅膀,我呀最爱吃!……”
百度spider组的“黑龙潭之行”在烤着鸡翅,唱着星爷的经典时达到高潮。大家在篝火旁围成一圈,开始玩“数7”加强版游戏,规则如下:
规则1:遇7的倍数或含7的数时pass。
规则2:遇有包含相同数字的数时pass。注意相同数字不必相邻。例如121。
数错的惩罚很残酷——吞食烤全羊。为避免惩罚,百度工程师们需要你——史上最强程序员的帮助。百度工程师想知道:
req1 x:符合规则1的第x个数是什么?
req2 y:符合规则2的第y个数是什么?
req12 z:同时符合规则1、2的第z个数是什么?
query n:数n是规则1中的第几个数,是规则2中的第几个数?
输入格式
输入的每一行为一个查询,由一个查询词和一个无符号整型数组成。共有四种查询,查询词分别为req1、req2、req12、query(区分大小写)。
输出格式
前三种查询输出一个无符号整型的解。对于“query n”的查询,若n是规则中的数则输出相应的解,否则输出-1。
输入样例
req1 10
req2 10
req12 10
query 14
输出样例
11
10
12
-1 13
评分规则
1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过1秒,否则该用例不得分;
2. 要求程序能按照输入样例的格式读取数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;
3. 该题目共有10个测试数据集,其中数据1~5主要考查正确性,满足x,y,z,n<=1000;输入6~10主要考查时间效率, 满足x<=10,000,000,y<=1,000,000,z<=240,000,n<=20,000,000。数据1和6只 包含req1,数据2和7只包含req2,数据3和8只包含req12,数据4和7只包含query,数据5和10包含全部四种查询。每组数据都恰好包含 100个查询。
4. 该题目20分。

3.繁忙的会议室预定问题
百度由最开始的7人团队迅速发展为几千人的大团队,而工程师们经常需要在一起进行“头脑风暴”,这样会议室就成了紧缺资源。为了有效利用资源,大家决定制定规则, 自动安排会议室的使用。
为了公平起见,应按照申请时间从早到晚依次考虑,先到先得,且申请一旦被接受就不能取消。在处理每条请求时,只要当前请求可以和前面已接受的所有请求同时满足时就必须被接受(如有必要,可以调整给已接受申请安排的会议室和开会时间)。注意同一时间开的不同会议必须在不同的会议室,而同一个人不能同时参加两个会议。
输入格式
输入第一行为会议室总数n和请求总数m;第二行是n个整数,表示会议室能够容量的人数。以下m行每行是一个请求,按请求时间先后顺序排列(即应优先满足在输入中更早出现的请求)。
每个请求中第一个是整数,表示会议需要的时间长度(单位:小时);之后为与会人名单。人名由不超过四个汉字组成,用半角逗号分隔(每人名字固定且唯一,有 重名的也在登记时区分开)。名单后的数字表示可以安排会议的时间,也以半角逗号分隔,如 10,11,14,15 表示第10, 11, 14, 15个小时可以开会(会议时间为9到19之间的正整数)。
输出格式
输出m行,依次表示每个请求是否被接受。1表示接受,0表示不接受。
输入样例:
2 4
20 2
3 张三,李四,王五 10,11,12,14,15
1 张三 12
4 王六,王七,王八,王九,王十 9,10,11,12,13,14,15
2 张三 14,15
输出样例:
1
0
0
1
样例解释
请求1可以满足,因此接受;在请求1接受的前提下请求2和请求3都无法满足,因此不接受。请求1和请求4可以同时满足(都在会议室1,前者用时间 10~12,后者用时间14~15)。需要特别注意的是:如果没有请求1,后三个请求可以同时满足。但是规则是先到先得,请求1只要可以满足就必须接受。
评分规则
1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过2秒,否则该用例不得分;
2. 要求程序能按照输入样例的格式读取数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;
3. 该题共有15个测试数据集,均满足n<=10,m<=10。每个会议最多有10人参加;
4. 该题目30分。

4.SQL中的SELECT语句
SQL中的SELECT语句用于从数据库中查询记录。某个工程项目数据库中有一个所有数据均为字符串的表,需要查询一些满足条件的记录数。本题考虑SELECT语句的简化形式,相关语句格式如下:
1. 计数语句,查询满足条件的记录条数。有两种格式:
格式1:SELECT COUNT(*) 子句> WHERE <条件>
格式2:SELECT COUNT(*) 子句>
2. 子集选择语句,选择满足条件的记录并组成一个集合。有两种格式
格式1:SELECT * 子句> WHERE <条件>
格式2:SELECT * 子句>
上述两种语句中的FROM子句具有相同的格式:
格式1:FROM
格式2:FROM (子集选择语句)
其中TABLENAME为该工程中惟一的表名,子集选择语句即上述用SELECT *开头的语句。
条件的格式为一条或多条=用关键字and连接(不区分大小写),其中FIELD为字段名,VALUE为数据值,它们均为由大小写字母和数字组成的长度不超过10的非空字符串。该条件表示所有特定的字段必须等于给定值。
给定表中的所有记录和若干条计数语句,输出所有语句的结果。
输入格式
输入第一行为三个整数c, n, q,分别表示数据库中表的列数、记录数和查询次数;第二行为表名(即TABLENAME);第三行为表中的c个字段名(FIELD),之间用一个或多个空 格隔开,字段名各不相同;接下来n行,每行表示一个记录,有c个数据值(VALUE),之间用空格隔开;接下去有q行,每行一条SELECT记录数语句, 该语句长度(包括空格)不超过1000。输入数据保证每条语句满足题目中给出的计数语句的定义,并且FROM子句的格式1中出现的表名和输入的表名一致。
输出格式
输出q行,每行一个整数,表示相应语句输出的结果(即满足条件的记录数)。
输入样例
4 5 6
Book
BookName Price PublishDate Author
NBAsports 10 2004 dearboy
SQL 20 2002 absorbed
IntrotoAlgorithm 59 2002 Thomas
MultipeView 60 2002 RichardHautley
NBAsports 10 2004 dearboy
SELECT COUNT(*) FROM Book WHERE BookName=NBAsports and Author=dearboy
SELECT COUNT(*) FROM Book WHERE Price=20
SELECT COUNT(*) FROM Book WHERE Author=lala
SELECT COUNT(*) FROM (SELECT * FROM Book WHERE BookName=NBAsports)
SELECT COUNT(*) FROM (SELECT * FROM Book WHERE BookName=NBAsports) WHERE Price=20
SELECT COUNT(*) FROM Book
输出样例
2
1
0
2
0
5
评分规则
1. 程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试用例上运行不能超过2秒,否则该用例不得分;
2. 要求程序能按照输入样例的格式读取数据,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;
3. 该题共有10个测试数据集,数据1的表与样例相同,并包含15条SELECT语句。数据2,3,4,5的表分别有1,2,5,7列,数 据6~10的表均有8列。数据2~5的表均有恰好1000条记录,并包含100个SELECT语句。数据6~10的表不超过3000条记录,并包含不超过 20000条SELECT语句。本题的后5组数据着重考查程序的时间效率;
4. 该题目30分。

2007年3月31日星期六

变态比赛规则最终版

通过多日的深入研究,终于做成了我的变态比赛规则的最终版!^_^ 其实之前那个C写的版本已经是算法的最终版了.但是想想程序的长度还是有点短了~~老师要求要有复杂性.本来是说要用C\C++做图形界面了(是图形界面,非Visual).但是想想这样是不是太麻烦了,上个学期已经体会过图形界面的制作复杂度了~~(就要写上一个汉字就要用点阵画半天~).终于通过不懈的努力摸清了VC写的dll如何用VB来调用了~~这样就可以VB与C混合编程了.
在VC中用C写成函数封装到dll中只需要添加一个.def文件来定义输出函数名.这样做好dll后在VB中就如同调用API一样来调用就可以了.这种方法适合小型规模的程序,十分方便^_^!!
然后依托VB强大而又方便的Window就可以做出一个花里胡哨的shell了.呵呵,为了加上一点难度,我就使用了VB中所有能使用的图形化编程方法(几乎了^_^!!).添加了FLASH来作为判断所输数据是否满足条件.添加图片装饰窗口.添加一个media player来展示视频(不管效率如何了~~)^_^!!一个呼哨的shell就做好了管他效果如何~~! 当然shell给dll提供了良好的数据过滤功能.
这就是这次课程设计的最终版了.还有最后一张logo拜托了一个学设计的同学来帮忙.要做就做绝对的专业的!^_^~~

2007年3月26日星期一

变态比赛规则的优化

知觉告诉我,我的程序的时间复杂度好像已经很小了(具体是多少啊?我不会算~~).但是看到循环里边那个sqrt函数就不爽!到论坛里求来一个牛牛牛的算法:牛顿迭代法~~名字多牛啊.^_^!!据说这个是在雷神之锤3里边用到的快速求平方根倒数的方法!恩~很牛!经过优化的算法如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1); // 计算第一个近似根
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x); // 牛顿迭代法
return x;
}

int Game(int N,long K)
{
long max,LE;
int p,LP;

if( N<=0 ‖ N>500 ‖ K<0 ‖ K>N*(N-1)/2 )
return 0;

if( K==0 ‖ K==N-1)
return 1;

if( N==1 ‖ K<N-1 )
return 0;

max=N*(N-1)/2;
while (1)
{

p=(int)(1.0/ InvSqrt((max-K)*2));
LP=N-p;
if (LP<0) return 0;
if (p==1 && LP>=1) return 1;
LE=max-p*(p-1)/2;
if (LE==K) return 1;
if (LE<K) return 0;
max=LE;
N=LP;
}
}

int main()
{
long K;
int N,Result;

printf("Please input N,K:");
scanf("%d,%d",&N,&K);

Result=Game(N,K);
if (Result) printf("YES");
else printf("NO");
return 1;
}

终于又见天日~~

不知道blogspot到什么时候才可以解禁啊 反正我这先能访问了再说.继续更新我的小博~~嘻嘻

2007年3月20日星期二

变态比赛规则之初步程序

考虑了几天了,受到上一个高人算法的启发我想到了这样一个算法:


#include <stdio.h>
#include <stdlib.h> 
#include <math.h>

int Game(int N,long K)
{
    long max,LE;
    int p,LP;

    if( N<=0 ‖ N>500 ‖ K<0 ‖ K>N*(N-1)/2 )
        return 0;

    if( K==0 ‖ K==N-1)
        return 1;

    if( N==1 ‖ K<N-1 )
        return 0;

    max=N*(N-1)/2;
    while (1)
    {
        p=(int) sqrt((max-K)*2);
        LP=N-p;
        if (LP<0) return 0;
        if (p==1 && LP>=2) return 1;
        LE=max-p*(p-1)/2;
        if (LE==K) return 1;
        if (LE<K) return 0;
        max=LE;
        N=LP;
    }
}

int main()
{
    long K;
    int N,Result;

    printf("Please input N,K:");
    scanf("%d,%d",&N,&K);

    Result=Game(N,K);
    if (Result) printf("YES");
    else printf("NO");
    return 1;
}

其算法原理还是基于前两天算法的研究.这个算法纯粹的使用循环而没有使用递归,但是算法复杂度我现在还不得而知(怎么算得啊?忘记了 呵呵~~).另外也不知道算法的正确性是否成立(没有测试数据),仅仅是我感觉上可行.呵呵 再研究~~.另外这个Beta还有可以改进之处.慢慢来吧~~

2007年3月17日星期六

N天以来关于变态比赛的研究~(效率有点慢)

哈哈 经过N天不懈的努力(好像都是玩了~~)终于对这个[变态比赛规则]程序算法有了一定的心得!!~~首先,介绍一下在网上搜到的高人的算法(听说这个题目的算法还不少,但是除了"暴力"递归的我认为在众多的程序中,这个写的比较好.复杂度要比光递归小了好多)
#include

int main(int argc, char *argv[])
{
int n, k;

/*if( argc!=3 )
{
printf("use: %s n k", argv[0]);
return -1;
}

n = atoi(argv[1]);
k = atoi(argv[2]);*/
scanf("%d %d",&n,&k); //input two numbers

if(foo(n, k)>0)
printf("YES\n");
else
printf("NO\n");

return 0;
}

int maxT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+(n-m)*(n-m-1)/2;
}

int minT(int n, int m)
{
if( n<=0 n>500 m<=0 ) return -1; if( m==1 ) return n*(n-1)/2; if( m>=n n==1 )
return 0;
return m*(n-m)+minT(n-m, m);
}

int foo(int n, int k)
{
int max, min;
int m;

if( n<=0 n>500 k<0>n*(n-1)/2 )
return -1;

if( k==0 k==n-1)
return 1;

if( n==1 k0; m-- )
{
max = maxT(n, m);
min = minT(n, m);
if( k<=max &&amp;amp; k>=min )
{
if( foo(n-m, k-m*(n-m))>0 )
return 1;
}
}
return -1;
}

然后,再介绍一下我这几天的心得了.我就是在读这段程序时(呵呵,至今我还没有完全搞明白段代码是个什么意思~~ 那位高手来给点拨一下啊.谢谢!),基本上看懂一点,但是突然受到这段代码的启发,想到了一个算法.首先,我一开始是摸不着头脑,只是明白了按规则最多应该有N*(N-1)/2场比赛[每组一个人],最少应该有N-1场比赛[一组一个人,其他人一组].或者0场比赛[所有人一组].后来换个角度来考虑,觉得不应该从有K场比赛,如何分这N个人来考虑.应该考虑一下有N个人,如何分组才能有这K场比赛.另外,也不应该把所有人分在一组,然后分开一个,然后再一个...这样反倒没有规律了.后来想到如果一开始是每一个人一组,然后没人之间都有比赛这样就是一个完全无向图.而合并一组就是把组内的边除去.也就是m个人分为一组的话,就从N阶完全无向图中除去一个m阶完全无向图.
就这样一直合并直到能得到K条边为止,或者只能得到一个小于K的边数.至于具体的算法我还没写出来^_^!! 同时也不知道这个算法是否可行.拭目以待了^_^!!

2007年3月12日星期一

关于Astar2006-3变态比赛规则的进一步讨论

首先,关于题目的补充要求(我们老师没有这样的要求,只是要求算法尽量的优化就可以了):
1.程序将运行在一台Linux机器上(内存使用不作严格限制),在每一测试数据集上运行不能超过10秒,否则该用例不得分;
2.要求程序能按照输入样例的格式读取数据文件,按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据,该题将不得分;
3.该题目共有3个测试数据集,每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%,30%,40%;
经过考虑我把题目抽象为N个元素,分为m组.每组人数为A1,A2,......,Am(均不为空[≠0]).其中
A1+A2+...+Am=N
A1(N-A1)+A2(N-A1-A2)+...+Am(N-A1-A2-...-Am)=K
用递归来解决,每次递归k值都在减少Am(N - Am),基于以上公式对Am递增,递归,回溯所有组合即可得出答案
在网上搜到一位牛人的文章中这样说:
这题我是O(n^4)的记忆化搜索。用了一种技巧合并状态。所以复杂度估计也只有O(N^3), 跑出所有数据在自己机上是5s.代码写的相对简单漂亮
呵呵,真想知道他这个算法是怎样的一个算法.

[转贴] 写的很好啊 幽默~~ 心声~~

Five reasons why you should marry me
A friend sent me the following in an email. It is so numerically funny.Five reasons why you should marry me -
1. I am a mature, responsible adult now:

2. I am a nice gentlemen, everyone likes me:

3. so many things I enjoy, spending time with you is my first choice:

4. I am the only one that matches you !

5. I love to save the world. Let us do it together !

嘿嘿



大家觉得怎么样呢? 可爱吧 真是原来世界上还有这么可爱的女生啊~~
Posted by Picasa

2007年3月11日星期日

作业题

AStar2006百度之星程序设计大赛试题

3.变态比赛规则 为了促进各部门员工的交流,百度举办了一场全公司范围内的“拳皇”(百度内部最流行的格斗游戏)友谊赛,负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式,而是自己制定了一个比赛规则。
由于一些员工(比如同部门或者相邻部门员工)平时接触的机会比较多,为了促进不同部门之间的交流,W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。

比如4个人,编号为1~4,如果分为两个组并且1,2一个组,3,4一个组,那么一共需要打四场比赛:1 vs 3,1 vs 4,2 vs 3,2 vs 4。 而如果是1,2,3一组,4单独一组,那么一共需要打三场比赛: 1 vs 4,2 vs 4,3 vs 4。

很快W.Z意识到,这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人,通过上面这种比赛规则,总比赛场数有可能为K场吗?比如3个人,如果只分到一组则不需要比赛,如果分到两组则需要2场比赛,如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。
相信作为编程高手的你一定知道该怎么回答这个问题了吧? 那么现在请你帮助W.Z吧。

输入要求:

每行为一组数据,包含两个数字 N, K( N∈(0,500] K∈[0,+∞) )。例:

2 0

2 1

3 1

3 2

输出要求:

对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K,则输出"YES",否则输出"NO"(请全部使用大写字母),每组数据占一行。例:

YES

YES

NO

YES

这就是这个学期的课程设计的变态题目了,完完全全是一个解决问题的算法题目。寒假里恶补的数据库看来是用不上了。今天才拿到这个题目,没有头绪勒。看看再说吧

PS到这种地步了 厉害啊 我要好好学习PS了 呵呵~~
Posted by Picasa

2007年3月9日星期五

通知

鉴于近段时间以来 Blogger的访问速度奇快无比 因此决定启用我闲置已久的blogger来作为我以后的blog的主要网站 ~~! 谢谢各位一直以来对我的无私支持与关怀~~!! 我会作的更好的~~!!!