传送门
题目描述
实现一个算法得到乌托邦树的高度,介绍如下:
乌托邦树每年经历 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();
}
}