csuoj-算法-Hanoi双塔问题

题目

解题思路

当有一个圆环时，需要移动1次。
当有两个大小不同的圆环时，需要移动3次。
当有三个大小不同的圆环时，将上面两个圆环看做一个圆环，按照两个圆环的方式进行移动。
可推出递推式：T(n)=1+2*T(n-1)

Java代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        BigInteger bigInteger1 = new BigInteger("1");
        BigInteger bigInteger2 = new BigInteger("2");
        BigInteger ss = bigInteger1;
        BigInteger ans = ss;
        for (int i = 1; i < n; i++) {
            ans = ss.multiply(bigInteger2).add(bigInteger1);
            ss = ans;
        }
        System.out.println(ans.multiply(bigInteger2));
    }
}