School of EECS, Peking University Wrap Up (2) http://net.pku.edu.cn/~course/cs101/2008 Hongfei Yan School of EECS, Peking University 12/26/2008

http://en. wikipedia. org/wiki/Alfred_Nobel http://en. wikipedia http://en.wikipedia.org/wiki/Alfred_Nobel http://en.wikipedia.org/wiki/Nobel_Prize http://baike.baidu.com/view/4024.htm 物理学最具天才的科学家合影 全球1/3的智慧 http://bbs.tiexue.net/post_3025568_1.html 史上最强合影 http://en.wikipedia.org/wiki/Solvay_Conference http://www.dkj1997.com/bbs/archiver/?tid-143.html 几乎可以肯定，世界上没有第二张照片，能像这张一样，在一幅画面内集中了如此之多的、水平如此之高的人类精英。   　这张照片是1927年第五届索尔维会议参加者的合影。索尔维是一个很像诺贝尔的人，本身既是科学家又是家底雄厚的实业家，万贯家财都捐给科学事业。诺 贝尔是设立了以自己名字命名的科学奖金，索尔维则是提供了召开世界最高水平学术会议的经费。这就是索尔维会议的来历。       照片的前排，坐着的都是当时老一辈的科学巨匠，中间那位当然谁都认识，那就是爱因斯坦，他其实应该算一个"跨辈份"的人物。左起第三位那个白头发老太太 就是居里夫人，她是这张照片里唯一的女性。在爱因斯坦和居里夫人当中那位老者是真正的元老级人物洛伦兹，电动力学里的洛伦兹力公式，是与麦克斯韦方程组同 等重要的基本原理，爱因斯坦狭义[wiki]相对论[/wiki]里的"洛伦兹变换"也是他最先提出的。       左起第二位则是量子论的奠基者普朗克，他在解释黑体辐射问题时第一次提出了"量子"的概念。这一排里还有提出原子结合能理论的郎之万、发明云雾室的威尔 逊等，个个堪称德高望重  第二排右起第一人是与爱因斯坦齐名的"哥本哈根学派"领袖尼尔斯·玻尔，玻尔第一个提出量子化的氢原子模型，后来又提出过互补 原理和哲学上的对应原理，他与爱因斯坦的世纪大辩论更是为人们津津乐道。玻尔旁边是德国大物理学家玻恩，他提出了量子力学的概率解释。       再往左，是法国"革命王子"德布罗意，他提出了物质法的概念，确立了物质的[wiki]波粒二象性[/wiki]，为量子力学的建立扫清了道路。德布罗意左边，是因发现了原子的康普顿效应而著称的美国物理学家康普顿。       再左边，则是英国杰出的理论物理学家狄拉克，他提出了量子力学的一般形式以及表象理论，率先预言了反物质的存在，创立了量子电动力学。这一排里，还有发明粒子回旋加速器的布拉格等.   　 第三排右起第三人，就是量子力学的矩阵形式的创立者海森堡，测不准原理也是他提出来的。他的左边，是他的大学同学兼挚友泡利，泡利是"泡利不相容原理"和 微观粒子自旋理论泡利矩阵的始作俑者。两人同在索末菲门下学习时，经常不按老师的要求循序渐进，而是自搞一套，老师竟也完全同意并鼓励他们这样做。       右起第六人，就是量子力学的波动形式的创立者薛定谔，量子力学里薛定谔方程，就像经典力学里的牛顿运动方程一样重要。薛定谔还是最早提出生物遗传密码的人 ;       以上这些人物，是二十世纪物理科学的最杰出代表，他们在量子论和相对论两个方向上所做的贡献，不仅彻底改变了人们的物质生活，而且改变了人类的思维方式和时空观念。在知识界可以这样说，不懂得这些思想的人，基本上可以视为落后于这个时代 　　他们都先后获得过诺贝尔物理奖。诺贝尔奖金之所以被公认为科学界的最高荣誉，实际上正是因为在二十世纪前期，年年都授予这些人，从而确立了这项奖金的威信  ;       彼得．德拜  ;美国物理化学家。1884年出生于荷兰。1901年进入德国亚琛工业大学学习电气工程，1905年获电子工程师学位，因他通过偶极矩研究及x射线衍射研究对分子结构学科所作贡献而于1936年获诺贝尔化学奖金。1966年逝世  ;       威廉．亨利．布拉格（Bragg，1862－1942）;现代固体物理学的奠基人之一，他早年在剑桥三一学院学习数学，曾任利兹大学、伦敦大学教 授，1940年出任皇家学会会长。由于在使用x射线衍射研究晶体原子和分子结构方面所做出的开创性贡献，他与儿子布喇格分享了1915年诺贝尔物理学奖。 父子两代同获一个诺贝尔奖，这在历史上恐怕是绝无仅有的。同时，他还作为一名杰出的社会活动家，在二三十年代是英国公共事务中的风云人物  ;       爱因斯坦  20世纪最伟大的科学家，被公认为人类历史上最具有创造性才智的人物之一。他的名字与相对论密不可分，其实，相对论包括两种理论：其一是他1905年提出声狭义相对论；其二是他1915年提出的广义相对论。后者，我们最好称之为爱因斯坦引力论 ;       埃伦费斯特 1880－1933 ;荷兰物理学家;保罗．狄拉克（Adrian Maurice Dirac，1902～1984）;英国物理学家。1930年，用数学方法描述电子运动规律时，发现电子的电荷可以是负电荷、也可以是正电荷的。狄拉克猜 想，在自然界中可能存在一种"反常的"带正电荷的电子。;薛定谔（schrodinger，1887&1961）奥地利理论物理学家，与爱因斯 坦、玻尔、玻恩、海森堡等一起于20世纪20年代后期，发展了量子力学。因建立描述电子和其他亚原子粒子的运动的波动方程，获得1933年诺贝尔物理奖。       康普敦（compton l892—1962）1922—1923年间，研究了x射线经金属或石墨等物质散射后的光谱。;德布罗意Louis　Victorde　 Broglie,1892～1989 ;法国物理学家 ;沃尔夫冈．泡利（WolfgangPauli，1900～1958）;美籍奥地利科学家，是迎着20世纪一同来到世界的，父亲是维也纳大学的物理化学教 授，教父是奥地利的物理学家兼哲学家;海森堡（Werner&Karl;Heidelberg;1907～1976）;德国理论物理学家，量子力 学第一种有效形式（矩阵力学）的创建者。 　　玻恩， 1882～1970;德国理论物理学家，量子力学的奠基人之一 尼尔斯．玻尔 1885年10月7日生于丹麦首都哥本哈根，父亲是哥本哈根大学的生理学教授．从小受到良好的家庭教育．1903年进入哥本哈根大学学习物理，1909年 获科学硕士学位，1911年获博士学位．大学二年级时研究水的表面张力问题，自制实验器材，通过实验取得了精确的数据，并在理论方面改进了物理学家瑞利的 理论，研究论文获得丹麦科学院的金奖章;普朗克，（1858～1947）;近代伟大的德国物理学家，量子论的奠基人;居里夫人（1867－1934）最著 名的女物理学家。她曾两次获诺贝尔奖，1903年的物理奖，1911年的化学奖。她受教育较晚，于1893年获物理学位，1894年获数学学位，1903 年获博士学位。居里夫人以放射性作为论文题目，她研究了很多物质，发现钍及其化合物的特性与铀相同。研究沥青铀矿时，她发现了镭和钋。1910年她成功的 分离了纯镭。居里夫人对巴黎的局里实验室的建立作出很大贡献  洛仑兹（Lorentz　1853～1928）与塞曼（1865～1943 ;因研究磁场对辐射现象的影响、发现塞曼效应，分享了1902年度诺贝尔物理学奖  朗之万 1872年1月23日生于巴黎，法国著名的物理学家;

