大整数问题一直很头疼，采用乘法原理的结果复杂度为$O(n^{2})$，最近看傅里叶变换有尝试用傅里叶变换加以改进。 设 $$ a=(a_{N-1}a_{N-2}…a_{1}a_{0}){10}=a{N-1}10^{N-1}+…+a_{0}10^{0}] [b=(b_{N-1}b_{N-2}…b_{1}b_{0}){10}=b{N-1}10^{N-1}+…+b_{0}10^{0} $$ 两个式子的乘积 $$ c = ab = c_{2N-2}10^{2N-2}+c_{2N-3}10^{2N-3}+…+c_{1}10^{1}+c_{0}10^{0} $$ 其中 $$ c_{k}=\sum_{i+j=k}a_{i}b_{j},(i=0,…,N-1) $$ 这种算法的时间复杂度为$O(n^{2})$。 逆天的是，${c_{k}}$居然逆天的等于${a_{k}}$和${b_{k}}$点的卷积。我们知道，卷积可以通过傅里叶变换的方式转化为普通乘法（函数卷积的傅里叶变换是函数傅里叶变换的乘积）。 于是，我们有： （1）求${a_{i}}$和${b_{j}}$的傅里叶变换（离散）${A_{i}}$和${B_{j}}$ （2）${A_{i}}$和${B_{j}}$逐项相乘得到${C_{k}}$ （3）对${C_{k}}$求傅里叶逆变换，得到${c_{k}}$ （4）进位，出结果 对复向量${x_{N-1},…,x_{1},x_{0}}$，离散傅里叶变换为： $$ X_{k}=\sum_{n=0}^{N-1}x_{n}e^{\frac{-2i\pi nk}{N}},(k=0,…,N-1) $$ 逆变换公式为： $$ x_{k}=\frac{1}{N}\sum_{k=0}^{N-1}X_{k}e^{\frac{-2i\pi kn}{N}},(n=0,…,N-1) $$ 例： 三位数（$N=3$）$a=456,b=987$，求c=ab。 结果为：c=450072。共 6 位数字，$N$扩展到$2^3 = 8$。 $$ { a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0 } = { 0, 0, 0, 0, 0, 4, 5, 6 } $$ $$ { b_7, b_6, b_5, b_4, b_3, b_2, b_1, b_0 } = { 0, 0, 0, 0, 0, 9, 8, 7 } $$

队列作为允许在前段删除和后端插入得线性表，和栈类似，是一种操作受限制得线性。进行插入操作的端称之为队尾，进行删除操作的端称之为队头。队列中没有元素时，称之为空队列。尽管操作受到限制，但是仍然具有使用价值，如可以利用队列结构编写消息队列处理消息，利用队列结构编写内存池时可以将可用内存区块加入一个队列中等待使用，等等。 这次实现的模版链队本质上仍是链表，这次的队列没有首节点，队列中全部元素均为队列中的成员。代码中注释了一个迭代器，是测试代码时候写的。 p.s.可以考虑重载[]来实现队列中的数据访问。。当然这是后话了。。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 // // Queue.

栈只具备入栈和出栈的性质，实现起来较为简单，其本质还是链表，只不过限制了任意节点的访问权限，因此栈不具备迭代器的功能。代码中注释了一个迭代器，是测试代码时写的，迭代效果略有Bug，访问数据会多访问到一个，但不影响栈本身的功能，无视就好～ p.s. 可以考虑重载[]来实现栈中的数据访问。。当然这是后话了。。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 // // Stack.

本文希望通过下面这个简单易懂的例子来阐述数学家们为何要将流形理论定义的晦涩以及流形背后的深刻含义，文中一些关键性的概念附上了wikipedia链接，方便快速回忆起它们。 学过定积分的同志们都知道，定积分可以求旋转体的体积，比如圆锥。 学过多元积分的同志们也都知道，求圆锥体积的时候可以用截面圆面积沿圆锥高度变化函数的积分。 到底什么是体积，为什么这两种求法的结果总是相同的？这里博主就介绍一下一般形式对体积计算。 首先，我们需要理解流形的概念。流形是可以类比到$n$维欧式空间的拓扑结构，流形上的每一个点都可以映射到欧式空间中。 我们通常意义上的建立空间直角坐标系，就是将一个几何体一一映射（双射）到了一个三维的欧式空间。把问题转化到欧式空间中是因为欧式空间有很多优良的性质，具体就不阐述了，可以在这个链接中查到相关知识，如果觉得不过瘾可以切换到英文版查看更为详尽的描述。 早期数学家们关心将点集映射到欧式空间中表现出的各种性质，后来数学家们才注意到，研究他们之间的映射会从深层面来揭示这些优良性质产生的原因。 我们知道，直角坐标到柱坐标之间的转化有公式（本质是映射$\phi$）： $$ \begin{equation} \rho = \sqrt{x^{2}+y^{2}} \end{equation} $$ $$ \begin{equation} \theta = \begin{cases} 0 & \mbox{if x = 0 and y = 0}\ \arcsin\left( \frac{y}{\rho} \right) & \mbox{if x > 0 or x = 0}\ -\arcsin\left( \frac{y}{\rho} \right) + \pi & \mbox{if x < 0} \end{cases} \end{equation} $$ $$ \begin{equation} h=z \end{equation} $$ 这个映射在三维欧式空间中几乎处处无穷可微，它的逆映射$\phi ^{-1}$可以更加方便的计算各阶微分： $$ \begin{equation} x = \rho \cos\theta,y = \rho \sin\theta,z = h \end{equation} $$

美国立国至今二百余年，The chief business of america is business，商业繁荣至今，有种东西居功至伟，也就是所谓的“Entrepreneurship”。影片中的乔布斯偏激、疯狂、固执、冷静、不顾一切、毅然决然。他专注于自己的事业，对自己努力的一切有着近乎宗教式的狂热，他执着于冒险，疯狂开拓，无所畏惧。乔布斯如今已经成了一个象征，这个改变了世界的科技天才，和某种意义上的精神领袖，因为乔布斯设计理念的哲学和美学已经深深影响了一批人，这种影响小到审美品位大到创意理念和生活哲学，这种影响是深远的，也正是因为乔布斯，设计变得无比重要。 流传这样一种说法，上帝在人间投掷了三个苹果，第一个诱惑了夏娃，第二个砸醒了牛顿，而第三个则留给了乔布斯。只有乔布斯，才能在让苹果在97年时不足14美元的股票上涨到现在，成为一个奇迹，成就了历史上绝无仅有的拯救行动；让创新的灵感得以体现在产品上，在细节上偏执的追求；拥有过人的营销本领，只要他弄懂了一个东西，都能以最简单的方式介绍给普通人听；在追求梦想和事业的鼎盛中奔驰，他的奇迹是没有人可以复制的、没有人能超越的。 天时、地利、人和。乔布斯身处崛起的时代，加之乔布斯的创新天分是无人能及的，他大胆的设想、与众不同的管理，缔造了苹果神话。影片极力表现了一个偏执狂人造就企业神话，乔布斯违背了所有管理手册的教条，违反了身为一个管理者应该真诚、体贴、谦虚、放权、在乎员工的感觉和用户的需求。但是，乔布斯总能深刻的洞察人性，即便他无可理喻到在电梯内看员工不顺眼就将其开除。在回归苹果公司后更加展露，回归苹果后的乔布斯重整了董事会，重新将苹果走向巅峰。 乔布斯在斯坦福大学毕业典礼上这么说道：你的时间有限，所以不要为别人而活，不要被教条所限，不要活在别人的观念里，不要让别人的意见左右自己内心的声音。最重要的是，勇敢地去追随自己的心灵和直觉，只有自己的心灵和直觉才知道你自己的真实想法，其他一切都是次要。牛顿亦云：站在巨人的肩膀上。我们时常告诫自己应该怎么做或者不该怎么做，不要走别人的错路。这并不意味着我们每个人都必须成为一个个墨守成规，有原则的人。 最后，苹果的“Think Different”或许正描述了乔布斯的一身： Here’s to the crazy ones. The misfits. The rebels. The troublemakers. The round pegs in the square holes. The ones who see things differently. They’re not fond of rules. And they have no respect for the status quo. You can quote them, disagree with them, glorify or vilify them. About the only thing you can’t do is ignore them.

今天听说反转单链表，于是博主就自己想了想。 顾名思义，反转单链表，就是让一个单链表反向。 反转一个单链表，最容易想到的思路就是： 方法一 牺牲空间。 此方法没什么可说的，直接创建一个新的链表，倒序将上一个链表的各个节点拷贝到新链表中，并释放原链表。值得注意的是，如果直接拷贝各个节点，显然复杂度较高，因为拷贝最后一个节点时需要先指向最后一个节点，而指向最后一个节点是需要话时间的。因此可以先开辟一个lenth()长度的数组，将各节点先存入数组中，再使用反序索引来创建新的反转单链表。 接下来容易想到的方法则是使用三个节点指针来进行操作。 ##方法二 先让两个节点指针p和q配合使两个节点的指向反向，同时用current记录剩下的链表。博主以前曾实现过一个模版链表，因此就在此基础上继续完善该链表。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 template <class T> void Chain<T>::reversal() { ChainNode *p = head; ChainNode *q = head->next; ChainNode *current; head->next = NULL; while(q){ current = q->next; // current用于纪录剩余的链表 q->next = p; p = q; q = current; } head = p; // 记得修改head，否则按head输出仅输出了最后一个节点 } 继续思考，发现其实可以不用这么麻烦，如果从第2个节点开始，依次将节点插入到头节点之后，最后将第一个节点插到表尾。

设 $$ P={ { x_{k} } = (…,x_{-2},x_{-1},x_{0},x_{1},…):x_{i}\in R} $$ 表示双向无穷实数列集合，按分量自然的定义$P$中的向量加法与数乘，则$V$构成一个无穷维为实线性空间。在实际中我们一般称$P$为离散时间信号空间。 对于信号空间$P$的一个子空间（平方可和子空间）： $$ \begin{equation} l_{2}=\left{ {x_{k}} \in P : \sum_{k=-\infty}^{+\infty}x_{k}^{2} < +\infty \right} \end{equation} $$ 是一个无线维的内积空间，其中的内积是自然定义的，即： $$ \begin{equation} \left( {x_{k}},{y_{k}} \right) = \sum_{k=-\infty}^{+\infty}x_{k}y_{k} \end{equation} $$ 于是两个离散信号${x_{k}}$与${y_{k}}$正交$\Longleftrightarrow \sum_{k=-\infty}^{+\infty}x_{k}y_{k} = 0$ 而在实际中，当所有用户共享整个频率信道，不同用户被分配至不同的时区，并且不同用户的通信信号在时域上没有任何重叠，即若以${x_{k}}$与${y_{k}}$分别表示两个不同用户的通信信号，则$x_{k}y_{k}=0,\forall k$（此时由向量${x_{k}}$与${y_{k}}$生成的子空间不但相交为0，而且还是正交的），因此${x_{k}}$与${y_{k}}$正交。这就是在通信信号中信号正交性起到的关键性作用。

这几天到了申请奖学金的日子，才逐步意识到一个人什么都不懂完全靠厚脸皮也可以混到不错的位置。当然这句话里面并没有暗含说我懂得如何如何多，这点不能误解。其实总结起来就是一句话，论人际交往的重要性。 拿我一个队友来说，确实是什么都不会的渣渣，完全靠厚着脸皮什么都不会，上个学期信誓旦旦说什么坚持到最后总会有回报，实际上这家伙仅仅只是为了学习而学习，脸皮厚到把书抄了一遍甚至完全不思考过也敢说“我特么学完了”，学完考完过后再也不会花一丝心思在知识的拓展和回顾上，第二个学期开学回来之后好像很有成就感的在朋友之间炫耀，你们还会C语言么，我完全记不得了，当然这么做不怪他，毕竟你转专业了，没必要再在你身上浪费时间。 可恨的是，我居然对特别傻逼的好像对他抱有一丝希望似的让他混到了我的数学建模队伍，在队里他没有发挥任何关键性的作用，白天午觉睡一个下午，晚上十二点以后必须睡觉，早上八点才起床。在机房做题的三天，我三天都没有回寝室。对我而言，他就是那种吃不了苦而且也不努力的队友，这种队友在队里面完全就是吃干饭混奖的，任何人都有功力心，只是程度不同罢了，你干了实事，和你共事的人绝对不会有半句怨言，必定会和你分享共同的荣耀。 我做自己的事，我写自己的字，简简单单的喜欢，不需要那么多的评论。这段文字结束后，这段话很快就会被人遗忘，世界还会是原来的模样，不爽的还会继续不爽，懂我的人，嘴角依旧那样上扬，只希望朋友们坚持信仰。 浸着汗水的作品，你们尽数拿去，虚荣到底有什么意义，苦短人生，还有太多正事要我去完成，保持沉默因为懒得同你们争论。谁说人不分三六九等，想要我反驳，请先掂量掂量掂量你自己的身份。作茧自缚，践踏自尊，我坐在观众席笑看，尔等的愚笨。

Created by 欧 长坤 & 郭 瞾阳 & 黄 沐 on 13-9-16. Copyright (c) 2013年 欧 长坤 & 郭 瞾阳 & 黄 沐. All rights reserved. 摘 要 碎片化程度不同的碎纸片，其复原难度各有不同。好的复原筛选算法有效的帮助人们减少复原的时间，提高复原的效率。 针对三个问题中复原碎纸片的难度递进关系，本文同样建立了具备递进关系的三个数学模型，并给出其算法。分别为信号相似性算法、边界积分匹配算法和行距匹配算法。针对复原文件的特性，本文将碎片的复原过程分划为三个独立的代码模块，分别为整行筛选模块、整行拼接模块和各行拼接模块。每个模块适当组合使用三个算法，达到精准筛选与匹配。 在问题一中，由于附件1和附件2所提供的待复原图片数量较少，因此直接采用信号相似性分析，来拼接待复原的图片，拼接结果显示，拼接的匹配率达到100%，无需人工干预。 在问题二中，随着碎片数的增加，为了减小拼接问题的复杂度，先筛选出整行碎片，则将该问题转化为问题一进行研究。而整行筛选的方式，中文碎片和英文碎片的处理方式上有细微差异。对于中文碎片而言，采用了行距分析算法等，半自动化的完成了整块碎片文件的拼接，其间人工干预3次。对于英文碎片而言，实际拼接过程中直接使用信号相似性算法来筛选整行更为有效，匹配率为84.21%，完成整块209张图像碎片拼接只需人工干预33次。 对于更复杂的双面碎片问题三而言，综合运用了三个模块进行全面筛选匹配，将匹配率优化为63.31%，完成整个518张图像碎片的拼接复原需要人工干预95次。 关键词： 一维信号, 相似性分析, 边际积分, 行距提取, OpenCV 限于篇幅，下面谈谈摘要中提到的核心模块和核心算法。 一维信号相似分析模型 文[1]对于测量信号$x(t),y(t)$,使用了Hilbert空间上的内积理论获得了对两个信号的相似性判定的衡量方法。设$x=[\xi_{1},\xi_{2},…]$和$x=[\eta_{1},\eta_{2},…]$为两个离散信号，为使能量误差 $$ \begin{equation} Q=\Vert x-\lambda_{0}y\Vert ^{2}=\sum_{n}(\xi_{n}-\lambda_{0}\eta_{n})^{2} \end{equation} $$ 只需要令$\frac{dQ}{d\lambda_{0}}=0$，得到 $$ \begin{equation} \lambda_{0}=\frac{\sum_{n}\xi_{n}\eta_{n}}{\sum_{n}\eta_{n}^{2}} \end{equation} $$ 此时对应的最小能量误差为 $$ \begin{equation} Q_{min}=\sum_{n}(\xi_{n}-\lambda_{0}\eta_{n})^{2} = \sum_{n}\xi_{n}^{2} - \frac{\sum_{n}\xi_{n}\eta_{n}}{\sum_{n}\eta_{n}^{2}} \end{equation} $$ 而最小相对能量误差为：

自从大一第一个学期末的时候买了iPhone 5，逐步对苹果这个公司有了不同的看法。之前对苹果整个公司的看法，都停留在最初级的道听途说。在为期几个月的iPhone使用中发现，苹果的产品确实做得好。因此第二个学期就开始筹划购买MacBook相关事宜了。 购买MacBook之前一直都很担心是否在Windows上面的我必须的生产工具在Macintosh上是否也有，直到这个学期拿下MacBook后才解除了这个疑惑。Macintosh确实是最先进的操作系统，没有之一。 在Windows上，我的需求不多，早期的时候还未接触编程，因此需求工具不多，也就几个数学类的软件，大学后详细接触了编程，于是需求软件一下子就多了起来。下面我把我所有的需有都罗列在下，以备使用。 Maple（数学三剑客之一） Mathematica（数学三剑客之一） Matlab（数学三剑客之一） Lingo（可惜没有Mac版本） 几何画板（很好终于有了Mac版本） Chrome（全套Google服务不说了） Visual Studio（Windows上必备） Microsoft Office（Windows上必备） Goagent（翻墙必备） QQ（这个就不说了） 有道云笔记（一开始接触的就是有道的云笔记，重要的是它和一些帐号绑定全套服务会方便很多。） 迅雷（不说了） 百度云（百度真的很有钱，） WPS（可惜没有Mac版本，否则就真的能彻底抛弃Windows了） Adobe系列（Photoshop、Aftereffect、Audition、Premier Pro） 有道词典（英语渣也就不说什么了） Xcode（在Mac下取代了Visual Studio，重要的是它是免费的。） iWork（在Mac下取代了Microsoft Office。） Wireshark（抓包什么的还是很有用的。） Evernote（印象笔记，多平台通吃，最近几年挂起来的这阵风是好的，软件多平台通吃，给用户以最大体验。） MPlayerX（自带播放器解码还是不行，必须有一个强大的后盾） VirtualBox（开源的，比VMware好的感觉） MathType（Mac版本的Office没有自带MathType，幸运的是Mathtype有Mac版本）