初从文，廿六乃成，负债十万。觅生计，十年无休，披星戴月秉烛达旦，蓄十万。不足购房，遂投股市，翌年缩至万余，抑郁成疾。医保曰，不符大病之条例，拒赔。乃倾其所有入院一周，无药自愈。友怜之，赊三鹿一包，冲而饮，卒。

某公司有一个保险柜，上面有n把锁。同时，公司里有7个秘书，每个秘书都有m个钥匙。问当n，m的值是多少时，才能使得只有半数以上(大于等于4个)秘书到齐时才能打开保险柜？并写出此时的钥匙分配方案。

答案：

n=35, m=20

一场猝不及防的灾难，一场与时间赛跑的救援，一个被废墟埋葬的县城。大灾大难后面，显示的是复杂的人心与人性。

声音在消失

       两个男孩被压在北川中学的废墟的同一个空隙里，一个消极地等待着，另一个则不断鼓动人们先救他。“先救我吧，叔叔，我是班上的第一名，”他说，“我以后一定考军校。”

　　死亡的气味是在5月15日下午开始在北川县城里弥漫开来的。那是一种甜、臭和焦糊的味道。地震在北川为害最烈，由于缺少尸袋，仍有大量遗体被摆放在街道上废墟的空隙间等待处理。废墟下面可能仍埋有上万人之多，而且正在不断死去。几千名军警和消防队员已经又饿又累。傍晚，成都军区某集团军坦克团的士兵们在河边广场上集结，开始吃这一天的第一顿饭：火腿肠，瓶装水。他们置身于真实的灾难现场，克制着挫败感。一个接受南方周末记者采访的士兵说：“这里有好事，也有坏事。”这句概括在此后被一再验证，直到5月19日哀悼日的下午。
　　北川县城处在一个几乎封闭的山谷之中，救援所需的人力、机械和物资都必须通过南方的山口进入。至15日下午，山口公路仍未打通，而官兵们修建的一条临时通道又在当日上午被山体滑坡阻塞，旁边树林中的“之”字形的小道也一度无法通行，士兵们只能用绳子把入城者吊下山坡。不断有躺在担架上的伤者被抬出。
　　解放军战士们再现了他们的优良传统，背着白发苍苍的老人爬上泥泞的山坡。在大片的灰白色的废墟间，士兵们列队行进，稍长的队伍就有旗手引路。
　　地震瞬间发生的一切都固化了。在禹龙干道上，时间停滞在一家三口骑着摩托车出城的时刻，他们被滚石打死。一辆桑塔纳汽车正在过桥，桥塌了，它保持着最初跌落在河床上的样子。大多数楼房倒塌了，甚至粉碎了，到处都是背包大小的瓦砾。没倒塌的楼房以怪异的角度矗立着，楼顶上的广告牌上标示着“距奥运会开幕还有88天”。汽车大小的石头冲进了居民楼。
　　在山口外，人们更多地获知北川创造了多少奇迹，并不能真切地感受到这里的一切是多么艰难。事实上大多数寻亲者得不到回音，大多数救援也只能以失败告终。15日，寻找亲人的队伍络绎不绝，可是从老城到新城，很少有人得偿所愿。来自德阳的6个建筑工人呆在一处居民区，他们中的一个在曾经是荣生酒店的废墟下面呼喊，可是没有人应答。寻找妹妹的刘晓琳同样无功而返。前一天她曾听到呼救声，呼救者在一幢还有形状的楼里告诉她这个楼是华星超市，“快救救我。”当天，这个呼救声一直在传出，可是一个晚上过去，声音消失了。
　　6个建筑工人不再呼叫，但也不离开。他们站立在倒塌的楼房上，可以从一个沥青屋顶跳到另一个沥青屋顶。在他们头顶10米处，赫然挂着一具男尸，好像跳水似的把上半身直插进废墟。
　　次日中午，赵剑平也在呼救。几个寻亲者发现了他，立刻高喊：“这里有活人！”可是沈阳消防救援队不能确定他的方位。仅仅两个小时后，寻亲者们再次呼叫赵剑平，已经没有了应答。需要救援的目标太多了，呼救者必须抓住救援者靠近的很短的时间。当宜兴消防队员从一个地方下撤时，寻亲者们愤怒地质问：“你们又要换防？”消防队员们回答说，山上发现了幸存者。
　　消防队员是专业的救援者。相比之下，“解放军和武警战士既缺乏专业救援培训，也没有专业器械。”武警某部的一位参谋说，“我们没有工具救不出人，看着人死去，心里很难受。”他们更多地承担了转运伤员、掩埋尸体和搜寻幸存者的任务，每当发现生命迹象，往往要去请消防队处置。
　　即便在北川中学的救援行动刚刚开始之时，浅埋伤员很多，救援还相当有成效----武警成都指挥学院的学员们一天之内就抬出了87具尸体，救出了31个活人----救援队伍就已经深感没有大型设备和专业技能的痛苦。
　　从13日早晨8时开始，武警战士们援救一个半边身体被压住的男生，当时他甚至可以伸出右臂接受点滴。县城内仅有2辆起吊设备，先后调来，始终无法吊起压在他身上的重物。当地施工人员猜测，孩子是被支撑整个教学楼的最重的那根十字梁压住了。下午开始下雨，男孩的母亲站在废墟上，给儿子撑着伞。另一个男孩被卡住了，多次营救不成之后，他主动要求截肢逃生。可是医生们没有必要的药物和设备，无法实施手术。下午，男孩开始休克，伏下头和双臂，在武警战士们面前死掉了。
　　晚上7时，医生诊断说，第一个男孩已经失去了生命体征，救援宣告放弃。他的母亲坐在那儿，扔掉了伞。“也没哭，就是坐在那，看着她儿子。”武警成都指挥学院的贺一民大校说。倒是该部队的何政委受不了，哭了。
　　救援者们在废墟下看到了人们的截然不同的反应。两个男孩被压在北川中学的废墟的同一个空隙里，一个消极地等待着，另一个则不断鼓动人们先救他。“先救我吧，叔叔，我是班上的第一名，”他说，“我以后一定考军校。”当他弄清楚站在外面的是武警之后，他改口说：“我以后考警校。”
　　这个男孩得救了。可是这是第一天的故事，却不是第三天的。当这支部队救出第一个孩子时，所有人都使劲鼓掌，非常激动，可是死伤枕籍的场面在其后几天中不断削弱着他们的敏感。悲剧太多了。13日，他们救出来的人因医疗队跟不上，伤者就那么躺在街上逐渐死去了。
　　“开始时看得心疼，现在麻木了。”士兵们说。疲劳也是一个严重问题。他们对自己的安危的关注也在下降。第一天，余震时每个人都会跑开，到了第三天，“震就震吧，也不跑，太累了。”
　　15日入夜后，部队撤离到城外的营地。发电机仍然不能运进山口，夜里无法救援，只有少数几支消防队留下来，凭借手电筒光继续工作。圆月当空，满城漆黑。这是72小时生命时间窗关闭后的第一个夜晚。

