-2

以下是我编写的近似值 103993/33102 的代码。用户输入精度。这里k是用户输入的精度，asd是字符串形式的值

int tot = 4687;
int divisor = 33102;
StringBuffer fraction=new StringBuffer();
int tmp = tot;
    for(long i=1;i<=k;i++)
    {
        tmp = tmp*10;
        int res = tmp/divisor;
        fraction.append(res);
        tmp = tmp - res*divisor;
    }
    asd="3."+fraction.toString();

但是，当用户输入 10^6 的精度时，会花费大量时间。时间限制为 1 秒。帮助！

4

2 回答 2

2

你的算法看起来不错。 StringBuffer是线程安全的，因此非常慢，因为它每次调用append. 使用StringBuilder，并以您知道自己需要的容量构建它，即k. 这可以防止数据的多个副本，因为内部的缓冲区StringBuilder被扩展以适应不断增长的字符串。

如果您阅读StringBuffer文档，这很清楚：

从 JDK 5 开始，该类已经补充了一个为单线程使用而设计的等效类 StringBuilder。通常应优先使用 StringBuilder 类，因为它支持所有相同的操作，但速度更快，因为它不执行同步。

由于您事先知道输出的确切大小，因此您还可以使用字节数组来保存数字。最终转换为长度为 10^6 的字符串和输出仍然很昂贵。当我运行下面的代码时，创建字节数组只需要 0.016 秒，转换为字符串需要 0.06 秒，打印需要超过 1 秒。为了取得进展，您必须对如何在 Java 中进行快速 i/o 进行一些研究。如果您切换到 C 或其他更接近硬件的语言，正常的 i/o 例程可能足够快。

public void run() {
    int k = 1000000;
    long start = System.currentTimeMillis();
    int tot = 4687;
    int divisor = 33102;
    byte [] buf = new byte[k];
    int tmp = tot;
    for (int i = 0; i < k; i++) {
        tmp = tmp * 10;
        int res = tmp / divisor;
        buf[i] = (byte)(res + '0');
        tmp = tmp - res * divisor;
    }
    System.out.println((System.currentTimeMillis() - start) * .001);
    String s = new String(buf);
    System.out.println((System.currentTimeMillis() - start) * .001);
    System.out.print("3."); System.out.println(s);
    System.out.println((System.currentTimeMillis() - start) * .001);
}
于 2013-03-03T20:28:40.283 回答
0

预先分配一个很大的字符串中的值，只做一个K个元素的子串，不用每次都计算，瞬间就有结果。

于 2013-03-03T20:41:09.040 回答