php 命令行下传参数

浏览数：20 / 时间：2015年06月09日

前言

最近阅读了Google黑板报的“数学之美”系列文章，加上最近工作和学习中接触了不少的算法最终都是由简单的数学公式或者定理解决了问题。我突发奇想地希望将我所知道的数学巧妙运用解决问题的实例记录下来。因此这篇博客诞生了，也希望我能够逐步地完善，并且写出一个系列的文章。话不多说，这篇文章就从引发我写下这篇博客的问题入手。

切饼问题

问题描述

假设我们有一个圆形的饼和一把刀。由于刀比较珍贵，刀的主人比较爱惜，因此要求我们尽可能的少用这把刀。但是我们希望能够将饼分给更多的人。总而言之，问题可以描述成，有这把刀沿直线在饼上切n刀，求出切完后饼的最大块数R[n]。

问题思路

要想解决这个问题首先，我们需要思考一些特例来得出一定的规律。如下图所示，第一刀只能将饼分为两块；第二刀可以与第一刀相交，并且将饼分为4块；以此类推第n刀可以与前n-1刀相交。

有了以上这个粗略的思路，我们需要额外的几个问题需要考虑或者证明：

1）是否第n刀总能与第n-1刀相交？由于线与线之间只有两种状态，即平行或相交。同时，相交的直线通过平移之后依然相交。所以我们可以通过平移相交的直线使之与饼内部相交。

2）已经切n-1刀以后，第n刀如何切割可以增加最多的块数。简单来说，我们是这寻找一条直线，通过这条直线的饼的子块最多。由于我们证明了第n刀可以和前n-1刀相交，而且显然只能各相交一次。前n-1刀在饼上某出最多可以分割出n-1+1块子块。

回答了以上的问题，我们就可以列出整个递归的规律了。

切割次数	最大子块个数	饼中某条直线上存在的最大子块数
0	1	1
1	2	2
2	4	3
3	7	4
4	11	5
5	16	6

用数学的表达式表示出来即，

最大子块个数用max_piece[n]表示，饼中某条直线上存在的最大子块数用max_piece_in_line[n]表示。非常容易推出通项公式为

max_piece[n]=max_piece[n-1] + max_piece_in_line[n-1]

max_piece_in_line[n] = n+1;

显然，我们已经可以通过递归或者动态规划的方式获得我们希望的答案。但是正如我前言中提到的，许多问题其实是能够有更加巧妙的数学方法的。因此，我们可以进一步的研究这个问题的数学通项公式。我们通过消除max_piece_in_line得：

max_piece[n]=max_piece[n-1] + n

进行简单变换，求出另一通项公式为：

a[n] = max_piece[n] - max_piece[n-1]=n

所以，a[n]+a[n-1]+...+a[1] = n+n-1+...+1 = (n+1)*n/2。并且a[n]+a[n-1]+...+a[1]=(max_piece[n] - max_piece[n-1]) + (max_piece[n-1] - max_piece[n-2]) +...+ (max_piece[1] - max_piece[0]) = max_piece[n] - max_piece[0]

因此，max_piece[n] - max_piece[0] = (n+1)*n/2。综上所述，max_piece[n] = (n+1)*n/2 + 1。