是否有一個智能算法,需要一個數概率並生成多維數組或容器內部的相應真值表生成給定輸入的真值表?
例:
n = 3
N : [0 0 0
0 0 1
0 1 0
...
1 1 1]
我可以與用於循環和If做,但我知道我的方式會很慢並且很耗時。所以,我在問如果有一個先進的功能可以用來儘可能地提高效率?
是否有一個智能算法,需要一個數概率並生成多維數組或容器內部的相應真值表生成給定輸入的真值表?
例:
n = 3
N : [0 0 0
0 0 1
0 1 0
...
1 1 1]
我可以與用於循環和If做,但我知道我的方式會很慢並且很耗時。所以,我在問如果有一個先進的功能可以用來儘可能地提高效率?
如果我們允許填充表全0開始,它應該是可能的,然後執行完全相同2^n - 1
填充設置1位,我們的願望。這可能不會比編寫手動循環更快,但它完全沒有修改。編號: 行std::vector<std::vector<int> > output(n, std::vector<int>(1 << n));
聲明向量的向量。外部向量是長度爲n,內部爲2^n
(n個輸入的真值結果的數量),但是我使用左移進行功率計算,因此編譯器可以插入一個常量而不是呼叫,例如pow
。在n=3
的情況下,我們收到了一個3x8矢量。我以這種方式組織它(而不是習慣上的8x3行,作爲第一個索引),因爲我們要在輸出數據中利用基於列的模式。以這種方式使用構造函數還可以確保矢量矢量的每個元素都被初始化爲0.因此,我們只需要擔心將值設置爲1,而將其餘的單獨留下。
第二套嵌套for
循環僅用於在完成後打印出結果數據,沒有什麼特別的。
第一組for循環實現了真正的算法。我們在這裏利用輸出數據中的基於列的模式。對於一個給定的真值表,最左邊的列將有兩部分:前半部分全部爲0,後半部分全部爲1.由於我們預先填充了零,因此將會應用一半填充半列開始的列高度我們需要的所有1。第二列將有1/4行0,1/4,1,1/4,0,1/4 1.因此,兩次填充將應用我們需要的所有1。我們重複這個,直到我們到達最右邊一列,在這種情況下,每隔一行是0或1.
我們開始說「我需要一次填充一半行」()。然後我們遍歷每一列。第一列從要填充的位置開始填充,然後用1填充多行。然後,我們增加行數並將填充大小減半(現在我們一次填充1/4行,但是我們跳過空白行並填寫第二次)下一列。
例如:
#include <iostream>
#include <vector>
int main()
{
const unsigned n = 3;
std::vector<std::vector<int> > output(n, std::vector<int>(1 << n));
unsigned num_to_fill = 1U << (n - 1);
for(unsigned col = 0; col < n; ++col, num_to_fill >>= 1U)
{
for(unsigned row = num_to_fill; row < (1U << n); row += (num_to_fill * 2))
{
std::fill_n(&output[col][row], num_to_fill, 1);
}
}
// These loops just print out the results, nothing more.
for(unsigned x = 0; x < (1 << n); ++x)
{
for(unsigned y = 0; y < n; ++y)
{
std::cout << output[y][x] << " ";
}
std::cout << std::endl;
}
return 0;
}
你想在二進制數字系統中編寫從0到2^N - 1的數字。它沒有什麼聰明的。您只需填充二維數組的每個單元格。你做不到比這更快。
您可以直接在數字上進行迭代。請注意,最右邊的列重複0 1
,然後下一列重複0 0 1 1
,然後是下一個0 0 0 0 1 1 1 1
依此類推。每列都重複2^columnIndex(從0開始),然後是1。
好吧,我知道,但我認爲有更快的事情。 – Ahmed 2010-08-17 16:55:12
您可以通過注意矩陣中的每一行代表一個n位二進制數,將其問題分成兩部分,其中n是概率數[原文如此]。
,所以你需要:
編輯:
如果你只擔心運行時間,那麼對於常數n,你總是可以預先計算表格,但它認爲你的計算複雜度爲O(2^n)
爲了詳細說明JK的答案... 如果你有n個布爾值(「概率」?),那麼你需要
卡諾圖或奎因 - 麥克羅斯基
http://en.wikipedia.org/wiki/Karnaugh_map http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
那應該朝向你在最小化所產生的真值表正確的方向。
我不想將其最小化,只是爲了創建它。 – Ahmed 2010-08-18 08:17:39
抱歉 - 太快閱讀這個問題 - 誤解了你的目標。 – schemathings 2010-08-18 15:01:49
我認爲'概率'在這裏是錯誤的詞。概率不會是一個整數。 – 2010-08-18 15:13:42