首页 > 专题系列 > Java解POJ > POJ 2680 Computer Transformation [解题报告] Java
2013
11-11

POJ 2680 Computer Transformation [解题报告] Java

Computer Transformation

问题描述 :

A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So, after the first time step, the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.

How many pairs of consequitive zeroes will appear in the sequence after n steps?

输入:

Every input line contains one natural number n (0 < n <= 1000).

输出:

For each input n print the number of consequitive zeroes pairs that will appear in the sequence after n steps.

样例输入:

2
3

样例输出:

1
1

解题代码:

(1)
//* @author import java.io.*; import java.util.*; import java.math.*; public class Main { public static void main(String[] args) { int n; BigInteger two,ans; Scanner cin = new Scanner (System.in); while(cin.hasNext()) { n = cin.nextInt(); two = BigInteger.valueOf(2); ans = two; if(n%2==0) { ans=ans.pow(n-1).subtract(two).divide(BigInteger.valueOf(3)).add(BigInteger.ONE); } else { ans=ans.pow(n-1).subtract(BigInteger.ONE).divide(BigInteger.valueOf(3)); } System.out.println(ans); } } }
(2)
import java.util.*; import java.math.*; public class Main{ public static void main(String[] args){ int n; BigInteger a[]=new BigInteger[1001]; a[1]=BigInteger.ZERO; for(int i=2;i<=1000;i++){ if(i%2==0) a[i]=a[i-1].multiply(BigInteger.valueOf(2)).add(BigInteger.ONE); else a[i]=a[i-1].multiply(BigInteger.valueOf(2)).subtract(BigInteger.ONE); } Scanner cin = new Scanner(System.in); while(cin.hasNext()) { n = cin.nextInt(); System.out.println(a[n]); } } }

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。