标签 编程 下的文章

《C++ Primer》5th 读书笔记

虽然说是这本书的笔记,但是还是会引入一些书外面的概念和新版标准的部分内容
对于不属于这本书的特殊的地方我会额外加以标注
[TOC]

第 1 章 开始

C++ 超级基础,

可以看我之前写的关于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 作为参数传入 函数,处理后返回

第 I 部分 C++ 基础

第 2 章 变量和基本类型

初始化与赋值

其实这个是老生常谈的问题了,因为总是有非常多的事情,在这个上面纠结

int a = 10;  // mov     DWORD PTR [rbp-4], 10
int b;       // 
int d = a;   // mov     eax, DWORD PTR [rbp-4]
             // mov     DWORD PTR [rbp-8], eax
int c = b;   // mov     eax, DWORD PTR [rbp-12]
             // mov     DWORD PTR [rbp-16], eax
b = 10;      // mov     DWORD PTR [rbp-12], 10

左侧为 c++ 代码,右侧为生成的汇编。这就很神奇了,你发现第二行定义变量 b 的时候,没有生成任何代码。在你尝试书写

int a = 10; // mov     DWORD PTR [rbp-4], 10
int b;      // 
b = 10;     // mov     DWORD PTR [rbp-12], 10

如上的代码的时候,生成的汇编也只有两行,就算你开 -O0 也一样,因为这个定义的语句,的确,什么事情也没有干,只是告诉编译器,「这个位置我占掉了,虽然里面的东西我没有明确给它,但是我占了,你得让接下来的变量都往后挪挪,而且不能说我不在」的这种状态。

类型、限定符、修饰符

int, char, short, long, long long, float, double, long double 等被称为基础数据类型,一切的一切基于此而产生

分析一个变量的具体类型,应该从右王座看,看到 & 就是引用类型,看到 [] 就是数组类型,看到 *就是指针类型,然后看 顶层const还是底层const

人们喜欢讨论 * 这个字符用于限定变量的时候的位置,就会产生下面三种结果

int *p1;  // *p1 的类型为 int
int * p1; // 两边各退一步
int* p1;  // p1 的类型为 int*

我个人倾向于使用 int* 的方式,将其作为一整个类型,因为 c++ 的类型系统过于复杂,比如

int x = 20;
int* px = &x;
decltype(x) px2 = px;

如果说是 *p 的类型为 type 的话,应当如何解释 decltype(x) 所推断出来的类型?所以,我倾向于使用 type* nameauto px3 = px;也是如此,如果不是类型,何来「类型推断」?
同理,引用类型也是这样

// 指针
type* name1;
// 引用
(type*)& name2 = name1;
// 上面这个是对于指针类型的引用,引用必须要初始化

下面讲讲关于 const 和 constexpr

在此之前,真正的 constant 实际上是使用 #define 来定义的,但是 c++11 出现了 constexpr,终于可以用正经的方式定义一个真正的 constant 了。
constexpr 要求变量或者表达式的值能够在编译器得到计算,于是乎,用 constexpr 修饰的变量,是一个定值
const 所代表的是,不变量,与变量相对,只是在使用的过程中不会发生变化,但不代表它是一个固定的值

int a;
std::cin >> a;
const int b = a;

合法么,合法,但是 b 的值会随着我们的输入而发生变化,但是在接下来试图改变b的值,都会造成编译器错误。
但其实也不一定的,虽然说不能直接通过b修改b所对应的对象值,但是我们可以通过间接的方式,访问到b,并修改,而且不会引发编译器错误。
这个我们可以拿 nim 中类似的语句进行对比

const str = "Hello World"
# Mutable variables
var c: int
c = 20
# Immutable variables
let e = c

nim 中
const 是常量,var 是变量,let 是不可变量
c++ 中
constexpr 是常量,没有限定符的各种类型 是变量,const 是不可变量
这样一比其实也不难发现 c++ 在发展上的滞后性了

const int i = 20;
// 不能修改的 int 类型变量(不变量也是不会变的变量)
const int* const pi = &i;
// 首先,a 是 const,a 本身的值不能改动
// 其次,是 const int* 类型,代表是 cosnt int 类型的指针
// 说明 a 所指向的对象是 int 且不能修改
const int*& const rpi = pi;
// 一个 const int* 类型的引用,且本身也不能修改,(虽然说引用本来就不能改,不知道加上有没有

我们再加上一个数组类型,数组类型就非常有趣了,因为其中的矛盾点实在太多了,比如可以弱化成指针,这一点就很折磨人,所以和别人解释,但是这个内容再在下一章解释

自动类型推断

auto
decltype(statment)
decltype(auto)     //c++17 引进

自定义数据结构,使用 struct 将各种数据归为一类,
但是好像没有看到 union 这个数据结构在这本书中被介绍
虽然说用的少,但其实,还是很有用的,比如用作动态类型的数据结构

第 3 章 字符串、向量和数组

其实这一章前面部分没有什么特别重要的事情,只不过介绍了 std::string 和 std::vector 两个标准库「容器」
我想这个内容可能看 C++ 标准库 可能更加适合一些
但有一点可以注意的就是

std::vector<std::string> a(10, "20");
std::vector<std::string> b{10, "20"};

的效果是一样的

迭代器

std::string::itrator;
std::vector<int>::itrator;

数组

int a[10];
using int10 = int[10];
int10 b;

第 4 章 表达式

提升,转换,重载,左右值

赋值,取址,解引用和下标……
都必须要使用左值,

decltype 对左值,取到的是一个引用,但对于右值,取到的是本来的类型
这个在之前的例子中有出现过

int i = 10;
int* pi = &i;
decltype (*pi) d = i;  // 实际上这是 int& 类型
decltype (pi) e = pi;  // 这个是 int* 类型
sizeof int
sizeof (1+1)
int a = f1() + f2();

像上面这两个函数返回值相加,但是你没有办法知道先执行的是哪一个函数,这个是不确定的,一定程度上也是线程不安全的

T operator+(const T &a, const T2 &b);

同理,因为加号会图上面这样子重载,对于某一个类型的重载,你也可以把int类型的+重载成*,这个以后再讲。f1和f2就成为了 operator+ 的两个参数,这样同样表明,函数作为函数参数时,其运行顺序也是不确定的

取余的运算比较复杂,日后重新罗列

第 5 章 语句

if

if-else

for

for

while

do-while

switch

break

continue

goto

throw

try

catch

第 6 章 函数

const 的故事到这里,才算真正地开始……

整个 c++11 就是一个类型斗争史,auto,decltype,template,using,透露出两个字,类型,类型,还是类型,函数重载、尾置返回、左值引用、右值引用也涉及到类型推断,
尾置返回类型

auto func (int i) -> int(*)[10];

函数参数中的顶层 const 会被忽略掉

void func (const int i);
void func (int i);

上面两个声明其实都是一个函数,会报错

void print (const int* i);
void print (const int i[]);
void print (const int i[10]);

上面三种声明,也是一样的,所以,在作为函数参数的时候,数组会弱化为指针

const int& i = 41;
void func (int& ar[]);   // 引用的数组
void func (int (&ar)[]); // 数组的引用

函数返回数组指针

int (*function(void))[10];  // 一个返回指向 int[10] 的指针的函数
// 使用尾置返回
auto function(void) -> int(*)[10];
using pi10 = int(*)[10];
pi10 function (void);

函数返回函数指针

int (*function (void)) (int*, int);
auto function(void) -> int(*)(int*,int);
using ifpii = int(*)(int*, int);
ifpii function (void);

关于如何向数组传入长度参数,其实还有别的小妙招

template <typename T>
void func (int& ar[T]) {

}
type (*function(parameters))[dimension] {

}

可以定义一个返回 数组的指针 的函数

折叠表达式(C++17 起)

template<typename... Args>
bool all(Args... args) { return (... && args); }
template<typename... Args>
bool any(Args... args) { return (... || args); }
template<typename... Args>
bool sum(Args... args) { return (... +  args); }

bool b = all(true, true, true, false);
 // 在 all() 中,一元左折叠展开成
 //  return ((true && true) && true) && false;
 // b 为 false
// 将一元折叠用于零长包展开时,仅允许下列运算符:

// 1) 逻辑与(&&)。空包的值为 true
// 2) 逻辑或(||)。空包的值为 false
// 3) 逗号运算符(,)。空包的值为 void()
// 注解
// 若用作 初值 或 形参包 的表达式在顶层具有优先级低于转型的运算符,则它可以加括号:

template<typename ...Args>
int sum(Args&&... args) {
//    return (args + ... + 1 * 2); // 错误:优先级低于转型的运算符
    return (args + ... + (1 * 2)); // OK
}

函数重载匹配其实也是一个很复杂的问题,
但是拒绝认识它也是可以的,就是不要写出具有歧义的重载函数

第 7 章 类

访问控制
public private protect
友元
friend
类成员
作用域和名字查找
构造函数初始化列表
委托构造函数
默认构造函数
=default =delete
隐式类类型转换
explicit

