2014年第5回ブルーブリッジカップC/C++プログラム設計本科B組省試合うどん(結果充填)

2014年第5回ブルーブリッジカップC/C++プログラム設計本科B組省試合テーマまとめ:
http://blog.csdn.net/u014552756/article/details/50574360
うどんを切る
1本の高筋ラーメン、真ん中を1刀切ると、麺が2本もらえます.先に1回折って、真ん中にナイフを切ると、麺が3本もらえます.2回連続で折って、真ん中を1本切ると、麺が5本もらえます.では、10回連続で折って、真ん中にナイフを切ると、どれだけの麺が得られるのでしょうか.考え方:折りたたみ回数はわずか10なため、データ規模は大きくなく、手算で簡単に完成することができます.0回折り、2本を得る.1回折りたたみ、2*2-1=3で2回折りたたみ、3*2-1=5で3回折りたたみ、5*2-1=9で4回折りたたみ、9*2-1=17で5回折りたたみ、17*2-1=33で6回折りたたみ、33*2-1=65で7回折りたたみ、65*2-1=129で8回折りたたみ、129*2-1=257で9回折りたたみ、257*2-1=513で10回折りたたみ、513*2-1=1025を得る
実は、上の考え方は再帰的で、このような考えをコードを通じて実現することができます.再帰には基本再帰とテール再帰の2つの形式があり,本稿ではそれぞれコード実装を行った.テール再帰は、通常、基本再帰よりも1つのパラメータを多くするプログラム効率をある程度向上させることができる.再帰の本質はスタックであり,もちろんスタックで実現でき,スタックオーバーフローを防止するために,データ規模が特に大きい場合にスタックを明示的に使用する.
答え:1025
基本再帰:

#include <iostream>
using namespace std;
int f(int n) {
    //     
    if(n == 0) {
        return 2;
    } else {
        return 2 * f(n - 1) - 1;
    }
}
int main(void) {
    cout << f(10) << endl;
    return 0;
}

末尾再帰:

#include <iostream>
using namespace std;
int f2(int n, int r) {
    //   
    if(n == 0) {
        return r;
    } else {
        return f2(n - 1, 2 * r - 1);
    }
}
int main(void) {
    cout << f2(10, 2) << endl;
    return 0;
}