🎉把您写的文章留下来🎉

[ssmath]

（Markdown）格式：

- 姓名+网络ID
  - 文章主题（类型标记）：文章发布地址、URL
  - 文章主题（类型标记）：文章发布地址、URL

类型标记有：A、R1、S、R2、W1、W2
详情请看正题部分：https://seveninnovationbasedoc.readthedocs.io/zh_CN/latest/Announcement/reading01.html

[yeshan333]

• A：算法（Algorithms），🖊做一道中等难度及以上的算法题或者学习一个有难度的算法，写下你的解题思路（多个）、想法、算法原理，把文章分享出来，文章可发表在各大技术平台或者你的个人博客、GitHub Project README

• R1：复审，检查（Review），Review一篇英文技术文章，把它翻译出来（跑通作者的代码，附带你的个人想法），然后把你整的以文章的形式记录分享出来👍

• S：分享（Share），📚写一篇文章，分享你进入大学到现在的学习感悟或者分享你的技术学习路线，脑图+白话文🎹

• R2：阅读（Read）👀，读一篇有深度的技术文章或者读一本科普书（比如人类简史），写下你的感悟，同样的把你的感悟以文章的形式分享出来

• W1：看（Watch），看一场技术主题演讲的视频，认识下大佬，以文章的形式写下你的感悟分享出来。不知道有哪些开发者技术活动，可以看下这篇文章：《权威发布丨SegmentFault 思否 2019 中国最受开发者欢迎的技术活动》，这些活动的视频和PPT大部分都会放出来，GitHub、B站或者官网应该能找到🍀

• W2：写（Write），写篇技术文章分享出来，主题随意，你们懂得😀

[HEtinto]

学习C++虚函数与动态多态性

-喻建明 HEtinto
  W2:

前言

C++中的虚函数的主要作用是为了实现多态，通过了解虚函数的作用，可以帮助我们理解多态实现的原理。

虚表

虚函数其实是通过一张虚表来实现的，称为V-Table，在这个表中，主要是一个类的虚函数的地址表。在有虚函数的类的实例中，虚表被分配在实例的内存之中，在使用父类指针来操作一个子类中存在的与父类中的成员函数同名的函数时，虚函数指针通过虚表实现动态绑定。

下面测试虚表所占用的内存空间大小：

```C++
#include <iostream>
using namespace std;
class Father
{
public:
	virtual void fun1() { cout << "父类" << endl; }
};

class Son 
{
public:
	void fun1() { cout << "子类" << endl; }
};

int main()
{
	Father f1;
	Son s1;
	cout << "类Father所占内存空间：" << sizeof(f1) << endl;
	cout << "类Son所占内存空间：" << sizeof(s1) << endl;
	cout << "虚表所占内存空间:" << sizeof(f1) - sizeof(s1) << endl;
	return 0;
}
```  

输出结果：

```
类Father所占内存空间：4
类Son所占内存空间：1
虚表所占内存空间: 3  
```  

虚表实际占用大小可能根据实际数据情况改变大小，这里只是验证其存在性。并且子类会继承父类的虚表，这样虚表同样会在子类实例中占用内存空间。

虚表的作用

虚表用于存储类的实例化对象中虚函数函数地址，它可以动态地存储虚函数的子类的同名函数的地址，用于区分子类和父类的同名函数，实现动态绑定。

下面我们来实际看一看虚表所实现的动态绑定：

```
#include <iostream>
using namespace std;
class Father
{
public:
	virtual void fun1() { cout << "父类：fun1()" << endl; }
	void fun2() { cout << "父类：fun2()" << endl; }
	void fun3() { cout << "父类：fun3()" << endl; }
};

class Son : public  Father
{
public:
	void fun1() { cout << "子类：fun1()" << endl; }
	void fun2() { cout << "子类：fun2()" << endl; }
	void fun3() { cout << "子类：fun3()" << endl; }
};

int main()
{
	Father f1;
	Son s1;
	cout << "类Father所占内存空间：" << sizeof(f1) << endl;
	cout << "类Son所占内存空间：" << sizeof(s1) << endl;
	Father& fp1 = s1;
	fp1.fun1();
	fp1.fun2();
	fp1.fun3();
	return 0;
}
```  

运行结果：

```
类Father所占内存空间：4
类Son所占内存空间：4
子类：fun1()
父类：fun2()
父类：fun3()
```  

分析：
1.Son类继承了父类Father类；
2.创建父类引用 fp1 并使之指向子类的实例化对象s1；
3.fp1调用方法fun1()，fun2(),fun3();
4.其中只有方法**fun1()在父类中有同名的虚函数；
5.结果显示动态绑定成功，方法fun1()**调用的是子类的方法，其余调用的是父类的方法，并且与之前相比，类Son的实例所占内存空间增加了3个字节，说明其继承了父类的虚表。

