TheBadZhang's Blog - 编程
type: channel
link: http://tbz.io/index.php/tag/%E7%BC%96%E7%A8%8B/
items: 凸包（Convex Hull）
items: 《51 单片机快速入门》读书笔记
items: 【转载】CppTemplateTutorial
items: std::tuple
items: 《C++ Primer》5th 读书笔记
items: OJ 需备算法
items: OJ 常用函数【C++】
items: OJ 常用函数【C】
items: 【leetcode-292】Nim 游戏——博弈论初步

凸包（Convex Hull）
type: item
date: 2021-04-21T12:09:53+00:00

《51 单片机快速入门》读书笔记
type: item
date: 2021-02-03T13:43:00+00:00
description: 51 单片机快速入门 [TOC] keil uVision5 第一步，点亮你的 LED 电源 晶振 复位电路 特殊功能寄存器 程序下载 第二步，硬件基础（Base）知识 电磁干扰 三极管 三八译码器 流水灯 定时器与数码管 中断与数码管动态显示 矩阵 LED 按键 步进电机与蜂鸣器 实例练习 UART串口通信 1602 液晶 1602 与 串口 i2c和e2prom ds1302 红外通信 模数转换和数模转换 RS-485 与 modbus协议 多功能电子钟 单片机开发常用工具 万用表 示波器 逻辑分析仪

【转载】CppTemplateTutorial
type: item
date: 2021-02-03T13:39:00+00:00
description: C++ Template 进阶指南 [TOC] 0. 前言 0.1 C++另类简介：比你用的复杂，但比你想的简单 C++似乎从它为世人所知的那天开始便成为天然的话题性编程语言。在它在周围有着形形色色的赞美与贬低之词。当我在微博上透露欲写此文的意愿时，也收到了很多褒贬不一的评论。作为一门语言，能拥有这么多使用并恨着它、使用并畏惧它的用户，也算是语言丛林里的奇观了。 C++之所以变成一门层次丰富、结构多变、语法繁冗的语言，是有着多层次的原因的。Bjarne在《The Design and Evolution of C++》一书中，详细的解释了C++为什么会变成如今（C++98/03）的模样。这本书也是我和陈梓瀚一直对各位已经入门的新手强烈推荐的一本书。通过它你多少可以明白，C++的诸多语法要素之所以变成如今的模样，实属迫不得已。 模板作为C++中最有特色的语言特性，它堪称玄学的语法和语义，理所应当的成为初学者的梦魇。甚至很多工作多年的人也对C++的模板部分保有充分的敬畏。在多数的编码标准中，Template俨然和多重继承一样，成为了一般程序员（非程序库撰写者）的禁区。甚至运用模板较多的Boost，也成为了“众矢之的”。 但是实际上C++模板远没有想象的那么复杂。我们只需要换一个视角：在C++03的时候，模板本身就可以独立成为一门“语言”。它有“值”，有“函数”，有“表达式”和“语句”。除了语法比较蹩脚外，它既没有指针也没有数组，更没有C++里面复杂的继承和多态。可以说，它要比C语言要简单的多。如果我们把模板当做是一门语言来学习，那只需要花费学习OO零头的时间即可掌握。按照这样的思路，可以说在各种模板书籍中出现的多数技巧，都可以被轻松理解。 简单回顾一下模板的历史。87年的时候，泛型（Generic Programming）便被纳入了C++的考虑范畴，并直接导致了后来模板语法的产生。可以说模板语法一开始就是为了在C++中提供泛型机制。92年的时候，Alexander Stepanov开始研究利用模板语法制作程序库，后来这一程序库发展成STL，并在93年被接纳入标准中。 此时不少人以为STL已经是C++模板的集大成之作，C++模板技止于此。但是在95年的《C++ Report》上，John Barton和Lee Nackman提出了一个矩阵乘法的模板示例。可以说元编程在那个时候开始被很多人所关注。自此篇文章发表之后，很多大牛都开始对模板产生了浓厚的兴趣。其中对元编程技法贡献最大的当属Alexandrescu的《Modern C++ Design》及模板程序库Loki。这一2001年发表的图书间接地导致了模板元编程库的出现。书中所使用的Typelist等泛型组件，和Policy等设计方法令人耳目一新。但是因为全书用的是近乎Geek的手法来构造一切设施，因此使得此书阅读起来略有难度。 2002年出版的另一本书《C++ Templates》，可以说是在Template方面的集大成之作。它详细阐述了模板的语法、提供了和模板有关的语言细节信息，举了很多有代表性例子。但是对于模板新手来说，这本书细节如此丰富，让他们随随便便就打了退堂鼓缴械投降。 本文的写作初衷，就是通过“编程语言”的视角，介绍一个简单、清晰的“模板语言”。我会尽可能地将模板的诸多要素连串起来，用一些简单的例子帮助读者学习这门“语言”，让读者在编写、阅读模板代码的时候，能像 if(exp) { dosomething(); }一样的信手拈来，让“模板元编程”技术成为读者牢固掌握、可举一反三的有用技能。 0.2 适宜读者群 因为本文并不是用于C++入门，例子中也多少会牵涉一些其它知识，因此如果读者能够具备以下条件，会读起来更加轻松： 熟悉C++的基本语法； 使用过STL； 熟悉一些常用的算法，以及递归等程序设计方法。 此外，尽管第一章会介绍一些Template的基本语法，但是还是会略显单薄。因此也希望读者能对C++ Template最基本语法形式有所了解和掌握；如果会编写基本的模板函数和模板类那就更好了。 诚如上节所述，本文并不是《C++ Templates》的简单重复，与《Modern C++ Design》交叠更少。从知识结构上，我建议大家可以先读本文，再阅读《C++ Templates》获取更丰富的语法与实现细节，以更进一步；《Modern C++ Design》除了元编程之外，还有很多的泛型编程示例，原则上泛型编程的部分与我所述的内容交叉不大，读者在读完1-3章了解模板的基本规则之后便可阅读《MCD》的相应章节；元编程部分（如Typelist）建议在阅读完本文之后再行阅读，或许会更易理解。 0.3 版权 本文是随写随即同步到Github上，因此在行文中难免会遗漏引用（ref）…

