質問: sum + stoi(S.substr(p1, p2 ) ); cout << "stoi(S.substr(p1, p2 ) )->" << stoi(S.substr(p1, p2)) << endl; cout << "sum->" << sum << endl; } else if (p1 + p2 > S.length()) { return 0; } dfs(p1, p2 + 1); dfs(p1 + 1, p2); } int main() { cin >> S; dfs(0,1); getchar(); //特に意味なし getchar(); //特に意味なし return 0; } ``` 125を入力した場合の実行結果 125 p1->0p2->1 stoi(S.substr(p1, p2 ) )->1 sum->1 p1->0p2->2 stoi(S.substr(p1, p2 ) )->12 sum->13 p1->0p2->3 stoi(S.substr(p1, p2 ) )->125 sum->138 p1->0p2->4 p1->1p2->3 p1->1p2->2 stoi(S.substr(p1, p2 ) )->25 sum->163 p1->1p2->3 p1->2p2->2 p1->1p2->1 stoi(S.substr(p1, p2 ) )->2 sum->165 p1->1p2->2 stoi(S.substr(p1, p2 ) )->25 sum->190 p1->1p2->3 p1->2p2->2 p1->2p2->1 stoi(S.substr(p1, p2 ) )->5 sum->195 p1->2p2->2 p1->3p2->1 この問題で再帰関数を使って全ての組み合わせを実行する方法はどんなプログラムになるのでしょうか。
回答: こんにちは。 ツリーサーチを使うのは良い方向性と思うのですが、漏れと重複なく2進数値を枚挙するのが難しいかもしれません。普通にインクリメントが優れているだけになかなか思いつかないです。 従って、再帰を使うことが目的であれば、 > > for (mask = 0; mask < (1 << keta - 1); mask++) > > > のループを再帰でループさせれば簡単です。 スタックの消費も酷いし可読性は劣化するし、好ましい方法ではないですけど、目的や性能で縛るのではなく、手段で縛るとある意味仕方のないことかも。 他に2進数のビット列を漏れや重複なく枚挙する方法として、グレイ・コードもあります。ハノイの塔はグレイ・コードで解けるらしいです。ハノイの塔って再帰で解くことが多いので、ハノイの塔アルゴリズムでグレイ・コードを生成すると、もしかするとスタックの消費を現実的な線にできるかも知れません。(スタック消費を桁数程度に抑えることができるたら許容されそうな気がします。インクリメントだと桁数のべき乗なのであんまりですから。) 実際にそうなるか検討していません。感ですので外れてたらごめんなさい。