虚表实现动态绑定的存储方式

下面给出父类的一个实例的虚表，（实际上，在子类继承了父类后，创建子类对象的同时，也会创建一个父类的对象，并调用父类的构造函数进行初始化）：

虚表地址	fun1()地址	fun2()地址	fun3()地址
0136FA08	00C69C38	00C69C3C	00C69C40

下面给出子类的实例化对象的虚表及其函数地址：

虚表地址	fun1()地址	fun2()地址	fun3()地址
0136F9FC	00C69B74	00C69B78	00C69B7C

下面给出虚表地址和虚表中函数地址的获取方法

```
	Father f1;
	Son s1;
	typedef void(*Fun)(void);
	Fun p = NULL;
	cout << "输出父类虚表及虚表中存储的函数地址" << endl;
	cout << "虚表地址：" << hex << (int*)(&f1) << endl;
	cout << "地址1：" << hex << (int*)*(int*)(&f1) << endl;
	cout << "地址2：" << hex << ((int*)*(int*)(&f1) + 1) << endl;
	cout << "地址3：" << hex << ((int*)*(int*)(&f1) + 2) << endl;
	cout << "输出子类虚表及虚表中存储的函数地址" << endl;
	cout << "虚表地址：" << hex << (int*)(&s1) << endl;
	cout << "地址1：" << hex << (int*)*(int*)(&s1) << endl;
	cout << "地址2：" << hex << ((int*)*(int*)(&s1) + 1) << endl;
	cout << "地址3：" << hex << ((int*)*(int*)(&s1) + 2) << endl;
```

**存储方式分析：**一个虚表将类的实例对象的虚函数函数地址按照声明顺序依次放在虚表之中。

实现方式：对于父类中的虚函数，在子类中若存在同名的函数，即可实现动态绑定，这时子类从父类中继承的虚表中的同名函数的地址就会替换为子类中的同名函数的地址；这样我们在调用时就不会调用父类的函数，而是调用子类的函数。

优劣分析

优势：
多态是OOP的关键，C++通过虚函数与对象的绑定实现动态多态，是C++作为面向对象语言的基石。这里不得不说的是，C++还支持静态多态，即通过函数重载实现多态，子类的函数若与父类中的函数重名，在子类调用该函数时，会自动覆盖父类的函数，但是这并不支持使用父类的指向子类引用以及父类的的指向子类的指针来调用，只能由子类自身的对象在调用时才会产生作用。

缺点：
1.虚函数主要是给子类使用同名函数进行重载之用的，因此子类不重载父类的虚函数的话是没有必要使用虚函数的。C++是默认不支持动态绑定的，需要通过虚函数来实现，而在其他OOP语言则是默认动态绑定，默认动态绑定是OOP语言的基本常识。

2.虚函数的安全性方面其实是有漏洞的，如果我们用父类的指针或者是引用指向子类的对象，而子类中存在不是重载父类虚函数的虚函数，我们想要通过父类的指针去访问子类自己的虚函数，那么这是非法的，但是我们可以通过指针的方式访问虚函数来达到违反C++语义的行为。

```C++
#include <iostream>
using namespace std;
typedef void(*Fun)(void);
class Father
{
public:
	virtual void fun1() { cout << "父类：fun1()" << endl; }
	void fun2() { cout << "父类：fun2()" << endl; }
	void fun3() { cout << "父类：fun3()" << endl; }
};

class Son : public  Father
{
public:
	void fun1() { cout << "子类：fun1()" << endl; }
	virtual void fun2() { cout << "子类：fun2()" << endl; }
	virtual void fun3() { cout << "子类：fun3()" << endl; }
};

int main()
{
	Father f1;
	Son s1;
	Father& fp1 = s1;
	cout << "尝试使用父类引用指向子类对象调用子类中的虚函数" << endl;
	fp1.fun2();
	fp1.fun3();
	cout << "使用虚表尝试使用父类引用指向子类对象调用子类中的虚函数" << endl;
	Fun p = NULL;
	for (int i = 1; i < 3; i++)
	{
		p = (Fun)*((int*)*(int*)(&fp1) + i);
		p();
	}
	
	return 0;
}
```  

程序运行结果：

```
尝试使用父类引用指向子类对象调用子类中的虚函数
父类：fun2()
父类：fun3()
使用虚表尝试使用父类引用指向子类对象调用子类中的虚函数
子类：fun2()
子类：fun3()
```  

3.根据虚表的性质，我们容易知道，父类的虚函数会存在于子类的虚表之中，我们可以通过子类的虚表去访问父类的非公有虚函数。