http://bbs.tiexue.net/post_3025568_1.html 1.彼得．德拜　美国物理化学家。1884年出生于荷兰。1901年进入德国亚琛工业大学学习电气工程， 1905年获电子工程师学位，因他通过偶极矩研究及x射线衍射研究对分子结构学科所作贡献而于1936年获诺贝尔化学奖金。1966年逝世。 [ 转自铁血社区 http://bbs.tiexue.net/ ] 2.威廉．亨利．布喇格（w.h.bragg，1862－1942）是现代固体物理学的奠基人之一，他 早年在剑桥三一学院学习数学，曾任利兹大学、伦敦大学教授，1940年出任皇家学会会长。由于在使用x射线衍射研究晶体原子和分子结构方面所作出的开创性 贡献，他与儿子w.l.布喇格分享了1915年诺贝尔物理学奖。父子两代同获一个诺贝尔奖，这在历史上恐怕是绝无人物。 3. 爱因斯坦是20世纪最伟大的科学家，被公认为人类历史上最具有创造性才智的人物之一。他的名字与相对论密不可分，其实，相对论包括两种理论：其一是他1905年提出声狭义相对论；其二是他1915年提出的广义相对论。后者，我们最好称之为爱因斯坦引力论。 4.埃伦费斯特 ( p. ehrenfest, 1880－1933) ——荷兰物理学家 5.1930年，英国物理学家保罗．狄拉克（paul adrien maurice dirac，1902～1984）用数学方法描述电子运动规律时，发现电子的电荷可以是负电荷、也可以是正电荷的。狄拉克猜想，在自然界中可能存在一种“反常的”带正电荷的电子 6.薛定谔（erwin schrodinger，1887-1961）奥地利理论物理学家，与爱因斯坦、玻尔、玻恩、海森伯等一起于20世纪20年代后期，发展了量子力学。因建立描述电子和其他亚原子粒子的运动的波动方程，获得1933年诺贝尔物理奖。 7.1922—1923年间，康普敦（a.h.compton l892—1962）研究了x射线经金属或石墨等物质散射后的光谱。 8.美籍奥地利科学家沃尔夫冈．泡利（wolfgang e.pauli，1900～1958），是迎着20世纪一同来到世界的，父亲是维也纳大学的物理化学教授，教父是奥地利的物理学家兼哲学家 9.海森伯，w.k.（werner karl heisenberg 1907～1976）德国理论物理学家，量子力学第一种有效形式（矩阵力学）的创建者 10.玻恩，m.(max born 1882～1970)德国理论物理学家，量子力学的奠基人之一。 11.尼尔斯．玻尔(bohr,niels)1885年10月7日生于丹麦首都哥本哈根，父亲是哥本哈根大学的 生理学教授．从小受到良好的家庭教育．1903年进入哥本哈根大学学习物理，1909年获科学硕士学位，1911年获博士学位．大学二年级时研究水的表面 张力问题，自制实验器材，通过实验取得了精确的数据，并在理论方面改进了物理学家瑞利的理论，研究论文获得丹麦科学院的金奖章 12.普朗克，m.（max planck 1858～1947）近代伟大的德国物理学家，量子论的奠基人。 13.居里夫人（1867－1934〕是最著名的女物理学家。她曾两次获诺贝尔奖，1903年的物理 奖，1911年的化学奖。她受教育较晚，于1893年获物理学位，1894年获数学学位，1903年获博士学位。局里夫人以放射性作为论文题目，她研究了 很多物质，发现钍及其化合物的特性与铀相同。研究沥青铀矿时，她发现了镭和仆。1910年她成功的分离了纯镭。居里夫人对巴黎的局里实验室的建立作出很大 贡献。 14.洛仑兹（hendrik antoon lorentz　1853～1928）与塞曼（pietr zeeman 1865～1943）因研究磁场对辐射现象的影响、发现塞曼效应，分享了1902年度诺贝尔物理学奖。 15.朗之万:1872年1月23日生于巴黎，法国著名的物理学家。