木头人

　　只是在类似的少数瞬间，悲伤才在废墟间汹涌起来。更多时候，人们只是像木头人一样站着，平静地寻找着，就像丢了点儿东西。

　　16日有薄雾，天气更热，楼顶的沥青都融化了。有些亲人被埋的寻亲者已经完全不顾自己的安危。他们从弯折的塔吊下钻过去，登上最高的废墟，四处呼喊，又钻进他们认为有他们亲人的空隙。在14日，山里突然打出信号弹，表示上游水库即将决堤，一时间城中军民皆飞奔出城，来不及出城的则向山上转移，被阻挡在山口外的寻亲者们听说了消息，却想在洪水到来之前抢救出自己的亲人，像疯了似的往县城里跑，形成一道汹涌的人潮。15日上午，决堤消息又一次传来，相同的场面再次上演。可是到了16日，这些最不甘心的人也开始绝望了。
　　北川老城有一片高高的废墟，他们就从屋顶到屋顶，在钢筋之间攀缘而上。四处都是奇异的场面。一栋楼嵌进了另一栋楼。一辆警车出现在7层楼的楼顶上。它从山间公路上被甩了下来。废墟下面在燃烧。几个废墟口在向外冒烟，火已经连续燃烧4天。
　　他们没有表现出悲伤。人们只是面无表情地在七八层楼高的废墟上攀爬着。有人跟他们说话的时候，他们逻辑清楚，语气正常，就像什么事都没有发生。当他们找到亲人所在的位置时，就停下来，一动不动地等待着。其实几十幢建筑完全混在了一起，根本没有人能分清哪里是哪里。
　　交通大学的一个学生的父亲在北川县文教局上班，被埋在了废墟下。有人建议他去下面找找，可是他不抱任何希望。“哪个是文教局？”他指着脚下的方圆一公里左右的一片废墟反问。
　　这里曾经是北川县城最繁华的地段，除了大量政府部门，还有电影院、文化站、百货公司、两个小学和一个幼儿园。“孩子死的最多，从婴儿到18岁。”总装备部的石卫波说。他的家就在北川。
　　交通大学的男生向我们要了三只香烟，点燃后插在废墟上，祭奠他的父亲。在危楼顶端的“悬崖”边上，他嚎啕大哭。他的母亲也在他身后哭起来。只是在类似的少数瞬间，悲伤才在废墟间汹涌起来。更多时候，人们只是像木头人一样站着，平静地寻找着，就像丢了点儿东西。
　　这位母亲可以很平静地回忆地震发生时的情形。她走在上班路上，地面突然开始摇晃，她就被摔到了很远的草坪上，听到“轰”的一声，灰烟腾起，就什么都看不见了。“一下子天就黑了。”几分钟后才看得到周围。她抱着一棵树，一个认识的人走过来告诉她，“财政局的楼飞了起来！”
　　13日上午，部队开始转运难民到绵阳的九洲体育馆。到19日，有父母的孩子开始在体育馆外给人们分发一些关于心理健康的小传单，孤儿们则被聚集到了体育馆内。大巴车一到绵阳，一些孩子就“变傻了”。下了车，他们一动不动，也不说话。“看着真是难受。”武警某部的一位少尉说。
　　在老城的废墟上，水泥是疏松的，在一个地方，我们可以像掰饼干一样把水泥预制板掰出任意形状。钢筋也是如此。有的水泥板中只有3根细小的钢筋，只需稍微用力就可以折断。
　　在地面上，山里乡镇的灾民们正在逃出来。李奋强(音)来自漩坪乡的一个村。他本来是去乡上求援的，发现漩坪已经被堰塞湖淹没，又跑到了县里，结果县城也没了。他失声痛哭，提醒几个解放军战士，大水湾峡谷已经壅塞，水憋住了，随时可能山洪暴发，“准备好逃命吧！”
　　这并不是一个谣言制造者，恰恰相反，是一个仗义的中年人。他并不准备往绵阳方向逃生。已经两天没吃饭了，他跟士兵们要了点食物。吃完饼干喝完水，他说：“回去！”又返回村子里报信。
　　由于交通管制，县城外也有大量的寻亲者。12日中午，杨先明因为喜欢上网不愿意做饭而和母亲吵嘴，跑出家，到附近空地发呆，地震发生后，他逃命到县城外的加油站露宿。他的父母在县城的菜市场卖菜为生，至16日仍未找到。他瘫在车辆进出的土路上，车辆都绕他而行，他光着脚，鞋子挂在脖子上，两脚已经血肉模糊，自称是走路走的。“进去三次了没找到人。”
　　寻亲者们不断地发现幸存者，“活人！活人！”的喊声不时从废墟上传来。不过死亡正在取得胜利。在13日，很多人都曾靠近过北川幼儿园，武警成都指挥学院副院长李俊国说，“一片小孩的哭声”，另一个幸存者则说，“里面都在喊‘婆婆’”。到了16日，幼儿园已经沉寂了。

“你们赶上了好时代”

　　在这里，特警已经抓了二十多个涉嫌趁火打劫者，用军用皮带捆着，在公路护栏下蹲了一溜儿。看上去他们都是附近居民。

