アルゴリズム::白準::Breutforce::15652::NとM(4)

9163 ワード
白駿 アルゴリズム#アルゴリズム# bruteforce テキストリンク

質問する



自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.
  • 1からNまで、自然水中からM個の数列
    • を選ぶ.
  • などの数字を複数回選択できます.
  • の数列を選択するには、降雨順に並べます.
  • 長さKの数列AはA 1≦A 2≦...≤AK-1≤AKが満たされた場合、降雨順と呼ぶ

    • 質問へのアクセス

  • の数値で重複する昇順を許可し、昇順コードの一部を変更するだけで実現できます.
  • 以前にこのサイクルに数字iが追加された場合、次のサイクルで数字i + 1から使用することができ、iから使用することができるようになった.

    • コード#コード#


    じゅんじゅんふごう

    #include <iostream>
using namespace std;
int n, m, a[8];
void solve(int idx, int num) {
	if (idx == m) {
		for (int i = 0; i < m; ++i) cout << a[i] << ' '; cout << '\n';
		return;
	}
	for (int i = num; i <= n; ++i) {
		a[idx] = i;
		solve(idx + 1, i);	// i + 1이면 오름차순, i니까 비내림차순.
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	solve(0, 1);
}

    オプションコード

    #include <iostream>
using namespace std;
int n, m, a[8];
void solve(int num, int cnt) {
	if (cnt == m) {
		for (int i = 0; i < m; ++i) cout << a[i] << ' '; cout << '\n';
		return;
	}
	if (num > n) return;
	a[cnt] = num;
	solve(num, cnt + 1);	// num을 선택하는 경우
	solve(num + 1, cnt);	// num을 선택하지 않는 경우
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	solve(1, 0);
}

    結果


    [独学]インストールGit(Mac版)
    byteバイト配列の圧縮