博文
http://acm.pku.edu.cn/course/，关于问题求解的好网址(2006-10-10 10:08:00)
摘要：http://acm.pku.edu.cn/course/......
问题求解 与 程序设计(2006-10-10 10:04:00)
摘要：
·课程概要
开课单位：信息科学技术学院
课程编号：00831630
课程名称：问题求解与程序设计
课程类型：全校通选课
学时学分：学分2.0，总34学时
先修课程：计算概论
授课时间：周二9-10节
授课教室：电教125
主讲教师：李文新
助 教：hawking，赵静
·最新通知
(5.26) 期末考试安排：5月29日上午9:00至11:00，计算中心4号机房
(4.27) 参考书目：《程序设计基础》，吴文虎 著，清华大学出版社，2003
《计算机程序的构造与解释》，裘宗燕 译，机械工业出版社，2004
(4.04) 开始提交出题作业，好的题目将推荐给POJ月赛
(3.10) 一旦被采纳，即可获得奖金！@_@
(3.22) 总完成题数即时排名
(3.10) 上机安排：周日中午12:30至2:30，计算中心4号机房
(3.10) 公用帐号：jtx75-6:jsjtxk@student6
(3.10) 上机内容：网上练习赛
(2.17) 觉得课程太难的同学请看这里
·课程内容
周次
主题
相关材料和链接
作业
第一周(2.10)
引言
题目1：1326 Mileage Bank
题目2：1148 Utopia Divided
1005
1006
第二周(2.17)
对局问题
张一飞解题报告：一类博弈问题的解答过程
1008
1013
第三周(2.24)
称球问题
1008参考程序 1013参考程序
Conqueror's batalion: Task Solution
1016
1048
第四周(3.2)
模拟问题
1016参考程序 1048参考程序
1207
1028
第五周(3.9)
问题抽象
1147 Binary codes
1063
第六周(3.16)
动态规划......
计算机概论讲义(2006-10-10 10:00:00)
摘要：计算概论讲义
第一讲
计算机与人类社会
2004.09.08
下载讲义
第二讲
计算机组成，操作系统
2004.09.15
下载讲义
第三讲
计算机的输入与输出设备
2004.09.22
下载讲义
第四讲
计算机内部的信息表示与处理
2004.09.29
下载讲义
第五讲
计算机存储设备， Excel
2004.10.13
下载讲义
第六讲
操作系统，VC编程环境 VC6下载
2004.10.20
下载讲义
第七讲
计算机网络基础,编程入门
2004.10.27
下载讲义 下载参考资料
第八讲
编程入门续
2004.11.03
下载讲义
第九讲
数组
2004.11.10
下载讲义
第十讲
复杂数据类型与问题求解
2004.11.17
下载讲义
第十一讲
习题课
2004.11.24
下载讲义
第十二讲
指针、动态数组、函数
2004.12.01
下载讲义
第十三讲
习题课一
2004.12.08
下载讲义
第十四讲
习题课二
2004.12.15
下载讲义
第十五讲
习题课三
2004.12.22
下载讲义
第十六讲
复习与答疑问......
多媒体技术课程学习(2006-10-07 19:24:00)
摘要：第一章 引言
第二章 音频
第三章 图形图象
第四章 视频
第五章 多媒体压缩编码
第六章 多媒体计算机系统组成
第七章 系统开发与应用
第八章 超文本与WEB系统
第九章 多媒体通信
第十章 多媒体数据库系统......
NOIP初赛练习题(2006-08-15 22:40:00)
摘要： NOIP初赛练习题
下列设备哪一项不是计算机输入设备( )
A)鼠标 B)扫描仪 C)数字化仪 D)绘图仪
答案：C
在外部设备中，绘图仪属于（ ）．
A．输入设备 B．输出设备 C．辅（外）存储器 D．主（内）存储器
答案：A
(0.5)10=( )16.
A) 0.1 B) 0.75 C) 0.8 D) 0.25
答案：C
设有一个含有13个元素的Hash表(O~12),Hash函数是:H(key)=key % 13,其中%是求余数运算。用线性探查法解决冲突,则对于序列(2、8、31、20、19、18、53、27),18应放在第几号格中( ) 。
A) 5 B) 9 C) 4 D) 0
答案：B
要使1…8号格子的访问顺序为:8、2、6、3、7、3、1、4,则下图中的空格中应填入( ) 。
1 2 3 4 5 6 7 8
4 6 1 -1 7 3 2
A) 6 B) O C) 5 D) 3
答案：C
将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下6种排法:
红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红
问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)
答案：35
在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为( )
A)2 B)3 C)4 D)5
答案：C
与二进制数101.01011等值的十六进制数为( )
A)A.B B)5.51 C)A.51 D)5.58
答案：D
在计算机硬件系统中，cache是( )存储器
A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓冲
答案：D
平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？
答案：751
设循环队列中数组的下标范围是1–......
阳光奥赛（www.noi3000.com），好网站(2006-08-15 21:47:00)
摘要：阳光奥赛（www.noi3000.com）
---------算法部分--------转自：http://www.noi3000.com/ShowClass2.asp?ClassID=4---------
[图文]图论的意义 (noi3000，2006年4月27日，192)
程序设计中几何算法二 (noi3000，2006年4月17日，108)
程序设计中几何算法一 (noi3000，2006年4月17日，129)
汉诺塔问题 (noi3000，2006年3月13日，478)
八皇后问题 (noi3000，2006年3月13日，298)
算法设计(动态规划法) (noi3000，2006年3月13日，142)
算法设计(分治法) (noi3000，2006年3月13日，198)
算法设计(贪婪法) (noi3000，2006年3月13日，149)
算法设计(回溯法2) (noi3000，2006年3月13日，140)
算法设计(回溯法1) (noi3000，2006年3月13日，200)
算法设计(递归法) (noi3000，2006年3月12日，154)
算法设计(递推法) (noi3000，2006年3月12日，53)
算法设计(穷举搜索法) (noi3000，2006年3月12日，63)
算法设计(迭代法) (noi3000，2006年3月12日，69)
基本算法讲座之数学篇 (noi3000，2006年3月5日，76)
排序算法简要说明 (佚名，2005年11月7日，88)
什么是算法 (cz1800，2005年11月7日，108)
----------------------------------------------------------------------......
二分法查找（转）(2006-08-15 21:34:00)
摘要：作者tag:c/c++ CSDN 推荐tag:web
function StorePage(){d=document;t=d.selection?(d.selection.type!='None'?d.selection.createRange().text:''):(d.getSelection?d.getSelection():'');void(keyit=window.open('http://www.365key.com/storeit.aspx?t='+escape(d.title)+'&u='+escape(d.location.href)+'&c='+escape(t),'keyit','scrollbars=no,width=475,height=575,left=75,top=20,status=no,resizable=yes'));keyit.focus();}
二分法——查找、排序以及库函数bsearch的用法
http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.2.2.1.htm
二分法查找
1、二分查找(Binary Search)
二分查找又称折半查找，它是一种效率较高的查找方法。
二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
2、二分查找的基本思想
二分查找的基本思想是：（设R[low..high]是当前的查找区间）
（1）首先确定该区间的中点位置：
（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：
①若R[mid].key>......
05_更多数据结构的课程请用以下网址登录(2006-08-15 21:14:00)
摘要：http://www.cstudyhome.com/datastruct1/index.htm
数据结构......
04_算法效率与存储空间需求(2006-08-15 21:11:00)
摘要：第四课
本课主题： 算法效率的度量和存储空间需求
教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用
教学重点： 渐近时间复杂度的意义与作用及计算方法
教学难点： 渐近时间复杂度的意义
授课内容：
一、算法效率的度量
算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：
1、事后统计的方法。
缺点：不利于较大范围内的算法比较。（异地，异时，异境）
2、事前分析估算的方法。
程序在计算机上运行所需时间的影响因素
算法本身选用的策略
问题的规模
规模越大，消耗时间越多
书写程序的语言
语言越高级，消耗时间越多
编译产生的机器代码质量
机器执行指令的速度
综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。
从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。 （原操作在所有该问题的算法中都相同）
T(n)=O(f(n))
上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。
求4*4矩阵元素和，T(4)=O(f(4))
f=n*n;
sum(int num[4][4])
{ int i,j,r=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
r+=num[i][j]; /*原操作*/
return r;
}
最好情况：
T（4）=O（0）
最坏情况：
T（4）=O（n*n）
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)
return 0;
return 1;
}
原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次......
03_算法(2006-08-15 21:09:00)
摘要：转自（http://www.cstudyhome.com/datastruct1/class03/class03.htm）
第三课
本课主题： 算法及算法设计要求
教学目的： 掌握算法的定义及特性，算法设计的要求
教学重点： 算法的特性，算法设计要求
教学难点： 算法设计的要求
授课内容：
一、算法的定义及特性
1、定义：
ispass(int num[4][4])
{ int i,j;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if(num[i][j]!=i*4+j+1)/*一条指令，多个操作*/
return 0;
return 1;
}/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性：
2、算法的五个特性：
有穷性
一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；
确定性
算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
可行性
一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入
一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
输出
一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。
例：
有穷性
haha()
{/*only a joke,do nothing.*/
}
main()
{printf("请稍等...您将知道世界的未日...");
while(1)
haha();
}
确定性
float average(int *a,int num)
{int i;long sum=0;
for(i=0;i<num;i++)
sum+=*(a++);
return sum/num;
}
main(......