　　在北川中学的最初的营救行动中，华西建工派来的4台吊车和山下一个水泥厂派来的4个工人起到了重要作用。武警战士们不懂建筑，此前进展缓慢。李俊国说： “我们有心无力，没有工具。”水泥厂的工人们则带来了他们的专业技能，先是对表层废墟进行支撑加固，之后开始挖掘下层废墟。一个空洞打开后，一名工人钻了进去，将尸体和活的学生拖了出来。询问他们怎么来的，4人说是厂长派他们来的，“厂长不派，我们自己也会来。”
　　当时，在县城里，效率最高的也是消防等专业队伍。“可惜的是，当时交通阻塞，消防车进不来。我们没有电钻、电锤、切割机，只有力气。如果道路先修通情况就不一样了。”张强说。
　　士兵们几乎完全是依靠人力完成了最初两天的救援工作。13日和14日，县城内堆积着大量的伤员，但要运输出去却无路可走，只能往山坡上拉。运送一个伤员需要至少20个士兵，没有担架，常常是用门板，或者在两跟木棍间捆上绳子来负担，在山下的用力推，在山上的用绳子拉，需要在六十多度的泥泞山坡上爬行一百多米的高度，“像拔河一样拔。”老城和新城之间有一座桥，断掉了，距河床三米高，要过河，需要80个人组成一座人工桥。他们用铁管去撬水泥预制板，铁管全拧成了麻花。
　　13日到14日中午，伤者很多，各部队没有分工，“都扑在面上”，没有区域责任，“全凭良心救人”。14日下午各部队开始 “分片”，试行了一个下午，效果不好，解放军和武警部队的战士们不擅长废墟救援。15日开始，“科学施救”的紧迫性越来越强，“分片”改为分组，大多数的组都由作战部队、消防队员和医生三方面联合组成。
　　实际上，早在救援刚刚开始之时，事实上的合作就已经开始了，尤其在建筑非常坚固的时候。
　　14日，贺一民带着人到县委勘察，爬上县委倾斜下陷到地面的屋顶，隐约听到里面有人呼救。他要求呼救者大点儿声，于是从下面传来了一个清晰的声音，“救救我，我是张书记！”这个人是北川县政法委书记张同凯。这里是县委大楼。
　　“你不要跟我说你是哪个，你就说你有多少人！”贺一民说。他喊来了沈阳消防队。消防人员拿来生命探测仪，把摄像头插进废墟，直到从屏幕上看到一只巨大的眼睛。救援随即开始。
　　武警战士一共20个人，轮流用铁锤砸楼顶，每人15锤，几轮下来，他们发现这种做法不可行。“钢筋又多，水泥标号又高，砸不开。”江西消防队的10个人赶了过来，带着气锤，不过沈阳消防队拒绝了他们的帮忙。他们花了比较长的时间，用电钻解决了问题。有3名官员获救。
　　15日下午，一个当地居民模样的男子拿着两个包出城，在山口处被特警队员截下。特警问：“一个学生书包，一个女包，哪个是你的？”男子说都是自己的。特警在女包中找出一个存折，问他账户名字是谁，他回答错误，立刻被拘捕。在这里，特警已经抓了二十多个涉嫌趁火打劫者，用军用皮带捆着，在公路护栏下蹲了一溜儿。看上去他们都是附近居民。一个被拘捕者偶然回头与记者对视，眼神中充满了耻辱和恐惧。
　　前一天，中国农业银行北川县支行曲山所的一位女员工嚷嚷说要自杀，贺一民等人询问后得知，她的家人被埋在了废墟下，而银行又遭到了洗劫。武警成都指挥学院的一个纵队保护并清理了银行，找出了一些金融凭证和将近100万元现金。同一天，有人在贺一民巡视时提示有人在洗劫商店。贺一民过去询问，这些人说自己遭了地震，回来把自己东西抢出去。贺一民让他们打开包，发现里面全是女性衣物。这些人想要逃，贺一民说：“你们赶上了好时代，唐山大地震时可以直接枪毙你们。”武警没权力抓人，他让他们滚，后又叫住，让这些人掏口袋，发现里面很多都是不知真假的首饰。在另外8个人身上，他们则找到了真的首饰。
　　只有置身其间，才会意识到这不只是一个灾难之地，还是一个拥有大量财富的县城。其实只要在废墟上走一走，就可以看到不少存折。瓦砾间也有各种记忆。卷宗。文件。照片。课本。
　　贺一民之后去找前线指挥部，提醒他们注意偷抢行为。据他称，后来见到海南特警当天就“抓了几个蟊贼”。16日，在废墟上，南方周末记者看到一个人走进了一家通讯器材店，出来时拿着一只手机。他边走边拆掉包装，从各个角度查看它。一个男人对我们辩解说：“现在拿点儿东西不叫抢劫，叫自救。”

士兵们尽力了

　　他们的身体是青色的和白色的，散发出呛人的气味，只有漂亮的头颅和柔软的身体仍旧是优雅的。

　　老城废墟的最顶点就是北川县幼儿园。地震发生时园中有五百多名孩子，被滑坡气浪推行二十多米，全部被埋，只有二十多人生还。16日下午，又有人在这里喊，“有人！”宜兴消防队的队员们走过来，开始挖掘。
　　队员们不停地挖出小花被、小花枕头，然后一个队员伸手下去，拎出了第一个孩子，紧接着是第二个。地震发生时孩子们正在午睡，死去后也保持着睡觉的姿势，小小的拳头握在胸前。
　　他们的身体是青色的和白色的，散发出呛人的气味，只有漂亮的头颅和柔软的身体仍旧是优雅的。那些小花被子被用来包裹童尸。半小时后，3具尸体被拉了上来，两个女孩和一个男孩，两个女孩都编着小辫，每个辫子上都扎着五颜六色的彩带。救援人员把他们放到下面的草地上。围在废墟边上的两个男人突然张开嘴巴，随后跑下了废墟。他们就是两个女孩的父亲。
　　一个年轻的母亲走过去看了一眼，大哭起来：“我的孩子啊！”另外两个母亲也跟着她哭起来。但是那并不是她们的孩子。“这些孩子都是我的孩子，”那个年轻的母亲哭着说，“我看着难受！”
　　她拿出手机，给我们看她女儿的照片。是个扎着两只辫子的胖嘟嘟的小姑娘，赵媛媛，3岁。手机里还有一段录像，小女孩在旋转木马上起伏着，转过脸看着镜头，一上一下，还在唱歌。
　　这是12点半，空气中是闪亮的雾气。空军开始空投物资。18只降落伞打开了，看上去非常高。顺着微风，4只降到了旁边的山坡上，剩下的都飘到了山外。这时，那两个男人开始在山坡上挖坑，他们的孩子的尸首就放在一边。一个男人挖了一半放弃了，他把尸首运到高处，重新开始挖掘。另一男子仍旧在原地挖着，那是一个斜坡，他又好像也不太会挖，每挖一铲，斜坡上的土都会垮下来一些。走过去跟他说话，他沉默不语。这个男人不停地挖着，但总也挖不好。
　　有一些人是没救上来的，不过大多数寻亲者也承认，士兵们尽力了。
　　武警某部的参谋张强(化名)谨慎地犹豫着，试图写一篇文章来表达自己的看法：“这次救灾的主要经验教训，一是指挥协调，救援不仅要有人数，还要有效率；二是修路为先，先让大型机械进入；三是重视专业性，救援质量可以提高；四是空军作用应该发挥得更多更大。”
　　3天后，北川县城沉寂了好多。城中的救援队伍已经没有那么庞大，更多的部队在城外的营地中活动。到处都是消毒粉的气味。一些进城的士兵们戴上了防毒面具，至少戴着大号的防护眼镜。穿着橡胶防护服的防化兵正在四处消毒。空气中充满了飘动的白色粉末。再次烈日当空。
　　中国地震救援队也转移到了这里，19日上午，他们还救了一个人。下午2点20分，他们在一处集结，准备哀悼日的默哀。一个队员站着值勤。他有礼貌又坚决地阻止人们通过。他个子是最矮小的，没有被击败。
　　老城的废墟仍然在燃烧，袅袅青烟萦绕在北川上空。几个乡民逡巡着，想从一处关卡通过，临时担任守卫的消防队员不搭理他们。我们问他们住哪里，回答是附近乡镇。再问做什么，回答却是：“到里边儿取点儿东西，很重要的东西。”稍早前，又有一拨人带着毛毯离开了县城。我们提醒他们中的一个：“小心一点儿。”他局促不安地避开了眼神。这已经是最后的、也许还遗留有生命的北川了。其后几日，因为山体渗水和余震的原因，北川的救援已经基本放弃。
　　中国地震救援队的队员们立正，帽交左手。哀悼日的汽车喇叭鸣响了，执著地响了10分钟。

