在java中查找分数（a/b）的重复部分并仅将重复整数打印为字符串？

html5 • • 问答

我正在解决一个分数问题，

  1. 如果分数部分重复，则将唯一重复的整数打印为字符串。
  2. 如果分数部分不重复，则在小数点后最多打印 4 位数字。
  3. 如果分数输出很简单，则直接将其打印为字符串。

例如

a) 1/3 = 0.3333... ，这里 3 是重复出现的，所以只需要打印 0.3。b) 5/2 = 2.5 -- 简单数学。c) 22/7 = 3.14287，这里 14287 是重复的，所以需要打印 3.14287

你能帮忙吗，解决方案应该有 O(k) 的时间复杂度和空间复杂度

public String fractionToDecimal(int numerator, int denominator) {
    StringBuilder tem = new StringBuilder();
    long q = numerator / denominator;

    return tem.append(q);
}

回答

这个问题相当复杂。您需要了解相当多的高级概念才能完全理解为什么会这样。

二进制与十进制

“1 除以 3 无休止地重复 3”这一概念仅在您预设十进制渲染系统时才有效。想一想：为什么“10”在“9”之后？比如，为什么“我们”决定不对“十”这个概念使用特定的符号，相反，这是数轴上的确切点，“我们”决定使用两位数，第一位和零位挨着写？这是一个随意的选择，如果你深入研究历史，人类做出这个选择是因为我们有 10 根手指。并非所有人都做出了这个选择，需要明确的是：苏美尔人拥有独特的数字，一直到 60，这解释了为什么一分钟有 60 秒，例如。有些偏远部落使用 6、3 甚至更奇怪的数字系统。

如果您想花一些有趣的数学时间，请在维基百科上阅读有关奇异数字系统的书。这是令人着迷的东西，是度过一个小时（或两个或十个！）

想象一个外星人的数字系统，它总共只有 3 个手指。他们会计算：

Human Alien
0     0
1     1
2     2
3     10
4     11
5     12
6     20
8     21
9     22
10    30

他们的数字系统并不“奇怪”或“糟糕”。只是不同。

然而，这个数字概念是双向的：比如，当你写“1 除以 4 = 0.25”时，25 也是“十进制”（有 10 位数字的数字系统的名称，就像大多数人在地球喜欢使用）。

在人类中，1 除以 10 是 0.1。很简单，对吧？

好吧，在“三指外星人”中，一除以三是... 0.1。

不是 0.1 重复。不，不。仅 0.1。它非常适合。在他们的数字系统中，一除以十实际上是相当复杂的，而在我们的数字系统中则简单得离谱。

计算机也是外星人。他们有2个手指。只有 0 和 1，仅此而已。计算机很重要：0 1 10 11 100 101 110 111等等。

a / b以十进制重复的运算可能不会以二进制重复。或者它可能。或者一个不以十进制重复的数字可能以二进制重复（1/5 以二进制无限重复，十进制，它只是 0.2，很简单）。

鉴于计算机不喜欢用十进制计数，任何基本操作都是即时的“失败者”——如果你在这里编写代码double或float在代码中的任何地方，你都无法再回答这个问题。

但是它需要二进制知识和一些相当基础的数学知识才能知道。

解决方案一：BigDecimal

注意：我认为这不是最好的方法，我会采用策略 2，但为了完整性......

Java 有一个被称为核心库的类java.math.BigDecimal，旨在在您不希望有任何损失时使用。double并且float是 [A] 基于二进制的，因此尝试使用它们来计算重复步幅是完全不可能的，并且 [B] 一直默默地将数字四舍五入到最接近的可表示数字。你得到四舍五入的错误。在double数学上，即使 0.1 + 0.2 也不完全是 0.3 。

由于这些原因，BigDecimal 存在，它是十进制的，并且是“完美的”。

问题是，嗯，它是完美的。在基础上，在 BigDecimal 数学中将 1 除以 3 是不可能的- 发生异常。您需要了解 BigDecimal 相当复杂的 API 才能了解如何解决此问题。您可以告诉 BigDecimal 您可以接受多少精确度。

所以，你可以做什么：

  • 将您的除法器和股息转换为 BigDecimal 数字。
  • 将这些配置为逗号精度后的 100 位数字。
  • 一分为二。
  • 将结果转换为字符串。
  • 分析字符串以找到重复的步幅。

该算法在技术上仍然不正确- 您可以拥有重复跨度超过 100 个字符的输入，或者一个看似具有重复跨度但实际上没有重复跨度的除法运算。

尽管如此，对于可能高达 100 左右的每个数字组合，您愿意投入使用，上述方法都可以。您还可以选择更进一步（超过 100 个数字），或者编写一个算法来尝试找到 100 个数字的重复步幅，如果失败，它只是使用while循环重新开始，不断增加使用的数字，直到您在输入中找到重复的步幅。

您将使用 BigDecimal 的许多方法并对结果字符串执行一些相当棘手的操作，以尝试正确找到重复步幅。

这是解决这个问题的一种方法。如果您想尝试，请阅读本文并玩得开心！

解决策略 2：使用数学

给定一个除数和被除数，您可以使用数学算法推导出下一个十进制数字。这不是太多的计算机科学，它纯粹是一个数学练习，因此，在寻找这个时不要在网上搜索“java”或“编程”或诸如此类的东西。

基本要点是这样的：

1/4 变成了数字 0.25，如何推导出来？好吧，如果您先将输入乘以 10，即计算 10/4，那么您真正需要做的就是用积分数学计算。4 可以放入 10 两次，还有一些剩余。这就是 2 的来源。

然后推导出 5：取剩下的数（4 两次与 10 相乘，剩下 2），再乘以 10。现在计算 20/4。那是 5，没有剩下任何东西。太好了，这也正是5从何而来，而我们得到的结论是没有必要继续。从现在开始都是零。

你可以用java代码编写这个算法。它永远不应该提及double或float（如果你这样做，你会立即失败）。a / b，如果 a 和 b 都是整数，则完全符合您的要求：计算 b 适合 a 的频率，并丢弃任何余数。然后，您可以通过一些更简单的数学运算获得余数：

int dividend = 1;
int divisor = 4;
List<Integer> digits = new ArrayList<>();

// you're going to have to think about when to end this loop
System.out.print("The digits are: 0.");
while (dividend != 0 && digits.size() < 100) {
   dividend *= 10;
   int digit = dividend / divisor;
   dividend -= (digit * divisor);
   digits.add(digit);
   System.out.print(digit);
}

我会留下你需要编写的代码来查找重复。当您的除数最终成为您之前见过的除数时，您可以确定它会“干净地”重复。比如做1/3的时候，经过这个算法：

第一次循环：

  • dividend (1) 乘以 10，变为 10。
  • dividend现在是整数除以除数 (3)，产生数字3。
  • 我们确定还剩下什么：数字乘以除数是 9，所以这 10 个中的 9 个已经用完，剩下 1。我们设置dividend为 1。

正如您所看到的，实际上没有任何变化：股息仍然是 1，就像它在开始时一样，因此所有循环都这样进行，产生无穷无尽的 3 个值，这确实是正确的答案。

您可以维护您已经看到的股息清单。例如，通过将它们存储在Set<Integer>. 一旦你点击了一个你已经看到的数字，你就可以停止打印：你已经开始重复了。

该算法具有始终正确的相当大的好处。

那我该怎么办？

我认为你的老师希望你弄清楚第二个，而不是钻研 BigDecimal API。

这是一个很棒的练习，但更多的是关于数学而不是编程。

以上是在java中查找分数（a/b）的重复部分并仅将重复整数打印为字符串？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>