Sum of Integers|AOJ|深さ優先探索(DFS)
深さ優先探索(DFS)を勉強中で、DFSを使って解ける優しめ問題という事で、
整数の和 | Aizu Online Judge を解きました。
<題意>
0 〜 9 の数字から異なる数をN個取り出して、和がSとなる組み合わせが何個あるか出力する
#include <bits/stdc++.h> using namespace std; struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star; // i --> 0 - 9までの数字 // sum --> 合計値 // cnt --> 和がSとなる組み合わせの数 // total --> 足す数(N個まで足す) int N, S, cnt; void dfs( int i, int sum, int total ) { //N回を満たしている 且つ 合計がSに達したものをcountする if( total == N && sum == S ) { cnt++; return; } //0-9まで探索したら or 足す回数がN回に達したら 終わり if( i == 10 || total == N ) return; //合計に i を足す場合 -> 足す回数を +1 する dfs( i + 1, sum + i, total + 1 ); //合計に i を足さない場合 dfs( i + 1, sum, total ); } int main() { while( cin >> N >> S ) { if( N == 0 && S == 0 ) break; //合計値の初期化 cnt = 0; //dfs( 数字の0から, 合計値0から, 足す数字0から) dfs( 0, 0, 0 ); cout << cnt << endl; } return 0; }
DFSを本で勉強したのですが、さっぱり実装出来る気がしなくて、
処理をいくつかに分割して書いてやっとまとまりました。
手順としては下記の工程を経ています。
1)足し算部分の再帰を書く
2)合計を取る部分を書く
3)合計がSとなったものをcountする部分を書く
4)合計に足す場合と、足さない場合を書く
5)N個だけ選んで和を取る部分を書く
個々の処理がどうなっているか良く解ったので理解が進みました。
この問題を解く際、グローバル変数に count と云う変数名を使ったら gccに怒られました。
std::count と区別がつかないよって事らしいです。
それから、returnで何も返さない関数はvoidで宣言する様で、そこも新たに覚えました。
(何も返さない関数を初めて書きました...!)
次はstack編も覚えなくてはみたいな感じです。