Desmo-J:   One discrete event simulation framework written in Java.   The advantage is easy to follow and good for a fresh men in this area or a temporary simulation developer.

another one in java is Ptolemy , by UC. Berkeley

C++SIM: wirtten in C++, for guies expert in C++, it is a good choice.

With the help of these frameworks, it should be some easier to develop one simulator of your use.

花了两个星期终于写完了。
还剩下一些功能没实现，但基本上不影响使用
基本符合IPMSG协议

目前功能：
局域网内聊天
收发文件，文件夹

安装方法：

（1）首先下载 IPMSG 程序包 （点击下载ZIP压缩文件）。

（2）安装 java1.5 以上版本， 设置 JAVA_HOME 环境变量

（3）下载swt类库到IPMSG安装目录，并更名为swt.jar

         swt下载主页：http://www.eclipse.org/swt/

（4）linux用户运行IPMSG.sh
        windows用户直接双击IPMSG.jar, 或者运行IPMSG.bat批处理文件

刚看到有人把一个海尔手机给组合到PSP中了。NND，这群猪真是太牛了！！现在skype又不能用，这实在是个办法。拉轰～

原帖：http://bbs.tgbus.com/viewthread.php?tid=2802114&extra=&page=1

在北京这个全球第12大拥挤的城市，你会发现，任何一个微不足道的东西都有可能成为稀缺资源，在你需要它的时候没了踪影，比如早上八九点钟的茅坑和公交车座。这有时候会让人很沮丧，能在公交车上站立一个小时然后再精神抖擞的在单位工作的人不是没有，但遗憾的是，不包括我。于是，预测下一个站牌最有可能下车的乘客是哪位便成了我每天不得不面对的问题。幸运的是，思考这个问题要比坐公交车本身有趣的多。

1。根据年龄来判断。 一般情况下，老人会在公园、小区、菜市场附近下车。中青年会集中在某几个热点站点下车。

2。注意乘客打电话，交谈时透漏的信息。通过它们来判断下车地点

3。注意乘客手中拿的东西。它们有可能告诉你乘客的工作单位或上学地点。

4。注意乘客的动作，对于快到站的乘客，他们往往会有些不自觉的动作，比如看窗外，整理衣服等等。 而对于那些打磕睡的乘客，你基本上可以放弃了，他们不到终点站很少有下车的。

5。如何车座分单双排，尽量靠双排站立。

6。车上人很多的时候不要站在两排座位的中间位置。妄图脚踏两只船，其后果往往和生活中的情况一样悲惨。

7。如果旁边有站立的老年人，那么尽量远离。他所能辐射到的范围内的座位基本上就是他的了。

8。找熟悉的面孔。如何经常坐某一路车，那么可以有选择的记住几个面孔。

9。在恰当的时刻作恰当选择。很多时候你连车座边的位置都捞不到，或者有时候你发现别的座位不断空出来，而你旁边的那个却一点动静没有。这个时候就要重新进行判断，然后在到达下个车站的时刻（一般这个时候车内的位置会重新洗牌）移动到最有利的位置上去。

10。RP at high level

附一个以前看过的漫画，祝大家在人生的旅途中也能尽快的找到适合自己的座位：

约瑟夫环：
有编号从1到n的n个人坐成一圈报数，报到m的人出局，下一位再从1开始， 如此持续，直止剩下一位为止，报告此人的编号x。

这几天在想约瑟夫环的一个逆问题，所以首先考虑了有没有一个形式化的函数J使得x=J(n,m)。虽然目前为止结果令人沮丧，但过程中还是有一些小发现 （以前居然没注意到）: J 的一个递推表示 J(n,m)=(J(n-1,m)+m) % n。

本来想自己写个证明过程，后来发现网上有个相当不错的证明了，摘录如下：

为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
  k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k     --> 0
k+1   --> 1
k+2   --> 2
...
n-1 --> n-k-1
0    -->  n-k
....
k-2   --> n-2
k-1   --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n=(x+m%n)%n = (x+m)%n.

那么有了这个递推公式，是否可以求出J的形式化表示？目前看来，除了m＝2的情况，答案是否定的。Knuth给出了m=2的形式化描述：设 n = 2^i + l 则 J(n,2) = 2l+1。 这个公式的证明比较巧妙，考虑到如果n=2^i, 则1会永远保持1号位，也就是最后的x＝1。那么对于n = 2^i + l 的情况，只要先出局l个数，剩下的数就是2^i的情况，此时永远保持1号位的就是2l+1。

约瑟夫环问题还有个比较有趣的故事：据说在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

呵呵，看样子学好数学还是有用的，关键时刻可以活命。吼吼！

