一题简单的oj好题大一

Question

Answer 1

普通版本：O(n)

#include<iostream>
#define MAXSIZE 40
using namespace std;

//double 精度高，有效数字 15-16 位，float 精度低，有效数字 6-7位，
//但是 double 消耗的内存是 float 的两倍，
//运算速度比 float 慢得多，建议能用 float 保证精度的就用 float，少用 double。
double Array[MAXSIZE];//先用double的看能不能过时间，不能就该用float

void init() {
    //递归比迭代花费的时间会比较长
    for (int i = 0; i < MAXSIZE; i++) {
        Array[i] = i <= 1 ? 1 : Array[i - 1] + Array[i - 2];
    }
}
int main() {
    init();//一次生成，不再递归
    int n,i;
    double result;
    while (cin >> n) {
        result = 0;
        for (i = 0; i < n; i++) {
            result += Array[i + 2] / Array[i+1];
        }
        printf("%.6lf\n", result);//保持六位小数
    }
}

优化版本 O(1)

#include<iostream>
#define MAXSIZE 40
using namespace std;
//double 精度高，有效数字 15-16 位，float 精度低，有效数字 6-7位，
//但是 double 消耗的内存是 float 的两倍，
//运算速度比 float 慢得多，建议能用 float 保证精度的就用 float，少用 double。
double Array[MAXSIZE];//先用double的看能不能过时间，不能就该用float
//double resultItems[MAXSIZE];
double resultComSum[MAXSIZE-1];//这里最大的为38个>题意的36,够用,1-37使用范围
void init() {
    //递归比迭代花费的时间会比较长
    double tmp=0;
    for (int i = 0; i < MAXSIZE; i++) {
        Array[i] = i <= 1 ? 1 : Array[i - 1] + Array[i - 2];
        if (i > 1) {
            //resultItems[i - 2] = Array[i] / Array[i - 1];  
            tmp += Array[i] / Array[i - 1];
            resultComSum[i -1] = tmp;
        }
    }
}
int main() {
    init();//一次生成，不再递归
    int n;
    double result;
    while (cin >> n) {
        result = resultComSum[n];
        printf("%.6lf\n", result);//保持六位小数
    }
}