00827008 李学钊 00827009 王战 00827010 李玉水 00827011 朱晓彤 00827012 宋立娜 00827013 吴桐 00827014 金赤 00827015 梁嘉良 00827016 李悦 00827017 姜含宇 00827018 裘东盈 00827019 朱元晴 00827020 张松南 00827021 戴兆毅 00827022 罗超文 00827023 陈颖 00827024 刘一洲 00827025 马涵宇 00827026 孙浩然 00827027 李芸邑 00827601 游云深 00827602 陈德愉 00827603 金达叶 00846054 陈恩石 00846075 盛昊骐 00846109 俞涛 00846161 伍银多 00846208 柏鹤 00846215 梁曦 student ID Name 00610065 程晓亮 00610091 高亮 00710105 凌云 00810002 杨奕 00810006 郑志桐 00810009 徐天扬 00810016 李潇瀚 00810020 王普舟 00810023 徐晋 00810027 曹怀卿 00810029 王凌宇 00810035 赵伯譞 00810037 张涛 00810040 姜延龙 00810044 许文馨 00810051 孙宇婷 00810055 李铮 00810060 姜军略 00810065 陈晨 00810068 邢佳伟 00810069 蔡恺珉 00810070 郑晟 00810073 郑雨晴 00810079 殷雨丹 00810082 沈琛骐 00810084 曹自强 00810088 张一丁 00810095 周昂 00810096 张潇洒 00810097 傅永平 00810098 李天阳 00810100 罗征 00810101 朱晗宇 00810106 彭霄 00810109 隋春宁 00810110 李若铭 00810113 张航 00810116 林雨晨 00810118 翟赞圣 00810119 吴曈勃 00810122 蒋骏骢 00810124 赵湉 00810129 官亚夫 00810130 文豪 00810136 陈苏悦 00810141 黄礼君 00810142 杨硕 00810146 宋环君 00810149 邱然 00810151 李晨 00810153 马润哲 00810154 王天民 00810156 常凤霞 00810159 张骏 00810162 程璐瑶 00827001 吴彤 00827002 李梦莹 00827003 金玉婷 00827004 李晓琼 00827005 王梦楚 00827006 胡帅 http://net.pku.edu.cn/~course/cs101/2008/2008_student_list.htm

