最MC论坛

标题: [KSの个人向教程]C语言、C++与算法竞赛学习笔记 [打印本页]
作者: KSkun    时间: 2014-12-1 19:57
标题: [KSの个人向教程]C语言、C++与算法竞赛学习笔记
采用刘汝佳《算法竞赛入门经典（第2版）》、《C++ Primer》与《算法导论》共同学习。
本帖仅用于分享个人学习C语言、C++与算法竞赛的心得，如有错误请指出。
本帖不会含有图片、视频资料，请各位善于动手实践。
由于使用GCC编译器，本帖中代码可能偏向于C++标准，请注意区分。
本帖之代码片段均使用Dev-C++/MinGW64编译，可能与部分OJ的要求不相同。

开坑于2014/12/1
转载请注明原帖地址、原作者名称及相关注意事项，谢谢。

KSkun/KS酱
http://ksmeow.moe/
作者: KSkun    时间: 2014-12-1 20:11
Day 1 《算法竞赛》第1部分 第1章
本笔记对新手可能不太友好，建议有基础再来阅读。

1.1 算术表达式
C语言（或是通用于其他语言）的算术运算符有：
  1. + - * / %
复制代码
+ 算术加
- 算术减
* 算术乘
/ 算术除
% mod
也可以包含math.h头文件使用更多的算术运算函数，例：
  1. #include <stdio.h>
  2. #include <math.h>

  4. int main() {
  5.     int a = sqrt(4); //sqrt(float f)用于开方
  6.     printf("%d\n", a);
  7.     return 0;
  8. }
  9. //Input: null; Output: 2
复制代码
12/9补充：需要注意的是，这里的sqrt()函数传入和返回的都是double值，强制转型为int值会有误差，请谨慎使用
算术运算式的结果如下：
int / int = int
float / float = float
int - float = float
以此类推

那么上面说到的scanf()和printf()函数怎么用呢
  1. scanf("%d", &a);
  2. //%d表示输入一个int, 如果替换成%f就表示输入一个float, 此处可以加上格式比如"%d %d\n%d"
  3. printf("%d %d\n%.1f", a, b, c);
  4. // \n为换行符, %.1f表示输出的浮点数保留1位小数
复制代码
作者: zuimc    时间: 2014-12-1 21:44
点个赞
作者: KSkun    时间: 2014-12-2 07:00
Day 2.1 《C++ Primer》第一章

1.2 初始输入和输出
C++中输入输出是对象形式的。
  1. std::cin >> a;
  2. std::cout << a;
复制代码
这里需要include一个C++头文件才能获得这个namespace里的对象
  1. #include <iostream>
复制代码
那么由C的function变为C++的object自然会简单很多
  1. std::cin >> 对象;
  2. std::cout << 对象;
  3. //同时std::endl表示换行符
复制代码
如果不想用std::的话可以加上如下语句
  1. using namespace std;
复制代码
这样编译器就会认为你默认在std namespace里调用了。
cin、cout对象是输入/出数据流，>>是输入运算符，而<<是输出运算符，I/O的过程就是向流写入、取出数据。

1.3 注释简介
这个不需要多讲，大家都熟悉。
  1. //单行注释
  2. /* 多行注释
  3. * 像这样
  4. * 可以持续很多行
  5. */
  6. // /*
  7. //  * 单行注释中的多行注释是被忽略的
  8. //  */
  9. /* 也可以这么用 */
复制代码
晚上回来写算法竞赛~
作者: Wolverine    时间: 2014-12-2 08:58
我现在也在学习C++，不过感觉还是JAVA好
作者: KSkun    时间: 2014-12-2 12:22
Wolverine 发表于 2014-12-2 08:58
我现在也在学习C++，不过感觉还是JAVA好

C++的效率、资源占用都比Java要好得多，但Java的跨平台通用性不容忽视，各有各的长处。
作者: KSkun    时间: 2014-12-2 12:49
Day 2.2 《C++ Primer》第1章

