入門
モスクワからモスクワへの移動に30分または1時間を費やさなければならない私たちは、まだ完全に目覚めていない脳を占有して暖めるものを探す必要があります。 誰かが読む、誰かが鳥を投げる、誰かが数学のパズルを解く。 たとえば、古典的なパズル：バスチケットの6桁の中に、番号100が得られるようにブラケットと演算子を配置します。解決策を見つけることができないことがあります。 アルゴリズムについて考えてみてください。
ブラケットと演算子を置き換えて、いくつかの数学エンジンをチェックする「額に」ソリューションは適合しませんでし
ポイントに行きましょう
明らかに、アルゴリズムの複雑さは指数関数的です。1枚のシートを追加すると、前のツリーの各シートを条件付きでノードに置き換えます。 いくつかの木は同じですが、漸近的には差はわずかです。
ただし、6桁の場合、プログラムは1秒未満で実行されるため、生存権があります。
C ++で実装します。 免責事項：私はまだ学習中です。 率直に言って悪いコードまたは単に最適でないコードが表示される場合は、お知らせください。
かなり簡単なコンストラクターをスキップして、次のツリーの作成を検討してください。 ツリーのノードは演算子であるため、括弧や優先順位に煩わされることはありません。 連結、加算、減算、乗算、除算の5つの演算子のみがあります。 単項マイナスは使用されません。 次の原則に従ってツリーをソートします。各右サブツリーに対して、すべての左サブツリーに沿ってパスを作成します。 演算子ごとに、つまり5回繰り返します。 サブツリー内では、まったく同じことが起こります。
ツリー生成
void BinTree::buildNext() { if (type == NUMBER) // , throw BinTreeLastTree(); // . try { left->buildNext(); } catch (BinTreeLastTree) { try { right->buildNext(); } catch (BinTreeLastTree) { bool isLast = false; leftSize++; if (leftSize == size) { leftSize = 1; type = (Operation)(type + 1); if (type == NUMBER) // , { type = CONCAT; // isLast = true; // «». } } delete left; delete right; generateSubTrees(); if (isLast) throw BinTreeLastTree(); // , « ». } } }
また、計算は成り立たないため、詳細については説明しません。
主な問題は同じ解決策でした。シリコンの友人は、（1+（2 + 3））と（（1 + 2）+3）は2つの異なるものであると確信しました。 その反対を説明するために、ブラケットの「スマートな」配置を適用し、結果のフィルタリングに時間を浪費しないように、これをstd :: setに割り当てます。
括弧コード
std::string BinTree::toString(bool parentheses) { switch (type) { case CONCAT: return left->toString() + right->toString(); case ADD: { std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)), rightStr = right->toString(!(right->getType() == ADD || right->getType() == SUB)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":""); } case SUB: { std::string leftStr = left->toString(!(left->getType() == ADD || left->getType() == SUB)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + right->toString() + (parentheses?")":""); } case MUL: { std::string leftStr = left->toString(!(left->getType() == MUL || left->getType() == DIV)), rightStr = right->toString(!(right->getType() == MUL || right->getType() == DIV)); return (parentheses?"(":"") + leftStr + operationSymbol[type] + rightStr + (parentheses?")":""); } case DIV: return (parentheses?"(":"") + left->toString() + operationSymbol[type] + right->toString() + (parentheses?")":""); case NUMBER: { char str[2] = {(char)(digit[0]+'0'), '\0'}; return str; } default: ; } throw BinTreeException(); }
出来上がり！
コールコード
int main() { std::string input; std::cin >> input; std::cout << busPuzzleSolve(input); return 0; } std::string busPuzzleSolve(std::string input) { return BinTree(input.c_str()).solve(); }
結果
123654 ((((1*2)+3)*6)-5)*4 ((1*(2+(3*6)))+5)*4 ((1*(2+3)*6)-5)*4 ((1*(2-3))+6)*5*4 ((1*2)+(3*6)+5)*4 ((1*2)-(3-6))*5*4 ((1*2)-3+6)*5*4 ((1/(2-3))+6)*5*4 ((12*3)-(6+5))*4 ((12*3)-6-5)*4 (1+23+6-5)*4 (1-((2*3)-(6*5)))*4 (1-(2*3)+(6*5))*4 (12+(3*6)-5)*4 1*(((2+3)*6)-5)*4 1*(2+(3*6)+5)*4 1*(2-(3-6))*5*4 1*(2-3+6)*5*4 1+((2+3+6)*(5+4))
rarアーカイブ内のSkyDriveのコード（+プロジェクトファイルコード::ブロック）（〜2.56 KiB）。
Pastebinコード。