c++ - "Utopian Tree"如何解决

Question

乌托邦之树每年经历 2 个生长周期。第一个生长周期发生在 Spring ，此时它的高度增加了一倍。第二个生长周期发生在夏季，当它的高度增加 1 米时。

现在，一棵新的 Utopian Tree 树苗在 Spring 来临之际被种下。它的高度是1米。你能求出 N 次生长周期后树的高度吗？

#include <iostream>
using namespace std;

int height(int n) {
    int h[61],i;
    h[0]=1;

    for(i=1;i<61;i++)
       { if (i%2!=0)               
           h[i]=h[i-1]*2;            
        else h[i]=h[i-1]+1;
}
    cout<<h[n];

    return 0;
}
int main() {
    int T;
    cin >> T;              
    while (T--) {
        int n;
        cin >> n;
        cout << height(n) << endl;
    }
}

Answer 1

这里有一个简单的解决方案，可以避免过多的计算。注意以下几点:

n:      Height:     Hint:
0       1           2^0

1       2*1=2       2^1
2       2+1=3       2^2 -1

3       2*3=6       2^3 -2
4       6+1=7       2^3 -1

5       2*7=14      2^4 -2
6       14+1=15     2^4 -1

7       2*15=30     2^5 -2
8       30+1=31     2^5 -1

9       2*31=62     2^6 -2
10      62+1=63     2^6 -1

11      2*63=126    2^7 -2
12      126+1=127   2^7 -1

13      2*127=254   2^8 -2
14      254+1=255   2^8 -1

15      2*255=510   2^9 -2
16      510+1=511   2^9 -1

and so on and so forth...

这意味着我们可以使用位移位并​​避免循环等。这是一个简单的解决方案:

int main(){
    //number of test cases
    int t;
    cin >> t;
    for(int i= 0; i< t; ++i){
        //number of cycles for the tree growth
        int n;
        cin >> n;
        if (n == 0)
            cout << 1 << endl;
        else if (n == 1)
            cout << 2 << endl;
        else if (n > 1){ 
                cout << ((1 << ( (n & 1) ? ((n+1)/2) : (n/2)) + 1) - ((n & 1) ? 2 : 1)) << endl;
        }
    }        
    return 0;
}

关键是将循环数分为奇数和偶数并进行相应处理。