【期】冲顶大会、百万英雄、芝士超人题目
游戏类型：
大小：72.57MB
扫一扫下载游戏
类似百万英雄的答题赢钱软件
本期小编为大家更新的是期，冲顶大会，百万英雄和芝士超人的题库。有需要这些问题答案的朋友可以来本站看看，之前题库小编通过表格为大家呈献出来哦。
&&&往期芝士超人、冲顶大会、百万英雄题目分享&&&
冲顶大会（13：00）：
1.巴西的国舞是哪种舞蹈?
[ '桑巴舞', '肚皮舞', '探戈' ]
答案：桑巴舞
2.星巴克诞生在美国的哪个城市?
[ '纽约', '西雅图', '洛杉矶' ]
答案：西雅图
3.下列名称不属于二十四节气的是?
[ '谷雨', '大伏', '芒种' ]
答案：大伏
4.下列哪种动物不会游泳?
[ '蛇', '企鹅', '河马' ]
答案：河马
5.周杰伦歌曲《烟花易冷》的故事背景在哪个城市?
[ '洛阳', '北京', '上海' ]
答案：洛阳
6韩国女团少女时代,出道时一共有几个人?
[ '9', '5', '12' ]
7.在茅台酿造工艺中,被称为&沙&的是?
[ '高梁', '沙土', '糯米' ]
答案：高粱
8.三大金字塔中最大的是？
[ '', '' , '' ]
答案：胡夫金字塔
9.动画形象唐老鸭首次出现的电影是哪一部?
[ '《聪明的小母鸡》', '《唐老鸭的侄子》', '《唐老鸭的草稿》' ]
答案：《聪明的小母鸡》
10.《儒林外史》作者吴敬梓在1月11日逝世,他这一生没经历过以下哪个皇帝的统治?
[ '雍正', '康熙', '顺治' ]
答案：顺治
11.宇宙中的伽玛射线暴是如何产生的?
[ '小行星撞击', '恒星爆炸', '行星爆炸' ]
答案：恒星爆炸
12.哪种动物的乳汁最适合替代人类母乳?
[ '牛', '驴', '羊' ]
冲顶大会（17：00）：
1.四六级单词书,和大部分英语考试词典中的第一个单词是什么?
[ 'abundant', 'abandon', 'ability' ]
答案：abandon
2.&失败乃成功之母&中&母&的意思是?
[ '妈妈', '先导/基础', '婆婆' ]
答案：先导/基础
3.汪峰出道时成立的乐队&鲍家街43号&,是北京的哪个地点?
[ '中央音乐学院', '中央美术学院', '中央戏剧学院' ]
答案：中央音乐学院
4.北京在哪一年申办奥运会成功的?
[ '2001', '2002', '2008' ]
答案：2001
5.由《大众电影》杂志社创办的奖项是?
[ '百花奖', '金鸡奖', '华表奖' ]
答案：百花奖
6.TEBOYS的英文全拼是?
[ 'The Fresh boys', 'The Fire Boys', 'The Fighting Boys' ]
答案：The Fighting Boys
7.以下哪位总统没有被雕刻在美国总统山上?
[ '乔治&华盛顿', '富兰克林&皮尔斯', '西奥多&罗斯福' ]
答案：富兰克林&皮尔斯
8.成语&香草美人&的含义是?
[ '忠君爱国的思想', '动人仪表的女子', '沁人心脾的气味' ]
答案：忠君爱国的思想
9.2017年,钟汉良和高晓松因为同个角度晒出什么微博而登上热搜?
[ '美腿', '早餐', '头发' ]
答案：早餐
10.刘禅的两位皇后都是谁的女儿?
[ '司马懿', '诸葛亮', '张飞' ]
答案：张飞
11.&户枢不蠹&的前一句是?
[ '流水不腐', '河水不腐', '海水不腐' ]
答案：流水不腐
12.以下哪个是人工降雨中所需要的?
[ '碘化金', '碘化银', '碘化铜' ]
答案：碘化银
冲顶大会（19：00）：
1.小说《三国演义》中谁死在了落凤坡
[ '诸葛亮', '鲁肃', '庞统']
答案：庞统
2.中国的空间站名字叫？
[ '礼炮号', '和平号', '天宫好']
答案：天宫号
3.小说《飘》创作的背景为？
[ '美国南北战争', '世界大战', '北美独立战争' ]
答案：美国南北战争
4.《水浒传》中孙二娘的绰号是？
[ '母大虫', '一丈青', '母夜叉]
答案：母夜叉
5.我们常吃的&猪肚&到底是猪的什么部位？
[ '胃', '肝', '肠' ]
6.写信时，信的结尾写上&此致&，&敬礼&，此致是什么意思？
[ '表示致敬', '到此为止', '在此敬礼' ]
答案：到此为止
7.成语&上根大器&是指？
[ '极为自负的人', '自作聪明的人', '天资极高的人' ]
答案：天资极高的人
8.在中国不插卡无讯号的情况下，任何手机都可以拨打的号码是？
[ '110', '112', '120' ]
9.哈雷彗星的最早记录是哪国人留下的？
[ '美国人', '中国人', '英国人' ]
答案：中国人
10.为什么&黑五&被商家们称作黑色星期五？
[ '因为没到周五就生意惨淡', '因为用黑笔记录盈利', '因为禁曲《黑色星期五》' ]
答案：因为用黑笔记录盈利
11.日本品牌&优衣库&的英文名是？
[ 'UNIOLO', 'UNIOLQ', 'UNIQLO' ]
答案：UNIQLO
12.在泰国，星期几的代表色是紫色？
[ '星期五', '星期六', '星期日' ]
答案：星期六
冲顶大会（21：00）：
1.2004年的夏季奥运会在哪里举行？
[ '雅典', '悉尼', '巴黎' ]
答案：雅典
2.RGB（三原色光模式）中的&G&是什么颜色？
[ '灰色', '蓝色', '绿色' ]
答案：绿色
3.色盲患者最普遍的不易分辨的颜色是？
[ '蓝绿', '黑白', '红绿' ]
答案：红绿
4.动漫《火影忍者》中，主角鸣人是哪个族群的？
[ '奈良一族', '宇智波一族', '漩涡一族' ]
答案：漩涡一族
5.足球起源于中国何地？
[ '山东', '云南', '新疆' ]
答案：山东
6.电影《泰坦尼克号》男主角为女主角画的是什么？
[ '素描', '水彩画', '油画' ]
答案：素描
7.奥运会五环的颜色自左至右的颜色排序为？
[ '蓝、黑、黄、绿、红', '蓝、黄、黑、绿、红', '蓝、黑、黄、绿、白' ]
答案：蓝、黄、黑、绿、红
8.台剧《恶作剧之吻》中江直树的弟弟叫？
[ '江裕树', '江直人', '江小树' ]
答案：江裕树
9.乐器中的&圆号&又称？
[ '英国号', '美国号', '法国号' ]
答案：法国号
10.综艺 《快乐大本营》是从哪一年开始播出的？
[ '1995年', '1997年', '1990年' ]
答案：1997年
11.1980年的今天，中国颁布了第一个个体工商户营业执照，它的经营范围是？
[ '日用百货', '食品', '皮革制品' ]
答案：日用百货
12.在节目《国家宝藏》中出现的《千里江山图》作者是？
[ '于蕾', '李晨', '王希孟' ]
答案：王希孟
百万英雄（11：00）：
1.以下哪种植物是生长在沙漠中?
[ '水仙花', '仙人掌', '荷花' ]
答案：仙人掌
2.以下人物当过唐朝皇帝的是?
[ '朱元璋', '李世民', '曹操' ]
答案：李世民
3.外号&飞人&的NBA著名球星是?
[ '科比', '乔丹', '姚明' ]
答案：乔丹
4.海水浮力比湖水更大是因为?
[ '海中盐分更多', '海中浪大', '海的面积比湖大' ]
答案：海中盐分更多
5.山东省的省会是?
[ '青岛', '济南', '大连' ]
答案：济南
6.&落霞与孤鹜齐飞,秋水共长天色&是作者在哪里看到的景象?
[ '岳阳楼', '黄鹤楼', '滕王阁' ]
答案：滕王阁
7.现在是晚上20点钟,再过8小时是几点钟?
[ '4点钟', '6点钟', '8点钟' ]
答案：4点钟
8.以下歌曲中,不是罗大佑创作的是?
[ '《童年》', '《明天会更好》', '《简单爱》' ]
答案：《简单爱》
9.地球的自转方向是?
[ '自西向东', '自东向西', '自南向北' ]
答案：自西向东
10.&世界四大国际电影节&不包括下列哪一项?
[ '东京国际电影节', '柏林国际电影节', '威尼斯国际电影节' ]
答案：东京国际电影节
11.一般来说,人成年后最多有多少颗牙齿?
[ '28', '30', '32' ]
12.&但使龙城飞将在,不教胡马度阴山&中的&龙城飞将&是哪个时期的人物?
[ '东汉', '西汉', '魏晋' ]
答案：西汉
百万英雄（13：00）：
1.我们会把农历的几月几日叫作&龙抬头&?
[ '二月二', '三月三', '四月四' ]
答案：二月二
2.&锅包肉&是下列哪个地区的名菜?
[ '淮扬', '川渝', '东北' ]
答案：东北
3.以下哪部作品是陈凯歌导演的?
[ '《让子弹飞》', '《霸王别姬》', '《春光乍泄》' ]
答案：《霸王别姬》
4.在算式&7-2=5&中,哪个数是&被减数&?
[ '7', '2', '5' ]
5.&两弹一星&中的&-星&指?
[ '彗星', '影视明星', '人造卫星' ]
答案：人造卫星
6.&垂涎三尺&中的&涎&是什么意思?
[ '眼泪', '口水', '瀑布' ]
答案：口水
7.中药&陈皮&是哪种植物的皮?
[ '香蕉', '冬瓜', '橘子' ]
答案：橘子
8.&梨花带雨&原本是用来形容哪位美女的?
[ '杨玉环', '西施', '嫦娥' ]
答案；杨玉环
9.哪项运动可以抱着球跑?
[ '足球', '篮球', '橄榄球' ]
答案：橄榄球
10.少年偶像组合 TFBOYS名称中的&F&是什么意思?
[ '梦想', '加油', '青春' ]
答案：加油
11.在摄影中,单反使用哪种镜头拍摄会让照片的视野更加开阔?
[ '广角镜头', '长焦镜头', '移轴镜头' ]
答案：广角镜头
12.&三江源&中的&三江&不包括?
[ '怒江', '长江', '黄河' ]
答案：怒江
百万英雄（19：00）：
1.以下哪个动物不会游泳?
[ '鸭子', '鸡', '海豹' ]
2.美国男子职业篮球联赛的简称是?
[ 'NBA', 'NFL', 'MLB' ]
3.以下数字中和四分之一不相等的是?
[ '百分之二十五', '零点二五', '二十五' ]
答案：二十五
4.迪士尼代表人物形象&米奇&是只?
[ '老鼠', '猫', '狗' ]
答案：老鼠
5.我国公民身份证号码最后一位的&X&代表数字几?
[ '10', '11', '12' ]
6.英剧《神探夏洛克》的主人公福尔摩斯因其剧中造型被粉丝昵称为?
[ '卷福', '米福', '马福' ]
答案：卷福
7.&变脸&是我国戏剧中哪个剧种的绝活?
[ '京剧', '川剧', '豫剧' ]
答案：川剧
8.下列城市不在长江边的是?
[ '成都', '武汉', '南京' ]
答案：成都
9.深得乾隆皇帝喜爱的大臣和珅姓什么?
[ '和', '钮祜禄', '爱新觉罗' ]
答案：钮祜禄
10.电视剧《春风十里不如你》化用了谁的诗句?
[ '杜审言', '杜甫', '杜牧' ]
答案：杜牧
11.下列省份自新中国成立以来没有更换过省会的是?
[ '河北', '河南', '湖南' ]
答案：湖南
12.粤语歌曲《千千阙歌》中的&阙&字是什么意思?
[ '遍', '首', '通&之&字' ]
百万英雄（20：00）：
1.以下是儒家的代表人物的是?
[ '老子', '孔子', '庄子' ]
答案：孔子
2.印第安人主要分布在哪个大洲?
[ '非洲', '大洋洲', '美洲' ]
答案：美洲
3.网络用语&爱豆&是指?
[ '偶像', '说话很逗', '喜欢豆子' ]
答案：偶像
4.《Panama》这首歌改编的舞蹈在抖音大火,这个舞蹈被大部分人称为?
[ '拍手舞', 'C哩C哩舞', '嘀哩嘀哩舞' ]
答案：C哩C哩舞
5.以下人物中没有出演电影《战狼》的是?
[ '吴刚', '张翰', '洪金宝' ]
答案：洪金宝
6.阿拉伯数字是什么人发明的?
[ '古印度人', '阿拉伯人', '中国人' ]
答案：古印度人
7.以下哪个选项属于土家族的代表建筑之一?
[ '吊脚楼', '窑洞', '四合院' ]
答案：吊脚楼
8.成语&才高八斗&一开始说的是谁?
[ '诸葛亮', '曹植', '谢灵运' ]
答案：曹植
9.著名文学家沈从文是哪个地方的人?
[ '湖南', '浙江', '山东' ]
答案：湖南
10.以下哪个是古代&砒霜&的别称?
[ '丧命散', '鹤顶红', '断肠散' ]
答案：鹤顶红
11.马拉松名字是来源于?
[ '人名', '地名', '历史上国家名字' ]
答案：地名
12.&春宵一刻值千金&的下一句是?
[ '花有清香月有阴', '金榜题名照归心', '花近高楼伤客心' ]
答案：花有清香月有阴
百万英雄（21：00）：
1.古诗&两个黄鹂鸣翠柳&的下句是?
[ '疑是银河落九天', '一行白鹭上青天', '门泊东吴万里船' ]
答案：一行白鹭上青天
2.08年北京奥运会主题曲是?
[ '北京祝福你', '北京欢迎你', '北京我爱你' ]
答案：北京欢迎你
3.以下哪个软件是图像处理软件?
[ 'PPT', 'WORD', 'PHOTOSHOP' ]
答案：PHOTOSHOP
4.10块钱等于多少分?
[ '10', '100', '1000' ]
答案：1000
5.四川话&摆龙门阵&是什么意思?
[ '拉拉家常', '打打麻将', '聚众斗殴' ]
答案：拉拉家常
6.伦敦城市标志之一的&伦敦眼&是什么建筑?
[ '塔桥', '摩天轮', '风车' ]
答案：摩天轮
7.下列动物不是澳大利亚特有的是?
[ '袋鼠', '羊驼', '考拉' ]
答案：羊驼
8.8开立方根等于多少?
[ '2', '3', '4']
9.动画电影《疯狂动物城》中,警官朱迪是一只?
[ '狐狸', '兔子', '熊' ]
答案：兔子
10.&玄武门之变&发生在哪位皇帝在位期间?
[ '唐太宗', '唐高宗', '唐高祖' ]
答案：唐高祖
11.&木马&这个名字来源于古希腊的哪场战争?
[ '希波战争', '特洛伊战争', '七年战争' ]
答案：特洛伊战争
12.由刘德华、张学友、黎明、郭富城同台演唱过的歌曲是?
[ '《吻别》', '《青春舞曲》', '《忘情水》' ]
答案：《青春舞曲》
百万英雄（22：00）：
1.&三人行,必有我师焉&出自以下哪部作品?
[ '《诗经》', '《三字经》', '《论语》' ]
答案：《论语》
2.一个三位数的最高数位是什么计数单位?
[ '十', '百', '千' ]
3.下列哪项不是汽车的安全配置?
[ '天窗', '安全气囊', '安全带' ]
答案：天窗
4.以下哪首歌曲对应的歌手不正确?
[ '简单爱周杰伦', '山丘李宗盛', '倔强那英' ]
答案：倔强那英
5.&本帮菜&是我国哪个地方风味菜的别称?
[ '上海', '重庆', '陕西' ]
答案：上海
6.一般来说,诺贝尔奖各奖项时隔几年颁发一次?
[ '1', '2', '4' ]
7.以下电影中没有出现虚拟空间的是?
[ '《黑客帝国》', '《盗梦空间》', '《银翼杀手》' ]
答案：《银翼杀手》
8.&完璧归赵&中除了赵国还涉及到哪个国家?
[ '齐国', '燕国', '秦国' ]
答案：秦国
9.哪位科学家发现了电磁感应现象?
[ '法拉第', '牛顿', '安培' ]
答案：法拉第
10.&&衣带水&的典故中,水指的是哪条?
[ '长江', '黄河', '珠江' ]
答案：长江
11.斯诺克比赛中在对手不失误的情况下,单杆最高得分是多少?
[ '145', '146', '147' ]
12.玻璃钢是很常见的一种制作材料,实际上它是一种?
[ '塑料', '钢化材料', '比较硬的玻璃' ]
答案：塑料
芝士超人（19：30）：
1.小s的中文名是?
[ '徐熙娣', '徐熙媛', '徐熙颜' ]
答案：徐熙娣
2.南京话&小潘西&是什么意思?
[ '小螃蟹', '小姑娘', '小笼包' ]
答案：小姑娘
3.美剧《破产姐妹》主人公是?
[ '两个男孩', '两个女孩', '男一女' ]
答案：两个女孩
4.海尔兄弟的內裤的颜色是?
[ '黄色和蓝色', '黄色和红色', '蓝色和红色' ]
答案：黄色和蓝色
5.巴黎圣母院是什么式建筑的代表作?
[ '哥特', '中式', '园林风格' ]
答案：哥特
6.哪项不是狼人杀游戏中的角色?
[ '预言家', '猎人', '梅林' ]
答案：梅林
7.《天线宝宝》中最高的是?
[ '喜羊羊', '熊大', '丁丁' ]
答案：丁丁
8.英国绅士为什么总是要手提把伞?
[ '拗造型', '气候原因', '防身' ]
答案：气候原因
9.李白的《秋风词》中&早知如此绊人心&下一句是?
[ '抱膝灯前影伴身', '昔年相望抵天涯', '何如当初莫相识' ]
答案：何如当初莫相识
10.著名运动品牌阿迪达斯是哪个国家的?
[ '日本', '德国', '韩国' ]
答案：德国
11.下列传世名画中不是唐代的是?
[ '《五牛图》', '《汉宫春晓图》', '《唐宫仕女图》' ]
答案：《汉宫春晓图》
12.在鸟类的感觉器官中,最先退化的器官是?
[ '听觉', '视觉', '嗅觉' ]
答案：嗅觉
芝士超人（20：30）：
1.下列清朝皇帝中哪位是末代皇帝
[ '宣统', '光绪', '同治' ]
答案：宣统
2.下列哪个不属于文学写作&小说三要素&之
[ '时间', '人物', '环境' ]
答案：时间
3.按平均每分钟说话的音节算哪个国家的人说话最快?
[ '法国', '日本', '德国' ]
答案：法国
4.孔子在家里的排名?
[ '老大', '老二', '老三' ]
答案：老二
5.供给人的机体热能的最主要营养物质是
[ '蛋白质', '脂肪', '糖' ]
6.&下半旗致哀&的由来是源于什么人物的去世
[ '酋长', '船长', '皇帝' ]
答案：船长
7.本场闪电场,一共几道题?
[ '8', '12', '24' ]
8.世界上第一部成文法典是
[ '《汉谟拉比法典》', '《法经》', '《乌尔纳姆法典》' ]
答案：《乌尔纳姆法典》
热门安卓游戏排行
类别：角色扮演
类别：角色扮演
类别：角色扮演
47089人推荐
56883人推荐
66741人推荐
75726人推荐
85490人推荐
95054人推荐
104915人推荐
最新安卓游戏排行
类别：射击游戏
类别：动作游戏
类别：角色扮演写在前面整个项目都托管在了 Github 上：这一节内容可能会用到的库文件有 Measurement 和 TestCase，同样在 Github 上可以找到。善用 Ctrl + F 查找题目。习题&题解1.4.1题目证明从 N 个数中取三个整数的不同组合总数为 N(N - 1)(N - 2) / 6。解答即为证明组合计算公式：C(N, 3)= N! / [(N - 3)! × 3!]= [(N - 2) * (N - 1) * N] / 3!= N(N - 1)(N - 2) / 6
显然 N 必须大于等于 3。N = 3 时公式正确，只有一种组合。N = 4 时公式正确，只有四种组合。扩展到 N+1 个数，将 N = N + 1 代入，可得：(N + 1)N(N - 1) / 6N + 1 个数能组成的三位数组合可以这样理解前 N 个数中取三个数的所有组合 +多出的一个数和前 N 个数中的任意取两个数的所有组合即为 N(N-1)(N - 2) / 6 + C(N, 2)变形后即为(N + 1)N(N - 1) / 6 得证。1.4.2题目修改 ThreeSum，正确处理两个较大 int 值相加可能溢出的情况。解答将 a[i] + a[j] + a[k] 改为 (long)a[i] + a[j] + a[k] 即可。此时整个式子将按照精度最高（也就是 long）的标准计算。long.MaxValue = 4775807 & int.MaxValue * 3 = 代码namespace Measurement
/// &summary&
/// 用暴力方法寻找数组中和为零的三元组。
/// &/summary&
public static class ThreeSum
/// &summary&
/// 输出所有和为零的三元组。
/// &/summary&
/// &param name="a"&输入数组。&/param&
public static void PrintAll(int[] a)
int n = a.L
for (int i = 0; i & ++i)
for (int j = i + 1; j & ++j)
for (int k = j + 1; k & ++k)
if ((long)a[i] + a[j] + a[k] == 0)
Console.WriteLine($"{a[i]} + {a[j]} + {a[k]}");
/// &summary&
/// 计算和为零的三元组的数量。
/// &/summary&
/// &param name="a"&输入数组。&/param&
/// &returns&&/returns&
public static int Count(int[] a)
int n = a.L
int count = 0;
for (int i = 0; i & ++i)
for (int j = i + 1; j & ++j)
for (int k = j + 1; k & ++k)
if ((long)a[i] + a[j] + a[k] == 0)
}1.4.3题目修改 DoublingTest，使用 StdDraw 产生类似于正文中的标准图像和对数图像，根据需要调整比例使图像总能够充满窗口的大部分区域。解答见代码，这里贴出绘图函数，窗体只是在得到测试结果之后简单调用以下这两个函数。代码public static void PaintLinear(double[] testResult)
//新建一个绘图窗口
Form2 linear = new Form2();
linear.Show();
//新建画布
Graphics canvas = linear.CreateGraphics();
//获取窗口区域
Rectangle rect = linear.ClientR
//计算单位长度（十等分）
int unitY = rect.Height / 10;
int unitX = rect.Width / 10;
//获取中心区域（上下左右增加 10% 的内补）
Rectangle center = new Rectangle(rect.X + unitX, rect.Y + unitY, unitX * 8, unitY * 8);
//绘制坐标系
canvas.DrawLine(Pens.Black, center.X, center.Y, center.X, center.Y + center.Height);
canvas.DrawLine(Pens.Black, center.X, center.Y + center.Height, center.X + center.Width, center.Y + center.Height);
//对 X 轴 10 等分，对 Y 轴 10 等分
int xaxisUnit = center.Width / 10;
int yaxisUnit = center.Height / 10;
//标记 X 轴坐标值
for (int i = 1; i &= 8; i += i)
canvas.DrawString(i + "N", linear.Font, Brushes.Black, center.X + i * xaxisUnit, center.Y + center.Height);
//反转坐标系
canvas.TranslateTransform(0, linear.ClientRectangle.Height);
canvas.ScaleTransform(1, -1);
//计算单位长度
double Unit = center.Height / testResult[3];
PointF[] result = new PointF[4];
for (int i = 0, j = 1; i & 4 && j &= 8; ++i, j += j)
result[i] = new PointF(center.X + j * xaxisUnit, (float)(center.Y + Unit * testResult[i]));
canvas.DrawLines(Pens.Black, result);
canvas.Dispose();
public static void PaintLogarithm(double[] testResult)
//新建一个绘图窗口
Form2 log = new Form2();
log.Show();
//新建画布
Graphics canvas = log.CreateGraphics();
//获取窗口区域
Rectangle rect = log.ClientR
//计算单位长度（十等分）
int unitY = rect.Height / 10;
int unitX = rect.Width / 10;
//获取中心区域（上下左右增加 10% 的内补）
Rectangle center = new Rectangle(rect.X + unitX, rect.Y + unitY, unitX * 8, unitY * 8);
//绘制坐标系
canvas.DrawLine(Pens.Black, center.X, center.Y, center.X, center.Y + center.Height);
canvas.DrawLine(Pens.Black, center.X, center.Y + center.Height, center.X + center.Width, center.Y + center.Height);
//对 X 轴 10 等分，对 Y 轴 10 等分
int xaxisUnit = center.Width / 10;
int yaxisUnit = center.Height / 10;
//标记 X 轴坐标值
for (int i = 1; i &= 8; i += i)
canvas.DrawString(i + "N", log.Font, Brushes.Black, center.X + i * xaxisUnit, center.Y + center.Height);
//反转坐标系
canvas.TranslateTransform(0, log.ClientRectangle.Height);
canvas.ScaleTransform(1, -1);
//计算单位长度
double Unit = center.Height / testResult[3];
PointF[] result = new PointF[4];
for (int i = 0, j = 1; i & 4 && j &= 8; ++i, j += j)
result[i] = new PointF(center.X + j * xaxisUnit, (float)(center.Y + Unit * testResult[i]));
canvas.DrawLines(Pens.Black, result);
canvas.Dispose();
}1.4.4题目参照表 1.4.4 为 TwoSum 建立一张类似的表格。解答代码分块↑时间分析↓1.4.5题目给出下面这些量的近似：a. N + 1b. 1 + 1/Nc. (1 + 1/N)(1 + 2/N)d. 2N^3 - 15N^2 + Ne. lg(2N) / lgNf. lg(N^2 + 1) / lgNg. N^100 / 2^N解答类似于取极限的做法。a. Nb. 1c. 1d. 2N3e. 1f. 2g. N100&1.4.6题目给出以下代码段的运行时间的增长数量级（作为 N 的函数）。a.int sum = 0;
for (int n = N; n & 0; n /= 2)
for (int i = 0; i & i++)
sum++;b.int sum = 0;
for (int i = 1; i & N; i *= 2)
for (int j = 0; j & j++)
sum++;c.int sum = 0;
for (int i = 1; i & N; i *= 2)
for (int j = 0; j & N; j++)
sum++;解答a. N + N/2 + N/4 + … = ~2N，线性。b. 1 + 2 + 4 + … = ~2N，线性。c. logN * N，线性对数。1.4.7题目以统计涉及输入数字的算数操作（和比较）的成本模型分析 ThreeSum。解答最外层循环进行了 N 次比较。次外层循环进行了 N^2 次比较。最里层循环进行了 N^3 次比较。内部 if 语句进行了 N^3 次比较。if 内部进行了 N(N-1) 次加法。加起来，~2N^3。1.4.8题目编写一个程序，计算输入文件中相等的整数对的数量。如果你的第一个程序是平方级别的，请继续思考并用 Array.sort() 给出一个线性对数级别的解答。解答平方级别：直接二层循环遍历一遍。线性对数：只遍历一遍数组，在遍历过程中用二分查找确认在剩余数组中是否有相等的整数。代码/// &summary&
/// 暴力查找数组中相等的整数对。
/// &/summary&
/// &param name="a"&需要查找的数组。&/param&
/// &returns&&/returns&
static int CountEqual(int[] a)
int n = a.L
int count = 0;
for (int i = 0; i & ++i)
for (int j = i + 1; j & ++j)
if (a[i] == a[j])
}暴力算法↑二分查找算法↓/// &summary&
/// 利用二分查找进行优化的查找相等整数对算法。
/// &/summary&
/// &param name="a"&需要查找的数组。&/param&
/// &returns&&/returns&
static int CountEqualLog(int[] a)
int n = a.L
int count = 0;
Array.Sort(a);
for (int i = 0; i & ++i)
if (BinarySearch.Rank(a[i], a, i + 1, a.Length - 1) != -1)
}1.4.9题目已知由倍率实验可得某个程序的时间倍率为 2^b 且问题规模为 N0 时程序运行时间为 T，给出一个公式预测该程序在处理规模为 N 的问题时所需的运行时间。解答1.4.10题目修改二分查找算法，使之总是返回和被查找的键匹配的索引最小的元素。（但仍能够保证对数级别的运行时间）解答修改二分查找的结束条件，找到后仍然向左侧寻找，如果还能找到更小的，则返回较小的下标；否则返回当前下标。代码namespace _1._4._10
/// &summary&
/// 二分查找。
/// &/summary&
public class BinarySearch
/// &summary&
/// 用递归方法进行二分查找。
/// &/summary&
/// &param name="key"&关键字。&/param&
/// &param name="a"&查找范围。&/param&
/// &param name="lo"&查找的起始下标。&/param&
/// &param name="hi"&查找的结束下标。&/param&
/// &returns&返回下标，如果没有找到则返回 -1。&/returns&
public static int Rank(int key, int[] a, int lo, int hi)
if (hi & lo)
return -1;
int mid = (hi - lo) / 2 +
if (a[mid] == key)
int mini = Rank(key, a, lo, mid - 1);
if (mini != -1)
else if (a[mid] & key)
return Rank(key, a, mid + 1, hi);
return Rank(key, a, lo, mid - 1);
}1.4.11题目为 StaticSETofInts （请见表 1.2.15） 添加一个实例方法 howMany()，找出给定键的出现次数且在最坏情况下所需的运行时间应该和 log(N) 成正比。解答这里给出官网上的 Java 实现：。howMany() 可以用二分查找实现，在找到一个值后继续向两侧查找，最后返回找到的次数。代码using S
namespace Measurement
/// &summary&
/// 有序数组，能够快速查找并自动维护其中的顺序。
/// &/summary&
public class StaticSETofInts
private int[]
/// &summary&
/// 用一个数组初始化有序数组。
/// &/summary&
/// &param name="keys"&源数组。&/param&
public StaticSETofInts(int[] keys)
this.a = new int[keys.Length];
for (int i = 0; i & keys.L ++i)
this.a[i] = keys[i];
Array.Sort(this.a);
/// &summary&
/// 检查数组中是否存在指定元素。
/// &/summary&
/// &param name="key"&要查找的值。&/param&
/// &returns&存在则返回 true，否则返回 false。&/returns&
public bool Contains(int key)
return Rank(key, 0, this.a.Length - 1) != -1;
/// &summary&
/// 返回某个元素在数组中存在的数量。
/// &/summary&
/// &param name="key"&关键值。&/param&
/// &returns&返回某个元素在数组中存在的数量。&/returns&
public int HowMany(int key)
int hi = this.a.Length - 1;
int lo = 0;
return HowMany(key, lo, hi);
/// &summary&
/// 返回某个元素在数组中存在的数量。
/// &/summary&
/// &param name="key"&关键值。&/param&
/// &param name="lo"&查找起始下标。&/param&
/// &param name="hi"&查找结束下标。&/param&
/// &returns&返回某个元素在数组中存在的数量。&/returns&
private int HowMany(int key, int lo, int hi)
int mid = Rank(key, lo, hi);
if (mid == -1)
return 1 + HowMany(key, lo, mid - 1) + HowMany(key, mid + 1, hi);
/// &summary&
/// 二分查找。
/// &/summary&
/// &param name="key"&关键值。&/param&
/// &param name="lo"&查找的起始下标。&/param&
/// &param name="hi"&查找的结束下标。&/param&
/// &returns&返回关键值的下标，如果不存在则返回 -1。&/returns&
public int Rank(int key, int lo, int hi)
while (lo &= hi)
int mid = (hi - lo) / 2 +
if (key & this.a[mid])
hi = mid - 1;
else if (key & this.a[mid])
lo = mid + 1;
return -1;
}1.4.12题目编写一个程序，有序打印给定的两个有序数组（含有 N 个 int 值） 中的所有公共元素，程序在最坏情况下所需的运行时间应该和 N 成正比。解答由于两个数组都是有序的，可以同时进行比较。设 i, j 分别为两个数组的下标。如果 a[i] == a[j]，i 和 j 都向后移动一位。如果 a[i] != a[j]，比较小的那个向后移动一位。循环直到某个数组遍历完毕。这样最后的时间复杂度 ~2N代码using S
namespace _1._4._12
* 编写一个程序，有序打印给定的两个有序数组（含有 N 个 int 值） 中的所有公共元素，
* 程序在最坏情况下所需的运行时间应该和 N 成正比。
class Program
static void Main(string[] args)
int[] a = new int[4] { 2, 3, 4, 10 };
int[] b = new int[6] { 1, 3, 3, 5, 10, 11 };
//2N 次数组访问，数组 a 和数组 b 各遍历一遍
for (int i = 0, j = 0; i & a.Length && j & b.L )
if (a[i] & b[j])
else if (a[i] & b[j])
Console.WriteLine($"Common Element:{a[i]}, First index: (a[{i}], b[{j}])");
}1.4.13题目根据正文中的假设分别给出表示以下数据类型的一个对象所需的内存量：a. Accumulatorb. Transactionc. FixedCapacityStackOfStrings，其容量为 C 且含有 N 个元素。d. Point2De. Interval1Df. Interval2Dg. Double解答对象的固定开销用 Object 表示。a. Accumulator使用 1.2.4.3 节给出的实现。= int * 1 + double + Object * 1= 4 * 1 + 8 + 16 * 1 = 32b. Transaction= string * 1 + Date * 1 + double * 1 + Object * 1= (40 + 16 + 4 + 4 + 2N) * 1 + (8 + 32) * 1 + 8 * 1 + 16 * 1= 128 + 2Nc. FixedCapacityStackOfStrings= string[] * 1 + string * N + int * 1 +& Object * 1= 24 * 1 + N * (64 + 2C) + 4 * 1 + 16 * 1= N * (64 + 2C) + 44= N * (64 + 2C) + 48（填充）d.Point2D= double * 2 + Object * 1= 8 * 2 + 16 * 1= 32e.Interval1D= double * 2 + Object * 1= 8 * 2 + 16 * 1= 32f.Interval2D= Interval1D * 2 + Object * 1= (8 + 24) * 2 + 16 * 1= 80g.Double= double * 1 + Object * 1= 8 * 1 + 16 * 1= 241.4.14题目4-sum。为 4-sum 设计一个算法。解答这里给出暴力方法，将最内侧循环换成二分查找即为优化版本。代码using S
namespace Measurement
/// &summary&
/// 用暴力方法查找数组中和为零的四元组。
/// &/summary&
public static class FourSum
/// &summary&
/// 输出数组中所有和为 0 的四元组。
/// &/summary&
/// &param name="a"&包含所有元素的数组。&/param&
public static void PrintAll(long[] a)
int N = a.L
for (int i = 0; i & N; ++i)
for (int j = i + 1; j & N; ++j)
for (int k = j + 1; k & N; ++k)
for (int l = k + 1; l & N; ++l)
if (a[i] + a[j] + a[k] + a[l] == 0)
Console.WriteLine($"{a[i]} + {a[j]} + {a[k]} + {a[l]} = 0");
/// &summary&
/// 计算和为零的四元组的数量。
/// &/summary&
/// &param name="a"&包含所有元素的数组。&/param&
/// &returns&&/returns&
public static int Count(long[] a)
int N = a.L
int cnt = 0;
for (int i = 0; i & N; ++i)
for (int j = i + 1; j & N; ++j)
for (int k = j + 1; k & N; ++k)
for (int l = k + 1; l & N; ++l)
if (a[i] + a[j] + a[k] + a[l] == 0)
}1.4.15题目快速 3-sum。作为热身，使用一个线性级别的算法（而非基于二分查找的线性对数级别的算法）实现 TwoSumFaster 来计算已排序的数组中和为 0 的整数对的数量。用相同的思想为 3-sum 问题给出一个平方级别的算法。解答由于数组已经排序（从小到大），负数在左侧，正数在右侧。
TwoSumFaster
设最左侧下标为 lo，最右侧下标为 hi。
如果 a[lo] + a[hi] & 0, 说明正数太大，hi--。
如果 a[lo] + a[hi] & 0，说明负数太小，lo++。
否则就找到了一对和为零的整数对，lo++, hi--。
ThreeSumFaster
对于数组中的每一个数 a，ThreeSum 问题就等于求剩余数组中所有和为 -a 的 TwoSum 问题。
只要在 TwoSumFaster 外层再套一个循环即可。
代码/// &summary&
/// TwoSum 的快速实现。（线性级别）
/// &/summary&
/// &param name="a"&需要查找的数组范围。&/param&
/// &returns&数组中和为零的整数对数量。&/returns&
static int TwoSumFaster(int[] a)
int i = 0;
int j = a.Length - 1;
int count = 0;
while (i != j)
if (a[i] + a[j] == 0)
else if (a[i] + a[j] & 0)
/// &summary&
/// ThreeSum 的快速实现。（平方级别）
/// &/summary&
/// &param name="a"&需要查找的数组范围。&/param&
/// &returns&数组中和为零的三元组数量。&/returns&
static int ThreeSumFaster(int[] a)
int count = 0;
for (int i = 0; i & a.L ++i)
int lo = i + 1;
int hi = a.Length - 1;
while (lo &= hi)
if (a[lo] + a[hi] + a[i] == 0)
else if (a[lo] + a[hi] + a[i] & 0)
}1.4.16题目最接近一对（一维）。编写一个程序，给定一个含有 N 个 double 值的数组 a[]，在其中找到一对最接近的值：两者之差（绝对值）最小的两个数。程序在最坏情况下所需的运行时间应该是线性对数级别的。解答先将数组从小到大排序，再遍历一遍即可得到差距最小的两个数。排序算法需要消耗 NlogN，具体见 MSDN：。代码using S
namespace _1._4._16
* 最接近一对（一维）。
* 编写一个程序，给定一个含有 N 个 double 值的数组 a[]，
* 在其中找到一对最接近的值：两者之差（绝对值）最小的两个数。
* 程序在最坏情况下所需的运行时间应该是线性对数级别的。
class Program
//总运行时间： NlogN + N = NlogN
static void Main(string[] args)
double[] a = new double[5] { 0.1, 0.3, 0.6, 0.8, 0 };
Array.Sort(a);//Nlog(N) 具体见 https://msdn.microsoft.com/zh-cn/library/6tf1f0bc(v=vs.110).aspx 备注部分
double minDiff = double.MaxV
double minA = 0;
double minB = 0;
for (int i = 0; i & a.Length - 1; ++i)//N
if (a[i + 1] - a[i] & minDiff)
minA = a[i];
minB = a[i + 1];
minDiff = a[i + 1] - a[i];
Console.WriteLine($"Min Pair: {minA} {minB}, Min Value: {minDiff}");
}1.4.17题目最遥远的一对（一维）。编写一个程序，给定一个含有 N 个 double 值的数组 a[]，在其中找到一对最遥远的值：两者之差（绝对值）最大的两个数。程序在最坏情况下所需的运行时间应该是线性级别的。解答遍历找到最小值和最大值即可。代码using S
namespace _1._4._17
* 最遥远的一对（一维）。
* 编写一个程序，给定一个含有 N 个 double 值的数组 a[]，
* 在其中找到一对最遥远的值：两者之差（绝对值）最大的两个数。
* 程序在最坏情况下所需的运行时间应该是线性级别的。
class Program
static void Main(string[] args)
double[] a = new double[5] { 0.1, 0.3, 0.6, 0.8, 0 };
double min = int.MaxV
double max = int.MinV
for (int i = 0; i & a.L ++i)
if (a[i] & max)
max = a[i];
if (a[i] & min)
min = a[i];
Console.WriteLine($"MaxDiff Pair: {min} {max}, Max Difference: {Math.Abs(max - min)}");
}1.4.18题目数组的局部最小元素。编写一个程序，给定一个含有 N 个不同整数的数组，找到一个局部最小元素：满足 a[i] & a[i-1]，且 a[i] & a[i+1] 的索引 i。程序在最坏情况下所需的比较次数为 ~ 2lgN。解答和二分查找的方式类似，先确认中间的值是否是局部最小，如果不是，则向较小的一侧二分查找。代码using S
namespace _1._4._18
* 数组的局部最小元素。
* 编写一个程序，给定一个含有 N 个不同整数的数组，找到一个局部最小元素：
* 满足 a[i] & a[i-1]，且 a[i] & a[i+1] 的索引 i。
* 程序在最坏情况下所需的比较次数为 ~ 2lgN。
class Program
static void Main(string[] args)
int[] a = new int[5] { 5, 6, 5, 3, 5 };
Console.WriteLine(LocalMinimum(a));
/// &summary&
/// 寻找数组的局部最小元素。
/// &/summary&
/// &param name="testcases"&寻找范围。&/param&
/// &returns&局部最小元素的值。&/returns&
static int LocalMinimum(int[] testcases)
int lo = 0;
int hi = testcases.Length - 1;
int mid = (hi - lo) / 2 +
while (lo & hi)
mid = (hi - lo) / 2 +
if (testcases[mid] & testcases[mid - 1] && testcases[mid] & testcases[mid + 1])
if (testcases[mid - 1] & testcases[mid + 1])
hi = mid - 1;
lo = mid + 1;
return -1;
}1.4.19题目矩阵的局部最小元素。给定一个含有 N^2 个不同整数的 N×N 数组 a[]。设计一个运送时间和 N 成正比的算法来找出一个局部最小元素：满足 a[i][j] & a[i+1][j]、a[i][j] & a[i][j+1]、a[i][j] & a[i-1][j] 以及 a[i][j] & a[i][j-1] 的索引 i 和 j。程序运行时间在最坏情况下应该和 N 成正比。解答算法过程类似于 “滑雪”，从数值较高的一侧向周围数值较小的一侧移动，直到到达“山谷”（局部最小）。首先在中间行搜索最小值，再将最小值与其上下两个元素比较，如果不满足题意，则“滑向”较小的一侧，矩阵被分为了两半（上下两侧）。在较小的一侧，找到中间列的最小值，再将最小值与其左右两个元素比较，如果不满足题意，类似的移动到较小的一侧（左右两侧）。现在查找范围缩小到了原来矩阵的四分之一，递归的进行上述操作，最后可以得到答案。每次查找最小值都是对行/列进行遍历，遍历耗时和 N 成正比。代码using S
namespace _1._4._19
* 矩阵的局部最小元素。
* 给定一个含有 N^2 个不同整数的 N×N 数组 a[]。
* 设计一个运行时间和 N 成正比的算法来找出一个局部最小元素：
* 满足 a[i][j] & a[i+1][j]、a[i][j] & a[i][j+1]、a[i][j] & a[i-1][j] 以及 a[i][j] & a[i][j-1] 的索引 i 和 j。
* 程序运行时间在最坏情况下应该和 N 成正比。
class Program
// 先查找 N/2 行中的最小元素，并令其与上下元素比较，
// 如果不满足题意，则向相邻的最小元素靠近再次查找
static void Main(string[] args)
int[,] matrix = new int[5, 5]
{ 26, 3, 4 , 10, 11 },
{ 5, 1, 6, 12, 13 },
{ 7, 8, 9 , 14, 15 },
{ 16, 17, 18, 27, 20 },
{ 21, 22, 23, 24, 25 }
Console.WriteLine(MinimumRow(matrix, 0, 5, 0, 5));
/// &summary&
/// 在矩阵中间行查找局部最小。
/// &/summary&
/// &param name="matrix"&矩阵。&/param&
/// &param name="rowStart"&实际查找范围的行起始。&/param&
/// &param name="rowLength"&实际查找范围的行结尾。&/param&
/// &param name="colStart"&实际查找范围的列起始。&/param&
/// &param name="colLength"&实际查找范围的列结尾。&/param&
/// &returns&矩阵中的局部最小元素。&/returns&
static int MinimumRow(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength)
int min = int.MaxV
if (rowLength & 3)
return int.MaxV
int mid = rowStart + rowLength / 2;
int minCol = 0;
// 获取矩阵中间行的最小值
for (int i = 0; i & colL ++i)
if (min & matrix[mid, colStart + i])
min = matrix[mid, colStart + i];
// 检查是否满足条件
if (matrix[mid, minCol] & matrix[mid - 1, minCol] && matrix[mid, minCol] & matrix[mid + 1, minCol])
return matrix[mid, minCol];
// 如果不满足则向较小一侧移动
if (matrix[mid - 1, minCol] & matrix[mid + 1, minCol])
return MinimumCol(matrix, rowStart, rowLength, mid + 1, colLength / 2 + 1);
return MinimumCol(matrix, rowStart, rowLength, colStart, colLength / 2 + 1);
/// &summary&
/// 在矩阵中间列查找局部最小。
/// &/summary&
/// &param name="matrix"&矩阵。&/param&
/// &param name="rowStart"&实际查找范围的行起始。&/param&
/// &param name="rowLength"&实际查找范围的行结尾。&/param&
/// &param name="colStart"&实际查找范围的列起始。&/param&
/// &param name="colLength"&实际查找范围的列结尾。&/param&
/// &returns&矩阵中的局部最小元素。&/returns&
static int MinimumCol(int[,] matrix, int rowStart, int rowLength, int colStart, int colLength)
int min = int.MaxV
int n = matrix.GetLength(0);
int mid = n / 2;
int minRow = 0;
// 获取矩阵中间列最小值
for (int i = 0; i & ++i)
if (min & matrix[i, mid])
min = matrix[i, mid];
// 检查是否满足条件
if (matrix[minRow, mid] & matrix[minRow, mid - 1] && matrix[minRow, mid] & matrix[minRow, mid + 1])
return matrix[minRow, mid];
// 如果不满足则向较小一侧移动
if (matrix[minRow, mid - 1] & matrix[minRow, mid + 1])
return MinimumRow(matrix, mid + 1, rowLength / 2 + 1, colStart, colLength);
return MinimumRow(matrix, rowStart, rowLength / 2 + 1, colStart, colLength);
}1.4.20题目双调查找。如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。编写一个程序，给定一个含有 N 个不同 int 值的双调数组，判断它是否含有给定的整数。程序在最坏情况下所需的比较次数为 ~3lgN。解答首先给出 BitMax 类的官方 Java 实现：。我们使用这个类生成双调数组，并使用其中的 Max() 方法找到双调数组的最大值。找到最大值之后分别对左右两侧进行二分查找，注意对于升序和降序的数组二分查找的实现有所不同。代码BitonicMax 类using S
namespace _1._4._20
/// &summary&
/// 双调查找类。
/// &/summary&
public class BitonicMax
/// &summary&
/// 生成双调数组。
/// &/summary&
/// &param name="N"&数组的大小。&/param&
/// &returns&&/returns&
public static int[] Bitonic(int N)
Random random = new Random();
int mid = random.Next(N);
int[] a = new int[N];
for (int i = 1; i & ++i)
a[i] = a[i - 1] + 1 + random.Next(9);
if (mid & 0)
a[mid] = a[mid - 1] + random.Next(10) - 5;
for (int i = mid + 1; i & N; ++i)
a[i] = a[i - 1] - 1 - random.Next(9);
/// &summary&
/// 寻找数组中的最大值。
/// &/summary&
/// &param name="a"&查找范围。&/param&
/// &param name="lo"&查找起始下标。&/param&
/// &param name="hi"&查找结束下标。&/param&
/// &returns&返回数组中最大值的下标。&/returns&
public static int Max(int[] a, int lo, int hi)
if (lo == hi)
int mid = lo + (hi - lo) / 2;
if (a[mid] & a[mid + 1])
return Max(a, mid + 1, hi);
if (a[mid] & a[mid + 1])
return Max(a, lo, mid);
}主程序using S
namespace _1._4._20
* 双调查找。
* 如果一个数组中的所有元素是先递增后递减的，则称这个数组为双调的。
* 编写一个程序，给定一个含有 N 个不同 int 值的双调数组，判断它是否含有给定的整数。
* 程序在最坏情况下所需的比较次数为 ~3lgN
class Program
static void Main(string[] args)
int[] a = BitonicMax.Bitonic(100);
int max = BitonicMax.Max(a, 0, a.Length - 1);
int key = a[50];
int leftside = BinarySearchAscending(a, key, 0, max);
int rightside = BinarySearchDescending(a, key, max, a.Length - 1);
if (leftside != -1)
Console.WriteLine(leftside);
else if (rightside != -1)
Console.WriteLine(rightside);
Console.WriteLine("No Result");
/// &summary&
/// 对升序数组的二分查找。
/// &/summary&
/// &param name="a"&升序数组。&/param&
/// &param name="key"&关键值。&/param&
/// &param name="lo"&查找的左边界。&/param&
/// &param name="hi"&查找的右边界。&/param&
/// &returns&返回找到关键值的下标，如果没有找到则返回 -1。&/returns&
static int BinarySearchAscending(int[] a, int key, int lo, int hi)
while (lo &= hi)
int mid = lo + (hi - lo) / 2;
if (a[mid] & key)
lo = mid + 1;
else if (a[mid] & key)
hi = mid - 1;
return -1;
/// &summary&
/// 对降序数组的二分查找。
/// &/summary&
/// &param name="a"&升序数组。&/param&
/// &param name="key"&关键值。&/param&
/// &param name="lo"&查找的左边界。&/param&
/// &param name="hi"&查找的右边界。&/param&
/// &returns&返回找到关键值的下标，如果没有找到则返回 -1。&/returns&
static int BinarySearchDescending(int[] a, int key, int lo, int hi)
while (lo & hi)
int mid = lo + (hi - lo) / 2;
if (a[mid] & key)
lo = mid + 1;
else if (a[mid] & key)
hi = mid - 1;
return -1;
}1.4.21题目无重复值之中的二分查找。用二分查找实现 StaticSETofInts （参见表 1.2.15），保证 contains() 的运行时间为 ~lgR，其中 R 为参数数组中不同整数的数量。解答直接将 Contains() 实现为二分查找即可。代码/// &summary&
/// 检查数组中是否存在指定元素。
/// &/summary&
/// &param name="key"&要查找的值。&/param&
/// &returns&存在则返回 true，否则返回 false。&/returns&
public bool Contains(int key)
return Rank(key, 0, this.a.Length - 1) != -1;
/// &summary&
/// 二分查找。
/// &/summary&
/// &param name="key"&关键值。&/param&
/// &param name="lo"&查找的起始下标。&/param&
/// &param name="hi"&查找的结束下标。&/param&
/// &returns&返回关键值的下标，如果不存在则返回 -1。&/returns&
public int Rank(int key, int lo, int hi)
while (lo &= hi)
int mid = (hi - lo) / 2 +
if (key & this.a[mid])
hi = mid - 1;
else if (key & this.a[mid])
lo = mid + 1;
return -1;
}1.4.22题目仅用加减实现的二分查找（Mihai Patrascu）。编写一个程序，给定一个含有 N 个不同 int 值的按照升序排列的数组，判断它是否含有给定的整数。只能使用加法和减法以及常数的额外内存空间。程序的运行时间在最坏情况下应该和 logN 成正比。解答普通二分查找是通过除法不断减半缩小搜索范围。这里我们用斐波那契数列来缩小范围。举个例子，例如数组大小是 100，比它大的最小斐波那契数是 144。斐波那契数列如下：0 1 1 2 3 5 8 13 21 34 55 89 144我们记 F(n) = 144,F(n-1) = 89, F(n-2) = 55。我们先查看第 0 + F(n-2) 个数，如果比关键值小则直接将范围缩小到 [55, 100]；否则则在[0, 55]之间查找。之后我们令 n = n-1。递归上述过程即可完成查找。代码/// &summary&
/// 使用斐波那契数列进行的查找。
/// &/summary&
/// &param name="a"&查找范围。&/param&
/// &param name="key"&关键字。&/param&
/// &returns&返回查找到的关键值下标，没有结果则返回 -1。&/returns&
static int rank(int[] a, int key)
// 使用斐波那契数列作为缩减范围的依据
int Fk = 1;
int Fk_1 = 1;
int Fk_2 = 0;
// 获得 Fk，Fk需要大于等于数组的大小，复杂度 lgN
while (Fk & a.Length)
Fk = Fk + Fk_1;
Fk_1 = Fk_1 + Fk_2;
Fk_2 = Fk - Fk_1;
int lo = 0;
// 按照斐波那契数列缩减查找范围，复杂度 lgN
while (Fk_2 &= 0)
int i = lo + Fk_2 & a.Length - 1 ? a.Length - 1 : lo + Fk_2;
if (a[i] & key)
lo = lo + Fk_2;
else if (a[i] == key)
Fk = Fk_1;
Fk_1 = Fk_2;
Fk_2 = Fk - Fk_1;
return -1;
}1.4.23题目分数的二分查找。设计一个算法，使用对数级别的比较次数找出有理数 p/q，其中 0&p&q&N，比较形式为给定的数是否小于 x?解答根据书中的提示，将二分查找中判断相等的条件改为两个数的差小于等于 1/N2。代码// 将二分查找中的相等判定条件修改为差值小于 x，其中 x = 1/N^2。
/// &summary&
/// 二分查找。
/// &/summary&
/// &param name="a"&查找范围。&/param&
/// &param name="key"&关键字。&/param&
/// &returns&结果的下标，没有结果时返回 -1。&/returns&
static int BinarySearch(double[] a, double key)
int lo = 0;
int hi = a.Length - 1;
double threshold = 1.0 / (a.Length * a.Length);
while (lo &= hi)
int mid = lo + (hi - lo) / 2;
if (Math.Abs(a[mid] - key) &= threshold)
else if (a[mid] & key)
lo = mid + 1;
hi = mid - 1;
return -1;
}1.4.24题目扔鸡蛋。假设你面前有一栋 N 层的大楼和许多鸡蛋，假设将鸡蛋从 F 层或者更高的地方扔下鸡蛋才会摔碎，否则则不会。首先，设计一种策略来确定 F 的值，其中扔 ~ lgN 次鸡蛋后摔碎的鸡蛋数量为 ~ lgN。然后想办法将成本降低到~ 2lgF。解答第一问：二分查找即可。第二问：按照第 1, 2, 4, 8,..., 2^k 层顺序查找，一直到 2^k & F，随后在 [2^(k - 1), 2^k] 范围中二分查找。代码这里建立了一个结构体用于返回测试结果：struct testResult
public int F;// 找到的 F 值。
public int BrokenE// 打碎的鸡蛋数。
}用于测试的方法：
/// &summary&
/// 扔鸡蛋，没碎返回 true，碎了返回 false。
/// &/summary&
/// &param name="floor"&扔鸡蛋的高度。&/param&
/// &returns&&/returns&
static bool ThrowEgg(int floor)
return floor &= F;
/// &summary&
/// 第一种方案。
/// &/summary&
/// &param name="a"&大楼。&/param&
/// &returns&&/returns&
static testResult PlanA(int[] a)
int lo = 0;
int hi = a.Length - 1;
int mid = 0;
int eggs = 0;
testResult result = new testResult();
while (lo &= hi)
mid = lo + (hi - lo) / 2;
if (ThrowEgg(mid))
lo = mid + 1;
hi = mid - 1;
result.BrokenEggs =
result.F =
/// &summary&
/// 第二种方案。
/// &/summary&
/// &param name="a"&大楼。&/param&
/// &returns&&/returns&
static testResult PlanB(int[] a)
int lo = 0;
int hi = 1;
int mid = 0;
int eggs = 0;
testResult result = new testResult();
while (ThrowEgg(hi))
if (hi & a.Length - 1)
hi = a.Length - 1;
while (lo &= hi)
mid = lo + (hi - lo) / 2;
if (ThrowEgg(mid))
lo = mid + 1;
hi = mid - 1;
result.BrokenEggs =
result.F =
}1.4.25题目扔两个鸡蛋。和上一题相同的问题，但现在假设你只有两个鸡蛋，而你的成本模型则是扔鸡蛋的次数。设计一种策略，最多扔 2√(N) 次鸡蛋即可判断出 F 的值，然后想办法把这个成本降低到 ~c√(F) 次。这和查找命中（鸡蛋完好无损）比未命中（鸡蛋被摔碎）的成本小得多的情形类似。解答第一问：第一个蛋按照 √(N), 2√(N), 3√(N), 4√(N),..., √(N) * √(N) 顺序查找直至碎掉。这里扔了 k 次，k &= √(N)。k-1√(N) ~ k√(N) 顺序查找直至碎掉，F 值就找到了。这里最多扔 √(N) 次。第二问：按照第 1, 3, 6, 10,..., 1/2k^2 层顺序查找，一直到 1/2k^2 & F，随后在 [1/2k^2 - k, 1/2k^2] 范围中顺序查找。代码这里我们同样定义了一个结构体：struct testResult
public int F;// 测试得出的 F 值
public int BrokenE// 碎掉的鸡蛋数。
public int ThrowT// 扔鸡蛋的次数。
}之后是测试用的方法：/// &summary&
/// 扔鸡蛋，没碎返回 true，碎了返回 false。
/// &/summary&
/// &param name="floor"&扔鸡蛋的高度。&/param&
/// &returns&&/returns&
static bool ThrowEgg(int floor)
return floor &= F;
/// &summary&
/// 第一种方案。
/// &/summary&
/// &param name="a"&大楼。&/param&
/// &returns&&/returns&
static testResult PlanA(int[] a)
int lo = 0;
int hi = 0;
int eggs = 0;
int throwTimes = 0;
testResult result = new testResult();
while (ThrowEgg(hi))
throwTimes++;
hi += (int)Math.Sqrt(a.Length);
if (hi & a.Length - 1)
hi = a.Length - 1;
while (lo &= hi)
if (!ThrowEgg(lo))
throwTimes++;
result.BrokenEggs =
result.F = lo - 1;
result.ThrowTimes = throwT
/// &summary&
/// 第二种方案。
/// &/summary&
/// &param name="a"&大楼。&/param&
/// &returns&&/returns&
static testResult PlanB(int[] a)
int lo = 0;
int hi = 0;
int eggs = 0;
int throwTimes = 0;
testResult result = new testResult();
for (int i = 0; ThrowEgg(hi); ++i)
throwTimes++;
if (hi & a.Length - 1)
hi = a.Length - 1;
while (lo &= hi)
if (!ThrowEgg(lo))
throwTimes++;
result.BrokenEggs =
result.F = lo - 1;
result.ThrowTimes = throwT
}1.4.26题目三点共线。假设有一个算法，接受平面上的 N 个点并能够返回在同一直线上的三个点的组数。证明你能够用这个算法解决 3-sum 问题。解答1.4.27题目两个栈实现的队列。用两个栈实现一个队列，使得每个队列操作所需要的堆栈操作均摊后为一个常数。解答实现比较简单，想象两个栈背靠背接在一起，左侧栈负责出队，右侧栈负责入队。当左侧栈为空时就把右侧栈中的元素倒到左侧栈，这个过程是 O(n) 的。但在这个过程之前必然有 n 个元素入栈，均摊后即为 O(1)。代码namespace _1._4._27
/// &summary&
/// 用两个栈模拟的队列。
/// &/summary&
/// &typeparam name="Item"&队列中的元素。&/typeparam&
class StackQueue&Item&
Stack&Item& H;//用于保存出队元素
Stack&Item& T;//用于保存入队元素
/// &summary&
/// 构造一个队列。
/// &/summary&
public StackQueue()
this.H = new Stack&Item&();
this.T = new Stack&Item&();
/// &summary&
/// 将栈 T 中的元素依次弹出并压入栈 H 中。
/// &/summary&
private void Reverse()
while (!this.T.IsEmpty())
this.H.Push(this.T.Pop());
/// &summary&
/// 将一个元素出队。
/// &/summary&
/// &returns&&/returns&
public Item Dequeue()
//如果没有足够的出队元素，则将 T 中的元素移动过来
if (this.H.IsEmpty())
Reverse();
return this.H.Pop();
/// &summary&
/// 将一个元素入队。
/// &/summary&
/// &param name="item"&要入队的元素。&/param&
public void Enqueue(Item item)
this.T.Push(item);
}1.4.28题目一个队列实现的栈。使用一个队列实现一个栈，使得每个栈操作所需的队列操作数量为线性级别。解答每次入队的时候将队列倒转，这样入队的元素就是第一个了。代码namespace _1._4._28
/// &summary&
/// 用一条队列模拟的栈。
/// &/summary&
/// &typeparam name="Item"&栈中保存的元素。&/typeparam&
class QueueStack&Item&
Queue&Item&
/// &summary&
/// 初始化一个栈。
/// &/summary&
public QueueStack()
this.queue = new Queue&Item&();
/// &summary&
/// 向栈中添加一个元素。
/// &/summary&
/// &param name="item"&&/param&
public void Push(Item item)
this.queue.Enqueue(item);
int size = this.queue.Size();
// 倒转队列
for (int i = 0; i & size - 1; ++i)
this.queue.Enqueue(this.queue.Dequeue());
/// &summary&
/// 从栈中弹出一个元素。
/// &/summary&
/// &returns&&/returns&
public Item Pop()
return this.queue.Dequeue();
/// &summary&
/// 确定栈是否为空。
/// &/summary&
/// &returns&&/returns&
public bool IsEmpty()
return this.queue.IsEmpty();
}1.4.29题目两个栈实现的 steque。用两个栈实现一个 steque（请见练习 1.3.32），使得每个 steque 操作所需的栈操作均摊后为一个常数。解答和用两个栈实现队列的方法类似。push 的时候把右侧栈内容倒到左侧栈，之后再入栈。pop 的时候也做相同操作，右侧栈内容进左侧栈，之后再出栈。enqueue 的时候则将左侧栈内容倒到右侧栈，之后再入队。代码namespace _1._4._29
/// &summary&
/// 用两个栈模拟的 Steque。
/// &/summary&
/// &typeparam name="Item"&Steque 中的元素类型。&/typeparam&
class StackSteque&Item&
Stack&Item& H;
Stack&Item& T;
/// &summary&
/// 初始化一个 Steque
/// &/summary&
public StackSteque()
this.H = new Stack&Item&();
this.T = new Stack&Item&();
/// &summary&
/// 向栈中添加一个元素。
/// &/summary&
/// &param name="item"&&/param&
public void Push(Item item)
ReverseT();
this.H.Push(item);
/// &summary&
/// 将 T 中的元素弹出并压入到 H 中。
/// &/summary&
private void ReverseT()
while (!this.T.IsEmpty())
this.H.Push(this.T.Pop());
/// &summary&
/// 将 H 中的元素弹出并压入到 T 中。
/// &/summary&
private void ReverseH()
while (!this.H.IsEmpty())
this.T.Push(this.H.Pop());
/// &summary&
/// 从 Steque 中弹出一个元素。
/// &/summary&
/// &returns&&/returns&
public Item Pop()
ReverseT();
return this.H.Pop();
/// &summary&
/// 在 Steque 尾部添加一个元素。
/// &/summary&
/// &param name="item"&&/param&
public void Enqueue(Item item)
ReverseH();
this.T.Push(item);
/// &summary&
/// 检查 Steque 是否为空。
/// &/summary&
/// &returns&&/returns&
public bool IsEmpty()
return this.H.IsEmpty() && this.T.IsEmpty();
}1.4.30题目一个栈和一个 steque 实现的双向队列。使用一个栈和一个 steque 实现一个双向队列（请见练习 1.3.32），使得双向队列的每个操作所需的栈和 steque 操作均摊后为一个常数。解答steque 作为队列的头部，stack 作为队列的尾部。pushLeft：直接 push 到 steque 中即可。pushRight：如果 stack 为空，则直接 enqueue 到 steque 中，否则就 push 到 stack 中。popLeft：如果 steque 为空，则将 stack 中的元素倒到 steque 中去（steque.push(stack.pop())），然后再从 steque 中 pop。popRight：如果 stack 为空，则将 steque 中的元素倒到 stack 中去，然后再从 stack 中 pop。代码namespace _1._4._30
/// &summary&
/// 用一个栈和一个 Steque 模拟的双向队列。
/// &/summary&
/// &typeparam name="Item"&双向队列中保存的元素类型。&/typeparam&
class Deque&Item&
Stack&Item&//代表队列尾部
Steque&Item&//代表队列头部
/// &summary&
/// 创建一条空的双向队列。
/// &/summary&
public Deque()
this.stack = new Stack&Item&();
this.steque = new Steque&Item&();
/// &summary&
/// 在左侧插入一个新元素。
/// &/summary&
/// &param name="item"&要插入的元素。&/param&
public void PushLeft(Item item)
this.steque.Push(item);
/// &summary&
/// 将栈中的内容移动到 Steque 中。
/// &/summary&
private void StackToSteque()
while (!this.stack.IsEmpty())
this.steque.Push(this.stack.Pop());
/// &summary&
/// 将 Steque 中的内容移动到栈中。
/// &/summary&
private void StequeToStack()
while (!this.steque.IsEmpty())
this.stack.Push(this.steque.Pop());
/// &summary&
/// 从双向队列左侧弹出一个元素。
/// &/summary&
/// &returns&&/returns&
public Item PopLeft()
if (this.steque.IsEmpty())
StackToSteque();
return this.steque.Pop();
/// &summary&
/// 向双向队列右侧添加一个元素。
/// &/summary&
/// &param name="item"&要插入的元素。&/param&
public void PushRight(Item item)
if (this.stack.IsEmpty())
this.steque.Enqueue(item);
this.stack.Push(item);
/// &summary&
/// 从双向队列右侧弹出一个元素。
/// &/summary&
/// &returns&&/returns&
public Item PopRight()
if (this.stack.IsEmpty())
StequeToStack();
return this.stack.Pop();
/// &summary&
/// 判断队列是否为空。
/// &/summary&
/// &returns&&/returns&
public bool IsEmpty()
return this.stack.IsEmpty() && this.steque.IsEmpty();
/// &summary&
/// 返回队列中元素的数量。
/// &/summary&
/// &returns&&/returns&
public int Size()
return this.stack.Size() + this.steque.Size();
}1.4.31题目三个栈实现的双向队列。使用三个栈实现一个双向队列，使得双向队列的每个操作所需的栈操作均摊之后为一个常数。解答三个栈分别命名为左中右。左侧栈和右侧栈负责模拟队列，和用两个栈模拟队列的方法类似。由于是双向队列，左栈和右栈会频繁的倒来倒去，因此每次都只倒一半的元素可以有效减少开销。有一侧栈为空时，另一侧栈中上半部分先移动到中间栈中，下半部分倒到另一侧栈里，再从中间栈拿回上半部分元素。这样可以确保接下来的 pop 操作一定是常数级别的。代码namespace _1._4._31
/// &summary&
/// 用三个栈模拟的双向队列。
/// &/summary&
/// &typeparam name="Item"&双向队列中的元素。&/typeparam&
class Deque&Item&
Stack&Item&
Stack&Item&
Stack&Item&
/// &summary&
/// 构造一条新的双向队列。
/// &/summary&
public Deque()
this.left = new Stack&Item&();
this.middle = new Stack&Item&();
this.right = new Stack&Item&();
/// &summary&
/// 向双向队列左侧插入一个元素。
/// &/summary&
/// &param name="item"&要插入的元素。&/param&
public void PushLeft(Item item)
this.left.Push(item);
/// &summary&
/// 向双向队列右侧插入一个元素。
/// &/summary&
/// &param name="item"&要插入的元素。&/param&
public void PushRight(Item item)
this.right.Push(item);
/// &summary&
/// 当一侧栈为空时，将另一侧的下半部分元素移动过来。
/// &/summary&
/// &param name="source"&不为空的栈。&/param&
/// &param name="destination"&空栈。&/param&
private void Move(Stack&Item& source, Stack&Item& destination)
int n = source.Size();
// 将上半部分元素移动到临时栈 middle
for (int i = 0; i & n / 2; ++i)
this.middle.Push(source.Pop());
// 将下半部分移动到另一侧栈中
while (!source.IsEmpty())
destination.Push(source.Pop());
// 从 middle 取回上半部分元素
while (!this.middle.IsEmpty())
source.Push(this.middle.Pop());
/// &summary&
/// 检查双端队列是否为空。
/// &/summary&
/// &returns&&/returns&
public bool IsEmpty()
return this.right.IsEmpty() && this.middle.IsEmpty() && this.left.IsEmpty();
/// &summary&
/// 从右侧弹出一个元素。
/// &/summary&
/// &returns&&/returns&
public Item PopRight()
if (this.right.IsEmpty())
Move(this.left, this.right);
return this.right.Pop();
/// &summary&
/// 从左侧弹出一个元素。
/// &/summary&
/// &returns&&/returns&
public Item PopLeft()
if (this.left.IsEmpty())
Move(this.right, this.left);
return this.left.Pop();
/// &summary&
/// 返回双端队列的大小。
/// &/summary&
/// &returns&&/returns&
public int Size()
return this.left.Size() + this.middle.Size() + this.right.Size();
}1.4.32题目均摊分析。请证明，对一个基于大小可变的数组实现的空栈的 M 次操作访问数组的次数和 M 成正比。解答首先，不需要扩容数组的的操作都只需访问数组一次，M 次操作就是 M 次访问。随后我们有性质， M 次栈操作后额外复制访问数组的次数小于 2M。这里简单证明，设 M 次操作之后栈的大小为 n，那么额外访问数组的次数为：S = n/2 + n/4 + n/8 +...+ 2 & n为了能使栈大小达到 n，M 必须大于等于 n/2因此 2M &= n & S，得证。因此我们可以得到 M 次操作后访问数组次数的总和 S' = S + M & 3M1.4.33题目32位计算机中的内存需求。给出 32 位计算机中 Integer、Date、Counter、int[]、double[]、double[][]、String、Node 和 Stack（链表表示）对象所需的内存，设引用需要 4 字节，表示对象的开销为 8 字节，所需内存均会被填充为 4 字节的倍数。解答Integer = 4(int) + 8(对象开销) = 12Date = 3 * 4(int * 3) + 8(对象开销) = 20Counter = 4(String 的引用) + 4(int) + 8(对象开销) = 16int[] = 8(对象开销) + 4(数组长度) + 4N = 12 + 4Ndouble[] = 8(对象开销) + 4(数组长度) + 8N = 12 + 8Ndouble[][] = 8(对象开销) + 4(数组长度) + 4M(引用) + M(12 + 8N)(M 个一维数组) = 12 + 16M + 8MNString = 8(对象开销) + 3*4(int * 3) + 4(字符数组的引用) = 24Node = 8(对象开销) + 4*2(引用*2) = 16Stack = 8(对象开销) + 4(引用) + 4(int) = 161.4.34题目热还是冷。你的目标是猜出 1 到 N 之间的一个秘密的整数。每次猜完一个整数后，你会直到你的猜测距离该秘密整数是否相等（如果是则游戏结束）。如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。解答1. 第一种方案，类似于二分查找，先猜测左边界(lo)，再猜测右边界(hi)，如果边界值猜中的话直接返回，否则：如果右边界比较热，那么左边界向右边界靠，lo=mid；否则，右边界向左边界靠，hi=mid。其中，mid = lo + (hi – lo)/2。每次二分查找都要猜测两次，~2lgN。2. 第二种方案，假设上次猜测值为 lastGuess，本次即将要猜测的值为 nowGuess，通过方程：(lastGuess + nowGuess)/2 = (lo + hi)/2可以求得 nowGuess，具体可以查看示意图：数字是猜测顺序，黑色范围是猜测值的范围（lastGuess 和 nowGuess），绿色的是实际查找的范围（lo 和 hi）。代码首先是 Game 类using S
namespace _1._4._34
/// &summary&
/// 某次猜测的结果。
/// &/summary&
enum GuessResult
// 比上次猜测更接近目标。
Equal = 0,
// 猜中目标。
Cold = -1,
// 比上次猜测更远离目标。
FirstGuess = -2 // 第一次猜测。
/// &summary&
/// 游戏类。
/// &/summary&
class Game
public int N { get; }
// 目标值的最大范围。
public int SecretNumber { get; }
// 目标值。
public int LastGuess { get; private set; }
// 上次猜测的值
/// &summary&
/// 构造函数，新开一局游戏。
/// &/summary&
/// &param name="N"&目标值的最大范围。&/param&
public Game(int N)
Random random = new Random();
this.N = N;
this.SecretNumber = random.Next(N - 1) + 1;
this.LastGuess = -1;
/// &summary&
/// 猜测，根据与上次相比更为接近还是远离目标值返回结果。
/// &/summary&
/// &param name="guess"&本次的猜测值&/param&
/// &returns&接近或不变返回 Hot，远离则返回 Cold，猜中返回 Equal。&/returns&
public GuessResult Guess(int guess)
if (guess == this.SecretNumber)
return GuessResult.E
if (this.LastGuess == -1)
this.LastGuess =
return GuessResult.FirstG
int lastDiff = Math.Abs(this.LastGuess - this.SecretNumber);
this.LastGuess =
int nowDiff = Math.Abs(guess - this.SecretNumber);
if (nowDiff & lastDiff)
return GuessResult.C
return GuessResult.H
/// &summary&
/// 重置游戏，清空上次猜测的记录。目标值和最大值都不变。
/// &/summary&
public void Restart()
this.LastGuess = -1;
}之后是实际测试的方法：using S
namespace _1._4._34
* 热还是冷。
* 你的目标是猜出 1 到 N 之间的一个秘密的整数。
* 每次猜完一个整数后，你会直到你的猜测距离该秘密整数是否相等（如果是则游戏结束）。
* 如果不相等，你会知道你的猜测相比上一次猜测距离秘密整数是比较热（接近），还是比较冷（远离）。
* 设计一个算法在 ~2lgN 之内找到这个秘密整数，然后设计一个算法在 ~1lgN 之内找到这个秘密整数。
class Program
/// &summary&
/// 某种方案的测试结果，包含猜测结果和尝试次数。
/// &/summary&
struct TestResult
public int SecretN// 猜测到的数字。
public int TryT// 尝试次数。
static void Main(string[] args)
Game game = new Game(1000);
TestResult A = PlayGameA(game);
game.Restart();
TestResult B = PlayGameB(game);
Console.WriteLine($"SecretNumber:{game.SecretNumber}");
Console.WriteLine("TestResultA:");
Console.WriteLine($"SecretNumber:{A.SecretNumber}, TryTimes:{A.TryTimes}");
Console.WriteLine();
Console.WriteLine("TestResultB:");
Console.WriteLine($"SecretNumber:{B.SecretNumber}, TryTimes:{B.TryTimes}");
/// &summary&
/// 方案一，用二分查找实现，需要猜测 2lgN 次。
/// &/summary&
/// &param name="game"&用于猜测的游戏对象。&/param&
/// &returns&返回测试结果，包含猜测结果和尝试次数。&/returns&
static TestResult PlayGameA(Game game)
result.TryTimes = 0;
result.SecretNumber = 0;
GuessResult guessR
int hi = game.N;
int lo = 1;
// 利用二分查找猜测，2lgN
while (lo &= hi)
int mid = lo + (hi - lo) / 2;
guessResult = game.Guess(lo);
result.TryTimes++;
if (guessResult == GuessResult.Equal)
result.SecretNumber =
guessResult = game.Guess(hi);
result.TryTimes++;
if (guessResult == GuessResult.Equal)
result.SecretNumber =
else if (guessResult == GuessResult.Hot)
/// &summary&
/// 方案二，根据 (lastGuess + nowGuess)/2 = (lo + hi) / 2 确定每次猜测的值。
/// &/summary&
/// &param name="game"&用于猜测的游戏对象。&/param&
/// &returns&返回测试结果，包含猜测结果和尝试次数。&/returns&
static TestResult PlayGameB(Game game)
result.TryTimes = 0;
result.SecretNumber = 0;
GuessResult guessR
int hi = game.N;
int lo = 1;
bool isRightSide = true;
// 第一次猜测
guessResult = game.Guess(1);
result.TryTimes++;
if (guessResult == GuessResult.Equal)
result.SecretNumber = 1;
while (lo & hi)
int mid = lo + (hi - lo) / 2;
int nowGuess = (lo + hi) - game.LastG
guessResult = game.Guess(nowGuess);
result.TryTimes++;
if (guessResult == GuessResult.Equal)
result.SecretNumber = nowG
else if (guessResult == GuessResult.Hot)
if (isRightSide)
if (isRightSide)
isRightSide = !isRightS
if (hi - lo &= 1)
if (game.Guess(lo) == GuessResult.Equal)
result.TryTimes++;
result.SecretNumber =
else if (game.Guess(hi) == GuessResult.Equal)
result.TryTimes++;
result.SecretNumber =
}1.4.35题目下压栈的时间成本。解释下表中的数据，它显示了各种下压栈的实现的一般时间成本，其中成本模型会同时记录数据引用的数量（指向被压入栈之中的数据的引用，指向的可能是数组，也可能是某个对象的实例变量）和被创建的变量数量。
数据的引用
创建的对象
基于大小可变的数组
基于大小可变的数组
解答1. 一个 Node 对象包含一个 int(泛型 Item) 的引用和下一个 Node 对象的引用。push 操作创建新 Node 对象时会创建一个引用。因此对于第一种情况，压入 n 个 int 类型的元素创建了 N 个 Node 对象，创建了 2N 个引用。2. 比起上一种情况，每个 Node 对象多包含了一个指向 Integer 的引用。因此对于第二中情况，压入 n 个 int 类型的元素创建了 N 个 Node 对象和 N 个 Integer 对象，比起第一种情况多创建了 N 个引用。3. 对于数组来说，创建对象只有扩容时重新创建数组对象一种情况，对于 N 次 push 操作只需要 lgN 次扩容，因此创建的对象为 lgN 个。每次扩容都需要重新创建引用，(4 + 8 +...+ 2N)(扩容) + N(每次 push 操作) = 5N - 4 = ~5N4. 创建引用和上题一样，创建对象则多出了装箱过程，每次 push 都会新建一个 Integer 对象，N + lgN = ~N。1.4.36题目下压栈的空间成本。解释下表中的数据，它显示了各种下压栈实现的一般空间成本，其中链表的结点为一个静态的嵌套类，从而避免非静态嵌套类的开销。
N 个 int 值所需的空间（字节）
基于大小可变的数组
~4N到~16N之间
基于大小可变的数组
~32N到~56N之间
解答1. N 个 Node&int& 对象的空间开销 = N * (16(对象开销) + 4(int) + 8(下一个 Node 的引用) + 4(填充字节)) = 32N2. 比起上一题来说，空间开销变为 = N * (16(Node 对象开销) + 8(Integer 对象引用) + (16(Integer 对象开销) + 4(int) + 4(填充字节)) + 8(下一个对象的引用) = 32N + 24N = 56N。3. 如果不扩容则是 4N，N 个元素最多可以维持 4N 的栈空间（少于四分之一将缩小）。4. 比起上一题，数组元素变成了引用每个占用 8 字节，还要额外加上 Integer 对象的每个 24 字节。= (8 + 24)N ~ (8 * 4 + 24)N1.4.37题目自动装箱的性能代价。通过实验在你的计算机上计算使用自动装箱所付出的性能代价。实现一个 FixedCapacityStackOfInts，并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。解答数据量比较大时才会有比较明显的差距。代码FixedCapacityStackOfInts，根据 FixedCapacityOfString 修改而来：using S
using System.C
using System.Collections.G
namespace _1._4._37
/// &summary&
/// 固定大小的整型数据栈。
/// &/summary&
class FixedCapacityStackOfInts : IEnumerable&int&
private int[]
private int N;
/// &summary&
/// 默认构造函数。
/// &/summary&
/// &param name="capacity"&栈的大小。&/param&
public FixedCapacityStackOfInts(int capacity)
this.a = new int[capacity];
this.N = 0;
/// &summary&
/// 检查栈是否为空。
/// &/summary&
/// &returns&&/returns&
public bool IsEmpty()
return this.N == 0;
/// &summary&
/// 检查栈是否已满。
/// &/summary&
/// &returns&&/returns&
public bool IsFull()
return this.N == this.a.L
/// &summary&
/// 将一个元素压入栈中。
/// &/summary&
/// &param name="item"&要压入栈中的元素。&/param&
public void Push(int item)
this.a[this.N] =
/// &summary&
/// 从栈中弹出一个元素，返回被弹出的元素。
/// &/summary&
/// &returns&&/returns&
public int Pop()
return this.a[this.N];
/// &summary&
/// 返回栈顶元素（但不弹出它）。
/// &/summary&
/// &returns&&/returns&
public int Peek()
return this.a[this.N - 1];
public IEnumerator&int& GetEnumerator()
return new ReverseEnmerator(this.a);
IEnumerator IEnumerable.GetEnumerator()
return GetEnumerator();
private class ReverseEnmerator : IEnumerator&int&
private int
private int[]
public ReverseEnmerator(int[] a)
this.current = a.L
int IEnumerator&int&.Current =& this.a[this.current];
object IEnumerator.Current =& this.a[this.current];
void IDisposable.Dispose()
this.current = -1;
this.a = null;
bool IEnumerator.MoveNext()
if (this.current == 0)
return false;
this.current--;
return true;
void IEnumerator.Reset()
this.current = this.a.L
}FixedCapacityStack&Item&using S
using System.C
using System.Collections.G
namespace _1._4._37
/// &summary&
/// 固定大小的栈。
/// &/summary&
class FixedCapacityStack&Item& : IEnumerable&Item&
private Item[]
private int N;
/// &summary&
/// 默认构造函数。
/// &/summary&
/// &param name="capacity"&栈的大小。&/param&
public FixedCapacityStack(int capacity)
this.a = new Item[capacity];
this.N = 0;
/// &summary&
/// 检查栈是否为空。
/// &/summary&
/// &returns&&/returns&
public bool IsEmpty()
return this.N == 0;
/// &summary&
/// 检查栈是否已满。
/// &/summary&
/// &returns&&/returns&
public bool IsFull()
return this.N == this.a.L
/// &summary&
/// 将一个元素压入栈中。
/// &/summary&
/// &param name="item"&要压入栈中的元素。&/param&
public void Push(Item item)
this.a[this.N] =
/// &summary&
/// 从栈中弹出一个元素，返回被弹出的元素。
/// &/summary&
/// &returns&&/returns&
public Item Pop()
return this.a[this.N];
/// &summary&
/// 返回栈顶元素（但不弹出它）。
/// &/summary&
/// &returns&&/returns&
public Item Peek()
return this.a[this.N - 1];
public IEnumerator&Item& GetEnumerator()
return new ReverseEnmerator(this.a);
IEnumerator IEnumerable.GetEnumerator()
return GetEnumerator();
private class ReverseEnmerator : IEnumerator&Item&
private int
private Item[]
public ReverseEnmerator(Item[] a)
this.current = a.L
Item IEnumerator&Item&.Current =& this.a[this.current];
object IEnumerator.Current =& this.a[this.current];
void IDisposable.Dispose()
this.current = -1;
this.a = null;
bool IEnumerator.MoveNext()
if (this.current == 0)
return false;
this.current--;
return true;
void IEnumerator.Reset()
this.current = this.a.L
}测试函数：using S
namespace _1._4._37
/// &summary&
/// FixedCapacityStackOfInts 测试类。
/// &/summary&
public static class DoubleTest
private static readonly int MAXIMUM_INTEGER = 1000000;
/// &summary&
/// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。
/// &/summary&
/// &param name="n"&随机数组的长度。&/param&
/// &returns&&/returns&
public static double TimeTrial(int n)
int[] a = new int[n];
FixedCapacityStackOfInts stack = new FixedCapacityStackOfInts(n);
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i & ++i)
a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
Stopwatch timer = new Stopwatch();
for (int i = 0; i & ++i)
stack.Push(a[i]);
for (int i = 0; i & ++i)
stack.Pop();
return timer.ElapsedTimeMillionSeconds();
/// &summary&
/// 返回对 n 个随机整数的栈进行 n 次 push 和 n 次 pop 所需的时间。
/// &/summary&
/// &param name="n"&随机数组的长度。&/param&
/// &returns&&/returns&
public static double TimeTrialGeneric(int n)
int[] a = new int[n];
FixedCapacityStack&int& stack = new FixedCapacityStack&int&(n);
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i & ++i)
a[i] = random.Next(-MAXIMUM_INTEGER, MAXIMUM_INTEGER);
Stopwatch timer = new Stopwatch();
for (int i = 0; i & ++i)
stack.Push(a[i]);
for (int i = 0; i & ++i)
stack.Pop();
return timer.ElapsedTimeMillionSeconds();
}主函数：using S
namespace _1._4._37
* 自动装箱的性能代价。
* 通过实验在你的计算机上计算使用自动装箱所付出的性能代价。
* 实现一个 FixedCapacityStackOfInts，
* 并使用类似 DoublingRatio 的用例比较它和泛型 FixedCapacityStack 在进行大量 push() 和 pop() 时的性能。
class Program
static voi