附：
约瑟夫环的一个逆问题：
有编号从1到n的n个人坐成一圈报数，报到m的人出局，下一位再从1开始， 如此持续，直止剩下一位为止。假设你在队列中的位置为x，如何选择m才能使最后一个人是你。

       我们与家乐福并没有仇，五一过后，如果顺道我也许还会去家乐福买东西。我们与法国和法国人民也没有仇，虽然在圣火传递期间他们做了很不光彩的事情。而且法国及其产品离我们普通国人并不像日本，美国那么近。比如达能，欧莱雅在它们的领域并没有什么技术优势。说句毫不客气的话，法国，我们看不上你。当然，法国也可以对着他们的奢侈品比如LV去自慰，完全当我在放P。

       可法国和家乐福还是成了国人的抵制对象。法国驻中国大使说他很遗憾。事实上，我们更遗憾。法国和家乐福成了这场无血战争的核心，成了这个倒霉蛋。我们也没办法，战争是你们西方人先挑起来的，当然情理上来讲也应该由你们买单。而家乐福则或是偶然或是必然的成了买单的主角。

       国人还是比较冷静。我们已经说好，抵制不是目的。我们不想家乐福垮台，更不想中法关系继续恶化。抵制是什么，是一种态度，是我们渴望理解万岁的诉求。我们没有CNN，我们没有BBC，可我们有13E中国人，我们应该也必须让西方人知道我们心中的想法。而且我们做到了，世界媒体对抵制家乐福的报道还是比较充分，虽然有很多报道不大厚道。不过，在经历了CNN之后，我们对他们的不厚道作为再没有感到什么遗憾。现在我们已经迈出了一只脚，世界媒体都在等着我们五一迈出的另一脚。那么就让我们迈的更响亮些，让世界知道我们中国人的心声。

One World One Dream One China

转自： http://gezhi.org/node/12

翻译自：芝加哥大学计算机系教授Lance Fortnow在他的Blog上写了一篇短文“The Secret of Success”

1. 聪明。你需要一种先天的才华才能成为一个成功的科学家。这种天才表现在多个方面：

• 解决问题的能力。使用正统的方法通过合适的途经来找到问题的答案。
• 创造性。原创性的研究要求一个人的眼光要超越现有的工具，找到新的解决问题的方法。
• 好的视野。能够发现新问题和新的研究方向。

2. 玩命工作。这方面没有异议。

3. 好运气。在正确的时间工作在合适的问题上。久而久之，就会得到幸运的垂青。

4. 自律。能够在一段时间专注于研究而不被其他事情所干扰，包括非研究性质的事务，互联网或者其他活动。有的人发现最好是为研究工作单独开辟时间，在这段时间里把自己藏起来思考问题。

5. 矢志不渝。愿意花相当多的时间在某个问题上，即使可能走到死路也不后悔。

6. 良好的训练。在学生阶段努力学习，拥有并“利用”好一个好的导师。阅读文献和教科书。当你看到一个定理时力图自己证明它，只有这样你才能很好地理解一个定理并从中受益。

7. 好的同事。拥有一群好的聪明的合作者，特别是可以和你的才能进行互补的人，可以帮助你做更多凭借个人力量无法完成的事情。即便仅仅和人讨论对某种想法的证明或者研究方向的可行性，也可以从很大程度上帮你找到解决问题的正确途经。

英文原文：

What does it take to be a successful in our profession?

• Intelligence. You need an innate talent in different forms to succeed as a scientist.
  • Problem Solving. Using well-established techniques in the appropriate way to find solutions.
  • Creativity. Original research means one needs to look beyond the current set of tools and develop new approaches to problems.
  • Vision. Discovering new problems and directions of research.