第 II 部分 C++ 标准库

第 8 章 IO 库

头文件类型描述
iostreamistream, wistream从流读入数据
ostream, wostream向流写入数据
iostream, wiostream读写流
fstreamifstream, wifstream从文件流读入数据
ofstream, wofstream向文件流写入数据
fstream, wfstream文件读写流
sstreamistringstream, wistringstream从 string 读入数据
ostringstream, wostringstream向 string 写入数据
stringstream, wstringstream读写 string

c++ 定义了上面这些流操作的类型,提供了最基础的流抽象功能,其他功能也可以基于此进行更深的抽象

但是,C++ 的流可能是一个非常失败的设计,因为输入输出的符号大家都不是很喜欢,而且在前期缺少合适的文本格式化工具,直到 c++20 引入了 format 库,才有所改观,但实际上现在没有任何一家的编译器是支持 format 库的再者是自带的 STL 库都没有提供对于标准化输入输出流的支持,只能自己手动输入输出。

但是我们也可以通过这个设计实现一个统一的输入输出操作

可以通过若干种标志判断当前流的状态处于失败、结尾、正常或者是异常
也可以通过对应的函数设置当前的状态

unitbuf, nounitbuf, flush, endl
立即刷新,不立即刷新,强制刷新,强制刷新并换行

我们可以使用 fstream 完成对文件流的读写操作,其具体操作与输入输出流并没有特别多的区别,唯一的是需要指明文件的路径和打开方式

需要注意的是,文件的写操作默认是附带 std::ios::trunc 的,这个意味着打开一个文件的时候,如果原先存在文件,则会将原先的文件删除

使用 stringstream 则可以对流进行细分,在实际使用中出现频率还是很高的

第 9 章 顺序容器

顺序容器主要有

类型介绍
vector动态数组,即长度可变,支持快速随机访问,数据连续存储,所以插入数据可能很慢
deque双向队列,长度可变,支持快速随机访问,头尾插入删除很快,数据连续存储的同时分块存储
list双向链表,长度可变,随机访问并不快速,任意一个元素的插入删除都很快,就链表的存储方式
forward_list单向链表,长度可变,随机访问也不快速,但是相比双向链表少了一个方向,所以在插入和删除时比自己手写的链表快不了多少
array静态数组,长度不可变,可以看作是原生数组的高级版本
string和vector类似,但是专门用于保存字符,同时提供大量字符串处理相关的函数
queue单向队列,由双向队列继承而来
priority_queue
stack栈,由双向队列继承而来

其实这里有一个很巧妙的点,为什么说是快速随机访问呢,确实,链表因为数据结构的问题,其实不支持随机访问,但是可以通过遍历的方式,实现一个非常慢速的随机访问,但也其实,可以通过一个vector存储链表的迭代器,再对vector随机访问,就可以实现对链表的随机访问了,这个适用于大规模的对于链表的随机访问

同时,这些容器库之所以要叫容器库,是因为它们提供了对任意类型的「容」,这个得益于 c++ 复杂的模板,在编译器对各种类型进行展开,同时,由于模板的存在,很多本来看上去很正常的名字,就变得极为不正常了,这也导致使用了模板的报错变得异常难读,学会从模板报错中找到正确的错误,也是一个非常重要的技巧

这些容器库,STL,都包含着若干统一的操作函数,但这里就不一一列举了,这不应该成为学习 c++ 的负担。诸如比较,构造,复制,交换,添加删除,以及各类迭代器(c++11 引入了一种新的反迭代器,还有各种容器的构造,赋值,交换,追加,插入,删除,移动,拷贝,这里也不加以细说。

往容器中添加元素又变得非常有复杂,但也没有那么复杂
push_back, push_front, emplace_back, emplace_front, insert,其中 emplace 系列函数于 c++11 引入,究其原因还是因为 c++11 带来的右值引用,push 系列函数在插入一个值的时候,会先对值进行拷贝,但是 emplcae 函数借用右值引用直接将值写入对应位置,减少了一次拷贝,一定程度上提升了性能(右值引用牛逼!)
https://zhuanlan.zhihu.com/p/213853588
pop_back, pop_front, erase 用于删除元素
各个迭代器的使用,forward_list独树一帜的特殊操作

对于容器的插入删除可能导致迭代器失效,因为移动了容器中实际内容的位置,vector在内容将要填满预先分配的空间时,会将当前空间扩大为两倍,使用capacity可以查看已分配的空间,size查看已使用的空间

对字符串的各种操作函数在这里也不加以赘述了,实际上字符串库应当搭配c++11引入的regex正则匹配库和c++20引入的format格式化库使用更加顺手,正则匹配是一个好东西,就是看起来效率非常差,但也没有那么差了

第 10 章 泛型算法

泛型,何为泛型,即通用的,对于任何类型都可以使用,类型无关
这些泛型函数主要通过迭代器和传入的函数进行使用
其中大多数函数定义在 algorithm 算法库中,c++11 提供了超过一百种的内置算法,为开发提供了非常有用的帮助,尤其是 sort 函数我使用的次数不可谓不多
find, find_if...
(我会在将来的某天详细地介标准库的内容,但不会是在这本书上
泛型算法主要分为只读算法,写算法和排序算法
查找算法,判断算法等算法为只读算法
写算法,插入算法(使用插入迭代器),拷贝算法(利用迭代器),
排序算法,sort不稳定排序,stable_sort稳定排序,性能上各有千秋

之后,这本书在这个地方介绍了一个非常重量的 c++11 更新,lambda 函数,同时,这也更一步的让c++拥有了函数式编程的风范,一个较为简单的方式声明并使用一个函数,其中的详细内容我会另开一个文章进行介绍,但书中没有在这里引入function函数用来存储lambda函数我感觉还是有些欠妥当,不过也介绍了bind函数关于绑定函数参数的内容,同时介绍了find_if 函数和for_each 函数。值捕获,引用捕获,隐式捕获,等等等等,设置返回值,自动推断返回值,这里甚至还产生了闭包,但是在这本书里貌似没有介绍到。在lua中,闭包是一个非常重要的概念,而且在介绍lua的书中大书特书了

这里详细介绍了插入迭代器和反迭代器

第 11 章 关联容器

1)set or map 2)可否重复 3)有无顺序
因此产生了八种不同的数据类型,分别是:set map multiset multimap unordered_map unordered_set unordered_multimap unordered_multiset

因为map存储了两个信息,这里还引入了一个新的对象 pair,用于构成一对的数据结构,分别存储 map的key和value。关联容器同样拥有普通容器的大部分操作。之所以叫做关联,是因为key之间是相互影响的。比如在map和set中,是不允许出现相同的key的,这叫关联。

关联容器可以使用任意类型当作key和value,总之非常有用,但是具体的操作并不在这里赘述。一个非常有用的地方,就是统计单词的数量和有多少种单词,map的key为单数,value为数量,即可进行统计。set的key为单词,即可统计单词的种类,因为set在数学上与集合的含义相类似,所以在这里其实对于set还有非常多的集合操作,这本书上也没有讲。
然后我也没什么好讲的了,毕竟关于标准库的介绍不应该成为负担

第 12 章 动态内存

从程序支持手动申请内存开始,人类就陷入了无限的与指针的抗争之中。人们为了正确处理这些内存,掉了数不清的头发。所有分配的对象,需要一个能够指向它们的指针才能调用。手动分配的对象不受作用域或者生命周期影响。但是用来存储这个指针的对象,存在作用域和生命周期,当语句块结束后,这个指针变量则会消失,也许指针变成返回值传到另一个变量之中,也许没有。如果没有的话,那么这个内存中的对象就彻底变得无主了,于是这个内存中的对象就无法已正常地形式进行清除了。

这就形成了垃圾,于是我们引入了垃圾回收的概念,这个在相当多的语言中都有直接的体会,但是,这么方便为什么c++不用呢?因为垃圾回收,浪费空间,也浪费性能,所以这个功能不会在c++中提供,诸如python和lua,会对一些垃圾自动「标记-清理」。如果尝试写python,循环地进行一些事项,你有可能发现自己的内存占用,忽高忽低,这个就是python垃圾回收的效果了。

智能指针

但是c++难道没有办法高效地实现垃圾回收了么?当然是有的。答案就是使用智能指针,智能指针是在C++11中引入的。既然问题出现在指针上,那么解决这个指针,那么所有的问题就迎刃而解了。借助 c++ 类所带来的 RAII 功能,我们可以轻松实现,创建时如何,销毁时如何的功能。这也为智能指针的出现,奠定了基础。

智能指针分为三类
shared_ptr
unique_ptr
weak_ptr

其中,shared_ptr可以被赋值,拷贝,即可以存在多份,每次赋值拷贝会调用对应的构造函数,返回这样一个指针也会产生拷贝。每一次执行上述的操作时,其内部的计数器,会让自己的值增加一,只要内部计数器的值达到零,就会自动销毁内存中的对象。当然,这个时候,智能指针对象也肯定不会存在的。其中,weak_ptr是不会增长这个计数器,但是,当目标对象被销毁后,使用 weak_ptr 又成了一个未定义行为。unique_ptr不允许拷贝、赋值等操作,只能单一存在

