编程论坛 → C++教室

这道题怎么做

cstdio 发布于 2018-10-04 15:23， 1962 次点击

你是超级英雄蚁人，面前有一颗定时炸弹需要你去拆除，但是炸弹外壳无法打开，
这让拆弹工作变的非常困难。突然，你发现外壳接缝处有一个 x 纳米大小的空隙，也就是说只要你的尺寸不超过 x 纳米，
你就可以进入炸弹内部去拆弹了。已知目前你的尺寸为 y 纳米，每次变身可以缩小，尺寸变为原来的 a 分之 b 倍。
求至少要变身几次才能拆弹成功？备注：纳米是长度单位，1 纳米=0.000000001 米

输入文件 antman2.in 输入第一行为四个正整数 x,y,a,b,由空格隔开。x<=10^8,y<=10^8,0<b<a<100

输出文件 antman2.out 输出一个整数，代表变身次数

输入输出样例 1： antman2.in antman2.out 100 300 3 1 1

输入输出样例 2： antman2.in antman2.out 1 1025 2 1 11

2 回复

#2

rohalloway2018-10-05 15:39

程序代码：

#include <iostream>

using namespace std;

int main()
{
    int x, y, a, b;
    int i = 1;

    cout << "x<=10^8, y<=10^8, 0<b<a<100" << endl;
    cout << "Pls input 4 number for x, y, a, b :" << endl;

    cin >> x;
    cin >> y;
    cin >> a;
    cin >> b;

    if (a > b)
    {
        while (true)
        {
            if (y * b / a > x)
            {
                i++;
                y = y * b / a;
            }
            else
                break;
        }
    }
    else
    {
        cout << "a must be > b";
    }
    cout << i << endl;

    system("pause");
    return 0;
}

我也是新手，你最好测试一下看看是不是你想要的

[此贴子已经被作者于2018-10-5 15:46编辑过]

#3

rjsp2018-10-08 09:44

难，难，难！
题目要求是求出 y * b^n <= x * a^n 成立n最小值。
如果直接用数学公式：进一取整| [ln(x)-ln(y)] / [ln(b)-ln(a)] |，最大的问题是没法保证浮点运算的精度，即代码好写可惜没法保证结果一定正确。
如果用整数运算+循环，按题目的要求取极值 x=1, y=100000000, a=100, b=99，那么算下来需要1833次，这就得自己写个大整数类，难度翻天了。

附：
x=1, y=100000000, a=100, b=99; 结果是 1833
x=1, y=99999989, a=97, b=89; 结果是 215

1