我在網上發現了一個有趣的問題：
你需要計算13位數字系統中13位數字的漂亮（前六位數字之和等于后六位數字之和）的數量，例如：數字0055237050A00是漂亮的，因為0 0 5 5 2 3 = 0 5 0 A 0 0，而數字 1234AB988BABA 是丑陋的，因為 1 2 3 4 A B！= 8 8 B A B A
我決定為此撰寫一個類，它將以轉換為陣列的形式存盤數字：
struct Number
{
explicit Number(size_t number);
Number& operator ();
Number& operator (int);
bool is_beautiful() const;
private:
std::array<uint8_t, 13> m_digits;
};
然后，在回圈中，檢查間隔中的所有數字：
Number number{ 0u };
size_t count_numbers = 0u;
for (size_t i = 0u; i < std::pow(13,13); i) {
count_numbers |= (number ).is_beautiful();
}
但是我想問一下這是否是最佳解決方案，也許您可??以使用算術在沒有陣列的情況下以某種方式做到這一點？如果是這樣，那么如何實施？
也許有一些特殊的演算法可以解決這個問題
uj5u.com熱心網友回復：
觀察1：第7位數字是否“漂亮”無關緊要，因此您只需乘以基數即可，無需遍歷所有數字。
Observation2：一旦你設定了除最后一個之外的所有數字，對于漂亮的數字，最多只有一個可行的解決方案。它的概括表明，一旦創建了其他一些數字，其他數字也隨之創建，因此這里肯定有改進的余地。
Observation3：這基本上歸結為“有多少種方法可以對每個數字求和 X”，并迭代所有這些選項，對它們進行平方（前 6 位數字和后 6 位數字）。現在，這要簡單得多，因為數字的總和與它們的數量呈線性關系，而不是指數。
這可以為我們提供一個 DP 解決方案，以獲得獲得每個總和的多種方法：
// stop clause: all zeros, you cannot get otherwise to sum 0.
DP[0, i] = 1
// There is no way to get to
DP[x, 0] = 0 | x > 0
DP[x, i] = DP[x-0, i-1] DP[x-1, i-1] ... = DP[x-(BASE-1), i-1]
用所有選項填充 DP 矩陣后，解決方案是：
(DP[0, 6]^2 DP[1, 6]^2 ... DP[MAX_SUM, 6]^2) * BASE
這是因為，對于某些 sum X，您有DP[X,6]^2辦法DP[X,6]為前 6 位數字創建漂亮的數字，對于最后 6 位數字也是如此。
此外，您需要乘以 BASE，作為第 7 位的選項數。
uj5u.com熱心網友回復：
雖然我普遍同意@amit的解決方案，但需要注意的一件事是，如果結果沒有被快取，DP 解決方案實際上對 OP 的特定問題有相當多的遞回，這將導致大約 350,000,000 次呼叫DP.
事實上，350,000,000 比 13^6 大 70 倍，所以你也可以考慮更天真地做最后一步，首先找到 0 到 13^6 之間每個數字的位數和，并存盤你可以存盤多少次sum 到一個特定的總和，該總和在 0 到 12*6 之間的范圍內。然后對時間進行平方，因為每邊有 6 個數字，第 7 個數字乘以 13。
uj5u.com熱心網友回復：
創建一個 6 行 13*6=78 列的整數矩陣。第 i col j 行包含第 i 1 位數字的總和為 j 的數字的計數。
將第 1 行初始化為 0 - 12 列中的 1。通過將前一行的計數相加來填充每個連續行，這些行移位 0 到 12 個空格。
最后，您將獲得所有可能數字和的計數。
取數字計數的平方和，然后乘以 13 以獲得可能的中心值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/367789.html
上一篇：線性規劃的變化？
下一篇：收集添加和洗掉元素時的代碼改進