std::tuple
type: item
date: 2021-02-03T09:14:00+00:00
description: tuple 模板是 pair 模板的泛化，但允许定义 tuple 模板的实例，可以封装不同类型的任意数量的对象，因此 tuple 实例可以有任意数量的模板类型参数（Parameter）。tuple 模板定义在 tuple 头文件中。 tuple 这个术语也适用于很多其他的场景，例如数据库，这里一个 tuple 就是由一些类型的不同数据项组成的，这和 tuple 的概念相似。tuple 对象有很多用途。当需要将多个对象当作一个对象传给函数时，tuple 类型是很有用的。 tuple 的操作 生成 tuple 对象的最简单方式是使用定义在 tuple 头文件中的辅助函数 make_tuple()。这个函数可以接受不同类型的任意个数的参数，返回的 tuple 的类型由参数的类型决定。例如： auto my_tuple = std::make_tuple ( Name{"Peter"，"Piper"}, 42, std::string{"914 626 7890"} ); my_tuple 对象是 tuple<Name，int，string> 类型，因为模板类型参数是由 make_tuple() 函数的参数推导出来的。如果提供给 make_tuple() 的第三个参数是一个字符串常量，my_tuple 的类型将是 tuple<Name,int,const*>，这和之前的不同。 tuple 对象的构造函数提供了可能会用到的每一种选择。例如： std::tuple<std::string, size_t> my_tl;//Default initialization std:: tuple<Name, std::string> my_t2 {Name {"Andy", "Capp"},std::string{“Programmer”}}; std::tuple<Name,std::string> copy_my_t2{my_t2}; // Copy constructor std::tuple<std::string, std::string> my_t3 {"this", "that"}; // Implicit conversion tuple 中的对象由默认构造函数用默认值初始化。为 my_t2 调用的构造函数将参数移到 tuple 的元素中。下一条语句会调用拷贝构造函数来生成 tuple，在最后一个构造函数调用中，将参数隐式转换为 string 类型并生成了一个 tuple 元素。 也可以用 pair 对象构造 tuple 对象，pair 可以是左值，也可以是右值。显然，tuple 只能有两个元素。下面有两个示例： auto the_pair = std::make_pair("these","those"); std::tuple<std::string, std::string> my_t4 {the_pair}; std::tuple<std::string, std::string> my_t5 {std::pair <std::string, std::string > { "this", "that"} }; 第二条语句从 the_pair 生成了一个 tuple，它是一个左值。the_pair 的成员变量 first 和 second 可以隐式转换为这个 tuple 中的元素的类型。最后一条语句从右值 pair 对象生成了一个 tuple。 可以用任何比较运算符来比较相同类型的 tuple 对象。tuple 对象中的元素是按照字典顺序比较的。例如： std::cout << std::boolalpha << (my_t4 < my_t5) << std::endl; tuple 对象中的元素是依次比较的，第一个不同的元素决定了比较结果。my_t4 的第一个元素小于 my_t5 的第一个元素，因此比较结果为 true。如果是相等比较，任何一对不相等的对应元素都会使比较结果为 false。 tuple 对象的成员函数 swap() 可以将它的元素和参数交换。参数的类型必须和 tuple 对象的类型一致。例如： my_t4.swap (my_t5); 通过调用成员函数 swap() 来交换 my_t4 和 my_t5 对应的元素。显然，tuple 中所有元素的类型都必须是可交换的，tuple 头文件中定义了一个全局的 swap() 函数，它能够以相同的方式交换两个 tuple 对象的元素。 因为 tuple 是 pair 的泛化，所以它的工作方式不同。pair 的对象个数是固定的，因此它们有成员名。tuple 中的对象数目是不固定的，所以访问它们的机制必须能够满足这种情况。函数模板 get() 可以返回 tuple 中的…

