暴力搜索是一個有趣的東西。至少劉汝佳是這么認為的。編程之美的4.10節就是典型的暴力題。雖然作者將其難度定義為一顆星，但卻不能因此認為這個類型的問題就是那么容易的，很多可能需要一些有創造力的想法。

不妨試試下面這幾道題：

Island of Logic:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=533

Meta-loopless sort:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=46

How big is it?:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=953

No tipping:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=1064

Addition chains:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=470

我先把其中的例題用深搜來試解一下。因為題目的解空間非常小，所以沒有做什么優化。

關于節后問題：問題1，N位的總回文數為：9*pow(10, n/2 + n&1 - 1)。問題2見下面的代碼。

1. 神奇的9位數：

vector<int> res;
int used[10];

void dfs(int i = 1, int v = 0) {
if (i == 10) {
res.push_back(v);
return;
}

for (int k = 1; k <= 9; ++k) {
if (used[k]) continue;
int vv = v*10 + k;
if (vv%i) continue;
used[k] = 1;
dfs(i+1, vv);
used[k] = 0;
}
}

int main() {
dfs();
for (size_t i = 0; i < res.size(); ++i)
cout<<res[i]<<'\n';
return 0;
}

2. 人過大佛寺×我=寺佛大過人以及問題2

下面的程序沒有經過優化，所以會比較慢一點。另外，評估函數也只是簡單滿足需要。

vector<string> results;
vector<int> tested;
vector<int> used;

string equation;
int base;

bool satisfy(const string& s) {
char* next = 0;
int r = strtoul(s.c_str(), &next, base);
while (*next != '=') {
char op = *next++;
int t = strtoul(next, &next, base);
switch(op) {
case '+': r += t; break;
case '-': r -= t; break;
case '*': r *= t; break;
case '/': r /= t; break;
}
}

int b = strtoul(++next, 0, base);
return r == b;
}

void init(const string& str, int b = 10) {
equation = str;
base = b;
used.assign(base, 0);
tested.assign(26, 0);
results.clear();
}

void dfs(size_t i = 0) {
while (i < equation.length() && !islower(equation[i])) ++i;
if (i >= equation.length()) {
if (satisfy(equation))
results.push_back(equation);
return;
}

char c = equation[i], cc = c;
if (tested[c - 'a']) return;
tested[c - 'a'] = 1;

for (int k = (i == 0 || !isalnum(equation[i-1])); k < base; ++k) {
if (used[k]) continue;
used[k] = 1;
char t = k < 10? '0' + k: 'A' + k - 10;
replace(equation.begin() + i, equation.end(), cc, t);
dfs(i+1);
cc = t; // for next iteration
used[k] = 0;
}
replace(equation.begin() + i, equation.end(), cc, c);
tested[c - 'a'] = 0;
}

void output(ostream& os) {
if (results.size()) {
for (size_t i = 0; i < results.size(); ++i)
os<<results[i]<<'\n';
}
else
os<<"No solution.\n";
}

int main() {
init("abcde*f=edcba", 10);
dfs();
output(cout);
cout<<'\n';

init("he*he=she", 10);
dfs();
output(cout);
cout<<'\n';

init("he*he=she", 16);
dfs();
output(cout);

return 0;
}

轉載于:https://www.cnblogs.com/acmaru/archive/2011/03/18/1987923.html

總結

以上是生活随笔為你收集整理的哑谜，回文和暴力之美的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。