Alan Turing Alan Turing, founder of computer science, artificial intelligence, and mathematical biology.

How to go over? 掌握课程讲义 掌握作业、模拟考试中涉及到的题目 期末考试题目还没有出，应该比模拟难 想挂这科很困难 课程网站上提供所有用到的slides. 掌握作业、模拟考试中涉及到的题目 主要是POJ题目，答案都公布在课程网站上 期末考试题目还没有出，应该比模拟难 模拟的题型较单一 想挂这科很困难 2008年策略： 期末题目做出一个，期末成绩就60分以上

Topics Overview, Computer, Tour of Computer Systems Programming Languages and Development Environment C++ Basics Array and Structure Data Representation POJ Problems: FAQ -> Input The C++ Standard Library -> Standard Template Library Tips: C string -> Newline -> Bitwise operator -> Recursion examples Function -> Recursion Pointer and Reference -> Variables: A Deeper Look Design of Algorithms -> Program Design

课程网站 & 论坛 课程网站 论坛主页 论坛邮件组 http://net.pku.edu.cn/~course/cs101/2008/ http://groups.google.com/group/cs101pku 论坛邮件组 cs101pku AT googlegroups.com Overview

Remind: 答疑 有关程序问题网上答疑 助教答疑 请注明题号 请说明问题所在，你的解题思路（算法） 请提交到讨论组 陆腾飞，东门外方正大厦三层，计算机科学技术研究所信息安全工程研究中心 单栋栋，理科1号楼1220房间 毛先领，理科1号楼1220房间

考核方式 Assignments: 30% Midterm exam: 20% Final exam: 50% http://poj.grids.cn/ (程序在线评测系统PKU Online Judge ) 注册账号,id格式为cs10108_XXXXXXXX, 08代表2008秋季学期, 后面是八位学号

Remind: 上机座位安排 http://net.pku.edu.cn/~course/cs101/2008/2008_student_list.htm …

理科学生对计算概论中各个知识点重要性的认识 not very correct ! [1] 张铭，谢柏青，“北京大学计算机基础课程教学体系调查”。《计算机教育》，2005年8月。PP18-21 闫宏飞： 1) 这个图我感觉有矛盾的地方，要I，需要B、G、和C的支持，所以B应该相应高些。 E、F的可以相对降低，尤其是F可以通过留作业、上机等环节自然掌握。 A只要简单讲一节课，剩余的由学生通过自己使用电脑体会。 2) 说明学生理解有误，需要教师引导。

Turing model: Programmable data processors A program is a set instructions that tell the computer what to do with the data. In the Turing model, the output data depends on the combination of two factors: the input data and the program. The idea of a universal computational device was first described by Alan Turing in 1937. He proposed that all computation could be performed by a special kind of a machine, now called a Turing machine. Although Turing presented a mathematical description of such a machine, he was more interested in the philosophical definition of computation than in building the actual machine. He based the model on the actions that people perform when involved in computation. He abstracted these actions into a model for a computational machine that has really changed the world. Computer

von Neumann model \ \

