POJ NOI MATH-7656 李白的酒

问题链接：POJ NOI MATH-7656 李白的酒。

总时间限制:: 1000ms
内存限制:: 65536kB

描述

李白街上走，提壶去打酒。遇店加一倍，见花喝一斗。n遇店和花，喝光壶中酒。

试问壶中原有多少酒？

释义：李白提壶上街买酒、喝酒，每次遇到酒店，便将壶中的酒量增添一倍，而每次见到花，便喝酒一斗，这样他遇店、见花经过n次，正好把酒全喝完了。问：壶中原有多少酒。

输入

一个正整数n，不超过100。

输出

一个小数，为壶中初始酒量（单位：斗），舍入到小数点后五位。

样例输入

样例输出

0.87500

来源

《奥数典型题举一反三（小学五年级）》 (ISBN 978-7-5445-2882-5) 第二章第一讲例3

问题分析

本题的关键是找出递推式，找出递推式后计算就简单了（参见程序注释）。

程序说明

（略）。

AC的C++语言程序：

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int n;
    double ak;

    cin >> n;

    // ak+1 = 2 * ak -1
    // ak = (ak+1 + 1) / 2, an+1 = 0
    ak = 0;
    for(int i=1; i<=n; i++)
        ak = (ak + 1) / 2;

    cout << fixed << setprecision(5) << ak << endl;

    return 0;
}