std::shared_ptr<std::string> sps(new std::string);
std::shared_ptr<std::string> sps2(sps);
std::shared_ptr<int> spi(new int[100])
std::unique_ptr<std::string> ups(new std::string)

手动分配、管理内存

使用 new 和 delete 关键字,即可完成对象的申请和销毁。但是这里有一个小小的问题,与我们之前所讲的东西有所不同的是,new 所返回的并不是如我们所想的 数组的指针,它直接返回的只是一个指针,我们在这个过程失去了数组的大小,而且你甚至不能判断它就是数组。

int* i = new int;     // 创建一个 int 对象
int* is= new int[10]; // 创建一个 int[10] 对象
delete i;             // 销毁一个 int 对象
delete [] is;         // 销毁一个 int[10] 对象

int* pi = new int[0]; // 创建一个空对象
// 实际上这句话什么事情也没有做,pi 所指向的值是未定义的

先分配内存空间,再进行初始化赋值

std::allocator

如果之前已经尝试过大量代码的同学,可能早就发现在使用STL的过程中,有一些报错的模板展开后,就有std::allocator类,

第 III 部分 类设计者的工具

第 13 章 拷贝控制

拷贝构造函数

Foo ();          // 默认构造函数
Foo (const Foo&) // 拷贝构造函数

合成拷贝构造函数,即默认的拷贝构造函数,会将源对象的所有内容拷贝到目标对象

std::string dots(10, '.');  // 直接初始化
std::string s(dots);        // 直接初始化
std::string s2 = dots;      // 拷贝初始化
std::string null_book = "9" // 拷贝初始化
std::string nines = std::string(100, '9')
// 拷贝初始化

拷贝赋值函数

Foo& operator= (const Foo&); // 拷贝赋值

同样的,拷贝复制也有合成拷贝赋值运算

移动构造函数

移动赋值运算符

析构函数

析构函数作为一种在对象生命周期结束的时候调用的一个函数,等同于给对象擦屁股的作用。于是,C++也提供了 RAII 等一系列功能。

生命周期如何结束:变量离开作用域,父级对象被销毁,容器被销毁,delete主动销毁,临时变量创建完整的表达式之后

C++ 三/五法则

当定义一个类时,我们显式地或隐式地指定了此类型的对象在拷贝、赋值和销毁时做什么。一个类通过定义三种特殊的成员函数来控制这些操作:拷贝构造函数、拷贝赋值运算符和析构函数。

拷贝构造函数定义了当用同类型的另一个对象初始化新对象时做什么,拷贝赋值运算符定义了将一个对象赋予同类型的另一个对象时做什么,析构函数定义了此类型的对象销毁时做什么。我们将这些操作称为拷贝控制操作。

  由于拷贝控制操作是由三个特殊的成员函数来完成的,所以我们称此为“C++三法则”。在较新的 C++11 标准中,为了支持移动语义,
  又增加了移动构造函数和移动赋值运算符,这样共有五个特殊的成员函数,所以又称为“C++五法则”。
  也就是说,“三法则”是针对较旧的 C++89 标准说的,“五法则”是针对较新的 C++11 标准说的。
  为了统一称呼,后来人们把它叫做“C++ 三/五法则”。

“需要析构函数的类也需要拷贝和赋值操作”
  从“需要析构函数”可知,类中必然出现了指针类型的成员(否则不需要我们写析构函数,默认的析构函数就够了),所以,我们需要自己写析构函数来释放给指针所分配的内存来防止内存泄漏。
  那么为什么说“也需要拷贝构造函数和赋值操作”呢?原因是:类中出现了指针类型的成员,必须防止浅拷贝问题。所以需要自己书写拷贝构造函数和拷贝赋值运算符,而不能使用默认的拷贝构造函数和默认的拷贝赋值运算符。

“需要拷贝操作的类也需要赋值操作,反之亦然”

“析构函数不能是删除的成员”
  如果析构函数是删除的,那么无法销毁此类型的对象。对于一个删除了析构函数的类型,编译器不允许定义该类型的变量或创建该类的临时对象。而且,如果一个类有某个成员的类型删除了析构函数,我们也不能定义该类的变量或临时对象。

让编译器使用合成

class Foo {
public:
    Foo () = default;
    Foo (const Foo&) = default;
    Foo& operator= (const Foo&);
    ~Foo () = default;
};
Foo& Foo::operator= (const Foo&) = default;

阻止拷贝

如果要阻止拷贝,就把上面对应的default换成delete删除即可,但是delete必须出现在成员第一次声明的地方,即

class Foo {
public:
    Foo () = default;
    Foo (const Foo&) = default;
    Foo& operator= (const Foo&) = delete;
    ~Foo () = default;
};

其中,析构函数若被删除,我们就无法释放这些对象

如果一个类有数据成员不能默认构造、拷贝、复制或者销毁,则类对应的成员函数将被定义为删除。其原因是为了避免所创造的对象无法被销毁

但是这个功能是在c++11中引入的,在此之前,我们可以通过把对应的成员函数定义为private,外部的环境则无法访问对应的成员函数,实现了删除。声明但不定义是合法的,但是当使用这个函数时,会报链接错误,即找不到对应的函数定义,通过private声明,则可以阻止用户(我们)调用private函数,实现控制。

试着联系之前出现过的 std::unique_ptr 的禁止拷贝

尝试书写自己的资源管理类

值一样的类和指针一样的类,对应了之前的string类型和智能指针

动态内存管理类(std::allocator 续)

教你怎么实现 vector 类

申请一块内存区域,然后使用 allocator 复制内存区域到新申请的区域

对象移动和移动语义

为了避免在前面管理内存的时候,出现无意义的拷贝赋值,所以在c++11引入了右值引用,减少了对数据的拷贝,提升了效率

int i = 42;           
int& ri = i;             // 左值引用
int&& rri = i;           // 编译错误,左值不能绑定到右值引用上
int& ri2 = 42 * i;       // 编译错误,右值不能绑定到左值引用上
const int& cri = 42 * i; // 右值可以绑定到常量左值引用上
int&& rri2 = 42 * i;     // 右值引用

右值是临时的,而左值是永久的(在作用域内是永久的)
右值引用的好处是可以延长临时变量的生命周期。其基础上也实现了移动语言std::move和完美转发std::forward
能出现在等号左边的就是左值,右值只能出现在等号右边

使用移动操作时,要标明函数是不抛出异常的,否则会为此做一些额外的工作

class StrVec {
public:
    StrVec (StrVec&&) noexcept;
};
StrVec::StrVec (StrVec&& s) noexcept : {
    // ...
}

引用限定符

class Foo {
public:
    Foo& operator= (const Foo&) &;      // 只能向可修改的左值赋值
};
Foo& Foo::operator= (const Foo& rhs) &;

第 14 章 重载运算与类型转换

不可重载的运算符

大多数运算符都是可以重载的,但是有5个运算符C++语言规定是不可以重载的.

  1. .(点运算符),通常用于去对象的成员,但是->(箭头运算符),是可以重载的
  2. ::(域运算符),即类名+域运算符,取成员,不可以重载
  3. .*(点星运算符,)不可以重载,成员指针运算符".*,即成员是指针类型
  4. ?:(条件运算符),不可以重载
  5. sizeof,不可以重载

C++ 只允许使用原本存在的运算符,而不支持自定义运算符,但是如果实现了这个功能,c++ 马上又起飞了

c++11 还引入了用户自定义字面量,似乎这个功能并没有在这本书中得以体现

long double operator"" pi(long double x) {
    return x*3.14159265357;
}
long double operator"" pi(unsigned long long x) {
    return static_cast<long double>(x)*3.14159265357;
}

通过如上的代码我们可以实现自定义字面量,实现了xpi的数学写法,当然也可以给自然底数加上这样的功能

auto rad = 3pi;
auto rad2 = 4.0pi;

c++20 其实还引入了一个新的运算符<=>三向比较运算符,俗称,飞碟运算符,这个就是后话了,这里也不赘述

重载运算符的使用

之前在一个群里听到有人吐槽 std::string 没有重载与部分类型的 + 运算,然后我就丢给了他这样子的代码

std::string operator+ (std::string str, int x) {
    return str+std::to_string(x);
}
auto str = std::string ("H") + 123;  // "H123"

实现了 std::string 与 int 类型的直接相加
当然,上面相加的一行,也等价为

auto str = operator+ (std::string("H"), 123);
// 同理
auto i = operator+ (123, 321);
// 也是成立的,但是 operator 只能同时有两个参数,而且写起来也格外麻烦

要注意的是,尽量不要使重载后的运算符的含义偏经离义,那会让使用者困惑。

又往下看了一些,发现 std::string 并没有把 + 作为自己的成员函数,而是当成了普通的非成员函数,所以也实现了 const char + std::string 的功能,如果是成员函数的话,const char 是不能放在前面的

