记录一次有趣的数学题

发表于 | 分类于 | | 阅读次数

记录一次有趣的数学题

前言

我本人数学水平极差，就是一个概念都要思考半天的人。但是很可惜我喜欢数学。我也很喜欢编程和算法。所以如果有什么工作是结合算法、数学和编程的我一定很喜欢。我知道很多大学生和研究生的作业题就是这样。于是我很乐意去动动我已经成白痴的脑子来尝试看一下。我已经工作了，于是乎心态和你们或许有很大不同。你们或许觉得很恶心因为你们不得不去做，我仅仅是觉得好玩慢慢的思考。
但是不代表我就比你们幸运哦。

问题描述

有一个函数f(x)对一组不重复的列表进行全排列（使用递归）。设这个类别中元素的个数是N个，于是我们定义计算递归函数f(x)调用次数的函数叫做F(n)。那么现在求下面这个公式的值：

解

现在可以看出来这个题目分两个部分，其一是要知道这个程序怎么写，然后是算出F(n)的公式。之后辨识一个球极限的数学问题。于是我们先看看这数学问题。

编程问题

全排列吗？我们可以轻易的看出来全排列是一个递归的过程。
想想我们人类手动全排列的时候是怎么思考的。我们先确定第一位数字是什么。那么这个排列需要知道剩下的（n-1）个数据的全排列，和第一个数组成新的排列。这样把每个数据都当成第一个元素一遍就可以得到所有的排列。
（看看下面的伪代码） 

1
2
3
4
5
6
7
8
9
10
11
12
13
这里认为 A是全排列的函数  
list是一个有n个元素的列表
function A(list){
//如果列表的长度是1就返回他本身
    if(list.length==1):
       return list
    
res = [];//保存结果的变量
// 对
foreach(obj on list):
    tmp = [obj : A(list without obj)] //注意这里表示 由obj 和 除了obj的list剩下的元素的全排列组成的新的排列的集合
    res->push(tmp)
return res;

相信编程能力很好的你。可以看出来我这里对于变量的表示不严谨，但是没有关系，这部妨碍我们理解这个递归的原理。和下一步进行解题。明白了为什么全排列是一个递归之后，我们便关心其中的这个解构就好了。我抽象出来如下。 

1
2
3
4
5
6
7
8
9
//这里认为react是一个根据自然数n生成升序列的函数 比如  
// react(5) => [1,2,3,4,5] n也表元素的个数
// 现在用react(5)-[2]表示 除去2这个元素 react(5)-[2] => [1,3,4,5] 显然它的元素个数是n-1
function a(react(n){
   for(react(n) as index=>value){//表示索引加上值
      则需要的排列
      value + a( react(n) - value);//注意这个也是一组排列
   }
}

可以看出来开始的时候有n个循环调用了n次函数a。然后每个调用又要循环n-1次。那么第二层的调用就有多少呢？n(n-1)。第三次就是n(n-1)(n-2).于是要求这些数的和。最后一个是多少呢？好好想想！，最后的结束条件是列表长度变为1。那么表示最后每个前一级调用了一次。于是n(n-1)(n-2)…(n-(n-1))也就是n！。哈哈那么这个公式是不就清晰了呢？

开始算吧少年。

数学问题

这其实已经很简单了。为了方便我们把公式抄一遍：

现在看看分数符号上方的部分。

我们看看n怎么表示呢。$ n = \frac{n!}{(n-1)!} $ 使用这个公式来替换就会有一个有趣的现象发生了。

注意这里下面还除以了一个n!呢！现在正好可以和分母的n!消掉。ok看看下面的公式

这个是啥呢？？ 你还没有看出来吗？？好吧同学我换一个顺序。

也就是

哦是不是似曾相识的感觉，这个数是什么？ 是自然常数 e。

我开始得到这里的时候就方了。还在想这个数是多少呢！看这个格式还以为是泰勒公式的逆运算。结果查了好久，算了好久，才发现这个数是e。哎~~老了。

传送门

自然常数

我将一直迷惑和无知，我是黄油香蕉君，再见。

给作者买杯咖啡吧。喵~