• Hard work. Enough said.
• Luck. Working on the right problem at the right time. If you work long enough` the law of averages will catch up with you (for good or for bad).
• Discipline. The discipline to focus on research for a period of time without getting distracted from other responsibilities or by the internet or other activities. Some people find it best to schedule time for research and hole themselves up somewhere to think about a problem.
• Commitment. Be willing to spend a considerable amount of time on a problem even if you keep running into dead ends.
• Training. Taking and working hard in classes. Having and taking advantage of a good advisor. Reading papers and textbooks. When you see a theorem in a paper try to prove it yourself first. Only then can you truly appreciate a proof and learn from it.
• Colleagues. Having co-authors, especially those that complement your talents, can help you do more than you could on your own. But just having good people to talk to, to bounce off proof ideas and discuss research directions can greatly help you find the right approach to a problem.

其他考参：

[1] http://weblog.fortnow.com/2005/07/secrets-of-success.html

[2] http://paulgraham.com/hs.html

D1 难度★★★★★
一只猫紧紧追赶着一只老鼠。就在猫将要抓住老鼠的时候，老鼠正好跑到一个圆形的池塘旁边，纵身跳入池内，猫抓了个空。猫舍不得这顿即将到口的美餐，于是盯住老鼠，在池边跟着老鼠游泳方向跳动，想等老鼠爬上岸来时抓住它。请问猫奔跑的速度至少是老鼠游水速度多少倍，猫才能看住老鼠，使得老鼠一上岸，就被猫逮住？假设老鼠和猫都非常聪明，它们可以任意改变运动方向而不影响速度。

D2难度★★★★
秋香和她的29个丫头排成一个大圆圈；给这个圆圈里的所有人按顺时针的次序编上号，秋香在第28号。
现在唐伯虎要说出一个数字，我们就设为X吧，然后圆圈里的人就从1开始顺时针报数，数到X的那一个人就退出圆圈，然后就用这个人的位置号代替X，继续接着从这个人的后面一个人开始报数，数到谁谁就退出；以次类推，直到最后圆圈里只剩下一个人。
聪明唐伯虎应该说一个多大的数字才能保证最后剩下一个人是秋香呢？呵呵

D4难度：★★★★
请写出都是合数的100个连续自然数

D6难度：★★★
某一会议上，许多人互相握手以致问候。请问握手次数为奇数的人的总数是奇数还是偶数？为什么？试证明。

D7难度：★★★
在123456789的某些数字中间填上加号或减号，使所得的值等于100 ？

D8难度★★
题目是这样的：在一个集中营里（为什么是集中营？因为那里才可以乱杀人啊，呵呵）有100个犹太人等待枪毙，德国军官突发奇想，让那100个人站成一排，先枪毙单数的人，比如站在位置1，3，5，7~~~~~~~~~~~99的，然后再把剩下的（位置2，4，6~~100）的人又组成一排，照样枪毙站在单数位置上的人，反复如此，直到最后剩下一个人，就让那最后一个人活下来，请问，最后活下来（剩下来）的一个人是100个人中站第几的？？

D9难度：★★★
三个男人打算采用骑双人自行车与步行的办法前往40英里远的某处，双人自行车最多只能坐两人，另一人只好步行。A的行走速率为10分钟1英里，B为l5分钟 1英里，而C则要用20分钟才能走完1英里。双人自行车的速率是每小时40英里，不管哪两个人坐在上面。假定他们利用最有效的办法，把骑车与步行巧妙地结合起来。试问:三人要完成这次短途旅行，至少要用多少时间?

D10难度：★★★
查利与弗雷迪把它们穿得很脏的硬领与袖套，总共30件，拿到一家中国人开的洗衣店里去洗涤。几天之后，弗雷迪从洗衣店里取回了一包送洗物，他发觉其中正好包括当初送洗的袖套的一半与硬领的三分之一，他为此付出洗涤费27美分。已知4只袖套同5只硬领洗涤费相等。 试问:查利把剩下的送洗物全部取回时，他要支付多少洗涤费？

D14难度：★★
“猫头鹰“号特快列车的机械师大吉姆说道：“离站后一小时，我们把机车头的一只汽缸放了汽，以原来速度的五分之三继续跑完这段旅程，这样一来就使我们到达下一车站的 时间误了两小时。如果再驶过50英里以后放汽，那么列车就会比现在早到40分钟。“
这两个车站之间的距离是多少?

D15难度：★★★☆
4个3位数的第1位数字（百位）都相等，这4个数字的和能被其中的3个数整除，求这4个数分别是多少？
来道附加题：不用计算器，迅速判断，31的11次方和17的14次方，那个比较大。

D18难度：★★
两个小伙子，身上带着同样多的钱，打算在赛马中采用罗斯林勋爵赌博法，即把赌注押在最孬的马身上，而且押下的赌金等于赌博公司开出的这匹马对1美元的赔率。吉姆把赌注押在劣马科希努尔身上，赌它会蠃得第一，而杰克则认为它可得第二，于是他们根据不同的赔率押下了不同的赌注，尽管这两笔赌注相加起来花去了他们所带赌金之和的一半。结果，他们居然都蠃了。蠃了钱后，吉姆身上的钱现在是杰克的2倍了。注意赌注必须是以整美元下的(不准有几角几分等零钱)，你能否猜出他们各赢了多少钱?

D19难度：★★★★
一只爱好户外运动的小兔子同一只乌龟沿着直径100码的圆形跑道背向行走，进行比赛。它们从同一地点出发，但起先兔子根本不动，直至乌龟完成了全程的八分之一(即圆形跑道周长的八分之一)以后才开始。兔子低估了对手的竞走能力，因此它慢吞吞地闲庭信步，一边啃啃青草，直至它在途中碰到了迎面而来的乌龟，在这一点兔子已走完全程的六分之一。
试问:为了赢得这场比赛，兔子必须把它的速度提高到以前速度的多少倍?

D23难度：★★★★
小明非常聪明，但对英语一窍不通。有一天，老师出了5道英语选择题，每题有4个选择（只有一个是正确答案）。许多同学做完后交给老师批（设他们都做了这5道题），老师只给出答对了几题。问题：所有考卷的答案至少有一题不同，小明看了多少张批完的考卷后，肯定能得满分？

D24难度：★★★
露易斯从她正看着的报纸上拾起头来，望着她的丈大说：“这样看来，威尔逊赢了。但他所得的票数比其他两人加起来还少。”
约翰点点头．“我看是这样，”他告诉她，“实际上我还注意到了有关投票结果的一件非常新奇的东西．那就是每两个人得票的和都是一个准确的立方数．你知道—个数乘以它自已两次便是立方．”
“我相信你说的，”他妻子微笑地说，“但马托克为什么要白
扔掉他的竞选基金呢?”
“这是一种令人沮丧的把戏，”约翰低声轻笑着，“他得到的
选票还不足百分之十”
请问三个候选人的得票各是多少？

D25
为便于大家讨论，不妨设飞机满油时的飞行距离为1，全程距离为2。有家公司研制出新型飞机,欲做广告进行环球飞行,此飞机加满油可绕地球飞行1/2圈,并可在空中互相加油(甲飞机可将自己油箱中的油加给乙飞机),问此环球计划是否可行?若可行,需出动多少驾飞机?(假设飞机不能另外携带汽油,并只能在出发点降落)
这题我们假设飞机只能同时起飞，速度相等，而且是单向飞行。
问：1。能实现吗？
2。如果同时起飞的飞机是8驾，则其中的一驾最远可飞行多少距离？（其余必须返回）
3。如果同时起飞的飞机是n驾，结果又如何？

D26难度：★★★★☆
数学家杜得尼曾经提出一个问题: 有9个犯人,他们放风的时候分成三组,每组三人.每一组的三个犯人用两副手铐铐在一起,也就是说中间的人分别与左边,右边的人同铐一副.现在请你排出犯人每天的放风分组表,使得在六天中,任何两个犯人恰有一次共同铐一副手铐.
答案格式如下:
第一天: XXX, XXX, XXX
第二天: XXX, XXX, XXX

D27难度：★★★★
把1到1亿所有数的数字（如18559为1+8+5+5+9）相加，得出和。

D28难度：★★★★
K 市刑侦大队第三小分队，奉命赶往相距400公里的边 境押回一名逃犯。为了争取时间，必须乘摩托车火速出发。但他们只有五辆摩托车，每辆车只能装带六只小油箱，而每只 小油箱也只能供行驶40公里。五名刑侦队员开动脑筋，很快就想出了一个好办法，胜利地押回了那名重要的逃犯，并从他 身上打开“缺口“，迅速破获了一个特大杀人、抢劫团伙。你可知道刑侦队员是如何迅速驶往边境的吗?

         昨天下午吃完饭，正好碰到一同学，就随便聊了聊。 他说刚参加完一个面试。我很感兴趣，因为下半年就该我找工作了，这方面的信息对我来说比较重要。看得出来，他有点小郁闷，说面试官是个BT。问了原因之后，我便很同意他这个观点了。面试官似乎对查找和排序很感兴趣，问的大部分都是这方面的。首先是让用n+lgn的时间复杂度求出一个无序数组的最大值和第二大值，tooooold，同学面不改色答之，然后O(n)求第k大， 同学是blabla, 又出个用基数排序的，同学也答出，面试官很是欣慰。同学于是得意啦，分析其复杂度，随口一句: 这个问题用基排最好，其他基于比较的最小也得nlgn。 面试官也是随口一句：嗯，是最小nlgn，不过为什么？ 同学说，当时他给雷到了。说，如果让他分析一个具体的排序算法，他可能还能应付，可这么个问题，有点让他找不到北。 是啊，好多时候，我们只记得结果，却忘记了得出结果的过程。

          其实这个问题也是一个toooooold的问题，好多年前就已经给计算科学家证出来了。 而且思路很简单：

比如要用基于比较的方法排序 A1,A2, A3,  其实就是找到一个两两比较序列，而这些序列都是下面这个二叉树中某一个从根到叶子的路径。

那么基于比较的排序的时间复杂度就是这颗数的深度H(N)。而且很容易知道叶子节点的个数就是N的排列 N！， 那么我们就有

                          2^H(N) >= N! > N*(N-1)*.....*(N/2) > (N/2)^(N/2)

                          H(N) > (N/2)lg(N/2) = O(nlgn)             得证

shuffle问题：

输入A1,A2,.....An,  B1,B2,.....Bn, 如何用O(n)的时间复杂度，O(1)的空间复杂度，将这个序列顺序改成 A1,B1,A2,B2,.....An,Bn

这个问题由来已久，我从网上注意到它也是去年的事了。据说是google面试题，后来也有人说是微软面试题。反正不一而足。 但有个共同点就是，大家都在讨论它，却没人能解它，至少所有讨论组的跟帖中都没有解。后来在zhiqiang同学的BLOG（http://zhiqiang.org/blog/posts/an-algorithm-face-interviews-question-test.html）看到，居然有数篇论文专门在讨论，都是用了置换cycle的办法。这个思路还是蛮容易想到，但就是做起来很困难，对数学的要求比较高，绝对需要潜下心来思考一阵子。不过即便如此这些解法的空间复杂度也是O（lgn*lgn）的，并不满足题目要求。 我把这个题目说给了几个同学，看他们有什么思路。后来他们也基本上都是处在了思考状态，无解。到了这个时候，我基本放弃了解这个题目。有一天，师兄201发给我一个网址，告诉我说可能有解了。我忧郁了一下，打开了网址，又是zhiqiang同学（http://zhiqiang.org/blog/posts/another-perfect-shuffle-algorithm.html），这次他把问题规约到了一个merge的问题上。是这么说的：

Art of Computer Programming, Volume 3上有一个难度为40分的Merge Sort习题：

已知数列，设计算法使得在线性时间，常数空间实现归并，也就是将原数组排序。

而Perfect Shuffle问题是可以规约到这个Merge Sort问题的：

mergeSort(x[1...2n]); // if this function solve Merge Sort problem
perfectShuffle(x[1...2n]): // then this solve Perfect Shuffle problem
     m <- max(x[1...2n])+1;
     x[i] <- x[i]+(2i-1)m,
     x[i+n] <- x[i+n] + 2im
     mergeSort(x[1...2n])
     x[i] <- x[i]%m

不错的想法！当时我的疑虑主要有两个，一个是x[i]+(2i-1)m这么大的值很有可能导致整型溢出。 另一个就是merge真的可解吗？我基本上是花了一天的时间来思考merge的解法。实际上，这是个更难的问题，比shuffle更难。我没有得出答案，不过这一天的思考对我还是很有帮助，至少它给出了我后来解出shuffle的思路。 呵呵，因为merge的问题我还弄出点小插曲，见笑。

(此解法有严重缺陷，sigh, stupid excitation, 记于4.10)

现给出shuffle问题的解法。程式兼举例说明， 如下：

n为偶数的情况：

                          程式                                               例子                                                           复杂度
初始：        数组A[n], B[n]                               :    A1,A2,A3,A4, | B1,B2,B3,B4       

折半交换： A[n/2+1, n] <-->B[1, n/2]              :    A1,A2,B1,B2,  | A3,A4,B3,B4                     :    O(n/2), O(1)

隔一叠加： For 1<=i<=n/2, B[2*i-1]+=A[i]
                  For  n/2<i<=n,  B[2*(i-n/2)]+=A[i]   :   A1,A2,B1,B2, | A1+A3,B1+A4,A2+B3,B2+B4 :   O(n),O(0)

隔一消减：For 1<=i<=n/2, A[i]=B[2*i-1]-A[i]
                For n/2<i<=n,  A[i]=B[2*(i-n/2)]-A[i] :  A3,B3,A4,B4, | A1+A3,B1+A4,A2+B3,B2+B4 :    O(n),O(0)

隔一再消减：For 1<=i<=n/2, B[2*i-1]-=A[i]
                For n/2<i<=n,  B[2*(i-n/2)]-=A[i]      :  A3,B3,A4,B4, | A1,B1,A2,B2                        :    O(n),O(0)

交换前后得解：A[1, n] <-->B[1, n]                  :   A1,B1,A2,B2, | A3,B3,A4,B4                        :    O(n),O(1)

n为奇数的情况可以转化成偶数情况解之，不做讨论。

（此解法主要思路用到了这个交换程式：#define swap(a,b)   a=a+b;b=a-b;a=a-b;）

（1） 输入a_1,   a_2,   ...,   a_n,   b_1,   b_2,   ...,   b_n，如何在O(n)的时间，用O(lgn*lgn)的空间，
将这个序列顺序改为a_1,   b_1,   ...,   a_n,   b_n。

（2）

把一个正整数变为1，求最少的步数？

具体是这样的：如果这个数是偶数，那么直接除2；如果是奇数，加1或减1变成偶数，
这样反复，一直到变为1，求最少需要几步？
例如 func（7）＝4；
int func(unsigned int n);
n为输入的的正整数。

（3）

一个数的三次方尾数是888,有什么规律吗?

（4）

一条楼梯有100级每次跨一级或两级，问上楼梯有多少种方法

(5)

已知两个有序数列 x1<x2<x3.....<xn， y1<y2<y3<...<ym 设计算法使得在线性时间，常数空间实现归并。

今天在做一个算法题目的时候正好要用到mod运算，发现小学就会的运算却蕴藏着许多有意思的地方，就设计了以下几个题目， 感兴趣的可以做下。

23 mod 10 ＝?

23 mod  -10 = ?

-23 mod 10 = ?

-23 mod -10 =?

已知 a mod 10 = 6 ,  b mod 10 = 9    求  （a+b) mod 10,   (a*b) mod 10,  a^2 mod 10,  a^n mod 10

a mod b mod c = a mod c 吗？如果不，什么时候相等？

已知 0 < a < b，求最小的n使得 a * 2^n mod b = a

已知 0 < a < b，求最小的n>1使得 a^n mod b = a

曾经看过一篇科幻小说，一个外星人来到地球收集人类的文化信息，他把所有资料都编码后，全人类的知识就变成了一长串数字n，然后1/n，再在一根特制的棒子上的1/n位置刻上标记，回去后得到这个位置信息，取倒数就得到了全人类的信息，虽然只带走了一根棒子，却满载而归

百度2005年的笔试题

1.实现 void delete_char(char * str, char ch);

  把str中所有的ch删掉，    尽可能节约空间和时间。

2.把字符串S中所有A子串换成B,这个没给函数原型

3.搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万

  要统计最热门的10条查询串. 内存<1G. 字符串长 0-255

  (1) 主要解决思路 //具体用词和原题不大一样

  (2) 算法及其复杂度分析

4.有字典,设计一个英文拼写纠正算法 (1) 思想 (2) 算法及复杂度 (3) 改进

5. { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字符串的集合

  要求把交集不为空的集合并起来,如上例会得到 { aaa, bb, ccc, dd, ff }, {gg}

  (1) 思想 (2) 算法及复杂度 (3) 改进

百度2006年的笔试题 百度校园招聘在线笔试 

1）15分
如下数据结构：
typedef struct TreeNode {
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}
请实现两棵树是否相等的比较,相等返回0否则返回其它值.并说明你的算法复杂度
int CompTree(TreeNode* tree1, TreeNode* tree2);
注:A,B两棵树相等当且仅当RootA->c==RootB->c，而且A和B的左右子树对应相等或
者左右互换后相等．
2）15分
已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写C语言函数实现从中去掉所有
ansi编码的的数字和字母（包括大小写).要求在原字串上返回结果。
int filter_ansi(char* gbk_string);
　　注：汉字的GBK编码范围是0x8140 - 0xFEFE
3）30分
芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片
好芯片，说明你所用的比较次数上限．
　其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．
坏芯片和其它芯片比较时，会随机的给出好或是坏。
4）40分
请设计一个网页存储系统，能存储千万量级的网页。
要求：
1.支持按照URL为键值的随机添加，删除和修改网页
2.支持多个线程同时添加，修改和删除
3.支持多线程按照入库时间批量的获取网页，并尽可能的快
提示:设计应包括如下几方面:
1.网页的存储方式设计,即硬盘数据的组织形式
2.如何支持随机查找
3.如何优化批量检索
4.增删改查之间的同步和互斥,如何达到最大的并发.
     系统限制和一些参考参数:
硬盘400G, 内存4G
硬盘的I/O比内存的I/O速度慢1000倍
硬盘的连续I/O比随机I/O快10倍
网页的平均长度为25K
附加：
请说明你的系统在亿到十亿规模的扩展方法．

百度2007年ECOM-商务软件笔试题（二）

一、 一个文本文件有多行，每行为一个URL。请编写代码，统计出URL中的文件名及出现次数。

　　a) 文件名不包括域名、路径和URL参数，例如http://www.rs.com/n.op/q/rs?id=1中的文件名是rs。

　　b) 部分URL可能没有文件名，例如http://www.abc.com/，这类统计为“空文件名”。

　　c) 出现在不同URL中的相同文件名视为同一文件名，例如http://www.ceshi.com/hi.php

　　和ftp://ftp.cdef.com/hi.php为同一文件名

　　文件内容示例如下：

　　http://www.test.com/abc/de/fg.php?id=1&url=http://www.test.com/index.html

　　http://www.ceshi.com/hi.jsp

　　ftp://ftp.ceshi.com/hi.jsp

　　http://www.hello.com/cw/hi.jsp?k=8

　　http://www.hi.com/jk/l.html?id=1&s=a.html

　　http://www.rs.com/n.op/q/rs?id=1

　　http://www.abc.com/

二、 一个简单的论坛系统，以数据库储存如下数据：

　　用户名，email，主页，电话，联系地址，发帖标题，发帖内容，回复标题，回复内容。

　　每天论坛访问量300万左右，更新帖子10万左右。

　　请给出数据库表结构设计，并结合范式简要说明设计思路。

三、 现有两个文件，

　　a)数据文件A，格式为：关键词、IP地址、时间，记录条数为1000万左右，该文件是无序排列的。

　　b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。

　　要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。

　　请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)

以前写代码从来没注意到，以为realloc函数还是比较温和的。最近因为realloc使用不当导致了一个很隐蔽的bug，才发现realloc许多以前没注意到的细节。

void* realloc(ptr,size) 分配内存要比malloc复杂多了，大体流程如下（需要注意的是，realloc 从来就不保证调整后的内存空间和原来的内存空间保持同一内存地址。相反，realloc 返回的指针很可能指向一个新的地址。所以在以下流程中不会强调返回值与ptr的关系，即便有些实现可能会相等。）：

if size==0

    释放ptr;

    return NULL;

else if  有足够多的堆空间

    分配size大小的堆空间;

    if( ptr!=null )

         拷贝ptr内容到新堆空间. ptr多余部分会截去.;

    如果必要，回收ptr;

    return 新堆空间的基地址;

else if 没有足够的堆空间

     ptr不做任何变动;

     return NULL;

以前写代码太关注于ptr的易失效性。 经常这样写代码：

ptr=relloc(ptr,size);

正常情况下它会工作的很好。可如果发生第三种情况，即堆空间不足，那么上面的代码会造成内存泄漏。比较安全的写法应该是

temp = ptr;

ptr=relloc(temp,size);

if(size!=0 && ptr==NULL)

    内存不足，做相应处理;

       对于一个在北京住惯的人，像我，春天要是只刮风，便觉得是奇迹；北京的春天是刮沙的。对于一个刚由外地来北京的人，像你，春天看见沙尘暴，便觉得是怪事；那你在北京一定天天有惊喜。自然，在沙漠的地方，沙尘暴是永远那么强势，可北京的沙尘暴，阴柔的反有点叫人害怕。
        呜呼，作为大中国的首都，而能常有沙尘的天气，北京真得算个“宝地”。
       设若单单是有沙尘，那也算不了出奇。请闭上眼睛想：一个老城，没山没水，房子那么贵，马路那么堵，居然还聚集了那么多忙忙碌碌的人，这是不是挺有境界？沙尘整把北京围了个圈儿，没缺着一点口儿。这一圈沙尘在春天特别可爱，好像是把北京放在一个小摇篮里，它们安静不动地低声地说“你们放心吧，明年春天我们还来”。真的，北京的人们在春天是面带苦笑的。他们一看那灰蒙蒙的天，心中便觉得有了着落，有了依靠。他们由天上看到地上，便不知不觉地想起："今天也许又要刮沙了吧？这样的天气，明天早上我的车又该去洗洗了吧？"就是这点幻想不能一时实现，他们也并不着急，因为有这样慈善的春天，干啥还希望别的呢！