c++ - 如何在没有 "/"的情况下进行除法？

Question

问题 2:考虑一个有 n 个元素的有限集 S；恰好有两个 S 的不同子集的数量称为“n 选择 2”，通常写为 n/2。你可能还记得 n/2=(n(n-1))/2。

下面是一个(简单的)C++ 函数，它接受一个非负整数 n 并返回 n/2(也是一个非负整数):

unsigned int n_choose_2(unsigned int n) {
    if(n==0) 
       return 0;
    else 
       return n*(n-1)/2;
 }

你的工作:编写一个同样返回 n/2 但具有以下约束的函数:

• 您不能使用乘法运算符*
• 不能使用除法运算符/
• 你不能有任何循环
• 您不能向函数添加任何其他参数
• 您的函数必须是独立的:没有辅助函数!
• 你不能使用任何全局变量
• 不能使用任何静态变量
• 您不能使用任何“位旋转”操作——没有移位等。

但是:

• 你可以使用递归
• 您可以使用 + 和 - 运算符。

这就是我得到的，需要帮助以避免使用 / 并检查我的方法是否正确。

unsigned int n_choose_2(unsigned int n) {
    if(n==0) 
         return 0;
    else 
         return n_choose_2(n)/2 - n/2;
}

Answer 1

这里有您需要的所有提示。您正在尝试计算 (n*(n-1))/2

让我们使用一个 Not Acceptable 但功能强大的解决方案来打印出第一组数字。

for (int n = 0; n < 20; n++)
{
    std::cout << "n_choose_2(" << n << "):  " << (n * (n-1)) / 2 << std::endl;
}

当然你不能提交那个，因为它使用了禁止的数学运算。但是让我们看看它打印出什么:

n_choose_2(0):  0
n_choose_2(1):  0
n_choose_2(2):  1
n_choose_2(3):  3
n_choose_2(4):  6
n_choose_2(5):  10
n_choose_2(6):  15
n_choose_2(7):  21
n_choose_2(8):  28
n_choose_2(9):  36
n_choose_2(10):  45
n_choose_2(11):  55
n_choose_2(12):  66
n_choose_2(13):  78
n_choose_2(14):  91
n_choose_2(15):  105
n_choose_2(16):  120
n_choose_2(17):  136
n_choose_2(18):  153
n_choose_2(19):  171

现在看看每行增加的量。

取任意两条相邻线(第一对除外)并减去差值。例如，n_choose_2(10) 是 45，n_choose_2(9) 是 36。n_choose_2(10) - n_choose_2(9) == 9 .

n_choose_2(19) - n_choose_2(18) 与 171 - 153 相同，即 18。

注意到这个模式了吗？

这就是你所需要的:

unsigned int n_choose_2(unsigned int n)
{
    if (n <= 1)
    {
        return 0;
    }

    // WHAT COMES NEXT IS UP TO YOU....
}