股价涨跌算法题

题目：股价一开始一块钱，然后股价涨一天，跌一天，涨两天，跌一天，涨三天，跌一天，以此类推，求第n天的股价。

根据题目绘制表格如下：

股价涨跌趋势

根据题目和表格观察规律，其中含有数列。假设没有跌，每天都是比昨天涨一块钱，那么股价肯定是等于n。实际上，股价是涨一天跌一天，涨二天跌一天，涨三天跌一天，涨四天跌一天，以此类推，可见跌的天序依次为3、6、10、15、21……，相邻数字相差依次为3、4、5、6……。

再继续观察股价和天序的关系，从10开始，往前观察。10以及前面总共有三次跌，那么4=10-2*3。9前面总共有两次跌，那么5=9-2*2，3以及前面总共有一次跌，那么1=3-2*1，1以及前面没有跌，那么1=1-2*0。其实所发现的这个方程式是合乎逻辑的，跌一次就少2，跌两次就少2的2倍，跌三次就少2的3倍，以此类推，因此当天的股价就是把n减去跌的天数的2倍。因此股价方程式为：price=n-2*m，其中m为跌的天数。

怎么得出跌的天数m？这是本题的难点了。前面我们观察到该题目有数列的规律，即股价跌于第3、6、10……天，这些数字有以下规律：

3=1+2
6=1+2+3
10=1+2+3+4

据此可推断，股价还会跌于第15、21、28天，因为，

15=1+2+3+4+5
21=1+2+3+4+5+6
28=1+2+3+4+5+6+7

那么，如何根据这样的规律计算得出跌的天数m？请看，

3=1+2      --- 1天
6=1+2+3    --- 2天
10=1+2+3+4 --- 3天

符合单调递增数列的累加和公式：sum=n*(n+1)/2，而我们要求的是n-1，但是，n不会总是3、6、10……此类数字中的一个啊，对此，我们可以采取向下取整的办法。比如，n等于4，最后经过向下取整，最后得出m等于1，又比如，n等于9，最后经过向下取整，最后得出m等于2。向下取整同样适用于3、6、10……之类的数字，比如n等于10，经过计算，m等于3，向下取整同样等于3。那么，我们可以得出方程式为：n=(m+1)*(m+2)/2，我们要求解的是m，因此该方程式变为：m=floor(sqrt(2*n+0.25)-1.5)，其中，sqrt表示取根，floor表示向下取整。

Okay，股价和第几天的关系，我们清楚了，不妨用Java将算法描述出来。

public class Stock {
    public static void main(String[] args) {
        int day = Integer.parseInt(args[0]);// 第几天
        System.out.println(calc(day));
    }

    public static int calc(int day) {
        int n = (int) Math.floor(Math.sqrt(day*2 + 0.25) - 1.5);// 跌了多少天
        int r = day - n * 2;// 股价
        return r;
    }
}