2

在过去的几天里，我一直试图解决这个问题，但我无法找到解决它的方法。所以，这里是：

给定以 4 为底（即 0、1、2、3 作为数字的数字），找出任何负整数或正整数的以 4 为底的表示形式中的多余 (-1)。示例：-6 = (-1)22 相反，(-1)22 超过 (-1) 基数 4 = 2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 8 - 16 = 10 - 16 = -6 以 10 为底

27 = 2(-1)(-1) 相反，2(-1)(-1) = (-1) * 4^0 + (-1) * 4^1 + 2 * 4^2 = -1 - 4 + 32 = 27

我确实提出了一些正数算法，但没有一个算法适用于所有负数，所以他们就扔进了垃圾箱。

谁能在这里给我一些线索？谢谢！

----------------

编辑：我将尝试以不会引起任何混淆的方式重新表述这个问题。

考虑通过从每个数字中减去 1 获得的基数，称为以 4 为底的余数-(-1)。在这个基数中，任何数字都可以用数字 -1、0、1、2 表示。所以，问题要求一种算法，将任何整数作为输入，并将该给定数字的表示形式作为输出。

例子：

十进制 -6 = -1 2 2 表示基数 4 的余数-(-1)。

为了验证这一点，我们采用 -1 -1 2 的表示并将其转换为十进制数，从最右边的数字开始，并使用通用以 n 为底的 10 算法，如下所示：

数字 = 2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 4 - 16 = -6

2 * 4^0 + 2 * 4^1 + (-1) * 4^2 = 2 + 4 - 16 = -6

4

1 回答 1

1

我不知道“quaterit”是否是这个表示中基数的正确词，但无论如何我都会使用它。

既然您说您已经有一个正数算法，我将尝试将负数作为输入并使用您已有的内容编写一些东西。下面的代码不太有效，但我会在最后解释原因。

int[] BaseFourExcessForNegativeNumbers(int x) {
    int powerOfFour = 1;
    while (-powerOfFour > x) {
        powerOfFour *= 4;
    }
    int firstQuaterit = -1;
    int remainder = x + powerOfFour;
    int[] otherQuaterits;
    if (remainder >= 0) {
        otherQuaterits = BaseFourExcessForPositiveNumbers(remainder);
    } else {
        otherQuaterits = BaseFourExcessForNegativeNumbers(remainder);
    }
    int[] result = new int[otherQuaterits.Length + 1];
    result[0] = firstQuaterit;
    for (int index = 0; index < otherQuaterits.Length; ++index) {
        result[index + 1] = otherQuaterits[index];
    }
    return result;
}

这里的想法是每个负数在这个表示中x都以 a 开头。(-1)如果(-1)是在那个4^n位置，我们想知道如何表示x - (-1)*4^n，看看如何表示其余的数字。

我写的代码不起作用的原因是它没有考虑第二个四分体是0的可能性。如果发生这种情况，我的代码将生成的数组将丢失那个0。事实上，如果BaseFourExcessForPositiveNumbers是以相同的方式编写，结果数组将丢失每个0，但否则将是正确的。一种解决方法是跟踪第一个 quaterit 占据的位置，然后使数组具有该大小，并从后到前填充它。

于 2016-11-18T19:58:09.727 回答