0

可以减去罗马数字而不转换为十进制数字吗？

例如：

X - III = VII

所以在输入中我有X和III。在输出中我有VII。

我需要算法而不转换为十进制数。

现在我没有主意。

4

7 回答 7

2

最简单的算法是为 Romans 创建 -- 函数。减去 AB 意味着同时重复 A-- 和 B--，直到 B 中没有任何内容。

但我想做一些更有效的事情

罗马数字可以以某种非常弱的方式被视为位置。我们会使用它。

让我们做一个简短的减法表：

X-V=V

X-I=IX
IX-I=VIII
VIII-I=VII
VII-I=VI
VI-I=V
V-I=IV
IV-I=III
III-I=II
II-I=I
I-I=_

并补充：

V+I=VI

CLX 和 MDC 级别也是如此。当然，您可以只创建一个表，但通过替换字母在不同级别上使用它。

  • 让我们以数字为例，A=MMDCVI=2606 a B=CCCXLIII=343

  • 让我们将它们分配到级别= 10 的幂。以下几个操作将仅在级别内。

    A=MM+DC+VI，B=CCC+XL+III

  • 然后减去

    AB= MM+(DC-CCC)+(-XL)+(VI-III)

  • 在每个级别，我们都有三个可能的字母：单位、五个单位和十个单位。组合（单元，五单元）和（单元，十单元）将被翻译成差异

    AB= MM+(DC-CCC)+(-L+X)+(VI-III)

  • 正常组合（其中高级符号在初级符号之前）将被转换为总和。

    AB= MM+(D+CCCC)+(-L+X)+(V+IIII)

  • 缩短相同符号的组合

    AB= MM+(DCC)+(-L+X)+(VII)

  • 如果某个级别为负数，则向高层借用一个单位。当然，它可以通过空级别工作。

    AB= MM+(DCCC)+(C-L+X)+(VII)

  • 现在，在每个级别中，我们将应用我们制作的减法表，减去每个减号，从表的顶部开始并重复它，直到没有减号。

    AB= MM+(CD-CC)+(L+X)+(IV-I)

    AB= MM+(CCC-C)+(L+X)+(III)

    AB= MM+(CC)+(L+X)+(III)

  • 现在，使用加法表

    AB= MM+(CC)+(LX)+(III)

  • 现在，我们将打开括号。如果某个级别有“_”，则其位置将没有任何内容。

    AB=MMCCLXIII =2263

结果是正确的。

于 2014-02-26T13:16:01.767 回答
1

有一个比简单地展开整个罗马数字更优雅的解决方案。这样做的缺点是 O(n) 的复杂性，而不是 O(log n)，其中 n 是输入数。

我发现这个任务很有趣。确实可以不用转换。基本上，您只需查看最后一位数字。如果它们匹配，则将它们带走，如果不匹配，则更换较大的那个。但是，整个任务会因“IV”之类的数字而变得复杂得多，因为您需要前瞻。

这是代码。由于这很可能是家庭作业，因此我取出了一些代码，因此您必须自己考虑其余部分的外观。

    private static char[] romanLetters = { 'I', 'V', 'X', 'L', 'C', 'D', 'M' };
    private static string[] vals = { "IIIII", "VV", "XXXXX", "LL", "CCCCC", "DD" };

    static string RomanSubtract(string a, string b)
    {
        var _a = new StringBuilder(a);
        var _b = new StringBuilder(b);

        var aIndex = a.Length - 1;
        var bIndex = b.Length - 1;

        while (_a.Length > 0 && _b.Length > 0)
        {
            if (characters match)
            {
                if (lookahead for a finds a smaller char)
                {
                    aIndex = ReplaceRomans(_a, aIndex, aChar);
                    continue;
                }
                if (lookahead for b finds a smaller char)
                {
                    bIndex = ReplaceRomans(_b, bIndex, bChar);
                    continue;
                }
                _a.Remove(aIndex, 1);
                _b.Remove(bIndex, 1);
                aIndex--;
                bIndex--;
            }
            else if (aChar > bChar)
            {
                aIndex = ReplaceRomans(_a, aIndex, aChar);
            }
            else
            {
                bIndex = ReplaceRomans(_b, bIndex, bChar);
            }
        }

        return _a.Length > 0 ? _a.ToString() : "-" + _b.ToString();
    }

    private static int ReplaceRomans(StringBuilder roman, int index, int charIndex)
    {
        if (index > 0)
        {
            var beforeChar = Array.IndexOf(romanLetters, roman[index - 1]);
            if (beforeChar < charIndex)
            {
                Replace e.g. IX with VIIII
            }
        }
        Replace e.g. V with IIIII
    }
于 2014-02-26T12:44:33.417 回答
0

除了检查输入数字的每个可能组合 - 假设输入是有界的 - 没有办法做你所要求的。罗马数字在数学运算方面很糟糕。

您可以编写一个不转换它们的算法，但它必须在某些时候使用十进制数。或者您可以将它们规范化为例如“IIIIII ...”，但是您需要再次编写一些等价词，例如“50 chars = L”。

于 2014-02-26T11:51:58.037 回答
0

粗略的想法：

创建每个罗马数字如何与更简单的数字相关的“地图”或列表，例如 IV 对应于 (II + II)，而 V 对应于 (III + II)，X 对应于 (V + V)。

