【数据结构入门训练DAY-14】 蓝桥杯2024年第十五届省赛真题-R 格式

前言

本次训练内容：

1. 蓝桥杯的准备训练。
2. 训练解题思维。

一、题目

小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R格式整数的做法是：

1. 将浮点数乘以 2n;

2. 四舍五入到最接近的整数。

输入格式

一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。

输出格式

输出一行表示答案：d 用 R 格式表示出来的值。

样例输入

2 3.14

样例输出

13

二、解题思路

        我相信很多朋友都和我一样，刚开始是使用<cmath>的pow求2的n次幂，然后用都double里的d乘以2的n次幂的值，最后用round来让它就近取整。但是很抱歉，它对一半。（破防了……）我想了想只能使用string然后加高精度了……。但是这俩东西我不太熟，只能去请教了一下别人的思路来做了。解题代码如下：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 大整数字符串加法（保证参数都为非负数的字符串）
string addString(const string &a, const string &b) {
    int i = a.size() - 1, j = b.size() - 1;
    int carry = 0;
    string res;
    while(i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if(i >= 0) {
            sum += a[i] - '0';
            i--;
        }
        if(j >= 0) {
            sum += b[j] - '0';
            j--;
        }
        carry = sum / 10;
        res.push_back(char('0' + sum % 10));
    }
    reverse(res.begin(), res.end());
    return res;
}

// 将大整数字符串乘以2
string maxstring(const string &s) {
    int carry = 0;
    string res;
    for (int i = s.size() - 1; i >= 0; i--) {
        int prod = (s[i] - '0') * 2 + carry;
        carry = prod / 10;
        res.push_back(char('0' + prod % 10));
    }
    if(carry) {
        res.push_back(char('0' + carry));
    }
    reverse(res.begin(), res.end());
    return res;
}

// 模拟除以 10^k，由于除数为10的幂，只需去掉末尾 k 位
string Pow(const string &num, int k) {
    if(num.size() <= (unsigned)k) return "0";
    return num.substr(0, num.size() - k);
}

int main(){
    int n;
    string d;
    cin >> n >> d;
    // 找到小数点位置，拆分整数
    int dotPos = d.find('.');
    int k = d.size() - dotPos - 1; // 小数位数
    // 整数 A = 去掉小数点后的数字串
    string A = d.substr(0, dotPos) + d.substr(dotPos + 1);
    // 计算 A * 2^n：重复 n 次乘以 2
    string val = A;
    for(int i = 0; i < n; i++){
        val = maxstring(val);
    }
    // 偏移量 offset = 10^k / 2，等价于 "5" 后面跟 (k-1) 个 '0'（k>=1）
    string offset = (k > 0) ? ("5" + string(k - 1, '0')) : "0";
    // 加上偏移量，完成四舍五入：计算 val + offset
    string sumVal = addString(val, offset);
    // 除以 10^k，即将字符串末尾 k 位去掉，得到最后的整数
    string result = Pow(sumVal, k);

    cout << result << "\n";
    return 0;
}

总结

        今天的题目让我感觉自己拿到想要的目标成绩还有一定距离，但是我相信只要坚持做下去就会得到胜利的果实，今天没有其他的感受，已经想麻了……。