Codewars Java练习：Perimeter of squares in a rectangle

题目

The drawing shows 6 squares the sides of which have a length of 1, 1, 2, 3, 5, 8. It’s easy to see that the sum of the perimeters of these squares is : 4 * (1 + 1 + 2 + 3 + 5 + 8) = 4 * 20 = 80

Could you give the sum of the perimeters of all the squares in a rectangle when there are n + 1 squares disposed in the same manner as in the drawing:

alternative text

#Hint: See Fibonacci sequence

#Ref: http://oeis.org/A000045

The function perimeter has for parameter n where n + 1 is the number of squares (they are numbered from 0 to n) and returns the total perimeter of all the squares.

perimeter(5)  should return 80
perimeter(7)  should return 216

1 2	perimeter(5) should return 80 perimeter(7) should return 216

题解

题目大意就是求斐波那契前缀和第N项的值的四倍。斐波那契数列本身有很好的性质，我们可以考虑如何变幻前缀和的项，而保证和不变

(1) $\begin{align*} &1+1+2+3+5+8+13+...+fib(n-1)+fib(n) \\ =&2+5+13+..+fib(n-2)+fib(n+1) \\ =&(-1)+1+2+5+13+...+fib(n-2)+fib(n+1) \\ =&(-1)+fib(n)+fib(n+1) =&fib(n+2)-1 \end{align*}$

上述推导，表示了fibonacci数列的前缀和恰好是一个fibonacci数列-1的数列。

import java.math.BigInteger;

public class SumFct {
	public static BigInteger perimeter(BigInteger n) {
    int _n = n.intValue();
    BigInteger x = BigInteger.valueOf(1);
    BigInteger y = BigInteger.valueOf(2);
    BigInteger _x = null, _y = null;
    for (int i=0;i<_n;i++) {
      _x = x;
      _y = y;
      y = _x.add(_y);
      x = _y;
    }
    return y.subtract(BigInteger.valueOf(1)).multiply(BigInteger.valueOf(4));
	}
}

import java.math.BigInteger;

public class SumFct {

public static BigInteger perimeter(BigInteger n) {

int _n = n.intValue();

BigInteger x = BigInteger.valueOf(1);

BigInteger y = BigInteger.valueOf(2);

BigInteger _x = null, _y = null;

for (int i=0;i<_n;i++) {

_x = x;

_y = y;

y = _x.add(_y);

x = _y;

}

return y.subtract(BigInteger.valueOf(1)).multiply(BigInteger.valueOf(4));

}

题目

题解

发表评论 取消回复

发表评论取消回复