재 귀 구 배열 과 조합 (중복 과 중복 없 음)
1. 배열 에 중복 요소 가 없습니다. 예전 부터 지금까지 배열 의 요 소 를 출력 배열 에 순서대로 배치 하고 다 놓 으 면 출력 한 다음 에 요소 의 위 치 를 재 귀적 으로 바 꾸 어 모든 배열 을 출력 할 때 까지 합 니 다.재 귀적 으로 하나의 태그 배열 을 사용 하여 어떤 요소 가 이미 배치 되 었 는 지 기록 합 니 다.
2. 배열 에 중복 요소 가 있 습 니 다. 이것 은 1 과 비슷 합 니 다. 하나의 태그 배열 로 특정한 요소 의 횟수 를 기록 하고 방치 할 때마다 1 을 줄 이 는 것 과 차이 가 있 습 니 다.
문제 1 의 코드 는 다음 과 같다.
void PermRecur(vector& ivec, vector& use, vector& res, int k)
{
// k size,
if (k == ivec.size())
{
for (int i = 0; i < k; ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = 0; i < ivec.size(); ++i)
{
// 0
if (use[i] == 0)
{
// 1
use[i] = 1;
res[k] = ivec[i];
PermRecur(ivec, use, res, k + 1);
// 0
use[i] = 0;
}
}
}
void Perm(vector& ivec)
{
int size = ivec.size();
assert(size > 0);
// 0
vector use(size);
vector res(size);
PermRecur(ivec, use, res, 0);
}
void main()
{
int a[] = {1, 2, 3};
vector ivec(a, a + 3);
Perm(ivec);
}
문제 2 의 코드 는 다음 과 같다.
#include
#include
#include
using namespace std;
void PermRecur(vector& num, vector& use, vector& res, int k)
{
// k size,
if (k == res.size())
{
for (int i = 0; i < k; ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = 0; i < num.size(); ++i)
{
// 0
if (use[i] > 0)
{
// 1
--use[i];
res[k] = num[i];
PermRecur(num, use, res, k + 1);
// 1
++use[i];
}
}
}
void Perm(vector& ivec)
{
assert(!ivec.empty());
int size = ivec.size();
vector res(size);
vector use;
vector num;
// ivec , num
use.push_back(1);
num.push_back(ivec[0]);
for (int i = 1; i < size; ++i)
{
int j = 0;
for (; j < i; ++j)
{
if (ivec[i] == ivec[j])
{
++use[j];
break;
}
}
if (j == i)
{
use.push_back(1);
num.push_back(ivec[i]);
}
}
PermRecur(num, use, res, 0);
}
void main()
{
int a[] = {1, 2, 2};
vector ivec(a, a + 3);
Perm(ivec);
}
n 크기 의 배열 을 지정 하여 모든 부분 집합 을 출력 합 니 다.하위 문 제 는 n 개 요소 에서 m 개 요 소 를 선택 한 다음 순환 호출 하면 됩 니 다.
1. 배열 에 중복 되 는 요소 가 없습니다. 예전 부터 나중에 배열 의 요 소 를 출력 배열 에 순서대로 배치 하고 요소 의 개수 가 m 에 이 르 렀 을 때 출력 하면 됩 니 다.그리고 재 귀 를 해서 나머지 요소 와 m 개의 요 소 를 교환 합 니 다.
2. 배열 에 중복 되 는 요소 가 있 습 니 다. 전체 배열 과 유사 합 니 다. 먼저 요소 의 횟수 를 다시 계산 한 다음 에 재 귀 합 니 다.
문제 1 의 코드 는 다음 과 같다.
#include
#include
#include
using namespace std;
void CombRecur(vector& ivec, vector& res, int m, int begin, int k)
{
// k m
if (k == m)
{
for (int i = 0; i < res.size(); ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = begin; i < ivec.size(); ++i)
{
res[k] = ivec[i];
CombRecur(ivec, res, m, i + 1, k + 1);
}
}
void Comb(vector& ivec)
{
assert(!ivec.empty());
for (int i = 1; i <= ivec.size(); ++i)
{
vector res(i);
CombRecur(ivec, res, i, 0, 0);
}
}
void main()
{
int a[] = {1, 2, 3};
vector ivec(a, a + 3);
Comb(ivec);
}
문제 2 의 코드 는 다음 과 같다.
#include
#include
#include
using namespace std;
void CombRecur(vector& num, vector& use, vector& res,
int m, int begin, int k)
{
// k m , m
if (k == m)
{
for (int i = 0; i < res.size(); ++i)
cout << res[i] << ' ';
cout << endl;
return;
}
for (int i = begin; i < num.size(); ++i)
{
// 0
if (use[i] > 0)
{
// 1
--use[i];
res[k] = num[i];
// begin i, i
CombRecur(num, use, res, m, i, k + 1);
++use[i];
}
}
}
void Comb(vector& ivec)
{
assert(!ivec.empty());
int size = ivec.size();
vector num;
vector use;
// ivec , num
num.push_back(ivec[0]);
use.push_back(1);
for (int i = 1; i < size; ++i)
{
int j = 0;
for (; j < i; ++j)
{
if (ivec[i] == ivec[j])
{
++use[j];
break;
}
}
if (j == i)
{
use.push_back(1);
num.push_back(ivec[i]);
}
}
// 1~n 1~n
for (int i = 1; i <= size; ++i)
{
vector res(i);
CombRecur(num, use, res, i, 0, 0);
}
}
void main()
{
int a[] = {1, 2, 2};
vector ivec(a, a + 3);
Comb(ivec);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
NYOJ 488 소수 링/ / 제목 링크:http://acm.nyist.net/JudgeOnline/problem.php?pid=488 이 문 제 는 hdu 1016 을 각색 한 것 이지 만 고 친 것 은 많 지 않다. 마찬가지 입 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.