输入输出运算符也是如此,应当作为非成员函数存在才能正常使用,不然以
ostream.>>(Foo) 的调用形式,是不能正确实现期望的功能的

ostream& operator<< (ostream& os, T t) {
    // ...
}

运算符介绍

算术运算符
无非就是加减乘除余和各种二元运算符
逻辑运算符
逻辑运算符和算术运算符使用方法基本一致
赋值运算符
普通的赋值运算符没有什么特别的,但是复合赋值运算符就有一些不同了,只传入一个参数,其中,左侧的被赋值对象的 this 指针会被传入
下标运算符
通常是返回访问元素的引用为好,此时可以多重下标运算
递增递减运算符
这里又有点小不同了,递增递减分为前置和后置,但是运算符重载总是以 operatorOPR的形式存在的,应当如何区分前置和后置呢?

int& operator++ ();    // 前置
int& operator++ (int); // 后置

后置递增运算符中,虽然出现了一个额外的参数,但是这个参数是不应当被使用到的,编译器为默认往里面传入0。此行为只是为了区分前后置

显式调用递增运算符

Foo p;
p.operator++(0); // 后置
p.operator++();  // 前置

成员访问运算符
虽然我们不可以重载点成员访问运算符,但是我们可以重载箭头成员访问运算符
函数调用运算符
重载这个运算符,可以让我们的类对象表现得像函数一样

Foo foo;
foo(123); // 此处已然不是构造函数

类型转换运算符
书中把这个内容放在了 lambda 的下面,但是我把它提了上来,放在了一起。类型转换函数一般形式如下:

operator type() const;  // 显式类型转换运算符

我们再一次联系之前所学到的内容,explicit

explicit type() const;

只有当我们尝试使用显式类型转换时,才会调用这个函数

static_cast<type> a;

书看到这里,也差不多能够解决我的一个疑问了,我当初就想,为什么一个流对象在循环中可以被当作条件使用,现在发现因为有隐式类型转换运算符重载的出现,所以在条件中,流被转换成一个bool类型的值返回,使循环可以正常运行

记得避免二义性转换

lambda 表达式再续前缘

cppreference 上面写道:lambda 就是创建一个闭包并返回,但是可能闭包这个概念解释起来也是过于复杂,所以 C++ primer 真的也只是做了一个 primer,从而不介绍具体的编程范式,这个大概可以在别的书中看到具体的操作方式。当然,网上也有很多类似的教程
c++ 是一个多范式编程语言,虽然在 lambda 出现之前就已经实现了函数式编程的功能,但是,lambda 表达式的存在,第一次让书写函数变得如此简练,写函数写起来真的是非常的爽快

于是乎,c++ 标准库为了符合的上自己的多范式编程语言的称号,也在 functional 中定义了一系列的函数式范式的类,用于生成对应的函数对象提供进一步的操作

算术关系逻辑
plus<T>equal_to<T>`logical_and`
minus<T>not_equal_to<T>logical_or<T>
multiplies<T>greater<T>logical_not<T>
divides<T>greater_euql<T>
modulus<T>less<T>
negate<T>less_equal<T>

可调用对象与function

今天下午,巨佬刚好怼着 std::function 喷了一堆,但是我也看不懂,他反驳的是 c++ 标准库中存在的那些糟粕,嫌弃 std::function 的性能之差,说 noexcept swap allocator 等东西满天飞,到 2021 年还没有解决,自己写的 ystdex::function 直接性能上都能把 libstdc++ 摁在地上锤 除了实现难度比较大,而且吐槽了新议程中的试图把信号槽系统搬进标准c++的事情

当我们尝试做一个复杂的计算器时,会运用到非常多的计算功能,这些计算功能就是通过函数实现的,所以如何保存一个函数,就显得非常重要了,c++是一个静态语言,也不支持反射,所以不可能通过生成代码的方式生成一个函数,如果尝试诸如 lua、python 等语言的话,可以尝试一下这种方式
函数表

int add(int i, int j) { return i + j; }
auto mod = [] (int i, int j) -> int { return i + j; }
struct divide {
    int operator() (int denominator, int divisor) {
        return denominator / divisor;
    }
}
std::map<std::string, int(*)(int,int)> binops;
binops.insert ({"+", add});  // 将 add 函数和 + 绑定在一起

但是我们不能将 mod 和 divide 存入 binops,其中 lambda 有自己的类类型,与函数指针类型不匹配。解决办法是……std::function

std::function<int(int, int)> f1 = add;
std::function<int(int, int)> f2 = divide();
std::function<int(int, int)> f3 = [] (int i, int j) -> int { return i * j; };

但是,std::function 会面临重载函数二义性的问题,因为赋值的时候只提供了一个关于函数的名字,但是没有任何参数,编译器无法推断此时应当使用哪一个函数存入 std::function

第 15 章 面向对象程序设计

面向对象的介绍

这个地方其实我自己也不知道应当如何介绍,只能抄一点书上的内容了
P525-576

面向对象的核心是数据抽象、继承和动态绑定

基类派生类(也称为父类,子类)
派生类需要通过在类派生列表中明确指出它是从哪(些)个基类派生而得到的

虚函数使得派生类可以修改继承得到的那些标记为虚函数的函数,使之表现出不同的行为

动态绑定,运行时绑定,这个概念很奇怪,总之就是在代码运行的时候对不同的对象使用不同的成员函数

面向对象的使用

定义基类
virtual
override
定义派生类

阻止继承
final

虚函数

抽象基类:只含有纯虚函数的基类

访问控制

在之前第六章的时候我们讨论过一些访问控制,这里更加深入地去了解他们
public
protected
private
friend

其他类的操作

拷贝,赋值,移动,构造,析构……与先前的语法一致,但是可能会有一些不同

第 16 章 模板与泛型编程

定义一个模板

函数模板

template <typename T>
int compare (const T& v1, const T& v2) {
    return v1<v2?-1:v2<v1?1:0;
}

其实上面的代码实现了一个三相比较符,这个在c++20中以及被引入
我感觉如果接住了重载运算符的功能,就是用户自己添加运算符应当成为一个符合标准的事情才对

模板的特殊操作

template <unsigned N, unsigned M>
int compare (const char (&p1)[N], const char (&p2)[M]) {
    return strcmp (p1, p2);
}

往函数中传入了一个数组!!!
这都归功于模板的实例化,编译器在编译器就将数据的大小用我们看不到的方式传入了函数之中,让函数也直接得到了数组的大小

我们也可以使用 constexpr 对函数修饰要求能够在编译期返回一个常量结果

模板的保存总是又臭又长,因为其实例化展开的过程非常**,经常会让保存变得难以看懂,尤其是标准库那互相依赖一报上百个的报错

类模板

template <typename T>
class Foo {

};

类模板其实和函数模板没有太大的区别,但是类模板需要手动指定类型实现实例化。类模板也存在偏特化和全特化,对视直接在类中写入对于什么样的类型执行什么样的操作。
比如 vector 和 map 创建一个对象的时候

在类外使用类模板名

template <typename T>
Foo<T> Foo<T>::operator+ (T a, T b) {
    // ...
}

一对一友元类,
通用和特定友好关系

令模板中的类型为自己的友元

模板类型别名

using strFoo = Foo<std::string>;

static 成员
每一个实例化的类都有自己对应的静态成员

模板参数的作用域

使用类的类型成员
这里可以看看之前我们是如何声明容器的迭代器的,那样子我们对于模板类的类型成员也会有所感觉了

模板类的默认模板形参

template <class T = int>
class Foo {
    // ...
}

类成员函数模板
其实本质上和函数模板并无区别,无非就是身在类中

实例化与成员函数

实例化
控制实例化

extern template class Blob<string>;
template int compare (const int&, const int&);

运行时绑定删除器
编译时绑定删除器

模板类型实参推断

类型转换与类型模板参数

template <typename T1, typename T2, typename T3>
T1 sum (T2, T3);

auto val3 = sum<long long>(i, lng);
// long long sum (int, long)

尾置返回类型

标准库中的类型转换模板

函数指针和实参推断

模板实参推断和引用
主要是关于引用折叠和右值引用的参数相关的内容

理解 std::move
std::move 的定义

template <typename T>
typename remove_reference<T>::type&& move (T&& t) {
    return static_cast<typename remove_reference<T>::type&&> (t);
}
std::string s1("hi"), s2;
s2 = std::move (std::string ("HELLO"));
s2 = std::move (s1);

从一个左值 static_cast 到一个右值是允许的

转发 std::forward

重载与模板

可变参数模板

模板参数包,函数参数包
我们使用一个省略号表示一个包,但是这个省略号实际上是由三个句号构成的,不是中文的省略号
使用 sizeof... 可以获取包的长度

template <typename T, typename... Args>
void foo (const T &t, const Args&... rest);

编写可变参数函数模板
包扩展
c++11 中引入的包,使得解包可以较为方便地通过递归的方式实现

template <typename T, typename... Args>
ostream& print (ostream& os, const T& t, const Args&... rest) {
    os << t << ",";
    return print (os, rest...);
}

