标签: rational-numbers

我曾经得到以下面试问题:

我在想一个正整数n.想出一个可以在O(lg n)查询中猜出它的算法.每个查询都是您选择的数字,我将回答"较低","较高"或"正确".

这个问题可以通过修改后的二进制搜索来解决,在该搜索中,列出2的幂,直到找到超过n的值,然后在该范围内运行标准二进制搜索.我认为这很酷的是,你可以比无限的力量更快地搜索特定数字的无限空间.

不过,我的问题是对这个问题稍加修改.假设我在0和1之间选择一个任意有理数,而不是选择正整数.我的问题是:您可以使用什么算法来最有效地确定我选择的有理数？

现在,我所拥有的最佳解决方案是在最多O(q)时间内通过隐式地走Stern-Brocot树(在所有有理数上的二叉搜索树)中找到p/q .但是,我希望运行时更接近我们为整数情况得到的运行时,可能是O(lg(p + q))或O(lg pq).有没有人知道如何获得这种运行时？

我最初考虑使用区间[0,1]的标准二进制搜索,但这只会找到具有非重复二进制表示的有理数,这几乎错过了所有的有理数.我还想过使用其他一些方法来枚举有理数,但是我似乎找不到一种方法来搜索这个空间给出更大/更小/更少的比较.

我正在研究std::ratio<>C++ 11标准中的类,它允许编译时合理算术.

我发现模板设计和用类实现的操作过于复杂,并且没有找到任何理由为什么他们不能通过实现一个非常简单的理性类并constexpr为操作符定义函数来使用更直接和直观的方法.结果将是一个更容易使用的类,并且编译时优势将保持不变.

有没有人知道当前std::ratio<>设计的优点与使用的简单类实现相比constexpr？实际上,我无法找到当前实现的任何优势.

我的任务是发展一个理性的阶级.如果500和1000是我的输入,则(½)必须是我的输出.我自己写了一个程序来找到它.

还有另一种找到解决方案的最佳方法,或者我的程序已经是最好的了吗？

public class Rational {

    public static void main(String[] args){

       int n1 = Integer.parseInt(args[0]);
       int n2 = Integer.parseInt(args[1]); 
       int temp1 = n1;
       int temp2 = n2; 

       while (n1 != n2){
         if(n1 > n2)
            n1 = n1 - n2;
         else
            n2 = n2 - n1;
       }      

      int n3 = temp1 / n1 ;
      int n4 = temp2 / n1 ;

      System.out.print("\n Output :\n");

      System.out.print(n3 + "/" + n4 + "\n\n" );
      System.exit(0);
    }  
}

在JavaScript中,有没有办法将十进制数(例如0.0002)转换为表示为字符串的分数(例如" 2/10000")"？

如果decimalToFraction为此目的编写了一个函数,那么decimalToFraction(0.0002)将返回该字符串"2/10000".

我有许多有理数的集合,每个有的分子和分母存储为一个大的(数百或数千位)无符号整数.我希望能够有效地测试a/b集合中任何给定的有理数是否等于集合中的任何其他有理数c/d.

a*d == b*c当然,最直接的方法是测试是否比计算完整产品更有效.

关于我的特定用例的一些注释:

• 我将测试的对很可能实际上是相等的(因为我已经预先计算并首先通过它们的浮点近似来比较它们),所以如果它们不相等的早期外出将不会为我节省很多时间.
• 我很好地预先计​​算了每个数字的额外数据,但每个数字只会用于少数比较,因此昂贵的预计算(例如素数因子分解)可能不值得.
• 偶尔的假阴性会很好,但误报不是.

我认为这在理论上可能是不可能的,但为了以防万一,将它扔到蜂巢头脑中.

我试图将具有十进制结果的用户键入的计算转换为分数.例如; 66.6666666667进入66 2/3.有什么指针吗？Thanx提前

我注意到在Coq对有理数的定义中,零的倒数被定义为零.(通常,除以零没有明确定义/合法/允许.)

Require Import QArith.
Lemma inv_zero_is_zero: (/ 0) == 0. 
Proof. unfold Qeq. reflexivity. Qed.

为什么会这样？

它可能会导致有理数的计算出现问题,还是安全的？

是否有算法来计算以下内容？

1. 如果除法的结果是重复的十进制(二进制).
2. 如果它重复,那么重复开始的是什么数字(表示为2的幂)？
3. 什么数字重复？

一些例子:

1/2 = 1/10 = 0.1 // 1 = false, 2 = N/A, 3 = N/A, 4 = N/A
1/3 = 1/11 = 0.010101... // 1 = true, 2 = -2, 3 = 10
2/3 = 10/11 = 0.101010... // 1 = true, 2 = -1, 3 = 10
4/3 = 100/11 = 1.010101... // 1 = true, 2 = 0, 3 = 10
1/5 = 1/101 = 0.001100110011... // 1 = true, 2 = -3, …

我一直在参加一个编程竞赛,其中一个问题的输入数据包括十进制格式的小数:0.75就是一个例子.

解析它Double是微不足道的(我可以用read它),但精度的损失是痛苦的.人们需要非常小心地进行Double比较(我没有),这似乎是多余的,因为Rational在Haskell中有一个数据类型.

当试图使用它时,我发现read一个Rational人必须提供以下格式的字符串:numerator % denominator,我显然没有.

所以,问题是:

解析分数的十进制表示形式的最简单方法是什么Rational？

还应考虑外部依赖项的数量,因为我无法在在线评判中安装其他库.

我发现了一个与有理数相关的问题.

给出了两个有理数,任务是找到它们之间最简单的有理数.

对于这个问题,有理数的简单性可以定义为具有最小分子的有理数,尽管我对这个度量的其他建议持开放态度,例如类似于数学堆栈交换的问题,如果它使解决方案更容易.

样本输入和输出可能是:

Inputs: 1110/416 and 1110/417, Output: 8/3
Inputs: 500/166 and 500/167, Output: 3/1

关于如何处理这个问题的任何想法或至少一个建议？我正在挣扎.

谢谢

编辑:

补充意见:

• 虽然在两个给定的有理数之间存在无限多的有理数,但确实有限的许多有理数比两者更简单.
• 平凡的解决方案可能只是尝试分子/分母的所有组合(分别从1到最高分子或分母),减少它们,并查看数字是否介于两者之间.我不确定它的O复杂性是什么,但我猜想有点像n ².