在计算例如 X - III 时，不要将其视为一个数学术语，而是一个字符串，它可以分几个步骤进行更改，您每次都检查要从减号运算符两侧删除的内容：

x - III                       // Nothing to remove
(V + V) - III                 // Still nothing to remove
(III + II + III + II) - III   // NOW we can remove a "III" from both sides
                              // while still treating these as roman numerals.

Result:      III + II + II
Rejoined:   V + II = VII.

如果你让每个数字对应于“地图”中尽可能简单的东西（例如 III 可以对应于 (II + I)，所以你不会被剩下的东西卡住），那么我很确定你可以在这里找出某种解决方案。

当然，这需要一堆字符串操作、比较和一个映射，您的算法可以从中“知道”如何比较或切换值。不完全是传统数学，但话又说回来，我想这就是罗马数字的工作方式。

于 2014-02-26T12:20:02.410 回答
0

解析输入字符串以对混合 5/10 基数（M、D、C、L、X、I）中的数字进行分组。即 MMXVII 产生 MM||||X|V|II。

现在通过成对取消数字，从右到左减去。即 V|III - II = V|II - I = V|I。

需要时，进行借位，即拆分下一个最高位（V 拆分为 IIIIII，X 拆分为 VV...）。示例：V|I - III = V| - II = IIIIII - II = III。借用可能需要递归，例如 X||I - III = X|| - II = VV| - II = V|IIIIII - II = V|III。

前缀符号 (IV, IX, XL, XC...) 使它更复杂一些。一种方法是预处理字符串以在输入时将其删除（替换为 IIII、VIIII、XXXX、LXXXX...）并进行后处理以在输出时恢复它们。

例子：

XCIX - LVI = LXXXXVIIII - LVI = L|XXXX|V|IIII - L|V|I = L|XXXX|V|III - L|V| = L|XXXX||III - L|| = XXXX||III = XXXXIII = XLIII

纯字符处理，不涉及算术。

Digits= "MDCLXVI"
Divided= ["DD", "CCCCC", "LL", "XXXXX", "VV", "IIIII"]

def In(Input):
    return Input.replace("CM", "DCCCC").replace("CD", "CCCC").replace("XC", "LXXXX").replace("XL", "XXXX").replace("IX", "VIIII").replace("IV", "IIII")

def Group(Input):
    Groups= []
    for Digit in Digits:
        # Split after the last digit
        m= Input.rfind(Digit) + 1
        Groups.append(Input[:m])
        Input= Input[m:]

    return Groups

def Decrement(A, i):
    if len(A[i]) == 0:
        # Borrow
        Decrement(A, i - 1)
        A[i]= Divided[i - 1] + A[i]
    A[i]= A[i][:-1]

def Subtract(A, B):
    for i in range(len(Digits) - 1, -1, -1):
        while len(B[i]) > 0:
            Decrement(A, i)
            B[i]= B[i][:-1]

def Out(Input):
    return Input.replace("DCCCC", "CM").replace("CCCC", "CD").replace("LXXXX", "XC").replace("XXXX", "XL").replace("VIIII", "IX").replace("IIII", "IV")

A= Group(In("MMDCVI"))
B= Group(In("CCCXLIII"))
Subtract(A, B)
print Out("".join(A))

>>> 
MMCCLXIII
于 2014-02-26T13:12:32.207 回答
0

我的想法的基本草图是构建简单的转换器，这些转换器通过迭代器或可观察对象链接在一起。

因此，例如，在事物的输入端，您有一个CConverter执行组合CD, CM,D和, , , 和M的变换。所有其他接收到的输入都不受干扰地传递。然后行中的下一个转换器将、、和转换为适当数量的s，依此类推，直到您拥有所有s 的流。CCCCCCCCCCCCCCCCCCCCCCCCCCCCXConverterXLXCLXXI

然后，您通过同步消耗这两个Is 流来执行减法。如果minuend先用完，那么答案是0否定的，在这种情况下，一切都出错了。否则，当subtrahend用完时，您只需开始I从被减数发出所有剩余的 s。

现在你需要转换回来。所以第一个INormalizer排队Is 直到它收到五个，然后它发出一个V. 如果它到达流的末尾并接收到四个，那么它会发出IV. 否则它只会发出与I接收到的一样多的 s 直到流结束，然后结束它自己的流。

接下来，VNormalizer排队Vs 直到收到两个，然后发出一个X. 如果它接收到一个IV并且它有一个排队V然后它发出IX，否则它发出IV。

如果它正在接收的流结束或刚刚开始发送Is 并且它仍然有一个V排队，那么它会发出它，然后发送流想要发送的任何其他内容，然后结束它自己的流。

依此类推，建立正确的罗马数字。

于 2014-02-26T12:30:14.200 回答
-1

枚举呢？

public enum RomanNumber
{
I = 1,
II = 2,
III = 3,
IV = 4,
V = 5,
VI = 6,
VII = 7,
VIII = 8,
IX = 9
X = 10
}

然后像这样使用它：

int newRomanNumber = (int) RomanNumber.X - (int) RomanNumber.III

如果您的输入是“X - III = VII”，那么您还必须解析该字符串。但我不会为你做这项工作。;-)

于 2014-02-26T11:43:37.797 回答