计算导论与C语言基础¶
information¶
计算导论：计算机的基本原理、计算机的发展趋势、程序运行的基本原理
C程序设计：感性认识C程序、理性认识C程序
Module 1 计算机的基本原理¶
计算机的基本原理（从数学危机到图灵机）¶
图灵奖 turing award
三次数学危机¶
第一次数学危机
毕达哥拉斯学派——数是万物的本源
深信一切数均可表示称整数或者整数只比
在证明勾股定理时发现呢某些直角三角形的三边之比不能用整数来表达（希帕索斯悖论）
第二次数学危机
微积分建立在无穷小的分析之上（牛顿和莱布尼茨分别独立发明了微积分）
贝克莱悖论（求x^2的导数的时候无穷小一会是0，一会作为分母又不能为0）
实数理论建立起了极限论的基本定理
导致了集合论的诞生
第三次数学危机
十九世纪下半叶，康托尔创立了集合论
“从自然数与康托尔集合论出发可以建立起整个数学大厦”
“一切数学成果可以建立在集合论上”
罗素悖论：S由一切不是自身元素的集合所组成，S是否属于S吗
哥德尔（Kurt Godel）不完备性定理：任何一个数学系统，只要它是从有限的公理和基本概念中推到出来的，并且可以从中推证出自然数系统，就可以在其中找到一个命题，对于我们既没有办法证明，也没有办法证伪
把数学彻底形式化的愿望本身就是不可实现的
判定一个未解的问题是否真的有解
在计算机中，叫做可计算问题
解决问题的边界
为计算建立一个数学模型，凡是计算模型能够完成的任务就是可计算的任务
图灵的贡献¶
Alan Turing
1936，24岁《论可计算数载判定问题中的应用》——理想的计算就起的数学模型，图灵机
1950 图灵测试
图灵机的构成¶
一条存储带、一个控制器
运作机理¶
存储带符号初始化、设置好自身的当前状态、控制器置于起始位置、准备好工作程序
条件、动作
示例¶
图灵机的意义¶
简单、强大、可实现
可计算性的判定
给出了一个可实现的通用计算的模型
数的二进制表示¶
计算机为什么能计算？
“数”在计算机中是如何表示的¶
字母表中的符号越多，读入的移动次数减少，程序的数量就会增加
字母表中的符号越少，程序量会减少，但读入移动次数就越多
字母表中的最优数量，可能是欧拉常数e（2.7182818284590）取整之后为3
与两个状态的电子元件相比，具有三个状态的电子元件在制造上更困难，可靠性更低
从二进制到八进制，只要每三位进行一次转换就行
十六进制，就是每四位进行一次转换
逻辑上“数”是如何计算的¶
数的表示：二进制
英国数学家Boole 布尔代数，为计算机的电路设计奠定了理论基础
二进制的布尔运算¶
基本的逻辑运算：与、或、非
复合逻辑运算：同或/异或、与非、或非、与或非
与运算：串联
或运算：并联
非运算：短路他
异或：两个变量相同结果为0，相异结果为1
同或：与异或相反
二进制下：
1 + 1 = 10
1 + 0 = 01
0 + 1 = 01
0 + 0 = 00
发现末尾的数相异的时候结果为1，相同的时候结果为0，说明二进制的加法运算是异或运算
而观察进位，可以发现只有末尾两个数字都是1的情况下才会有进位，所以这是一个与运算
简而言之，二进制的加法，本位是异或运算的结果，进位是与运算的结果
以上的机器就是半加器
多个半加器串联，得到全加器就能用来计算带进位的情况
物理上如何实现数的计算¶
异或门、与门、或门
基本的布尔运算都可以由电路实现
Module 2 计算机的历史与未来¶
计算机的发展历程¶
现代计算机
电子管计算机、晶体管计算、集成电路计算机、超大规模继承电路
帕斯卡12岁独立发现三角形内角和等于180度
帕斯卡与费马的通信形成了概率论的基础
帕斯卡加法器1642年
齿轮装置，能够完成6位的加法和减法，是一种系列齿轮组成的装置，依靠发条转动
1673年，莱布尼茨在帕斯卡加法器的基础上，建造了一台能够进行四则运算的机械计算机器，仍然用齿轮及刻度盘操作，能够达到16位里
1822年，巴贝奇，制造出第一台差分机，可以处理3个不同的5位数、计算精度可以达到6位小数
1834年，巴贝奇提出了分析机的概念
分析机一共分为三个部分：堆栈、运算器、控制器
尝试使用机械方式（蒸汽动力）实现计算过程
计算用的程序和数据存储在穿孔卡片上
阿达奥古斯塔（augusta）为分析机编制了人类历史上第一批计算机程序
手工的方式工艺是有极限的
霍列瑞斯（Hollerith），IBM创始人
发明了制表机，电子穿孔卡片汇总
1935年，IBM制造了IBM601，能够在一秒钟之内计算出乘法运算
1941年，德国Zuse完成了Z3的研制工作
第一台可编程的电子计算机
可处理7位指数、14位小数
大量真空管的应用
每秒钟能做3到4次加法，一次乘法在3到5秒
普遍认为的第一台计算机ENIAC¶
宾夕法尼亚大学莫尔学院1945年完成，1946年2月14日正式启动
ENIAC不是存储程序式的计算机
编程是通过手工插接线的方式进行的
ENIAC到EDVAC¶
冯诺依曼 1952年EDVAC制造完成，世界上第一台存储程序计算机
第二代计算机¶
1947年，贝尔实验室发明了晶体管，更小、更便宜、功耗更少、更可靠
产生了操作系统
产生了高级编程语言Fotran, Cobol
第三代计算机¶
1958年，德州仪器 基尔比发明了集成电路，直接用硅片制造芯片
操作系统可移植
C语言开始产生
第四代计算机¶
始于20世纪70年代
使用超大规模的集成电路
第一块微处理器是1971年制造的intel4004
2400个晶体管，计算能力与ENIAC相当
尺寸只有3mm * 2mm
计算机的发展在硬件、软件全方位出现瓶颈
摩尔定律：CPU的性能价格比每18个月翻一番
Moore‘s LAW
第五代计算机¶
超算
“绿色计算”：2009年时，每次google所消耗的能源能够煮熟一杯咖啡
新型的计算模式——云计算
摩尔定律下的计算危机¶
单位面积中能够制造的晶体管的数目每18个月翻一番
1970年intel 4004
1990年intel 80486
摩尔定律还能坚持多久？
第一点：散热，晶体管密度和速度的增加，会消耗更多的电力，产生更多的热能
扩大体积，虽然能扩大表面积，但是意味着需要更高的电压，会使热量产生的更多
第二点：晶体管大小的限制，晶体管很快就会变成一个原子大小，任何纳米和传统工艺对这种情况都没有办法
第三点：电泄漏，随着晶体管提及的缩小，电泄漏的清醒也不断增加，越来越影响芯片的计算能力
量子计算机、生物计算机、DNA计算机、光子计算机、分子计算机
量子计算机的基本原理¶
理查德费曼，1982年提出利用量子体系实现通用计算
分析模拟量子物理世界所需要的计算能力远远超过了经典计算机所能达到的能力
用实验室中一个可控的量子系统
一个量子比特能够同时保持多种状态
举例：经典计算机2个比特某一特定时刻只能存储一对0或者1，但是量子计算机可以同时存储4对0或者1
理论上300个量子比特能承载的数据时2的300次方，这将超过整个宇宙的原子数量总和
需要对计算过程进行纠错，即用大量的计算来冗余计算，确定出正确的答案
难点：与外界环境隔离才能保持良好的相干性，与外界环境良好耦合才能控制演化并读出结果
Module 3 程序运行的基本原理¶
冯诺依曼：
电路能够完成计算
但是不能通过重新“组合不同电路”的方式，去完成新的计算任务
通过某种命令来控制计算机，让计算机按照这种命令来运行，这种命令可以用电信号表示
这种命令不是“临时输入”计算机，而是存放在某个地方，随时可以更改
存储程序式计算机：EDVAC
冯诺依曼结构：控制器、运算器、存储器、输入设备、输出设备
控制器：统一指挥并控制计算机个部件协调工作 (命令记录员、控制信号产生器、命令解释器)
运算器：对数据进行算数运算和逻辑运算（计算结果、计算电路、数据暂存）
存储器：存储待操作的信息与中间结果，包括机器指令和数据（高速缓存、内存、外存）
运算器、存储器的一部分和控制器集合在CPU里
存储器¶
一个存0或1的单位叫bit ，位
8个bit叫byte，字节，是程序里能控制的最小单位
1kb 1024字节
1MB
1GB
1TB
1PB
计算机中存储器的分类：寄存器、高速缓存、内存、外存
寄存器：CPU内部，用于存放待操作数和结果
高速缓存（cache）：通常在CPU内部，用做数据缓存区
内存：存放CPU中的运算数据
存储器的原理¶
静态RAM的六管基本存储单元
高电位和低电位互相保持促进，就能更好地存储数字
地址解析器由行地址译码器和列地址译码器，同时在行和列导通可以读出数字
RAM (random access memory)
快速可擦除存储器-u盘
DDR double data rate SDRAM 双数据输出同步动态存储器
地址与数据单元
32位的存储器，最大的寻址空间是2的32次方，也就是4个G
程序运行的基本原理¶
冯诺依曼式计算机执行存储好的程序
指令集是用来计算和控制计算机系统的一套指令的集合
主要有两种：Intel X86指令集和 ARM指令集
指令码 + 操作数 = 指令
CPU指令的执行过程¶
- PC 程序计数器 中包含程序的地址，会将程序的地址发给地址寄存器
- AR 地址寄存器 会去相应的地址中将指令取出来放入指令寄存器
- OP | ADDR 指令寄存器IR ，将指令交给指令译码器，看看指令要完成什么
- 指令寄存器发现命令中包含地址，又要返回地址寄存器中到相应的存储器地址，并将取出的数字存入缓冲寄存器DR中
- ID 指令译码器
- 然后由OC操作控制器和TG时序产生器发送一个命令给ALU 算数逻辑单元
- 由ALU完成运算，并将结果放入AC累加器当中
程序的执行¶
编译，将程序先编译成汇编代码 再将汇编代码汇编成机器码 让机器码由CPU运行
Module 4 感性认识计算机程序¶
使用IDE进行调试¶
- log法，即在需要调试的地方进行输出值print
- 断点法，在可以的地方打上断点
step over是跳到下一句
Step into 是如果这一行由调用函数的话，就会进入那个函数
step out就是跳出函数
程序设计语言的学习¶
knowledge和skill
存储程序式计算机
编程语言的单词
编程语言里的数和计算符号
编程语言中的句式
编程作业¶
编程题1 冒泡算法¶
/*
* 根据自己的理解写冒泡排序算法，数组大小在1000以内
* 第一行是n，表示数组的大小，接着n行是数组的n个元素
* 按照从小到大进行排列
*/
#include <iostream>
using namespace std;
int main () {
int n, a[1000];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 冒泡算法核心：从小到大，发现相邻的数有不符合规则的就互相交换
// 每一遍会将一个最大的数字转移到标号最大处
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) {
cout << a[i] << endl;
}
return 0;
}
编程题2 奇偶排序¶
/*
* 奇偶排序
* 输入十个整数，将十个整数按升序排列输出，并且奇数在前，偶数在后。
*/
#include <iostream>
using namespace std;
int main () {
int a[10];
// 首先是输入10个整数
for (int i = 0; i < 10; i++) {
cin >> a[i];
}
// 第二步是使用双指针法将奇数和偶数分别放在前后两侧
// 注意：只要出现一个不符合排序的数字，那么必然有个数字和它进行对应，进行双指针交换
int l = 0, r = 9;
while (l < r) {
bool leftIsOdd = a[l] % 2 == 1;
bool rightIsEven = a[r] % 2 == 0;
if (leftIsOdd) {
l++;
} else if (rightIsEven) {
r--;
} else if (!leftIsOdd && !rig htIsEven) {
int temp = a[l];
a[l] = a[r];
a[r] = temp;
}
}
// 对奇数部分进行冒泡
int start = 0, end = l;
for (int i = start; i < end -1; i++) {
for (int j = start + 1; j < end + start - i; j++ ) {
if (a[j - 1] > a[j]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
// 对偶数部分进行冒泡
start = l, end = 10;
for (int i = start; i < end - 1; i++) {
for (int j = start + 1; j < end + start - i; j++ ) {
if (a[j - 1] > a[j]) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
for (int i = 0; i < 10; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}
Module 5 从现实问题到计算机程序¶
解决问题的方案
描述给电脑听：结构化程序设计的思想，先抽象后具体，直到能够使用顺序、分支、循环搞定
可以先写出程序的轮廓，然后再补变量的定义
整数排序
循环结构
结构化程序设计¶
由若干个模块组成
模块之间高内聚，模块功能单一
模块之间低耦合，一个模块被改动的时候，指挥影响自己
Module 6 理性认识C程序 导论¶
程序设计语言的分类：
机器语言 0101010这种低级语言
汇编语言 load 0 a这种低级语言
高级语言 C
FORTRAN 第一门高级程序设计语言
19060 algo 60 A语言
1970 贝尔实验室ken Thompson PDP-7 B语言 UNIX
1972在B语言的基础上发展和完善出了C语言，并重写了UNIX
1978 The C programing language
C语言的规范定义得相当宽泛
long数据长度不断与int即可
short不常于int即可
相同程序在不同编译器上具有不同解释
相同程序在不同平台上运行结果不同
1979 贝尔实验室 C with classes 即c++，扩展了面向对象部分
#include <iostream>
using namespace std;
int main () {
// 输入培养皿数量、编号以及细菌繁殖率；
int n;
int id[100];
double rate[100];
cin >> n;
for (int i = 0; i < n; i++) {
int initial, final;
cin >> id[i] >> initial >> final;
rate[i] = (double) final / initial;
}
// 将所有的输入按照从大到小排列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i -1; j++) {
if (rate[j + 1] > rate[j]) {
int tmpId = id[j];
id[j] = id[j + 1];
id[j + 1] = tmpId;
double tmpRate = rate[j];
rate[j] = rate[j + 1];
rate[j + 1] = tmpRate;
}
}
}
// 计算相邻之间的差值，相差最大的一组就是两组细菌的分界线
double maxDiff = 0;
int maxDiffIndex = 0;
for (int i = 0; i < n - 1; i++) {
double diff = rate[i] - rate[i + 1];
if (diff > maxDiff) {
maxDiff = diff;
maxDiffIndex = i;
}
}
cout << maxDiffIndex + 1 << endl;
for (int i = maxDiffIndex; i >= 0; i--) {
cout << id[i] << endl;
}
cout << n - maxDiffIndex - 1 << endl;
for (int i = n - 1; i >= maxDiffIndex + 1; i--) {
cout << id[i] << endl;
}
return 0;
}
Programming Assignment: 理性认识C程序 导论 编程题¶
#include <iostream>
using namespace std;
int main () {
int n, grade[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> grade[i];
for (int i = 0; i < n; i++) {
for (int j = 1; j < n - i; j++) {
if (grade[j - 1] < grade[j]) {
int tmp = grade[j];
grade[j] = grade[j - 1];
grade[j - 1] = tmp;
}
}
}
cout << grade[0] << endl;
return 0;
}
编程题＃3：最高的分数¶
#include <iostream>
using namespace std;
int main() {
int a[10];
for (int i = 0; i < 10; i++) {
cin >> a[i];
}
// 冒泡，不断比较相邻的两个数，如果顺序错了，那么就交换
for (int i = 0; i < 9; i++) {
for (int j = 1; j < 10 - i; j++) {
// 与刚才的冒泡排序不同，我们不只是通过较数字的大小决定顺序
// 如果左边的为偶数，右边的为奇数，那么顺序也需要颠倒
bool leftIsEven = a[j - 1] % 2 == 0;
bool rightIsEven = a[j] % 2 == 0;
if ((leftIsEven && !rightIsEven) ||
(leftIsEven == rightIsEven && a[j - 1] > a[j])) {
int temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
for (int i = 0; i < 10; i++) {
cout << a[i] << ' ';
}
return 0;
}
编程题＃4：最大奇数与最小偶数之差的绝对值¶
描述¶
输入6个正整数，且这6个正整数中至少存在一个奇数和一个偶数。
设这6个正整数中最大的奇数为a，最小的偶数为b，求出|a-b|的值
¶
输入¶
输入为一行，6个正整数,且6个正整数都小于100
输入保证这6个数中至少存在一个奇数和一个偶数
¶
输出¶
输出为一行，输出最大的奇数与最小的偶数之差的绝对值
做法一：（太复杂）
#include <iostream>
#include <cmath>
using namespace std;
int main () {
int num[6];
for (int i = 0; i < 6; i++) {
cin >> num[i];
}
// 双指针法将所有数进行奇偶排序，奇数在左边，偶数在右边
int l = 0, r = 5;
while (l < r) {
bool leftIsOdd = num[l] % 2 == 1;
bool rightIsEven = num[r] % 2 == 0;
if (leftIsOdd) {
l++;
} else if (rightIsEven) {
r--;
} else if (!leftIsOdd & !rightIsEven) {
int tmp = num[l];
num[l] = num[r];
num[r] = tmp;
}
}
// 对奇数和偶数部分分别进行排序
for (int i = 0; i < l; i++) {
for (int j = 0; j < l - i -1; j++) {
if (num[j] < num[j + 1]) {
int tmp = num[j];
num[j] = num[j + 1];
num[j + 1] = tmp;
}
}
}
for (int i = l; i < 6; i++) {
for (int j = l; j < 5 + l - i; j++) {
if (num[j] < num[j + 1]) {
int tmp = num[j];
num[j] = num[j + 1];
num[j + 1] = tmp;
}
}
}
// 计算并且输出最大的奇数和最小偶数的差值
cout << abs(num[0] - num[5]) << endl;
return 0;
}
做法二：（注意题意）
#include <iostream>
#include <cmath>
using namespace std;
int main () {
int maxOdd = 0, minEven = 100;
for (int i = 0; i < 6; i++) {
int a;
scanf("%d", &a);
if (a % 2 == 1) {
if (a > maxOdd) maxOdd = a;
} else {
if (a < minEven) minEven = a;
}
}
cout << abs(maxOdd - minEven) << endl;
return 0;
}
编程题＃5：分离整数的各个数位¶
#include <iostream>
using namespace std;
int main () {
char str[4];
cin >> str;
for (int i = 0; i < 3; i++) cout << str[i] << endl;
return 0;
}