时间戳

首页 > 解决方案 > 在java中查找重复部分（a / b）并仅将重复整数打印为字符串？

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

问题描述

我正在解决分数的问题，

  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);
}

标签： javamath

解决方案

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

二进制与十进制

'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循环重新开始，不断增加 # of使用的数字，直到您在输入中找到重复的步幅。

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

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

解决方案策略 2：使用数学

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

基本要点是这样的：

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) 整除，产生 digit 3。
  • 我们确定剩下的是什么：除数乘以 9，因此这 10 个中的 9 个已用完，剩下 1。我们设置dividend为 1。

如您所见，实际上没有任何变化：被除数仍然是 1，就像一开始一样，因此所有循环都是这样进行的，产生无穷无尽的 3 个值流，这确实是正确的答案。

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

该算法具有始终正确的巨大优势。

那我该怎么办？

我认为您的老师希望您弄清楚第二个，而不是深入研究 BigDecimal API。

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

推荐阅读