What happens and why, when you run hello on your system ? 1 # include <stdio.h> 2 int main() 3 { 4 printf(“hello, world\n”); 5 } 编译之前，它还只是个普通的文本文件，每个字符都用一串二进制0、1表示。为简短起见，这里写为十进制数字。也就是说它们被存为： In their classic text on the C programming language [40], Kernighan and Ritchie introduce readers to C using the hello program shown in Figure 1.1. Although hello is a very simple program, every major part of the system must work in concert in order for it to run to completion. In a sense, the goal of this book is to help you understand what happens and why, when you run hello on your system. We begin our study of systems by tracing the lifetime of the hello program, from the time it is created by a programmer, until it runs on a system, prints its simple message, and terminates. As we follow the lifetime of the program, we will briefly introduce the key concepts, terminology, and components that come into play. Later chapters will expand on these ideas. Tour of Computer Systems

一个典型的硬件系统 PC ALU 系统总线 存储器总线 IO桥 主存储器 总线接口 扩展槽，留待网络适配器等设备使用 USB控制器 CPU 寄存器组 PC ALU 系统总线 存储器总线 IO桥 主存储器 总线接口 IO总线 扩展槽，留待网络适配器等设备使用 USB控制器 图形适配器 磁盘控制器 通讯关系 存储在磁盘上的hello可执行程序文件 鼠标 键盘 显示器 磁盘

从键盘读取hello命令 PC ALU 系统总线 存储器总线 IO桥 主存储器 总线接口 USB控制器 图形适配器 磁盘控制器 鼠标 键盘 CPU 寄存器组 PC ALU 系统总线 存储器总线 “hello” IO桥 主存储器 总线接口 IO总线 USB控制器 图形适配器 磁盘控制器 当在键盘输入hello时，操作系统将一个个字符传入寄存器，再把它们放入主存。 鼠标 键盘 显示器 磁盘 存储在磁盘上的hello可执行文件 用户输入hello 触发程序的执行

从磁盘加载可执行文件到主存 PC ALU hello代码 系统总线 存储器总线 IO桥 主存储器 总线接口 USB控制器 图形适配器 CPU 寄存器组 PC ALU hello代码 “hello,world\n” 系统总线 存储器总线 IO桥 主存储器 总线接口 IO总线 USB控制器 图形适配器 磁盘控制器 当在键盘敲回车时，操作系统执行一系列命令将代码和数据从磁盘调入主存。 鼠标 键盘 显示器 磁盘 存储在磁盘上的hello可执行文件

从存储器写输出串到显示器 PC ALU hello代码 系统总线 存储器总线 IO桥 主存储器 总线接口 USB控制器 图形适配器 CPU 寄存器组 PC ALU hello代码 “hello,world\n” 系统总线 存储器总线 IO桥 主存储器 总线接口 IO总线 USB控制器 图形适配器 磁盘控制器 一旦hello代码和数据存入主存，CPU就开始执行hello程序中的指令并依照这些指令将“hello\n”中的字节从存储器中拷贝到寄存器组再从寄存器中输送到显示终端。 鼠标 键盘 显示器 磁盘 存储在磁盘上的hello可执行文件 显示”hello, world\n” 完成程序执行

操作系统提供的抽象表示 进程是操作系统对运行程序的一种抽象 虚拟存储器为每个进程提供一个假象，好像每个进程都在度占地使用主存。 每个进程看到的存储器都是一致的，成为虚拟存储器。 文件是字节序列

Programming Languages and Development Environment C++ Basics Fundamental types Arithmetic operator Control structures Array and Structure & POJ Problem I

ASCII reserves the first 32 codes (numbers 0–31 decimal) for control characters: codes originally intended not to carry printable information, but rather to control devices (such as printers) that make use of ASCII. For example, character 10 represents the "line feed" function (which causes a printer to advance its paper), and character 27 represents the "escape" key often found in the top left corner of common keyboards. Code 127 (all seven bits on), another special character, equates to "delete" or "rubout". Though its function re ... Data Representation

二进制示例

无符号整数 计算机会用固定的位数N保存无符号整数 范围为 0 ~ (2^N -1) 表示法 N = 8, 0 ~ 255 首先将整数转换为二进制数 如果二进制数不足 N 位, 则二进制左边补 0, 使总位数为 N位 若数的二进制位超过N, 则溢出(overflow)