转发参数包

模板特例化

第 IV 部分 高级主题

第 17 章 标准库特殊设施

认识 std::tuple

tuple 类似于 pairs,但是与 pairs 想不不同的是,pairs 只能存有两个(一对)类型,但是 tuple 可以存储若干个类型,所以这个类,在很多情况下也被用作函数返回值(与 struct 非常相近是不是?)

再会 std::bitset

其实 bitset 类,在这本书的开头我们就已经看到过了,现在是郑重其事地介绍一遍

可以理解为二进制数组,类似于java的bitmap吧,可以用来存储而静止图像

一个无限长度的整数类,也有支持的对应的运算符

初遇正则表达式

正则表达式才是真正的大头,这个功能真的是非常非常有用

头文件 regex

组件们

名称介绍
regex表示正则表达式的类
regex_match进行正则匹配
regex_search寻找第一个与表达式匹配的子序列
regex_replace使用给定正则替换目标序列
sregex_iterator调用regex_match匹配string中的所有匹配子序列
smatch容器类,保存搜索结果
ssub_matchstring中匹配子表达式的结果

我们将在之后的时间里,详细地补充 regex 的使用方法,对于如何书写一个正则表达式,也会在届时详细补充

子表达式

随机数

在出现专门的随机数库之前,我们使用 cstdlib 提供的 rand 和 srand 生成随机数,但是 rand 返回的随机数结果是有范围,而且属于平均的随机,而且生成随机数的质量并不是很高,但是胜在速度足够快

随机数引擎

使用随机数引擎,我们甚至可以生成符合正态分布的随机数

再探 IO 库

我们讲了很多关于流的操作,但是我们没有将如何控制一个流。
但实际上,这个部分可以放弃了,在实际使用中,真的用的非常少,大家宁愿使用 printf, sprintf,也不会去使用 ostream 或者 stringstream 的格式化,因为真的是又臭又长,但是好处是处理效率很快,但是相比需要关心这个狗屁格式,显然是使用 c++20 引入的 format 库更加实用有效。

单字节操作
is.get, os.put, is.putback, is.unget, is.peek
多字节操作
is.get, is.getline, is.read, is.gcount, os.write, is.ignore

流随机访问
seek 和 tell 函数

第 18 章 用于大型程序的工具

异常处理

抛出异常

如何抛出一个异常其实还是一个非常富有技术含量的活

terminate 函数用于终止程序的运行,

如果代码写的足够多了,你经常可以发现自己的程序被杀死了,输出一条结果 xxx terminate: xxxx,大多数情况下是因为指针的问题,这个致命的异常要是一直没有被捕获,就会返回到最外层,然后调用 terminate 函数,终止程序的运行

捕获异常

noexcept

这个是不抛出异常,在我们之前使用 function 的时候也见到过

命名空间

命名空间的定义,使用,嵌套定义,分块定义,内联,无名,模板特例化,

调用命名空间内的成员

using 的使用

类、命名空间和作用域

多重继承和虚继承

第 19 章 特殊工具与技术

控制内存分配

当当,new 和 delete 相关的重载在这里出现了,我之前完全没有发现重载运算符那里没有讲new 和 delete,对了,delete 操作也是需要添加 noexcept 的修饰符的

c 中使用 malloc free 来分配释放内存,C++ 也继承了这部分功能

运行时类型识别(RTTI)

dynamic_cast

typeid 运算符,可以获取类型并返回 type_info

但是,其实 typeid 是一个非常慢的操作,我之前用这个玩意儿,还被大佬吐槽了一番,

枚举类型

C++11 引入了限定作用域的枚举类型,也让枚举拥有了更多的类型

枚举类型、联合体、结构体,这个在 c 中是作为一个基础的数据结构,在很早的时候就会被介绍到的,但是这里为了防止我们书写不那么 c++ 风格的代码,从而延后了。

限定枚举的作用域,在c中,枚举是在整个作用域可见的,导致枚举的名字不能重复,或者重复的意义可能出现不同,从而导致问题
使用 class 和 struct 表明枚举的范围

enum T { Tname1, Tname2, Tname3, Tname4 };
enum class CT { a, b, c, d };
Tname1  // ok
a       // not ok
CT::a   // ok

我们还可以限定枚举中元素的类型,默认为 int,

enum class intValues : unsigned long long {
    charTyp = 255, shortTyp = 65535, intTyp = 65535,
    // 这里出现了一个非常有趣的事情,int 的上限居然和 short 一样
    // 这个是因为标准没有明确规定int的具体长度,只规定了一个范围
    longType = 4294967295UL, long_longType = 18446744073709551615ULL
};

枚举类型的前置声明

enum class intValues : unsigned long long;

枚举的形参匹配

只能是枚举,就算值和枚举一样,对应的还是枚举,而非这个值

类成员指针

数据成员指针

const std::string CLASS::* pdata;
// 指向 CLASS 对象的 std::string 成员 的 指针

成员函数指针

char (CLASS::* pmf2) (CLASS::X, CLASS::y) const;
// 指针叫 pmf2,指向来自 CLASS 的函数
// 函数返回值为 char, 不能再函数内部修改变量的值
// 传入参数为 CLASS::X 和 CLASS::Y
using c = char (CLASS::*)(CLASS::X,CLASS::Y) const;
// 使用别名
c pmf3;

成员指针函数表
将成员函数作为可调用对象

嵌套类

只是如此嵌套而已,似乎并没有什么可以多讲的

局部类

和嵌套类也很相似,但是没有什么特别的不同,我把它提前放置在这里

联合体:union

特殊的类,将多种数据结构在一个空间上存储,实现类型的动态变化
union 用于实现了 lua的动态类型

c++11更新之后,它就变成一种特殊的类,拥有了权限控制,默认都是 public

union UT{
    char cval;
    int ival;
    long long llval;
    double dval;
    std::string sval;
};
std::map <std::string, UT> valueStack;

同枚举,类,结构体一样,联合体是可以匿名的

我们可以使用枚举存储当前联合体中存储的类型,在进行操作时加以判断

C++ 的固有不可移植性

因为 c++ 为了高效,需要编译到机器码,机器码则与对应的硬件设施相关,而其调用的库则是平台相关,导致c++的移植总是需要重新编译一串代码

位域

volatile
volatile 要求编译器不要对这个变量以及相关的进行优化,因为在多线程下,如果某一段代码被优化了,另一个线程对其的修改其实就不能生效了,这就会导致一定的问题,具体的可以看到 https://www.zhihu.com/question/31459750/answer/52061391 。书中对其描写非常之少

extern "C"
让链接器使用其他语言的编译器编译其中的代码,但是得让这个代码和c++能够一起运行

附录 A 标准库

A.1 标准库名字和头文件

A.2 算法概览

find (beg, end, val)
find_if (beg, end, unaryPred)
find_if_not (beg, end, unaryPred)
count (beg, end, val)
count_if (beg, end, unaryPred)

all_of (beg, end, unaryPred)
any_of (beg, end, unaryPred)
none_of (beg, end, unaryPred)

A.3 随机数

索引

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) {
                     xn = table[n>> 20] << 6;
                 } else {
                     xn = table[n>> 18] << 5;
                 }
             }
             xn = (xn + 1 + (n/ xn)) >> 1;
             xn = (xn + 1 + (n/ xn)) >> 1;
            return ((xn * xn) > n) ? --xn : xn;
         } else {
            if (n>= 0x100000) {
                if (n>= 0x400000) {
                     xn = table[n>> 16] << 4;
                 } else {
                     xn = table[n>> 14] << 3;
                 }
             } else {
                if (n>= 0x40000) {
                     xn = table[n>> 12] << 2;
                 } else {
                     xn = table[n>> 10] << 1;
                 }
             }

             xn = (xn + 1 + (n/ xn)) >> 1;
            return ((xn * xn) > n) ? --xn : xn;
         }
     } else {
        if (n>= 0x100) {
            if (n>= 0x1000) {
                if (n>= 0x4000) {
                     xn = (table[n>> 8]) + 1;
                 } else {
                     xn = (table[n>> 6] >> 1) + 1;
                 }
             } else {
                if (n>= 0x400) {
                     xn = (table[n>> 4] >> 2) + 1;
                 } else {
                     xn = (table[n>> 2] >> 3) + 1;
                 }
             }
            return ((xn * xn) > n) ? --xn : xn;
         } else {
            if (n>= 0) {
                return table[n] >> 4;
             }
         }
     }
    return -1;
}

https://blog.csdn.net/hunterlew/article/details/45341253
https://blog.csdn.net/xtlisk/article/details/51249371
https://blog.csdn.net/wanchuanhua/article/details/5996708
http://bbs.mydigit.cn/simple/?t2329623.html
https://www.cnblogs.com/signal/p/3818332.html
https://www.cnblogs.com/atyuwen/archive/2009/11/09/1598942.html

【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 个石子,不能拿的人为败者,问谁会胜利

巴什博奕是博弈论问题中基础的问题

它是最简单的一种情形对应一种状态的博弈

