题目
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:
#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
题解
题目大意就是求斐波那契前缀和第N项的值的四倍。斐波那契数列本身有很好的性质,我们可以考虑如何变幻前缀和的项,而保证和不变
(1)
上述推导,表示了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)); } }