アルゴリズムレッスンを見て整理した内容

さいきかんすう

じこよびだししかんすう
無限ループに陥りたくないなら
1.終了条件を指定する必要があります.少なくとも1つ以上が無限ループに陥らない場合があるべきである.(base case)
2.無限ループを繰り返すと、最終的にbasecaseに収束します.

フィボナッチ、工場

最大公約数(gcd)、最小公倍数

数学関数だけでなく、他の多くの問題も解決できます.

文字列の長さを計算する方法

この概念は?これは不思議ですね...
こんな戻り方で近づいてみよう…!

コード実装でそうすることができます.

文字列を1つずつ減らして("")に近づける方法!

すべてのループ関数は、重複文に変更できます.

同駅も設立される.すべての複文は再帰的に表現することができる.

サイクル関数は複雑なアルゴリズムを簡単に分かりやすくする.

ですが、関数呼び出しによってオーバーヘッドが発生する可能性があります.

さいきせっけい

少なくとも1つのbasecase、すなわち循環終了しないcaseが必要である

無限ループに陥らないように

すべてのcaseは最終的にbasecaseに収束します!!!

暗黙パラメータを明示パラメータに変換!~~!!

back-tracking

歩いているうちに袋小路に出くわして、また帰ってしまった.
私が最近決めた決定を覆して、他の選択を探します.
ステータススペースツリーを表示します.

すべてのノードがステータススペースツリーをブラウズする必要はありません.
私が選んだ道が間違っていることに気づいたら、私は振り向いて別の道を選んだ.
遡及とは,深さ優先探索方式で探索探索探索解を行うアルゴリズムである.

トレースの例

https://www.acmicpc.net/problem/15652
問題の説明
自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.

1からNまで、自然水中からM個の数列

を選ぶ.

などの数字を複数回選択できます.

均一な数列は降雨順に

並べなければならない.
解答方法

メイン関数にnとmを入力します.

per(ディスプレイスメント)という名前の配列に、シーケンスを構成する値が格納されます.

goという関数は、再帰呼び出しによってシーケンスを構成する.
−go関数におけるcntがmに等しい場合は脱出可能な条件である.
go関数を呼び出すたびにcnt値が1増加し、無限ループに陥ることを回避します.
-go関数にfor文が表示されると、再帰呼び出しが発生します.

go関数のパラメータから見ると、最初のパラメータcntは現在いくつかの値を与えている.(動的構成のシーケンス長または各アレイの値数)

go関数の2番目のパラメータcurはfor文で★iの初期値★である.

現在、cntの列1番目のiに1の値が加算されます.(配列のindexは0から始まる必要があり、シーケンスは1からNまでの値を含む必要があるためです.)

であり、同じ値をシーケンスに含めることができるので、再帰関数を呼び出すときにgo(cnt+1,i)を呼び出す.同じ値をシーケンスに含めることができない場合は、go(cnt+1,i+1)を呼び出すとよい.

の部分を理解していない場合は、手でコードを描く作業が役立ちます.

#include <iostream>

using namespace std;

void go(int cnt, int cur);
int n, m;
int per[8] = { 0, };

int main(void) {
	cin >> n; // 전체수
	cin >> m; // 순열 개수

	go(0, 0);
	return 0;
}


void go(int cnt, int cur) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << per[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = cur; i < n; i++) {
		per[cnt] = i + 1;
		go(cnt + 1, i);
	}
}

上の問題を分かりやすい図にまとめてみました.

1.レベル1で1を選択し、レベル2でまず1を選択します.
2.総選択値の個数2がmに等しいため、2級から1級に再昇格する.(逆トレース)
3.レベル2ステージ値の1は既に使用されていますか?したがって、2番目の値2が選択されます.
4.上記の2番目の手順を繰り返します.
5.レベル2の数字3を選ぶ過程も同じです.
6.上記第2の手順を繰り返す.
7.[ 1,1],[1,2],[1,3]が出力されました.したがって、レベル1の選択値は2となり、2で選択可能なレベル2の値も上記の手順と同様になり、[2,2]、[2,3]が出力される.
8.残りの過程は自分で推測してください…!