回到顶部
博弈分析
我们从最简单的情景开始分析

当石子有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 个,这样下去先手一定失败

  1. 巴什博奕 (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
第一个人获胜

其他实例:

  1. 大学英语四级考试就要来临了, 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
1
3

Sample Output
Kiki
Cici
分析:

如果你是先手,考虑你的必胜态。注意,因为任何正整数都能写成若干个 2 的整数次方幂之和 (相当于十进制转二进制)。由于规定只能取 2 的某个整数次方幂,只要你留给对手的牌数为 3 的倍数时,那么你就必赢,因为留下 3 的倍数时,对手有两种情况:
1:如果轮到对方抓牌时只剩 3 张牌,对方要么取 1 张,要么取 2 张,剩下的你全取走,必赢!
2:如果轮到对方抓牌时还剩 3k 张牌,对手不管取多少,剩下的牌数是 3x+1 或者 3x+2。轮到你时,你又可以构造一个 3 的倍数。 所以无论哪种情况,当你留给对手为 3k 的时候,你是必胜的。
题目说 Kiki 先抓牌,那么当牌数为 3 的倍数时,Kiki 就输了。否则 Kiki 就能利用先手优势将留给对方的牌数变成 3 的倍数,就必胜。

代码如下:

#include <iostream>
using namespace std;
int main () {
    int num;
    while (cin>>num ) {  
        if(num%3!=0) cout<<"Kiki"<<endl;
        else cout<<"Cici"<<endl; 
    }
    return 0; 
}
  1. 土地拍卖
    Problem Description
    小鸡同学和鹏程同学始终没有逃过退学的命运,因为他们没有在程序设计竞赛中获奖,还为了争抢莎莎大打出手。现在等待他们的只能回家种田。要种田得有田才行,小鸡听说街上正在举行一场拍卖会,拍卖的物品正好就是一块田地。于是,小鸡带上他的全部积蓄,冲往拍卖会。后来发现,整个拍卖会只有小鸡和他的死对头鹏程。通过打听,小鸡知道这场拍卖的规则是这样的:刚开始底价为 0,两个人轮流开始加价,不过每次加价的幅度要在 1~N 之间,当价格大于或等于田地的成本价 M 时,就把这块田地卖给这次叫价的人。小鸡和鹏程虽然比赛不行,但是对拍卖却十分精通,而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。由于抽签决定,所以每次都是由小鸡先开始加价,请问,第一次加价的时候,小鸡要出多少才能保证自己买得到这块地呢?

Input
本题目包含多组测试,请处理到文件结束 (EOF)。每组测试占一行。每组测试包含两个整数 M 和 N (含义见题目描述,0

# include<stdio.h>
int main() {
    int n,m;
    while(scanf("%d %d",&m,&n)!=EOF) {
        if(m%(n+1)==0) {
            printf("none\\n");
            continue;
        } 
        if(m<=n) {
            printf("%d",m);
            for(int i=m+1; i<=n; i++) printf(" %d",i);
            printf("\\n");
            continue;
        } 
        printf("%d\\n",m%(n+1));
    } 
    return 0;
}
  1. 威佐夫博奕(Wythoff Game)

这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。
有两堆火柴棍,每次可以从某一堆取至少 1 根火柴棍 (无上限),或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了,如果你不知道这个博弈定理,对于小数目的火柴棍数,可能还能推出来,但是如果火柴棍数一多,就不行了。看了下面的这个介绍,你也会有一种被骗的感觉。
首先我们知道两堆火柴是没有差别的,也就是说第一堆有 a 根,第二堆有 b 根和第一堆有 b 根,第二堆有 a 根是一样的结果。
我们用一个二维的状态(a,b) 来记录当前剩下的火柴数,表示第一堆剩下 a 根火柴,第二堆剩下 b 根火柴。同样我们假设两个人的编号是 A 和 B,且 A 先取。
那么如果某个人遇到了这样的状态 (0,0) 那么也就是说这个人输了。这样的状态我们叫做奇异状态 , 也可以叫做失败态。
那么接下来的几个失败态为 (1,2),(3,5),(4,7),(6,10),(8,13)……
我们用 a [i] 表示失败态中的第一个,b [i] 表示失败态中的第二个.(i 从 0 开始).
那么我们可以看到 b [i] = a [i]+i;(i >= 0),a [i] 是前面的失败态中没有出现过的最小的整数
下面我们可以得到三个基本的结论。

  1. 每个数仅包含在一个失败态中
    首先我们知道 a [k] 是不可能和前面的失败态中的 a [i],b [i] 重复的 (这点由 a [i] 的得到可以知道)
    b [k] = a [k]+k > a [k-1]+k>a [k-1]+k-1+1>a [k-1]+(k-1) = b [k-1]>a [k-1] 这样我们知道每个数仅在一个失败态中。
  2. 每个失败态可以转到非失败态。
    加入当前的失败态为 (a,b),那么如果我们只在一堆中取的话,肯定会变成非失败态 (这点由第一点可以保证), 如果从两堆同时取的话,由于每个失败态的差是不一样的,所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取,都会得到一个非失败态。
  3. 每个非失败态都可以转到一个失败态
    对于这个结论,首先我们要知到每个状态 (a,b) 要么 a = a [i], 要么 b = b [i].(每个数都出现在一个失败态中), 下面我们分两种情况来讨论
    I.a = a [i]. 如果 b = a 的话那么一次取完就变成了 (0,0). 如果 b > b [i] 的话,那么我们从第二堆中取走 b-b [i] 就变成了一个失败态。如果 b < b [i]. 那么我们从两堆中同时取走 a-a [b-a [i]] 这样得到失败态 (a [b-a [i]],a [b-a [i]]+b-a [i])(a [i] = a)
    II.b = b [i]. 如果 a > a [i] 那么我们从第一堆中取走 a-a [i] 根火柴.
    如果 a <a [i]. 这里又分两种情况。第一是 a = a k
    那么我们从第二堆取走 b - b [k] 就行了。
    第二是 a = b [k] 这样的话由于两堆火柴是没有区别的,所以我们把 b 变成 a [k] 就行了,也即是从第二堆火柴中取走 b - a [k] 就变成了失败态
    至于怎么判断一个状态是否是失败态。我们可以用下面的方法来判断 (本人暂时还不会证明)
    a[i] = i*(1+√5)/2 b[i] = a[i]+i;
    那么这就是一个失败态

找规律分析
第一个(0 , 0),先手输,当游戏某一方面对( 0 , 0)时,他没有办法取了,那么肯定是先手在上一局取完了,那么输。
第二个 ( 1 , 2 ),先手输,先手只有四种取法,
1)取 1 中的一个,那么后手取第二堆中两个。
2)取 2 中一个,那么后手在两堆中各取一个。
3)在 2 中取两个,那么后手在第一堆中取一个。
4)两堆中各取一个,那么后手在第二堆中取一个。
可以看出,不论先手怎么取,后说总是能赢。所以先手必输!
第三个 ( 3 , 5 ),先手必输。首先先手必定不能把任意一堆取完,如果取完了很明显后手取完另一堆先手必输,那么
假如看取一堆的情况,假设先手先在第一堆中取。 取 1 个,后手第二堆中取 4 个,变成(1 ,2)了,上面分析了是先手的必输局。
取 2 个,后手第二堆中取 3 个,也变成( 1 , 2)局面了。
假设先手在第二堆中取,取 1 个,那么后手在两堆中各取 2 个,也变成 (1 , 2) 局面了。
取 2 个 ,那么后手可以两堆中都去三个, 变成 ( 0 , 0)局面,上面分析其必输。
取 3 个,后手两堆各取 1 个 ,变成( 1 , 2)局面了。
取 4 个,后手在第一堆中取一个,变成( 1 , 2)局面了。
可见不论先手怎么取,其必输!
第四个(4 , 7),先手必输。
自己推理可以发现不论第一次先手如何取,那么后手总是会变成前面分析过的先手的必输局面。
那么到底有什么规律没有呢,我们继续往下写。
第四个 ( 6 ,10 )
第五个 ( 8 ,13)
第六个 ( 9 , 15)
第七个 ( 11 ,18)
会发现他们的差值是递增的,为 0 , 1 , 2, 3, 4 , 5 , 6, 7…..n
而用数学方法分析发现局面中第一个值为前面局面中没有出现过的第一个值,比如第三个局面,前面出现了 0 1 2,那么第三个局面的第一个值为 3 ,比如第五个局面,前
面出现了 0 1 2 3 4 5 , 那么第五个局面第一个值为 6。
再找规律的话我们会发现,第一个值 = 差值 * 1.618
而 1.618 = (sqrt(5)+ 1) / 2 。
大家都知道 0.618 是黄金分割率。而威佐夫博弈正好是 1.618,这就是博弈的奇妙之处!

下面来看看威佐夫博弈常见的三类问题:

1)给你一个局面,让你求是先手输赢。
有了上面的分析,那么这个问题应该不难解决。首先求出差值,差值 * 1.618 == 最小值 的话后手赢,否则先手赢。(注意这里的 1.618 最好是用上面式子计算出来的,否则精
度要求高的题目会错)