read until EOF from cin in C++ Ctrl-D is EOF on Unix On DOS/Windows, Ctrl-Z is EOF POJ 3248 求最大公约数 int x,y; while (cin>>x>>y) { …. } POJ Problem II

C++ standard library C library IOStream library. String library. The popular C library, is also part of the of C++ language library. IOStream library. The standard C++ library for Input/Output operations. String library. Library defining the string class. STL: Standard Template Library. Templates defining containers, algorithms... C++标准库很大,在现在的情况下,C++标准库确实越来越好,因为大的库会包含大量的功能.标准库中的功能越多,开发自己的应用程序时能借助的功能就越多,C++库并非提供一切(很明显的是没有提供开发和图形用户接口的支持),但确实提供了很多.标准C++库中主要有以下主要组件:

Recursion #include <iostream> using namespace std; long long factorial (long long a) { if (a > 1) return (a * factorial (a-1)); else return (1); } int main () long long number; //cout << sizeof(long long) << endl; cout << "Please type a number: "; cin >> number; cout << number << "! = " << factorial (number); Recursion is the property that functions have to be called by themselves. It is useful for many tasks, like sorting or calculate the factorial of numbers. Function

Newline is a special character or sequence of characters signifying the end of a line of text. represent a newline with one or two control characters: use either LF (Line feed, 0x0A) or CR (Carriage Return, 0x0D) individually, or CR followed by LF (CR+LF, 0x0D 0x0A) LF:    Unix and Unix-like systems (GNU/Linux, AIX, Mac OS X, FreeBSD, etc.), and others CR+LF: most other early non-Unix, DOS, Microsoft Windows CR:    Commodore machines, Apple II family, Mac OS up to version 9 and OS-9 http://en.wikipedia.org/wiki/Newline Tip II

POJ 2689 大小写字母互换 #include <iostream> using namespace std; int main () { char a[81]={'\0'}; cin.getline(a, 81); for (unsigned i=0; i<strlen(a); i++) { if ( 'A'<=a[i] && a[i]<='Z') { a[i] |= 0x20; //the difference between 'A' and 'a' is 0x20 continue; } if ( 'a'<=a[i] && a[i]<='z') a[i] &= 0xDF; cout << a << endl;; Tip III

Recursive algorithm for Towers of Hanoi Moving n disks can be viewed in terms of moving only n-1 disks, as follows: Move n-1 disks from peg 1 to peg 2, using peg 3 as a temporary holding area. Move the last disk from peg 1 to peg 3. Move the n-1 disks from peg 2 to peg 3, using peg 1 as a temporary holding area. http://net.pku.edu.cn/~course/cs101/resource/CppHowToProgram/5e/html/ch06le v1sec28.html Let us assume that the priests are attempting to move the disks from peg 1 to peg 3. We wish to develop an algorithm that prints the precise sequence of peg- to-peg disk transfers. If we were to approach this problem with conventional methods, we would rapidly find ourselves hopelessly knotted up in managing the disks. Instead, attacking this problem with recursion in mind allows the steps to be simple. Tip IV

What are pointers? Pointers are basically the same as any other variable. However, what is different about them is that instead of containing actual data, they contain a reference to the memory location where information can be found. This is a very important concept. Many programs and ideas rely on pointers as the basis of their design, linked lists for example. Pointer and Reference

Process virtual address space Kernel virtual memory Memory mapped region for shared libraries Run-time heap (created at runtime by dynamic allocation)‏ User stack (created at runtime)‏ Unused Memory invisible to user code 0xc0000000 0x08048000 0x40000000 Read/write data Read-only code and data Loaded from the hello executable file printf() function 0xffffffff new used in C++ The virtual address space seen by each process consists of a number of well-defined areas, each with a specific purpose. You will learn more about these areas later in the book, but it will be helpful to look briefly at each, starting with the lowest addresses and working our way up: Program code and data. Code begins at the same fixed address, followed by data locations that correspond to global C variables. The code and data areas are initialized directly from the contents of an executable object file, in our case the hello executable. You will learn more about this part of the address space when we study linking and loading in Chapter 7. Heap. The code and data areas are followed immediately by the run-time heap. Unlike the code and data areas, which are fixed in size once the process begins running, the heap expands and contracts dynamically at run time as a result of calls to C standard library routines such as malloc and free. We will study heaps in detail when we learn about managing virtual memory in Chapter 10. Shared libraries. Near the middle of the address space is an area that holds the code and data for shared libraries such as the C standard library and the math library. The notion of a shared library is a powerful, but somewhat difficult concept. You will learn how they work when we study dynamic linking in Chapter 7. Stack. At the top of the user’s virtual address space is the user stack that the compiler uses to implement function calls. Like the heap, the user stack expands and contracts dynamically during the execution of the program. In particular, each time we call a function, the stack grows. Each time we return from a function, it contracts. You will learn how the compiler uses the stack in Chapter 3. Kernel virtual memory. The kernel is the part of the operating system that is always resident in memory. The top 1/4 of the address space is reserved for the kernel. Application programs are not allowed to read or write the contents of this area or to directly call functions defined in the kernel code. A Tour of Computer Systems, at page 15 http://net.pku.edu.cn/~course/cs101/2008/resource/ch1-preview.pdf