1.4 控制流
首先是俩循环语句，不多说，看示例。
  1. while(condition)
  2.     statement
  3. //while循环当条件为true时继续循环，为false时停止循环，先检查条件再执行循环
  4. for(init-statement; condition; expression)
  5.     statement
  6. //for循环括号里一个初始化语句一个条件一个表达式不需要多讲，先后顺序同while
复制代码
这里顺便讲一下赋值运算符和前后缀递增/减运算符
运算符类型运算符作用
赋值运算符=将右边的值赋给左边的变量
复合赋值运算符+=将右边的值加给左边的变量
复合赋值运算符-=将右边的值减给左边的变量
复合赋值运算符*=将右边的值乘给左边的变量
复合赋值运算符/=将右边的值除给左边的变量
递增运算符++将变量值加1
递减运算符--将变量值减1

赋值运算符大家都知道是什么意思，所以这里解释一下“左值”、“右值”和递增/减运算符的用法0。来看两个问题
(1)++a和a++有什么区别呢？
(2)来看一段代码：
  1. #include <stdio.h>
  2. int main() {
  3.     int a = 0;
  4.     ++++a;
  5.     printf("%d\n", a);
  6.     return 0;
  7. }//Input: null; Output: 2
复制代码
那么这里的++++a是应该理解为什么呢？

左值、右值的概念解读：
根据它们的名称，我们可以简单地理解为左值是能位于赋值运算符左侧的对象，而右值则是右侧，但需要知道的是这是不准确的。
C++ Primer是这么解释的：当一个对象被用作右值的时候，用的是对象的值（内容）；当对象被用作左值的时候，用的是对象的身份（在内存中的位置）。
这么解释是没有错的，简单地再次归纳一下，赋值运算就是将右侧对象的值写入左侧对象中，即左值是可“写”的，右值是可“读”的。
让我们用一个例子进一步地解释。++a与a++的关系，那么让我们进行一些实验：
①
  1. #include <stdio.h>
  2. int main() {
  3.     int a = 0;
  4.     ++a = 8;
  5.     printf("%d\n", a);
  6. }//Input: null; Output: 8
复制代码
②
  1. #include <stdio.h>
  2. int main() {
  3.     int a = 0;
  4.     a++ = 8;
  5.     printf("%d\n", a);
  6. }//Errored
复制代码
运行①的时候，我们发现编译器没有报错，说明++a是一个左值，这句根据运算符优先表可以转化为(++a) = 8;意思是说先对a进行递增运算，然后赋值8给a，此时++a返回的是一个对象a，确实是一个左值。
而在编译②的时候，编译器给出了这样的错误：[Error] lvalue required as left operand of assignment，意为赋值运算左边的操作数必须为左值，即a++不是一个左值。此句应理解为(a++) = 8;，但由于a++返回的是一个右值（后面可能会讲到，C++11之前返回的是一个常量，常量的值为递增运算前a的值），该赋值语句并不合法，因此编译器报出了编译错误。由此，我们了解了左值和右值的实质。

接下来是对问题(2)的解读，由上面所述，我们可以得知这句语句应该理解为++(++a)，不必多讲。

1.4.3在Day 3或Day 4讲解。
作者: EDC    时间: 2014-12-2 20:38
我能说没有C语言基础的已经看瞎了吗
作者: zuimc    时间: 2014-12-2 21:24
继续点赞
作者: KSkun    时间: 2014-12-2 22:36
EDC 发表于 2014-12-2 20:38
我能说没有C语言基础的已经看瞎了吗

...本来就没打算写给新手看了
作者: KSkun    时间: 2014-12-2 22:36
zuimc 发表于 2014-12-2 21:24
继续点赞

2x赞 get
作者: KSkun    时间: 2014-12-3 00:41
Day 3.1 《算法竞赛》第1章

1.2 变量及其输入
Problem 1 a+b问题
Problem 2 圆柱体的表面积

P1不用多讲
  1. #include <stdio.h>
  2. int main() {
  3.     int a, b;
  4.     scanf("%d%d", &a, &b);
  5.     printf("%d %d\n", a + b);
  6.     return 0;
  7. }