2)给你一个局面,让你求先手输赢,假设先手赢的话输出他第一次的取法。
首先讨论在两边同时取的情况,很明显两边同时取的话,不论怎样取他的差值是不会变的,那么我们可以根据差值计算出其中的小的值,然后加上差值就是大的一个值,当
然能取的条件是求出的最小的值不能大于其中小的一堆的石子数目。
加入在一堆中取的话,可以取任意一堆,那么其差值也是不定的,但是我们可以枚举差值,差值范围是 0 — 大的石子数目,然后根据上面的理论判断满足条件的话就是一种合理的取法。

  1. 尼姆博奕(Nimm Game)
    指的是这样的一个博弈游戏,目前有任意堆石子,每堆石子个数也是任意的,双方轮流从中取出石子,规则如下:
    1) 每一步应取走至少一枚石子;每一步只能从某一堆中取走部分或全部石子;
    2) 如果谁取到最后一枚石子就胜。
    也就是尼姆博弈(Nimm Game)。
    必败局面:也叫奇异局势。无论做出何出操作,最终结果都是输的局面。必败局面经过 2 次操作后,可以达到另一个必败局面。
    必胜局面:经过 1 次操作后可以达到必败局面。
    即当前局面不是必败局面就是必胜局面,而必胜局面可以一步转变成必败局面。
    最终状态:
    (1)最后剩下一堆石子;(必胜局面)
    (2)剩下两堆,每堆一个;(必败局面)
    (3)当石子剩下两堆,其中一堆只剩下 1 颗,另一堆剩下多于 n 颗石子时,当前取的人只需将多于 1 颗的那一堆取出 n-1 颗,则局面变为刚才提到的必败局面。(必胜局面)
    判断当前局势是否为必胜(必败)局势:
    1)把所有堆的石子数目用二进制数表示出来,当全部这些数按位异或结果为 0 时当前局面为必败局面,否则为必胜局面;
    2)在必胜局面下,因为所有数按位异或的结果是大于零的,那么通过一次取,将这个(大于其它所有数按位异或的结果的)数下降到其它所有数按位异或的结果,这时局面就变为必败局面了。

我们用 (a,b,c) 表示某种局势

  1. 首先 (0,0,0) 显然是奇异局势,无论谁面对奇异局势,都必然失败。
  2. 第二种奇异局势是 (0,n,n),只要与对手拿走一样多的物品,最后都将导致 (0,0,0)。仔细分析一下,(1,2,3) 也是奇异局势,无论对手如何拿,接下来都可以变为 (0,n,n) 的情形。
    对于以上两种情况,均有三个数疑惑后为零。其实,只要取完数后使得剩下局面为三数异或结果为零,则胜。

例如 (14,21,39),14 (+) 21=27,39-27=12,所以从 39 中拿走 12 个物体即可达到奇异局势 (14,21,27)。
我们来实际进行一盘比赛看看:

甲:(7,8,9)->(1,8,9) 奇异局势

乙:(1,8,9)->(1,8,4)

甲:(1,8,4)->(1,5,4) 奇异局势

乙:(1,5,4)->(1,4,4)

甲:(1,4,4)->(0,4,4) 奇异局势

乙:(0,4,4)->(0,4,2)

甲:(0.4,2)->(0,2,2) 奇异局势

乙:(0,2,2)->(0,2,1)

甲:(0,2,1)->(0,1,1) 奇异局势

乙:(0,1,1)->(0,1,0)

甲:(0,1,0)->(0,0,0) 奇异局势

甲胜。

代码:

import java.util.Scanner;

/**
 * Created by YYL on 2017/2/24.
 */
//A先取,若A面对奇艺局面,则失败
public class NimmGame {
    public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();//堆数
        int [] temp=new int[n];
        for (int i = 0; i <n ; i++) {
            temp[i]=scanner.nextInt();//初始化每堆的个数
        }
        int result=temp[0];
        for (int i = 1; i <n ; i++) {
            result^=temp[i];
        }
        if(result==0)
            System.out.println("B胜");
        else
            System.out.println("A胜");
    }
}

运行结果

3
7 8 9
A 胜
————————————————

理论: 博弈 2: 巴什博奕(Bash Game)

巴什博奕基础情形
只有一堆 n 个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取 m 个。最后取光者得胜。

如果 n = m + 1; 我们假设第一个人拿走了 k 个, 还剩下 m + 1 - k。 因为 1<=(m + 1 - k)<= m, 所以, 剩下的部分一定可以被第二个人一次性取走。

现在我们将上述规律加一推广:
如果 n=(m+1)r+s(r∈ N,s<= m);
那么先取者要拿走 s 个物品,如果后取者拿走 k(k<= m) 个,那么 先取者再拿走 m+1-k 个,结果剩下(m+1)(r-1)个,
以后保持这样的取法,那么先取者肯定获胜

那么在我方取最优解的情况下:
现在我们就发现了巴什博弈的一个必败态: (m + 1)* r (r∈ N);
那么巴什博弈的必胜态也就可以反推出来: (m + 1)* r + k (1<=k<= m, r ∈N);

现在我们换一个角度来考虑这个问题:
如果物品数量随机,那么先手一方胜利的概率是 m/(m+1),后手方胜利的概率是 1/(m+1)

对于上述的问题, 我们可以用 mod 的方法快速的求出答案(其实三种博弈的最优美之处就是能用 %^& 这三个符号完美解答)