《C++ Primer》5th 读书笔记
type: item
date: 2021-01-29T14:13:00+00:00
description: 《C++ Primer》5th 读书笔记 虽然说是这本书的笔记，但是还是会引入一些书外面的概念和新版标准的部分内容 对于不属于这本书的特殊的地方我会额外加以标注 [TOC] 第 1 章 开始 C++ 超级基础（Base）， 可以看我之前写的关于c++的必知必会的文章 UB(Undefined-Behaviors) 未定义行为 char 是 signed char 还是 unsigned char 是未定义的 int 是大于等于 short 小于等于 long 的 流 流可以作为 condition，用于判断是否到了流末尾，当到达流末尾时为 false，所以我们经常可以看到如下的写法 int n; while (std::cin >> n) { // do somthing... } 此时调用了 std::cin 类的 >> 函数，往 n 中输入数据，返回的是 std::cin 类的 istream 对象，到达流末尾时（通常这个标记为 EOF(End-Of-File)），在windows上可通过 Ctrl-z 和 Ctrl-d 输入 EOF 符号，标志流结束。 >> 作为一个函数，同理 std::cout << "Hello World" << std::endl; 的 << 也是一个函数，但是你会发现，其中存在多次调用，因为 std::cout<< 的返回值是一个 ostream 对象，即 std::cout 本身，所以实现了上面这样子的连续调用，但实际上，这个操作可以像下面这样分解， std::cout << "Hello World"; std::cout << std::endl; 这两种写法是完全等价的，于是就引出了一个问题，线程安全，因为，这个操作可以被等价分成两份，所以它的操作是不原子的，就可能在别的线程中，被插入，造成输出顺序混乱，比如输出了 Hello World123123\n 但是你想要输出的是 Hello World\n123123 其中，上面的\n的是转义字符，让换行看起来更加明显。解决办法也是有的，使用原子锁，但是这个内容是在后面学习多线程时才会讲到的，所以这里不加以赘述。 字面量 字面量大致可以分为两种，一种是语言提供的字面量，一种是库提供的字面量 语言提供的字面量，例如（其实我也没有仔细研究过具体哪些属于哪些，反正把自己知道的都列出来了） // 指针字面量 nullptr; // 布尔字面量 true;false; // 整数字面量 auto a = 1; // int a auto b = 0x1; // int b auto c = 01; // int c // 二进制字面量在 c++14 中引入 auto d = 0b1; // int d auto e = 1u; // unsigned int e auto f = 1ll; // long long f auto uf= 1ull; // unsigned long long f auto g = 1l; // long g // 其实这些后缀大小写都是可以的，为了方便书写，这里都写小写 // 浮点数字面量 auto h = 1.0l; // long double h auto i = 1e-1; // double i auto j = 1.0f; // float j auto k = 1e-1f; // float k // 字符(串)字面量 auto l = "Hello"; // const char *l auto m = u"World"; // const char16_t *m auto n = U"你好"; // const char32_t *n auto o = u8"世界"; // const char8_t *o auto p = L'！'; // wchar_t p auto q = '!'; // char q 但实际上，部分字面量会根据自己的数据大小自动变更数据类型，如果数据超过了long所能承载的范围，就会自动变为 long long，类型都是所能承受的最小类型，当然，char和short不在此列； 用户自定义字面量 使用运算符重载的方式 auto operator"" end(something) { } 就可以弄一个 somethingend 的一个字面量，something 作为参数（Parameter）传入 函数，处理后返回 第 I 部分 C++ 基础 第 2 章 变量和基本类型 初始化与赋值 其实这个是老生常谈的问题了，因为总是有非常多的事情，在这个上面纠结 int a = 10; // mov DWORD PTR [rbp-4], 10 int b; // int d = a; // …

OJ 需备算法
type: item
date: 2020-05-20T12:52:34+00:00
description: OJ 必须要了解的算法（如果要和别人比时间的话） 1. 数据量巨大的时候 std::cin, std::cout TLE (超时) static bool speedUP = [](){std::ios::sync_with_stdio(false); cin.tie(nullptr); return true}(); // 静态变量先于 main 函数初始化，以实现直接调用 lambda 函数 // std::ios::sync_with_stdio (false); 用以关闭 同步功能，不写缓存，不 flush // cin.tie (nullptr); 用于绑定输入流，nullptr 为当前输入流 // 写了一个 lambda 函数并调用了 https://byvoid.com/zhs/blog/fast-readfile/ https://zhuanlan.zhihu.com/p/35652783 https://www.jianshu.com/p/fa8ad995d300 2. 快速整数平方根（牛顿迭代打表）（std::sqrt 的 4 倍） inline int mysqrt(int n) { static int table[256] = { 0, 16, 22, 27, 32, 35, 39, 42, 45, 48, 50, 53, 55, 57, 59, 61, 64, 65, 67, 69, 71, 73, 75, 76, 78, 80, 81, 83, 84, 86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 99, 101, 102, 103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145, 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157, 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168, 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178, 179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188, 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197, 198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206, 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215, 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223, 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231, 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238, 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246, 246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255 }; int xn; if (n >= 0x7FFEA810) return 0xB504; if (n >= 0x10000) { if (n >= 0x1000000) { if (n >= 0x10000000) { if (n >= 0x40000000) { xn = table[n>> 24] << 8; } else { xn = table[n>> 22] << 7; } } else { if (n>= 0x4000000) {…

OJ 常用函数【C++】
type: item
date: 2020-05-17T07:37:23+00:00

OJ 常用函数【C】
type: item
date: 2020-05-17T07:36:55+00:00

【leetcode-292】Nim 游戏——博弈论初步
type: item
date: 2020-05-16T15:45:00+00:00
description: 【leetcode-292】Nim 游戏——博弈论初步 Nim 游戏 看到这标题，我还是觉得有趣的，因为 Nim 是一门十岁半的语言，满有趣的 但是我看到题目我还是很奇怪的，看上去好像很简单诶，做起来感觉又很奇怪，然后翻了评论，看到了这么一个博弈论的东西 CPP class Solution { public: bool canWinNim(int n) { return n%4>0; } }; C bool canWinNim(int n){ return n%4>0; } Lua function canWinNim (n) return n%4>0 end 巴什博奕 巴什博奕： 两个顶尖聪明的人在玩游戏，有n 个石子，每人可以随便拿1−m 个石子，不能拿的人为败者，问谁会胜利 巴什博奕是博弈论问题中基础（Base）的问题 它是最简单的一种情形对应一种状态的博弈 回到顶部 博弈分析 我们从最简单的情景开始分析 当石子有1−m 个时，毫无疑问，先手必胜 当石子有m+1 个时，先手无论拿几个，后手都可以拿干净，先手必败 当石子有m+2−2m 时，先手可以拿走几个，剩下m+1 个，先手必胜 我们不难发现，面临m+1 个石子的人一定失败。 这样的话两个人的最优策略一定是通过拿走石子，使得对方拿石子时还有m+1 个 我们考虑往一般情况推广 设当前的石子数为n=k∗(m+1)+r 先手会首先拿走r 个，接下来假设后手拿走x 个，先手会拿走m+1−x 个，这样博弈下去后手最终一定失败 设当前的石子数为n=k∗(m+1) 假设先手拿x 个，后手一定会拿m+1−x 个，这样下去先手一定失败 巴什博奕 (Bash Game) 首先我们来玩一个比较古老的报数游戏。A 和 B 一起报数，每个人每次最少报一个，最多报 4 个。轮流报数，看谁先报到 30. 如果不知道巴什博弈的可能会觉得这个是个有运气成分的问题，但是如果知道的人一定知道怎样一定可以赢。 我们先看下一个一眼就能看出答案的例子 比如说我们报到 5 (4+1), 每次报最多报 4 个，最少报 1 个。那么是不是后者一定可以赢呢？答案是肯定的。好了到这巴什博弈的精髓基本就 OK 了。 那么如果我们要报到 n+1, 每次最多报 n 个，最少报 1 个的话，后者一定能够赢。 现在我们需要报数到 n, 而每次最多报数 m 个，最少报数 1 个。我们可以化成这样 n = k*(1+m)+r (0 <= r <= m）这样的话如果 r 不等于 0 那么先手一定会赢，为什么呢？首先先手报 r 个，那么剩下 k 倍 (1+m) 个数，那么我们每次报数 1+m-k (B) 个数就一定能保证最后剩下 1+m 个，那么就到了上面我们说的那个了，先手就一定会赢，如果 r=0 那么后手一定会赢，道理一样的。 (r 为任意自然数，s≤m), 即 n%(m+1) != 0, 则先取者肯定获胜 代码： import java.util.Scanner; /** Created by YYL on 2017/2/24. */ //先报数到n者胜，每次最少报m1,最大报m2，且1<=m1<m2<n; public class BashGame { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m1=scanner.nextInt(); int m2=scanner.nextInt(); if(m1<1||m2>=n); else { if(n%(m1+m2)!=0) System.out.println("第一个人获胜"); else System.out.println("第二个人获胜"); } } } 运行结果： 30 2 6 第一个人获胜 其他实例： 大学英语四级考试就要来临了， Kiki 和 Cici 在紧张的复习之余喜欢打牌放松。“升级”？“斗地主”？那多俗啊！作为计算机学院的学生，Kiki 和 Cici 打牌的时候可没忘记专业，她们打牌的规则是这样的： 1、 总共 n 张牌； 2、 双方轮流抓牌； 3、 每人每次抓牌的个数只能是 2 的幂次（即：1，2，4，8，16…） 4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者； 假设 Kiki 和 Cici 都是足够聪明并且每次都是 Kiki 先抓牌，请问谁能赢呢？ Input 输入数据包含多个测试用例，每个测试用例占一行，包含一个整数 n（1<=n<=1000）。 Output 若 Kiki 能赢的话输出 “Kiki”，否则输出 “Cici”，每个实例的输出占一行。 Sample Input …