蓝桥杯-乌托邦树

传送门

题目描述

实现一个算法得到乌托邦树的高度,介绍如下：

乌托邦树每年经历 2 个生长周期。每年春天，它的高度都会翻倍。每年夏天，它的高度都会增加 1 米。 对于一颗在春天开始时种下的高 1 米的树，问经过指定周期后，树的高度为多少。

输入描述

输入一个数字 N (0≤N≤1000)，表示指定周期。

输出描述

输出一个数字，为经过指定周期后树的高度。

由于N的数值是0到1000，所以本来以为暴力过不了，结果居然过了。。
代码很简单

暴力解法

 import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
       int x = scan.nextInt();
       int sum = 1;
       int i ;
    
      for( i = 0; i < x ; i++){
        if(i % 2 == 0){
        sum = sum *2;}
        else{
        sum = sum +1;}
      }
        System.out.println(sum);
        scan.close();
    }
} 

这里应该采用java的高精度描述，以下是Java高精度描述的两种方式。

方式一

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //树的生长周期树
        int n=scan.nextInt();
        int h[]=new int[10000005];
        //树高度的位数
        int b=1;
        //树的高度初始值为1米
        h[0]=1;
        //如果flag为1则是春天，为0则是夏天
        int flag=1;
        while(n>0){
          //每年春天，树的高度会翻倍,将树的高度各位的数值乘以2，之后再进行进位处理
          if(flag==1){
            for(int i=0;i<b;i++){
            h[i]*=2;
          }
          flag=0;
          }
          else{
            h[0]+=1;
            flag=1;
          }
          //大于10的位数需要进位
          for(int i=0;i<=b-1;i++){
            if(h[i]>=10){
              h[i+1]+=(h[i]/10);
              h[i]%=10;
            }
          }
          if(h[b]!=0)
          {
            b++;
          }
          n--;
        }
        for(int i=b-1;i>=0;i--){
          System.out.print(h[i]);
        }
        scan.close();
    }
}

方式二

import java.util.Scanner;
import java.math.BigInteger;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //树的生长周期
        int n=scan.nextInt();
        //树的初始高度为1
        BigInteger h=new BigInteger("1");
        //如果flag为1则是春天，为0则是夏天
        int flag=1;
        while(n!=0){
          if(flag==1){
            //春天树的高度加倍，用add方法进行加法运算
            h=h.add(h);
            flag=0;
          }
          else{
            //夏天树的高度增加1米
            h=h.add(new BigInteger("1"));
            flag=1;
          }
          n--;
        }
        //输出结果
        System.out.println(h);
        scan.close();
    }
}