`

巴什博弈演变

硬币问题 1
Alice 和 Bob 在玩这样的一个游戏, 给定 k 个数组 a1,a2,a3,……ak。 一开始, 有 x 枚硬币, Alice 和 Bob 轮流取硬币, 每次所取硬币的枚数硬顶要在 a1,a2,a3,……ak 之中。 Alice 先取, 取走最后一枚硬币的一方获胜。 当双方都采取最优策略的时候, 谁会获胜? 题目假定 a1,a2,a3,……ak 之中一定有 1。

下面我们来分情况讨论到达自己时, 还有 j 枚硬币的胜负情况:

  1. 题目规定, 取光所有的硬币就获胜, 这等价于轮到自己时如果没有硬币就失败, 因此 j = 0 时是必败态。
  2. 如果对于某个 i(i<=i<= k), 就 j - ai 是必败态, 那么 j 就是必胜态(如果当前有 j 枚硬币, 只要取走 ai 枚对手就必败→自己必胜);
  3. 如果对于任意的 i(1 <= i <= k), j - ai 都是必败态的话, j 就是必败态(无论对手这么走, 对手都必胜, 自己必败)

根据这些规则, 我们都能利用动态规划算法按照 j 从小到大的顺序计算必胜态。, 只要看 x 是必胜态还是必败态, 我们就知道谁会取胜;

通常来说, 通过考虑每个小状态的取胜条件, 判断必胜条件和必胜态, 是有胜负的游戏的基础;

上代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int x,k;
bool win[100000];
int a[100000];

void Bash()
{//轮到自己没有硬币则必败;
    win[0] = false;

    for (int i = 1; i <= x; i++) {
//如果可以让对手达到必败态, 则自己必胜;
        win[i] = false;
        for (int j = 0; j < k; i++)
            win[i] |= (a[j] <= i && !win[i - a[j]]); // |=   真真为真 真假为真  假假为假
    }
}

int main(void) {
    while (scanf("%d %d", &x, &k) != EOF) {
        for (int i = 0; i < k; i++)
            scanf("%d", &a[i]);
        sort(a, a + k);
        memset(win, 0, sizeof(a));
        Bash();
        if (win[x]) printf("Alicce!\\n");
        else printf("Bob!\\n");
    }
    return 0;
}

硬币问题 2
n 枚硬币排成一个圈。Alice 和 Bob 轮流从中取一枚或者两枚硬币, 不过, 取两枚时这两枚必须是连续的。硬币取走之后留下空位,想个空位的硬币被认为是不连续。 A 开始先取, 取走最后一枚硬币的一方获胜。双方都采取最优策略的时候谁会取胜?

20160129203621025.jpg

按照上面问题的想法, 我们来拆分一下问题;

20160129203755543.jpg

首先我们是想一下如下的情况。 将所有的剩余硬币分成完全相同的组别, 这个是必胜状态还是必败状态?

事实上这是必败态, 无论采取什么策略, 对手只要在另一组中使用相同的策略, 就有回到了相同分组的状态, 而最终的相同分组状态就是(0,0);

接下来, 我们回归正题。A 在第一取走一枚或者两枚硬币之后,称圈的硬币就变成了长度为 n - 1 或者是 n - 2 的。 Bob 只要在中间位置根据链的奇偶性, 在链的中间位置取走 1 或者 2 枚, 就可以把所有的硬币分成长度相同的两个链。

20160129222551788.jpg

正如我们所说的,这是必败态, 也就是说, Alice 必败, Bob 必胜,只不过, 当 n <= 2, Alice 可以一步取光, 所以胜利的是 Alice, 除此之外, 在都进行最优解的情况下, Alice 必败。

int k;

if(k <= 2) printf("Alice!\\n");
else printf("Bob\\n");

Euclid’s Game(poj 2348)
poj 传送门

题目大意:

给定两个整数 a, b。Alice 和 Bob 轮流用较大的数减去较小的数的整数倍, 并且相减之后的值不小于 0。 如果在自己的回合之内, 相减之后的结果为零, 那么获胜。Alice 先手。

根据上述两个问题我们有两个规律可以用上:1. 将大问题划分为小问题在进行解决 2. 寻找开始(或结束)位置的必败态(或必胜态)在加以正推(或倒推);

划分: 我们按照后续处理的差别, 将其分为 3 类:
1.b < a, 我们将 a b 进行交换, 使得 b 恒大于 a;
2.a > (b - a);
3.a < (b - a) ;

对于第一种情况, 为了便于后续处理, 我们将其认为是默认情况;
对于第二种情况, 我么可以选择在 b 的基础上减去 a, 或者减去 2a 和以上;(这一种是有余地的方案)
对于第三种情况, 我们仅仅只有减去 a 这一种方法;

对于第一种情况:默认的调整方式, 我们用来调整 a,b 代表的值, 在这里不用讨论(这里实际指的就是 swap 函数的调用过程)
对于第三种情况, 仅仅只有一种方案: 继续向下迭代, 直到出现最终结局;
对于第二种情况: 假设 x 是使 b - ax <a 成立的整数, 那么在第二种情况中又可以分为两种情况 I. b - ax; II.b - a (x - 1);

下面我们讨论 二.I: 这种情况和第三种情况类似, 只能向下迭代, 寻找最终的结果;
对于情况二.II:这种情况的后继情况就是情况就只有 b - ax 这一种情况, 很巧, 这又回到了情况三。而经过了两次转换, 这种情况依旧是必胜态;

int a, b;

bool flag = true;
while(true) {
    if(a > b) swap(&a, &b);
    if(b % a == 0) break;
    if(b - a > a) break;
    b -= a;
    flag = !flag; 
}
if(flag) printf("Alice!\\n");
else printf("Bob!\\n");

博弈论基础知识:巴什博奕 + 威佐夫博奕 + 尼姆博弈 (及 Staircase)

【嵌牛导读】:介绍一些博弈,因为算法有时候就是应用在博弈问题上。

【嵌牛鼻子】:巴什博奕 (Bash Game)。威佐夫博奕 (Wythoff Game)。尼姆博奕 (Nimm Game)。Nim Staircase 博奕。

【嵌牛提问】:什么是巴什博奕 (Bash Game)。威佐夫博奕 (Wythoff Game)。尼姆博奕 (Nimm Game)。Nim Staircase 博奕?

【嵌牛正文】:

(一) 巴什博奕 (Bash Game):

只有一堆 n 个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取 m 个。最后取光者得胜.

若 (m+1) | n,则先手必败,否则先手必胜。

显然,如果 n=m+1, 那么由于一次最多只能取 m 个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发

现了如何取胜的法则:如果 n=(m+1) r+s,(r 为任意自然数,s≤m), 那么先取者要拿走 s 个物品,如果后取者拿走 k (≤m) 个,那么先取者再拿

走 m+1-k 个,结果剩下 (m+1)(r-1) 个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下 (m+1) 的倍数,就能最后获胜.

(二) 威佐夫博奕 (Wythoff Game):

有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜.

奇异局势下先手必败,非奇异局势下先手必胜。

这种情况下是颇为复杂的。我们用 (ak,bk)(ak ≤bk ,k=0,1,2,...,n) 表示两堆物品的数量并称其为局势,如果甲面对 (0,0), 那么甲已经

输了,这种局势我们称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20).

可以看出,a0=b0=0,ak 是未在前面出现过的最小自然数,而 bk= ak + k, 奇异局势有如下三条性质:

1、任何自然数都包含在一个且仅有一个奇异局势中.

由于 ak 是未在前面出现过的最小自然数,所以有 ak > ak-1 , 而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 . 所以性质 1. 成立.

2、任意操作都可将奇异局势变为非奇异局势.

事实上,若只改变奇异局势 (ak,bk) 的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势。如果使 (ak,bk) 的两

个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势.

3、采用适当的方法,可以将非奇异局势变为奇异局势.

假设面对的局势是 (a,b), 若 b = a, 则同时从两堆中取走 a 个物体,就变为了奇异局势 (0,0);如果 a = ak ,b > bk, 那么,取走 b - bk 个物

体,即变为奇异局势;如果 a = ak , b <bk , 则同时从两堆中拿走 ak - ab - ak 个物体,变为奇异局势 ( ab - ak , ab - ak+ b - ak)

;如果 a > ak ,b= ak + k, 则从第一堆中拿走多余的数量 a - ak 即可;如果 a <ak ,b= ak + k, 分两种情况,第一种,a=aj (j < k), 从

第二堆里面拿走 b - bj 即可;第二种,a=bj (j < k), 从第二堆里面拿走 b - aj 即可.

从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜.

那么任给一个局势 (a,b), 怎样判断它是不是奇异局势呢?我们有如下公式:

ak =k (1+√5)/2, bk= ak + k (k∈N)

奇妙的是其中出现了有关黄金分割数的式子:$\\frac{1+\\sqrt{5}}{2} = 1.618...$, 若两堆物品个数分别为 x,y (x<y),则 k=y-x,再判断 x 是否等于 $y-x\\times \\frac{1+\\sqrt{5}}{2}$ 即可得知是否是奇异局势。

参考例题:POJ1067 取石子游戏

参考代码:

var a,b:longint;begin repeat readln(a,b); if a>b then begin a:=a xor b; b:=a xor b; a:=a xor b; end; if a=trunc((b-a)*(sqrt(5)+1)/2) then writeln(0) else writeln(1); until seekeof;end.

(三) 尼姆博奕 (Nimm Game):

有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜.

这种情况最有意思,它与二进制有密切关系,我们用 (a,b,c) 表示某种局势,首先 (0,0,0) 显然是奇异局势,无论谁面对奇异局势,都必然失

败。第二种奇异局势是 (0,n,n), 只要与对手拿走一样多的物品,最后都将导致 (0,0,0). 仔细分析一下,(1,2,3) 也是奇异局势,无论对手如

何拿,接下来都可以变为 (0,n,n) 的情形.

计算机算法里面有一种叫做按位模 2 加,也叫做异或的运算,我们用符号 xor 表示这种运算。这种运算和一般加法不同的一点是 1+1=0. 先看

(1,2,3) 的按位模 2 加的结果:

1 = 二进制 01

Xor 2 = 二进制 10

Xor 3 = 二进制 11

———————

0 = 二进制 00

对于奇异局势 (0,n,n) 也一样,结果也是 0.

任何奇异局势 (a,b,c) 都有 a xor b xor c =0。该结论可以推广至若干堆,都是成立的。

如果我们面对的是一个非奇异局势 (a,b,c), 要如何变为奇异局势呢?假设 a < b< c, 我们只要将 c 变为 a xor b, 即可,因为有如下的运算

结果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0. 要将 c 变为 a xor b, 只要从 c 中减去 c-(a xor b) 即可.

(四) Nim Staircase 博奕:

这个问题是尼姆博弈的拓展:游戏开始时有许多硬币任意分布在楼梯上,共 n 阶楼梯从地面由下向上编号为 0 到 n。游戏者在每次操作时

可以将楼梯 j (1<=j<=n) 上的任意多但至少一个硬币移动到楼梯 j-1 上。游戏者轮流操作,将最后一枚硬币移至地上(0 号)的人获胜。

算法:将奇数楼层的状态异或,和为 0 则先手必败,否则先手必胜。证明略。

例题:Poj1704

这道题可以把两个棋子中间间隔的空格子个数作为一堆石子,则原题转化为每次可以把左边的一堆石子移到相邻的右边的一堆中。也就

是阶梯尼姆博弈,注意对输入数据先排序,然后倒着往前数(a [n]-a [n-1]-1 为第一个),奇数个数到的就做一下 xor,其中最前面的看

做 a [1]-0-1,参考程序:

var t,n,b,i,j:longint; a:array [0..1000] of longint;begin readln (t); repeat dec (t); readln (n); for i:=1 to n do read (a [i]); qsort (1,n);// 快排略 j:=0; b:=0; for i:=n downto 1 do begin inc (j); if odd (j) then b:=b xor (a [i]-a [i-1]-1); end; if b=0 then writeln ('Bob will win') else writeln ('Georgia will win'); until t=0;end.

其他题目

【hdu-1846】Brave Game

【hdu-4764】Stone

https://www.cnblogs.com/zwfymqz/p/8460192.html
版权声明:本文为CSDN博主「yyl424525」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/yyl424525/article/details/56840182
版权声明:本文为CSDN博主「sun897949163」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/sun897949163/article/details/50609070
https://www.jianshu.com/p/0b84d77a3bfd