Virtual memory The program thinks it has a large range of contiguous addresses; but in reality the parts it is currently using are scattered around RAM, and the inactive parts are saved in a disk file. http://en.wikipedia.org/wiki/Virtual_memory Variables: A Deeper Look

Storage duration @ running view is the property of an object that defines the minimum potential lifetime of the storage containing the object. There are three storage durations: static, automatic, and dynamic. automatic storage is also called stack memory. heap memory is for dynamic storage. The storage duration that a variable has depends on how you create the variable. [ISO/IEC 14882-2003] Section 3.7, 3.8, "Object Lifetime" describes a number of situations in which trying to access an object outside of its lifetime leads to undefined behavior. https://www.securecoding.cert.org/confluence/display/cplusplus/DCL30- CPP.+Declare+objects+with+appropriate+storage+durations http://www.devarticles.com/c/a/Cplusplus/More-on-Handling-Basic-Data-Types/10/ http://drdobbsonline.net/cpp/184403437 http://www-ee.eng.hawaii.edu/~tep/EE160/Book/chap14/chap14.html http://en.allexperts.com/q/C-1040/2008/8/Memory-management-C.htm 38 38

The following statements have different meanings const char *p = "asdfasdf"; char p2[] = "asdfasdf"; char *p3 = (char[]){"asdfasdf"}; const char *p4 = (const char[]){"asdfasdf"}; *(p+1) = `a`; *(p2+1) = `a`; *(p3+1) = `a`; *(p4+1) = `a`; 一.  http://bbs.chinaunix.net/viewthread.php?tid=934969 1. in C++, a string literal has type "const char[]" with static storage duration 但是 const char str[] = "asdfasdf"; const char *p = str; 2. in C, a string literal has type " char[]" with static storage duration 那么 { char *p = "asdfasdf"; char p2[] = "asdfasdf"; char *p3 = (char[]){"asdfasdf"}; } 都不同。第一个在栈上有一个指针，指向某个只读串（通常在只读页里的）。 第二个在栈上有个字符串，第三个在栈上有个指针指向栈上的一个字符串（无名的，可修改）。 那么对于后两种情形，是否一定有个static storage duration的只读串用于初始化栈呢？ 要的，理由很简单，这个串的地址在栈中，要到运行时才知道地址，知道要放哪，也就是当前栈上。这需要一个显示的copy动作。 3. char p[] = "abcd"; char *p1 = (char []){"abcd"}; 不一样的。p是数组，不是指针。p在栈上分配，并且通过copy的方式初始化。 p1是指针，初始化为一个匿名物体（一个数组）的地址，那个匿名数组如上情形。 后一种在栈上多了个指针。 二. ISO/IEC 9899:1999 (E), page 77. http://www.dmk.com/c/lit.html The following three expressions have different meanings: "/tmp/fileXXXXXX" (char []){"/tmp/fileXXXXXX"} (const char []){"/tmp/fileXXXXXX"} The first always has static storage duration and has type array of char, but need not be modifiable;  the last two have automatic storage duration when they occur within the body of a function, and the first of these two is modifiable. Like string literals, const-qualified compound literals can be placed into read-only memory and can even be shared.  For example, (const char []){"abc"} == "abc" might yield 1 if the literals' storage is shared. 39 39

1 #include <iostream> 2 using namespace std; 3 //int a[3000000]; 4 int main() 5 { 6    //int a[3000000];   7    int* a = new int[3000000];  8    a[0] = 1; 9 } // text segment. Better // stack segment. Fault // heap segment. Best 40

