-1

在 n 维网格（最大 10^7 维）中是两个点。他们在每个轴上都有假想的传感器。当这两个点可以发现自己时，我需要算法来计算所有可能的选项。

正式写自我的任务文档（翻译成英文）：
让坐标（a1，a2，...，an）的A和坐标（b1，b2，...，bn）的B 是n-中的两个点维空间并且存在i ∈ 1, 2, ..., n使得ai = bi然后A 和 B 互相看到

示例：
在长度为 10的一维空间中，共有45 个组合，当他们看到对方时如何放置2 个点（他们每次都看到对方）。很容易组合 10C2 (10 of 2) = 45

如何通过程序以 2,3,4,...,10^7 维度计算它（我更喜欢 C#）？

我拥有的正确测试数据：
输入：
1
10
输出：45

输入：
2
5 8
输出：220

输入：
3
8 12 11
输出：14784

更多解释：
当空间中的两个点互相看到（在同一轴上）时，输出是组合的数量。在一维空间中只有一个轴，所以他们总是互相看到对方。在二维空间中是 2 轴，所以他们只能在某些情况下看到对方

这个图像示例解释的不仅仅是我认为的文字

4

2 回答 2

1

我确定这是正确的。
C(x,y) 是 y 的组合 x。
假设我们有一个维度，我们称它为长度为 8 的 X。有 C(8,2) = 8*7/2 = 28 种可能看到彼此。
当我们添加第二个维度，命名为 Y，长度为 12 时，现在我们有 12 条平行于 X 的线。所以我们有 12*28=336 种可能性在平行于 X 的所有线上找到。现在，在 Y 维度上，我们有 C( 12,2) = 66 种可能性。有 8 行这样的，所以 66*8=528。
总共：336 +528= 846 种可能性
现在让我们添加另一个维度，标记为 Z，长度为 11。一行中有 C(1,2) = 11*10/2 = 55，（注意）我们有 8* 12行这样。所以是 55*8*12 = 5280 种可能性！
现在我们总共有：
平行于 X 轴：C(8,2)*11*12 = 3696
平行于 Y 轴 C(12,2)*8*11 = 5808
平行于 Z 轴 C(11,2)*8*12 = 5280
TOTAL = 14784

一般来说 n 维的公式 n1,n2... nk长度为：
C(ni,2) 之和 * (n1*n2...*nk)/ni
或更短：(n1*n2*n3...nk)/2 之和 * (ni-1)

例如：尺寸为 3,8,9,11：
(3*8*9*11)/2*(3-1) = 2376
(3*8*9*11)/2*(8-1) = 8316
(3*8*9*11)/2*(9-1) = 9504
(3*8*9*11)/2*(11-1) = 11880
总计 = 32076

最简单的方程：
(n1*n2* n3...ni)(n1+n2+...ni - k)/2，其中 ni 是长度，k 是维数

于 2017-03-24T16:32:08.997 回答
0

我已经创建了示例代码，因此您可以尝试一下。我已经检查它工作正常。

等式是：C(n,r)=n!/(r!(n−r)!)

示例： 1. 10C2=45 2. 10C3=120

public void Calc()
{
  int result= nCr(10, 3);
}

public int nCr(int n,int r )
{   
   int nValue=1;
   int rValue = 1;
   for (int i = n-r+1; i <= n; i++)
   {
       nValue = nValue*i;
   }
   for (int i = 1; i <= r; i++)
   {
        rValue = rValue*i;
   }
   return nValue/rValue;
}
于 2017-03-24T16:14:06.680 回答