```C++
#include <iostream>
using namespace std;
typedef void(*Fun)(void);
class Father
{
private:
virtual void fun1() { cout << "父类：fun1()" << endl; }
};

class Son : public  Father
{
public:
};

int main()
{
	Son s1;
	Fun p = NULL;
		p = (Fun)*((int*)*(int*)(&s1) + 0);
		p();
	return 0;
}
```  

运行结果：

```
父类：fun1()
```  

##结语
C++语言作为一个混合型的语言，与Java等纯面向对象语言有所不同，也具许多优点，比如说较高的灵活性、强大的功能和高效率等；在学习C++的过程中要敢于了解C++的深层次的问题，通过代码调试、合理运用指针、地址去探索C++的奥秘。在这次学习虚函数中，就较多地使用了指针和引用等方式去逐步发现C++实现多态的原理。

5/16/2020 9:49:49 PM by yujianming

[HEtinto]

分治算法

-喻建明 HEtinto
  -A:#2

思想

分治法：在求解一个输入规模为n，而n的取值又很大的问题时，直接求解往往非常困难。这时，可以先分析问题本身所具有的某些特性，然后从这些特性出发，选择某些适当的设计策略来求解。

分治算法的思想是将一个复杂的问题分解成许多子问题，然后对子问题进行求解，子问题求解得出的结果将构成原来问题的解。

分治算法执行过程：

  
1.根据问题规模决定是否需要分治，对于规模较小的问题,不需要进行分治处理。
2.进入分治环节后，考虑将主问题分解为规模较小的子问题，并且这些子问题要与原问题形式一致。
3.利用递归解决这些子问题。
4.将子问题合并的到主问题的解。

问题引入

计算 x 的 n 次幂。

常规思路

``` python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            if N >= 1:
                return x * quickMul(N - 1)

        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)


s = Solution()
print(s.myPow(2, 1024))

```

这是一个递归求解思路，可以被程序正常调用和运行；但是随着程序的递归次数的增加，将会超过 python3 的最大递归深度（1000左右），运行将会报错。这里测试的是计算2的1024次方，运行结果显示超过最大递归深度

RecursionError: maximum recursion depth exceeded in comparison

分析：递归程序会占用大量的内存空间，如果不设法提高递归程序的空间使用效率和运算效率，会对内存和算力造成很大的浪费。

###分治实现
下面提供分治算法的解答思路：
首先，对程序中关于 N==0 和 N==1 情况将不采取分治，在 N>1 时采取分治，在分治时二分幂次，例如：计算 x 的 2N 次方，我们利用 x^N * x^N = x^2N, 把问题先分解成两个较小的问题，然后递归地执行上述操作，若是计算奇次幂那么只需要额外再乘一个 x，程序中由  return s * s * x  实现。

具体算法实现

```python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            if N == 1:
                return x
            s = quickMul(N//2)
            if N % 2 == 0:
                return s * s
            else:
                return s * s * x
        return quickMul(n) if n >= 0 else 1.0 / quickMul(n)


s = Solution()
print(s.myPow(2, 1024))
```  

执行上述代码可得出结果(结果较长这里只显示部分结果):

179769313486231590772930519078902473361797697894230657273430081157732675805500…………

效率分析

在第一种递归算法下，容易知道，程序进行的递归次数就是所求幂次的大小。

在第二种算法下，在计算 2 的 1024 次方时递归只进行了 10 次，而第一种算法需要进行 1024 次，采用分治思想的算法效率相比不采用分治处理的算法而言效率是很高的。

递归次数是10次的原因：程序中 N = 1024， 如果 N 不等于 0 或 1，执行递归 且令 N = N // 2，在第10次计算后 N = 1, 不再进入递归。下面给出实际测试代码：

```python
class Solution:
    def __init__(self):
        self.degree = 0
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            if N == 1:
                return x
            """递归次数加一"""
            self.degree += 1
            s = quickMul(N//2)
            if N % 2 == 0:
                return s * s
            else:
                return s * s * x
        return quickMul(n) if n >= 0 else 1.0 / quickMul(n)


s = Solution()
print(s.myPow(2, 1024))
print("递归次数：", s.degree)
```

递归次数：10

分治算法经典问题

• 二分搜索
• 大整数乘法
• Strassen矩阵乘法
• 棋盘覆盖
• 合并排序
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 汉诺塔

总结

对于一个规模很大的问题，在进行直接求解时往往十分困难，但是问题本身可以分成若干个较小的问题，这些较小的问题相对于之前的问题而言更容易求解，然后通过合并这些较小问题的解得出原问题的解，这样对于提高程序效率具有很大的帮助。

[liuyingqiao2019]

学习感悟

-刘樱桥 liuyingqiao2019

S:

入学到现在，也曾痛苦与迷惘过。途中最大的感悟便是--实践出真知，实践是提升技术最快的方法，学而不思则罔。

我曾用一周的时间学完C语言的基础知识，用2天是时间忘记，最终花了2个月的时间”复习“。也曾花两个月的暑假时间学习Python，直到被提问才发现，自己其实并没有掌握多少相关的知识点，只看书只看教程、缺乏一定的实践是学不好一门语言的。这时才突然发现”敲十万行代码才算入门某门语言“这句话似乎是有一定的道理的。当然，只搞项目，不去了解项目的原理，虽然做出来的项目很多，但那毕竟是参考别人的，不是自己的。

只有自己敲一遍代码，才能知道自己的漏洞在哪里，不足在哪里。比如说，我就有着多学一门语言，就容易将其把已经掌握的语言混杂起来。刚学JAVA时，我便会与C语言混淆，再学C++时，又会把C++和JAVA混淆。因此，我不得不花时间去辨析、区分两者语言及其结构的共同点与不同点，甚至于去研究两个数的交换的多种方法。仔细一想，其原因还是代码量不够。

学习途中不够专注。学着JAVA的同时，一会跑去捣鼓数据库，一会弄个Linux服务器练手。一时兴起就会这边看看那也瞅瞅。

以上，便是我从入学到现在所出现的坏毛病+踩的坑。

[liuyingqiao2019]

我们为什么会生病读书笔记

-刘樱桥 liuyingqiao2019

R2:

前言

全书共15章，属于生物类科技文。原本是打算看完再写的，但怕遗忘，现记录一下我的一些感想。另全书我只看到了第8章，第8章往后的内容我暂时不发表言论。

内容

文章开篇声明了全书是从演化解释的角度去思考问题的，也就是以解答类似于为什么自然选择留下了这些基因，为什么人们会对某种疾病更易感之类的问题。全思路大致上是这样子的：首先，我们为什么会生病？从我们中学学过的高中知识可以知道，像类似感冒发烧这样的病因是因为机体遭遇了病毒的入侵。如今年的疫情，为什么吃蝙蝠的人生病了？因为蝙蝠携带的病毒入侵了人体，引发了发热、咳嗽等症状。那么，为什么让人们感染上的恰好是新型冠状病毒而不是其他病毒？换句话来说，为什么人们对新型冠状病毒这么易感？原因是人们自身携带的某种基因会对这个病毒出现易感现象。那么为什么自然选择没有把这个基因给剔除？ok,这个问题，就是这本书所要解决的问题，即关于起源和功能的问题。

首先呢，我们知道，大自然对人类身体的构造是相当精妙的。比如四肢长骨的架构为空心管状，在重量最小、材料最节约的情况下还同时具备了最大的强度和弹性，并且比同等重量的实心钢筋的强度高。但大自然在某些“设计”方面也出现一些失误和偏差：如我们的气管和食道在咽喉交叉，那么我们在吃饭的时候说话或者大笑，食物就会流入气管造成堵塞，严重些的后果甚至是死亡，即“噎死”。对于大自然种种精妙的设计之下，发生这种疏忽可以说是反常的，而这个机制为什么就没有被淘汰呢？为什么人类就不能像鱼一样，呼吸道与食道单独的分开？

自然选择不是一蹴而就的，是一点一点的慢慢的改变。不可能因为某一些的不合理设置就把所有东西都推倒重建。而像人类的呼吸道和食道的交叉问题，其实只要吃东西时不说话就能有效的减少伤亡。倘若人类同鱼一样让呼吸道与食道单独分开，那势必有着脖子过粗等弊端。曾在看到过这样一个问题：已知像车轮这种圆形的构造是最为省力的行走方式，那么为什么人类进化出来的不是车轮，而是腿呢？而在B站上曾看到过这一问题的动画解答诠释了自然选择这一点。为了省力，圆形可以简化为扇形。而为了适应各种地形凹凸不平的变化，在扇形的基础上，又增加了几条承重轴，久而久之，车轮的行走方式，在人类身上体现的，也正是腿的基本构造。这便是自然选择的力量，那么为何自然选择没有将某些基因剔除呢？

据研究显示，患有镰刀型贫血症的患者不容易感染疟疾。原因是引起镰刀型贫血症的基因同时具有防止疟疾的作用。那么当某地疟疾蔓延严重时，这些镰刀型贫血症的患者便生存了下来。即自然选择不会剔除对携带者有益处的基因。即引起对新冠病毒的易感现象的基因，在某个方面所表现的作用是对携带者有益的。

演化是一个渐进的过程，它没有跃进，只有微小的改变，而每一种改变都必须具有立竿见影的益处。尽管有着许多的基因会造成了一定的弊端，但也会带来更大的益处，因此才被自然选择留了下来。