学习笔记

Hanoi汉诺塔问题 引入 汉诺塔是我们已经再熟悉不过的东西了，其游戏的规则是有a，b，c三个杆子，同时在a上有n个盘子，我们需要通过移动将所有盘子都移动至c杆，但移动的过程中每次只能移动一个盘子，且大盘子不能在小盘子上。 解析 我们如果需要对这个题编写程序可以采用递归的思想，将这个大问题分解成一步一步的小问题，例如现在所有盘子都在a上，我们可以把最大的盘子上面的n-1个盘子先移动到b这个空盘上，然后将最大的盘子移动到c这个目标杆上，对于剩下的n-1个盘子亦是如此。每次我们先借用辅助盘将最大盘上面的所有盘子移动到辅助盘，然后将最大盘再移动到目标盘，以此分解问题，以此我们可以写出程序的主要函数，如下所示： ➕➕ hanoi.cpp Copy to clipboard 1 2 3 4 5 6 7 8 9 10 11 void hanoi(int n,int a,int b,int c) { if(n==1) { cout<<"a->c"<<endl; } else hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,b,a,c); } 对于上述程序我们来分析一下时间复杂度，其中move函数的时间复杂度可以记为常数，几乎不耗时，故该函数时间复杂度主要由两个递归函数hanoi决定，则(T(n)=2 times T(n-1) +c)，按照规律递推下去可知该函数时间复杂度为(O(2^n))。   拓展 我们发现最终如果要实现汉诺塔这个盘子的移动最终需要(2^n)这么多步，而这正好是我们n个位数的二进制数能表示的所有情况，那么我们想象能不能把两者进行联系呢。显然这是可以的，我们首先将二进制数从小到大排好，例如(0000,0001,0010, cdots)，然后将这些盘子按照大小从小到大标号，从1开始，并将盘子与二进制的位数关联，标号越小位数越低，例如标号为1的盘子则代表最右边的位数，后我们将二进制数与前一个数比较，若是某位从0变为了1那么就将该位代表的盘子向左移动到最近的可行的柱子，接下来我们将通过三个盘子汉诺塔为例子展示这个思想，如下表： 此用二进制表示汉诺塔移动方式给我们提供了新的思路，此发现实为巧妙，小编第一次了解时大受震撼。

Gale-Shapley算法 稳定匹配 给定 n 个医院序列 H 和 n 个学生序列 S。每个医院会对所有学生按照其偏好进行排序。 每个学生同样也会对所有医院按照其偏好进行排序。每个医院 h ∈ H 与学生 s ∈ S 一一配对。如果所有医院与学生都进行了配对，就称其达到完全匹配。配对中的不稳定配对 h ↔ s 即为：        – h 当前配对的对象为 s′，而 h 的偏好是 s > s′。        – s 当前配对的对象为 h′，而 s 的偏好是 h > h′。显然，只有在信息交互的过程才会发现不稳定配对。稳定匹配就是没有不稳定配对的完全匹配。 Gale-Shapley算法 该算法主要解决了事物之间匹配的问题，利用该算法能够求出最佳匹配也就是稳定匹配。现通过一例子来说明。设有一组男生w和一组女生m需要寻找对象，且每个男生和女生都有自己的偏好，且他们各自的偏好如下：[m_1 , w_1 > w_2 >w_3][m_2 , w_1>w_3>w_2][m_3,w_1>w_3>w_2][w_1,m_2>m_1>m_3][w_2,m_1>m_2>m_3][w_3,m_3>m_1>m_2]根据Gale-Shapley算法，我们首先遍历男生w，按照男生的需求的优先级先与女生匹配，若男生先要所选的女生已经被匹配了，那么需要观察女生的喜好，对比已经匹配的男生和想要匹配的男生，选择优者，被淘汰者则按照自己的顺序继续寻找女生匹配。该过程在该例子中可以表现为一下具体执行：[m_1 按照优先级首先与 w_1 匹配，现有配对： m_1 leftrightarrow w_2] [m_2 按照优先级与w_1 匹配，但w_1已有配对，择优选择m_2，m_1重新配对选择w_2，现有配对：m_1 leftrightarrow w_2 , m_2 leftrightarrow w_1] [m_3 按照优先级选择w_1 但w_1已有配对，择优选择m_2，m_3重新配对选择w_3，现有配对：m_1 leftrightarrow w_2,m_2 leftrightarrow w_1,m_3 leftrightarrow w_3]按照算法最后的稳定匹配为[m_1 leftrightarrow w_2,m_2 lef … 阅读更多

数字逻辑基础 1.1 绪论 1.1.1 模拟信号与数字信号 电子电路在接收或者处理电压或电流信号可分为模拟信号和数字信号两类。模拟信号：幅值在上限和下限之间连续，即幅值在上限和下限之间可以取任意实数值的信号。                 模拟信号可以是时间连续信号，也可以是时间离散信号。时间离散信号可以看成是对时间连续模拟信号采样得到的，也称作采样信号。数字信号：幅值的取值是离散的，即幅值被限制在有限个数值之内的信号。                 数字信号可以是时间连续信号，也可以是时间离散信号。数字信号具有保持和突变的特点，即数字信号在一段时间内保持高电平或低电平，而高                   电平和低电平之间的转化是瞬间的。  1.1.4 数字电路的优点 1.数字电路稳定，精度高 模拟电路精度较低，一般只有千分之一，需要数值较精确，例如5.5v和5.8v虽只差0.3v但元件可能工作在不同状态。而如果采用书籍加法器，电压值用二进制数表示，只要增加二进制数的位数就可以提高精度。如32位的数字加法器可以达到(1/2^{32})的精度。 2.数字电路易于设计和测试 3.数字电路可以实现十分复杂的算法 4.数字电路处理的数字信号易于保存 5.数字电路更易小型化和集成化   1.2 数制和码制 1.十进制 任何一个十进制数都可以用位置计数法及加权和的形式来表示[(D)_{10} = (d_{n-1} d_{n-2} cdots d_{1} d_{0} cdot d_{-1} d_{-2} cdots d_{-m} )_{10} = sum_{i=-m}^{n-1} d_i 10^i]式中n表示整数部分的位数；m表示小数部分的位数；(d_i) 是十进制数D的数码，表示(0 sim 9) 这十个数码中的一个；和式中数字10表示十进制的基数，决定了数码的个数；(10^i) 表示处于确定位置的数码(d_i)的权重。例如，十进制数123.45可以按照各数码的权重展开为：[(123.45)_{10} = 1 times 10^2 + 2 times 10^1 + 3 times 10^0 + 3 times 10^1 + 5 times 10^{-2}]十进制数有多种表达方式，例如123可以表示为((123)_{10})、((123)_D)、123D等形式，同样的 … 阅读更多