IT牛人博客聚合

要说起RSA算法的话就不得不提欧拉这个伟大的数学家，他在数学的很多方面都有很多研究，而RSA也正是基于他在数论上的欧拉公式才建立起来的。欧拉公式稍后再说，先简单说一下公钥密钥的非对称算法的概念，平常我们用的加密算法往往都是对称的，也就是说加密密钥和解密密钥是一样的，比如凯撒密码，你把每个字母后移3位，a变成d，b变成e，这里3就是加密密钥，然后解密的时候前移3位，这时候3就是解密密钥，非对称加密顾名思义就是加密密钥和解密密钥是不同的，恩，数学就是能干很多神奇的事情啊。

数论在很长的一段时间里被认为是没用的，纯数学的，优美的理论，一直到1976年。当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人提出了公开密

查看全文: http://www.udpwork.com/item/7123.html

在计算机科学里，有时间复杂度的概念，然后就有P,NP,NPC,NP-hard的概念，平常大家说的这个题是np的，只能搜了，其实是理解错了np的概念，首先要明确np并不是“不是p”的意思，p大家都清楚是指有多项式时间的算法，而np看全称是“nondeterministic polynomial time”，是说非确定多项式时间，进一步说，正如图片上说的p是属于np的，所有p问题都是np问题。

ok，下面仔细说一下，按照官方的解释呢
p是指在多项式时间能由确定型图灵机解决的问题
np是指在多项式时间能由非确定型图灵机解决的问题
确定型图灵机可以理解为就是按照某种固定的算法，一步步求出解的程序，而非确定型图灵机其实是概念上的，他的

查看全文: http://www.udpwork.com/item/6876.html

    数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 Fn ，那么有：

      Fn+1 · Fn+1 - Fn · Fn+2 = (-1)n

    今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。

 

查看全文: http://www.udpwork.com/item/6747.html

假设有这么一个网站，它的userid是从1开始依次递增(step=1)，我们想知道这个网站有多少用户，那么最简单的方式就是，马上去注册一个新用户，然后看看userid是多少。假设这个方法不可行，比如，这是一个需要邀请才能注册的论坛。我们只能从这个论坛的帖子中，提取userid，来估计。那么该怎么估计？

假设用户的总数为N，那么userid的取值范围就是[1,N]。假设我们取到n个样本，这n个样本的userid的最大值是maxU,最小值是minU，那么用maxU估计N行不行？当然可以。但是毫无疑问，maxU肯定是小于等于N的，那么到底小多少呢？如何从样本中把这个差值估计出来？假如我们把样本的userid按照从小到大排列，可以得到下面

查看全文: http://www.udpwork.com/item/6689.html

看到网上一些对于md5的介绍还有对于当初王小云所做的破解有很多的误解，或者说不理解，然后觉得对于这些事情只要说明白还是比较好理解的说。

首先md5其实就是一种hash，或者叫散列函数，有的地方叫杂凑函数，都是一个东西啦，其实他就是一种映射，而平常最常见的就是说md5是不可逆的，为什么不可逆呢，有人就说就是像有些函数没有反函数那样了，其实还是有点抽象，考虑md5是多对一的映射，也就是说很多不同的经过md5变换之后可能会是相同的，那么既然多对一，自然是不可逆啦╮(╯▽╰)╭，你怎么会知道他到底是由哪个变换过来的呢。在密码学的应用里，说是单向函数，或者说单向变换，一种是这种多对一不可逆，还有一种是说逆工程会非常困难，举个例子吧，假设f

查看全文: http://www.udpwork.com/item/6638.html

    有一个正方形的房间，房间的四壁都是镜子。房间里有一个天使和一个恶魔。假设房间是一个单位正方形 [0, 1] × [0, 1] ，那么天使和恶魔便是这个正方形内的两个点 (a, b) 和 (c, d) 。恶魔想要在原地发射致命激光杀死天使（激光可以无限地在镜子间反射）。天使可以根据恶魔的位置，预先在房间里放置一些守卫为自己挡住激光（守卫实际上也是一个个点）。当然，天使可以在自己周围密密麻麻地放一圈守卫，围成一个封闭的圆形，从而让恶魔不管朝什么方向发射激光，最终都无法击中天使。我们的问题是，能把守卫的数量减少到可数个点吗？能把守卫的数量减少到有限个点吗？

  &nbs

查看全文: http://www.udpwork.com/item/6521.html

    在集合 {1, 2, ..., n} 中选出尽可能多的子集，使得每个子集所含的元素个数都是奇数，但是任意两个子集的交集都含有偶数个元素。那么，我们最多能够选出多少个这样的子集来？

    容易看出，我们至少可以选出 n 个子集。例如，当 n = 4 时， {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗？简单地尝试后，你会觉得似乎不行。不过，这却并不是显然的，因为存在一些不那么平凡的方案，也能让子集的数量达到 n ，例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4}

查看全文: http://www.udpwork.com/item/6291.html

    这是我前几天看到的一个视频。毫无疑问，它是我所见过的各种生命游戏构造中最神奇的一个：

      

    在 LifeWiki 中有一个词条详细介绍了这个构造：它叫做 OTCA metapixel ，是由 Brice Due 在 2005 至 2006 年间构造的。其中，每一个 metapixel 的大小为 2048 × 2048 ，周期为 35328 。

 

视频出处：http://www.youtube.com/watch?v=QtJ77qsLrpw

查看更多：

