OneCoder Avatar
OneCodercoderli.com · 958 篇博文
一级

C++ 算法考级专栏

真题分析、矩阵探测、递归回溯与基础语法

🎨 视觉封面

【GESP】C++一级练习 luogu-B2069, 求分数序列和

📅 2024-11-17·✍️ OneCoder·计算中...·⏱️ 5 分钟
#GESP#C++#基础语句

一级练习,难度提升了一些。根据规律,构造数列计算。

luogu-B2069

题目要求

描述

有一个分数序列 q1p1,q2p2,q3p3,q4p4,q5p5,...\frac{q_1}{p_1}, \frac{q_2}{p_2}, \frac{q_3}{p_3}, \frac{q_4}{p_4}, \frac{q_5}{p_5}, ...,其中 qi+1=qi+pi,pi+1=qi,p1=1,q1=2q_{i+1} = q_i + p_i, p_{i+1} = q_i, p_1 = 1, q_1 = 2。比如这个序列前 66 项分别是 21,32,53,85,138,2113\frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \frac{13}{8}, \frac{21}{13}。求这个分数序列的前 nn 项之和。

输入

输入一行一个正整数 nn,其中 n30n \le 30

输出

输出一行一个浮点数,表示分数序列前 nn 项的和,精确到小数点后 44 位。

输入样例-1

2

输出样例-1

3.5000


题目分析

  • 读取项数nn的值
  • 初始化分母mm为1,分子zz为2,和sumsum为0
  • 在每次循环中,计算当前项的值并累加到sumsum
  • 根据题目中给出的分子和分母的排列关系,更新下一个分子和分母的值
  • 输出和sumsum,保留到小数点后4位

示例代码

C++ 18 行
#include <cstdio> // 包含输入输出流头文件

int main() {
    int n; // 定义整数n,用于存储输入的项数
    scanf("%d", &n); // 从输入流中读取n的值
    int m = 1; // 初始化分子母1
    int z = 2; // 初始化分子为2
    double sum = 0; // 初始化和为0
    for (int i = 1; i <= n; i++) { // 循环n次,计算前n项的和
        sum += (double)z / m; // 计算当前项的值并累加到sum
        int temp = z; // 保存当前分子的值
        z = m + z; // 更新下一个分子为当前分子加上当前分母
        m = temp; // 更新下一个分母为当前分子
    }
    printf("%.4f", sum); // 输出和,保留到小数点后4位

    return 0; // 返回0,表示程序执行成功
}

其实,在孩子最开始做的时候,我没有注意到题目中给出的分子、分母的排列规律,我教孩子按照分子、分母各自成为一个斐波那契数列的方式计算,得出的结果。复杂度显然提升了很多,代码参考如下:

C++ 32 行
#include <cstdio>
int main() {
    int n;
    scanf("%d", &n);
    int a1 = 1;
    int a2 = 2;
    int b1, b2;
    b1 = 2;
    b2 = 3;
    double m;
    double z;
    double sum = 0;
    double s1 = (double)b1 / (double)a1;
    double s2 = (double)b2 / (double)a2 + s1;
    if (n == 1) {
        printf("%.4f", s1);
    } else if (n == 2) {
        printf("%.4f", s2);
    } else {
        for (int i = 3; i <= n; i++) {
            m = a2 + a1;
            a1 = a2;
            a2 = m;
            z = b2 + b1;
            b1 = b2;
            b2 = z;
            sum += (double)z / m;
        }
        printf("%.4f", sum + s2);
    }
    return 0;
}

💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745)Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder (lihongzheshuai)

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

0 条讨论
✨ 支持点击留言直接回复 · Markdown 引用格式
💬 还没有读者留言,快来成为第一个讨论者吧!