问题2:考虑一个包含n个元素的有限集S;S恰好为2的不同子集的数量称为“ 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;
}
这是您需要的所有提示。您正在尝试计算(n*(n-1))/2
让我们使用一种不可接受但实用的解决方案来打印出第一组数字。
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....
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句