查看全文: http://www.udpwork.com/item/6280.html

    网友 @ipondering 分享了一个非常精彩的数学趣题集，里面有很多我之前从没见过的趣题，其中有些问题的题目和解答都相当漂亮。近段时间里，我打算从中选一些最精彩的题目来讲讲。今天的题目是该趣题集中的第二题，原题背景涉及到 King Arthur 和 Merlin 的故事，我就舍去简化了。

    某个国王手下有 n 个大臣。国王定期主持国家会议，届时 n 个大臣将会间隔均匀地坐在圆桌上。每个座位前都有一盏照明灯，只有所有的灯都亮了，会议才能开始进行。如果有些灯没亮，国王会下达指令，让指定位置上的大臣按下座位前的灯的开关，把没亮的灯都打开。例

查看全文: http://www.udpwork.com/item/5994.html

恩，上图就是大名鼎鼎的莫比乌斯环，估计大部分人听到莫比乌斯这个名字首先想到的是这个吧，不过和今天讲的Möbius inversion，即莫比乌斯反演没有多大关系，不过他们都是指的一个人，德国数学家、天文学家莫比乌斯。那下面我们就来说莫比乌斯反演了。

当初看到这个东西的时候，应该是在一本组合数学书上看到的吧，当时只见到公式非常的犀利，还在迷糊的情况下，套公式做了几个题，真是非常的囧啊。话说莫比乌斯怎么高深的名字是什么东西呢，浅显一点说，其实就是容斥原理！
容斥原理应该都很清楚的吧

假设我们要求P(A∪B∪C)，但是我们现在只知道P(A)，P(B)，P(c)，那么P(A∪B∪C)=P(A)+P(B)+P(C)-P(A∩B)-(B∩

查看全文: http://www.udpwork.com/item/6397.html

    数学之美不但体现在漂亮的结论和精妙的证明上，那些尚未解决的数学问题也有让人神魂颠倒的魅力。和 Goldbach 猜想、 Riemann 假设不同，有些悬而未解的问题趣味性很强，“数学性”非常弱，乍看上去并没有触及深刻的数学理论，似乎是一道可以被瞬间秒杀的数学趣题，让数学爱好者们“不找到一个巧解就不爽”；但令人称奇的是，它们的困难程度却不亚于那些著名的数学猜想，这或许比各个领域中艰深的数学难题更折磨人吧。

    今年年初时，我曾经写过一篇名为 千万别学数学：最折磨人的数学未解之谜 的文章，选取并翻译了 Mathematical Puzzles

查看全文: http://www.udpwork.com/item/5952.html

话说你看到这幅图是不是感觉很坑爹啊，这不是连分数吗，怎么会跟期望问题有关咧，其实吧，在一些可能会出现无限步骤的求期望的问题中，他们的思想还是有些类似的。

先看这个连分数的求法，略去1+1/的那部分看剩下的，假设剩下的是x那么整个式子是=1+1/x的，那么x=2+1/x，然后解一个一元二次方程，然后这个式子显然是正的啊！所以x=1+sqrt(2)，最后求得答案是1+1/x=srqt(2)

下面来看这个期望问题，从A退出的概率是1/2，从A到B的概率是1/2，从B退出的概率是1/2，从B到A的概率是1/2，问从A到退出期望会走几步，也就是说平均走几步才能出去。
标准的做法是用每一个的步数乘以概率然后加起来，就是0*1/2+1*(1

查看全文: http://www.udpwork.com/item/6398.html

    今天听说了 Conway's Soldiers ，这是 Conway 大牛在 1961 年提出的一个数学谜题（似乎 Conway 的出镜率也太高了），我觉得非常有意思，在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面。

    假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子（就像孔明棋一样）。这是棋子的唯一一种移动方式。现在，在某个位置画一条无限长的水平线，你需要在水平线下面放置足够多的棋子，使得它们前仆后继地往水平线上方跳，最终能够跳到水平线以上 n 个单位的位置。

查看全文: http://www.udpwork.com/item/5782.html

    这次的趣题来源于 UyHiP 今年八月份的谜题：概率均等地随机选取一个恰好含有 n 个 0 和 n 个 1 的 2n 位 01 串，这个 01 串平均会有多少个 0 和 1 个数相等的前缀（包括空串和整个串本身）？

    为了叙述简便起见，下面我们把所含 0 和 1 个数恰好相等的 01 串叫做平衡的 01 串。例如， 010010110011 就是一个平衡 01 串，它有四个平衡前缀，空串、 01 、01001011 以及整个 01 串本身。我们需要求出的就是，任取一个长为 2n 的平衡 01 串，平衡前缀的个数的期望值是多少。

&nbs

查看全文: http://www.udpwork.com/item/5752.html

    在一篇老日志中，我提到了一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续两个正面？它的答案是 6 次。它的计算方法大致如下。

    首先，让我们来考虑这样一个问题： k 枚硬币摆成一排，其中每一枚硬币都可正可反；如果里面没有相邻的正面，则一共有多少种可能的情况？这可以用递推的思想来解决。不妨用 f(k) 来表示摆放 k 枚硬币的方案数。我们可以把这些方案分成两类：最后一枚硬币是反面，或者最后一枚硬币是正面。如果是前一种情形，则我们只需要看前 k - 1 枚硬币有多少摆法就可以了；如果是后一种情形，那么倒数第二枚硬币必须是反面，因而

查看全文: http://www.udpwork.com/item/5633.html

    这道题的答案有几个字母？答案：four。

    有趣的是，这是唯一的答案。如果令函数 f(n) 表示非负整数 n 的英文表达中有多少个字母（不算空格和短横线）， n=4 是该函数的唯一不动点。

       n    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …

      f(n)  4, 3, 3, 5, 4, 4, 3,

查看全文: http://www.udpwork.com/item/5612.html