程序设计与算法(一)
郭 炜
信息科学技术学院
微博：http://weibo.com/guoweiofpku
学会程序和算法，走遍天下都不怕!
讲义照片均为郭炜拍摄
来自中国大学MOOC
https://www.icourse163.org/learn/PKU-1001553023?tid=1466879449#/learn/announce
郭炜老师还在中国大学MOOC开设另外三门好评如潮的4.9分高分课程，特别适合后续学习，请不要错过：
- 程序设计与算法(二)算法基础(国家精品)
http://www.icourse163.org/course/PKU-1001894005
- 程序设计与算法(三)C++面向对象程序设计(国家精品)
http://www.icourse163.org/course/PKU-1002029030
- 实用Python程序设计 (强烈推荐，Python的百科书式大全课程，入门、提高均非常适合！)
http://www.icourse163.org/course/PKU-1460924165
面向对象的程序设计概论
学好C++的建议
如果您想学好C++，这里有一些建议：
学好C++需要先掌握C语言的基本知识。因为C++是在C语言的基础上扩展而来的，所以熟悉C语言的基本语法和数据结构等知识是非常重要的。
学习编程最好从入门级别做起。建议您可以看一些新手教程，比如《C++ Primer》、《C++ Primer Plus》等书籍，慢慢熟悉语言的基本语法和核心概念。
多练习编程实践。只有不断尝试，不断打码，才能快速理解语言的用法和特点，提高自己的编程技术。
参与开源社区的项目。加入一些相关的开源社区，阅读、参考一些优秀的代码，借鉴他人的经验和思路，提高自己的编程实力。
反省自己的错误。无论是初学者还是资深程序员，都必须时刻审视自己的编程风格和代码质量，及时发现和纠正问题，不断提高自己的编程水平。
总之，想学好C++，需要坚持不懈地学习和实践，不断锤炼自己的编程技能。
初步理解
相比较于面向过程的程序设计来说有更多的封装的函数可以使用，相比较来说会比较方便。但是如何去设计整个程序的思路也是需要一定的训练的。
C++是C语⾔的继承，它既可以进⾏C语⾔的过程化程序设计，⼜可以进⾏以抽象数据类型为特点的
基于对象的程序设计，还可以进⾏以继承和多态为特点的⾯向对象的程序设计。C++擅⻓⾯向对象程序设计的同时，还可以进⾏基于过程的程序设计，因⽽C++就适应的问题规模⽽论，⼤⼩由之。
C++不仅拥有计算机⾼效运⾏的实⽤性特征，同时还致⼒于提⾼⼤规模程序的编程质量与程序设计
语⾔的问题描述能⼒。
C++刷算法的认识
所以说， C++ 是⼀⻔可以兼容C语⾔语法的⾯向对象语⾔。其实对于刷算法来说，它是否是⾯向对象
语⾔并不重要，它关于⾯向对象的部分（继承封装多态之类）我们也可以完全不学习，⽽且对于已经懂C语⾔的⼈来说，想要⽤ C++ 刷算法，⼏乎没有多少学习成本。也就是说，你完全可以在 C++ 的⽂件⾥⾯使⽤C语⾔的语法，这不会产⽣报错。⽽那些好⽤的 C++ 特性⼜可以随意的使⽤，像是增强版功能的C语⾔。对于刷算法来说， C++ 最⼤的好处是拥有 STL （标准模版库），就像 Java 的集合框架⼀样， C++ ⾥⾯封装了很多常⽤的数据结构，⽽只需掌握STL和C++的⼀些和C语⾔稍有区别的基本语法，就完全可以使⽤ C++ 来刷PAT、LeetCode和蓝桥杯，这对算法之路是⼤有裨益的～下⾯是⼀段关于 STL 的简介：
这些“容器”有list，vector，set，map等，STL也是算法和其他⼀些组件的集合。STL的⽬的是标准化 组件，这样就不⽤重新开发，可以使⽤现成的组件。STL现在是C++的⼀部分，因此不⽤安装额外的 库⽂件。 什么意思呢，⽐如说刷算法过程中需要⽤到集合 set ，我们知道 set 的特点是集合内的元素不重复 （特别地，在 C++ ⾥⾯， set 是会⾃动排序的集合， unordered_set 是不会⾃动排序的集合），⽐如 在set⾥分别放进 4、1、1、2、3 这⼏个元素，set⾥会⾃动变成 1、2、3、4 ，如果我们只会C语⾔，可 能需要⼀个个把数据放到数组⾥⾯，然后⼿动编写⼀些代码，检查进来的每⼀个元素在数组中是否已 经存在，如果存在就不要再放进数组，最后对整个数组进⾏排序，才能达到set的效果。但是如果直接 使⽤ C++ ，我们就可以在头⽂件⾥⾯加个 #include <set> ，然后直接把 set 当作⼀个类似于数组的容 器，把所有元素直接丢到⾃⼰定义的这个set类型的容器⾥，就会⾃动实现去重（去除重复元素）和排 序的步骤～⽐如说题⽬要求将最后所有的答案去重后按从⼩到⼤的顺序输出，就可以直接将所有的答 案元素放到set⾥⾯输出即可～这样我们在刷题过程中就能更好地集中精⼒解决代码思路、算法⽅⾯的 问题，⽽不是⼀个简单的答案输出或语法⽅⾯的问题，在考试过程中也能⼤⼤地节省时间，降低代码 的错误率～
二进制和十六进制
用0和1表示各种信息
计算机的电路由逻辑门电路组成。一个逻辑门电路可以看成一个开关，每个开关的状态是“开"（高电位）或“关”（低电位），即对应于1或0
课程推荐 【【计算机科学速成课】[40集全/精校] - Crash Course Computer Science】 https://www.bilibili.com/video/BV1EW411u7th/?share_source=copy_web&vd_source=3b2cc08efb537592debc1e358b5d787f
计算机的电路由逻辑门电路组成。一个逻辑门电路可以看成一个开关，每个开关的状态是“开"（高电位）或“关”（低电位），即对应于1或0
二进制数的一位，取值只能是0或1，称为一个“比特”(bit)，简写：b
计算机的电路由逻辑门电路组成。一个逻辑门电路可以看成一个开关，每个开关的状态是“开"（高电位）或“关”（低电位），即对应于1或0
二进制数的一位，取值只能是0或1，称为一个“比特”(bit)，简写：b
八个二进制位称为一个“字节”（byte),简写: B
计算机的电路由逻辑门电路组成。一个逻辑门电路可以看成一个开关，每个开关的状态是“开"（高电位）或“关”（低电位），即对应于1或0
二进制数的一位，取值只能是0或1，称为一个“比特”(bit)，简写：b
八个二进制位称为一个“字节”（byte),简写: B
1024(210)字节称为1KB ，1024KB称作1MB(1兆)，
1024MB称作1GB，
1024GB称作1TB。
用0和1表示各种信息
0和1足以表示和传播各种信息。
比如, 用8个连续的0或1（即1个字节）来表示一个字母、数字或标点符号
，比如用“00100000”表示空格，用“01100001”表示字母“a”,用
“01100010”表示字母“b”，用“01100011”表示字母“c”……。由8个
0或者1的组成的串，一共有28即256种不同的组合，这就足以表示10个阿拉伯数字以及英语中用到的所有字母和标点符号了。此即为ASCII编码方案。
图片、视频和可执行程序，也可以用0和1表示
给定一个K进制数
给定一个K进制数，求它是多大 假设有一个n+1位的K进制数，它的形式如下： AnAn-1An-2。。。。。。A2A1A0 (比如 八进制数 1723) 则其大小为： A0×K0 + A1×K1 + ……+ An-1×Kn-1+ An×Kn 数就是数，没有进制之分，只有数的表示形式，才有进制之分。 所谓“十进制数”，是“数的十进制表示形式" 的简称。 给定一个数，求其K进制表示形式 10 求数的K进制表示形式 -- 短除法 给定一个整数N和进制K，那么N可表示成以下形式： N = A0×K0+A1×K1+A2×K2+……+An-1×Kn-1+An×Kn = A0 +K (A1 +A2×K1+……+An-1×Kn-2+An×Kn-1 ) N除以K所得到的余数是A0，商是A1+A2×K1+……+An-1×Kn-2+An×Kn-1。将这个商再除 以K，就得到余数A1，新的商是 A2 + A3×K1+……+An-1×Kn-3+An×Kn-2 不停地将新得到的商除以K，直到商变成0，就能依次求得A0 、A1、 A2 …… An-1 、An 。显然，Ai <K ( i = 0…n)，且最终得到的K进制数就是: AnAn-1An-2。。。。。。A2A1A0 K进制小数 11 K进制小数 0.A0A1……An的值是： A0×K-1+A1×K-2+……+An×K-(n+1) (0.12)10 = 1 ×10-1 + 2 ×10-2 (0.1)3 = 1 ×3 -1 即1/3, 表示成10进制就是无限循环小数 可见，n进制下的有限位小数，在m进制下可能就无法精确表示，因为会无限 循环 十进制有限位小数，在二进制的情况未必能用有限位数表示出来。计算机内 存有限，不可能存放无限位，因此计算机的小数运算会有误差。比如，计算 机其实无法精确表示 4.9，只能精确表示4.899999999...之类一个很接近的数
十六进制数
十六进制数应该有16个数字，除0到9外：
A 10
B 11
C 12
D 13
E 14
F 15
小写也可以
为什么是C++而不是C语言
为什么是C++而不是C语言
C语言是好东西，但是有点弱
C++ 更是好东西，但是有点烦
我们要学的，是C++的一部分，基本上就是:
C语言+ STL （STL是C++中能让你节省大量编程时间的神兵！)
因为暂时不写大程序，因此不用关心“面向对象”的事情！
C++的基本数据类型
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aQ8w1ouo-1683000164580)(2023-04-17-17-08-03.png)]
用sizeof运算符求变量占用字节数
sizeof(变量名) sizeof(类型名) 能够得到某个变量或某一类型变量占用的字节数 int n1 = 10; double f; char c; printf("%d,%d,%d,%d",sizeof(n1),sizeof(short), sizeof(double),sizeof(c)); 输出： 4,2,8,1
变量和数据类型进阶
有符号整数和无符号整数
short、int、long、long long 类型的变量，可以表示正数，也可以表示负数，称为有符号的整数类型。
unsigned short， unsigned int, unsigned long,unsigned long long类型的变量，只会被看作非负数，称为无符号的整数类型
有符号整数的表示方式
将最左边的位（最高位)看作“符号位”。符号位为0，则表示是非负数，其绝对值就是除符号位以外的部分；符号位为1，则表示是负数，其绝对值是所有位取反（0变1，1变0）后再加1。
将一个负整数表示为二进制的方法：
(1） 设置符号位为1
（2） 其余位等于绝对值取反再加1
有符号整数的表示方式
给定一个负整数的二进制表示形式，求该负整数:
该负整数的绝对值是其二进制表示形式取反再加1(取反加1后的结果要看作是正数）。
将一个负整数表示为二进制的方法：
1） 设置符号位为1
2） 其余位等于该负数的绝对值的二进制表示形式取反再加1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CP3eA4kJ-1683000164580)(2023-04-17-17-14-27.png)]
字符类型到整型的互相转换
字符型数据可以转换成整型数据 int k = 'a' ; //k内容变为'a'的ASCII码，即97 printf("%d",k) ; //输出：97 整型数据也可以转换为字符型数据，但只会留下最右边的一个字节（第0位 到第7位），其他字节丢弃 int n = 98; char k = n ; //k内容变98,98是字符'b'的ASCII码 printf("%c",k) ; //输出：b
类型自动转换示例
#include <cstdio> #include <iostream> using namespace std; int main() { int n1 = 1378; //1378的十六进制形式是 0x562 short n2; char c = 'a'; double d1 = 7.809; double d2; n2 = c+1; //n2变为98 , 97是'a'的ASCII码 printf("c=%c,n2=%d\n",c,n2); //输出 c=a,n2=98 c = n1; // n1是0x562, 0x62被当做ASCII码赋值给c,c变为 'b' printf("c=%c,n1=%d\n",c,n1); //输出 c=b,n1=1378 n1 = d1; // d1=7.809, 去掉小数部分后赋值给n1,n1变为7 printf("n1=%d\n", n1); //输出 n1=7 d2 = n1; //d2变为7 printf("d2=%f\n",d2); //输出 d2=7.000000 return 0;
cin,cout和scanf,printf比较
cin,cout 速度比scanf,printf慢,输入输出数据量大时用后者
一个程序里面不要同时用cin和scanf,不要同时用cout和printf