复制代码
P2需要注意的是圆柱体面积计算需要用到π这个常量，应该使用双精度浮点数作为变量以获得更精确的结果。
  1. #include <stdio.h>
  2. #include <math.h>
  3. int main() {
  4.     const double pi = acos(-1.0);//求出π的值并保存为常量
  5.     double r, h, s1, s2, s;
  6.     scanf("%lf%lf", &r, &h);
  7.     s1 = pi * r ^ 2;
  8.     s2 = 2 * pi * r *  h;
  9.     s = s1 * 2.0 + s2;
  10.     printf("Area = %.3f\n", s);
  11.     return 0;
  12. }
复制代码
作者: KSkun    时间: 2014-12-3 13:00
Day 3.2 《C++ Primer》 第1章

1.4.3 读取数量不定的输入数据
这里实际上是对cin和while循环的利用，不多赘述，看示例。
  1. #include <iostream>
  2. using namespace std;
  3. int main() {
  4.     int a = 0, sum = 0;
  5.     while(cin >> a) sum += a;
  6.     cout << sum << endl;
  7.     return 0;
  8. }
复制代码
这是一个不给定数据数量的计算总和的程序，由于不管是C语言的scanf还是C++的cin读取数据的时候都会返回一个状态，我们便可以利用这个状态。这里意为一旦读取失败就终止循环。
需要注意的是，当我们输入数据的时候，输入完成所有数据，但程序还没停止请求输入，这时我们要在数据的末尾加一个文件结束符。
在Windows中，文件结束符可以用Ctrl+F输入，在你的调试窗口内可能会显示为“^F”。

1.4.3节之后，C++ Primer又讲了几个编译错误，这里稍微提一下。
语法错误（Syntax Error）：程序员犯了C++语言文法上的错误。
例如
  1. int main {}
复制代码
就是有语法错误的语句段，这里的main函数没有参数列表，是非法的。
类型错误（Type Error）：向不对应的类型使用不对应的操作。
例如
  1. int a = "wow";
复制代码
就是有类型错误的语句段，这里的a变量是int类型的，但我们却尝试将字符串"wow"的值赋给它。
声明错误（Declaration Error）：使用未声明的对象或者错误地声明。
例如
  1. #include <iostream>
  2. int main() {
  3.     cout << "Declaration Error!" << endl;
  4.     return 0;
  5. }
复制代码
就是有声明错误的程序，这里的cout在std这个namespace里声明，而我们并没有用std::调用它或者using namespace std;。

1.4.4 if语句
不多说。
  1. if(condition) ...
复制代码
if语句是当条件为真的时候才执行语句的控制流。

判断运算符
运算符名称作用
==相等运算符判断两个对象的值是否相等
>大于运算符判断值大小
>=大于等于运算符判断值大小
<小于运算符判断值大小
<=小于等于运算符判断值大小
!=不相等运算符判断值是否不相等
判断运算符返回的是一个判断结果（true/false），不要把它们跟赋值运算符搞混了哦。
作者: zuimc    时间: 2014-12-3 13:24
KSkun 发表于 2014-12-3 13:00
Day 3.2 《C++ Primer》 第1章

1.4.3 读取数量不定的输入数据

还是PHP爽... 变量随便用
作者: KSkun    时间: 2014-12-3 19:03
zuimc 发表于 2014-12-3 13:24
还是PHP爽... 变量随便用

233333“PHP是世界上最好用的语言”
作者: KSkun    时间: 2014-12-4 21:45
停更大概4天，学业缘故
作者: lovemc    时间: 2014-12-20 07:40
大触　我已瞎了，表示比小白还要小白啊ＱＡＱ
作者: KSkun    时间: 2015-1-24 21:38
对于长时间停更这里深感抱歉，但是由于学业、项目等缘故短时间内不能续更，预计寒假开始不定期更新，敬请期待。



欢迎光临 最MC论坛 (http://www.zuimc.com/) Powered by Discuz! X3.2