算法 1984年图灵奖获得者瑞士科学家尼克劳斯·沃斯（Niklaus Wirth)，Pascal语言的发明者和结构化程序设计创始者 1976年出版了《算法+数据结构 = 程序设计》，提出了著名的公式：“程序 ＝ 数据结构 ＋ 算法” 。 算法：解决问题的计算方法（步骤） 数据结构：数据存储的模型 语言：描述算法和数据结构的工具 程序：用语言描述出来的算法和数据结构 计算机只是一个计算工具，它本身不能主动帮助我们做任何事情，需要我们告诉它如何进行计算。 程序设计就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，只不过描述的手段有所变化而已。 Design of Algorithms

Quick sort /* qsort: sort v[left]...v[right] into increasing order */ #include <iostream> #include <cstdlib> #include <algorithm> #include <ctime> using namespace std; void qsort(int v[], int left,int right); int main() { int n; cout<<"Enter number of elements: "; cin>>n; int* a=new int[n]; srand(time(0)); for (int i=0; i<n; ++i) a[i] = rand()%(n<<2); cout<<"Initial Order of elements "; for (int i=0; i<n; ++i) cout << a[i] <<" "; cout<<"\n"; int left=0, right=n-1; qsort (a,left,right); cout <<"Final Array After Sorting: "; for (int i=0; i<n; ++i) cout<< a[i] << " "; cout << endl; delete [] a; } Quick sort /* qsort: sort v[left]...v[right] into increasing order */ void qsort(int v[], int left,int right) { if (left >= right) // do nothing if array contains return; // fewer than two elements // move partition elem to v[0] swap (v[left], v[(left+right)/2]); int last = left; for (int i=left+1; i<=right; ++i) // partition if (v[i] < v[left]) swap (v[++last], v[i]); swap (v[left], v[last]); // restore partition elem qsort (v, left, last-1); qsort (v, last+1, right); } Page 87, The C Programming Language (2nd Edition), by Brian W. Kernighan, Dennis M. Ritchie, 1998 (book5) Our version of quicksort is not the fastest possible, but it’s one of the simplest. We use the middle element of each subarray for partioning. Tip IV

Program Design 简单计算题 棋盘走子步数 模拟 猴子选大王(约瑟夫问题) 可模型化的问题 拦截导弹计数

泛型程序设计 泛型程序设计，简单地说就是使用模板的程序设计法 标准模板库 (Standard Template Library) 将一些常用的数据结构（比如链表，数组，二叉树）和算法（比如排序，查找）写成模板， 以后则不论数据结构里放的是什么对象，算法针对什么样的对象，则都不必重新实现数据结构，重新编写算法。 标准模板库 (Standard Template Library) 是一些常用数据结构和算法的模板的集合。 主要由 Alexander Stepanov 开发，于1998年被添加进C++标准 有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。 http://en.wikipedia.org/wiki/Alexander_Stepanov Alexander Stepanov (born November 16, 1950 in Moscow) is the key person behind the C++ Standard Template Library, which he started to develop around 1993 while employed at HP Labs. He had earlier been working for Bell Labs close to Andrew Koenig and tried to convince Bjarne Stroustrup to introduce something like Ada Generics in C++[1]. He is currently employed by Adobe Systems. Stepanov is the father of eight grown children and is a grandfather to five. STL

References http://net.pku.edu.cn/~course/cs101/2008/info.html Book1, Foundations of Computer Science: From Data Manipulation to Theory of Computation Book2, C++ How to Program (5th Edition) Book3,程序设计导引及在线实践 Book4, Schaum's Outline of Programming with C++ Book5, The C Programming Language (2nd Edition) Book6, Computer Systems: A Programmer's Perspective http://net.pku.edu.cn/~course/cs101/2008/resource/CSAP_cn.pdf http://net.pku.edu.cn/~course/cs101/2008/resource/cplusplus.com_20081105/ http://net.pku.edu.cn/~course/cs101/resource/www.cppreference.com/ http://net.pku.edu.cn/~course/cs101/2008/resource/cplusplus.com_20081105/doc/tutorial/index.html http://net.pku.edu.cn/~course/cs101/resource/cprogramming.com/tutorial/lesson1.html