計算超立方體中座標的數量

在N維網格中，單元格的座標表示爲X1，X2，...，XN。任何具有負座標的細胞都是白色的。原點單元（全零座標）被着色爲黑色。（X1，X2，...，XN）中一個單元格的顏色取決於具有座標（X1-1，X2，...，XN）的N個單元格，（X1，X2-1，... ，XN），...，（X1，X2，...，XN-1）。當且僅當這N個座標中黑色單元的數量是偶數時，該單元才被着色爲白色，否則該單元被着色爲黑色。計算超立方體中座標的數量

現在，給出子超立方體的起始和終止座標。所有的座標將是查詢完成的非負整數。我們必須計算這個子超立方體中有多少超單元格是黑色的？

請建議我提示，參考或任何可以幫助我解決它的東西。

來源

2011-08-13 Bharat Kul Ratan

什麼意思'任何具有負座標的單元格？任何具有*至少一個負座標或僅具有*負座標的單元格？ – phimuemue

任何單元座標由n分量組成。這指的是如果任何組件是否定的。 –

好吧，超立方體的*開始*和結束*座標是什麼？我認爲超立方體是「{0,1}^n」（即，只有長度爲n的0-1元組）。（子）超立方體的定義如何？ – phimuemue

以衆所周知的分形這條規則的結果 - The Sierpinski triangle

這裏是它在2D圖像：

enter image description here

來源

2011-08-13 18:29:09

蠻力算法：

fill the hypercube (the needed part) with value 'unknown'. 
color[00000] = 1 #black 

sum = 0 
for each cell in sub-hypercube: 
    sum += getcolor(cell) 
    return sum 

getcolor(cell): 
    if color[cell] == unknown 
     c = 0 #white 
     for each neighbour cell in decreasing direction within non-negative boundary: 
      c = c xor getcolor(neighbour) 
     color[cell] = c 
    return color[cell]

來源

2011-08-13 10:56:24

計算超立方體中座標的數量

回答

相關問題