智商大考验之排列组合
发布网友
发布时间：2022-04-25 20:32
共5个回答
热心网友
时间：2022-06-17 04:44
#include <stdio.h>
#include <stdlib.h>
void Print(int* beg, int* end)
{
while(beg != end)
printf("%d ", *beg++);
putchar('\n');
}
void C(int n, int m)
{
int i;
int *p1, *p2, *trace_back;
if(n == m)
{
for(i = 0; i < m; ++i)
printf("%d ", i + 1);
return;
}else if(m > n)
return;
p1 = (int*)malloc(sizeof(int) * m);
for(i = 1; i <= m; ++i)
p1[i - 1] = i;
trace_back = p1 + m - 1;
do{
Print(p1, p1 + m);
if(*trace_back < n)
++*trace_back;
else
{
while(*trace_back - *(trace_back - 1) <= 1)
--trace_back;
--trace_back;
++*trace_back;
for(p2 = trace_back + 1; p2 != p1 + m; ++p2)
*p2 = *(p2 - 1) + 1;
trace_back = p1 + m - 1;
}
}while(*p1 != n - m + 1);
Print(p1, p1 + m);
free(p1);
}
int main()
{
C(5, 3);
return 0;
}
n选m的排列：
#include <stdio.h>
#include <stdlib.h>
inline void Swap(int* lhs, int* rhs)
{
int tmp = *lhs;
*lhs = *rhs;
*rhs = tmp;
}
void Reverse(int* beg, int* end)
{
while(beg < end)
Swap(beg++, --end);
}
void Print(int* beg, int* end)
{
while(beg != end)
printf("%d ", *beg++);
putchar('\n');
}
inline int Cmp(const void* lhs, const void* rhs)
{
return *(const int*)rhs - *(const int*)lhs;
}
void P(int* beg, int* mid, int* end)
{
if(end- mid > 1)
qsort(mid, end - mid, sizeof(int), Cmp);
int* nav = end - 1;
Print(beg, mid);
for(;;)
{
int* tmp = nav;
if(*--nav < *tmp)
{
int* rmbt = end;
while(*--rmbt <= *nav);
Swap(nav, rmbt);
if(tmp <= mid)
{
Reverse(tmp, end);
if(end - mid > 1)
qsort(mid, end - mid, sizeof(int), Cmp);
}
Print(beg, mid);
nav = end - 1;
}
if(nav == beg)
{
Reverse(beg, mid);
break;
}
}
}
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
P(a, a + 3, a + 5);
return 0;
}
递归全排列：
#include <stdio.h>
#include <stdlib.h>
inline void Swap(int* lhs, int* rhs)
{
int tmp = *lhs;
*lhs = *rhs;
*rhs = tmp;
}
void Print(int* beg, int* end)
{
while(beg != end)
printf("%d ", *beg++);
putchar('\n');
}
void P(int* cbeg, int* beg, int* end)
{
int* p;
if(beg == end - 1)
Print(cbeg, end);
else
for(p = beg; p != end; ++p)
{
Swap(p, beg);
P(cbeg, beg + 1, end);
Swap(p, beg);
}
}
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
P(a, a, a + 3);
return 0;
}
还有个递归n选m的，考虑到其实现比较糟糕，所以不写了。
你要哪个?
热心网友
时间：2022-06-17 04:44
using namespace std;
ifstream fin ("pl.in");
ofstream fout("pl.out");
int kin(int a[],int t,int m){
//判断a数组中从a[1]~a[t]中是否有m ,判重
for (int i=1;i<=t;i++)
if (a[i]==m) return 1;
return 0;
}
void aout(int a[],int r){
//输出a数组
for (int i=1;i<=r;i++)
fout<<a[i]<<' ';
fout<<endl;
}
int main(){
int n,r,s,i,k;
int a[21];
fin>>n>>r;
i=1;k=1;s=0;
a[i]=k;//试探的数为k,试探位置为i+1
while (i>=0){
while (kin(a,i,k)) k++;
if (k<=n){
i++;//试探成功
a[i]=k;
k=1;
}
else{
k=a[i]+1;
i--;//回溯
}
if(i==r){
aout(a,r);
s++;
k=a[i]+1;
i--;
}
}
fout<<"共有"<<s<<"个数"<<endl;
}
热心网友
时间：2022-06-17 04:45
#include<iostream>
using namespace std;
void print(int a[], int n)
{
for (int i=0; i<n; i++) cout<<a[i];
cout<<endl;
}
void swap(int &a, int &b)
{
int t = a; a = b; b = t;
}
void reverse(int a[], int i, int j)
{
while (i<j) swap(a[i++],a[j--]);
}
void main()
{
int i, j, n;
cout<<"n=";
cin>>n;
int* a = new int[n];
for(i = 0; i < n; i++)
a[i] = i + 1;
while (1)
{
print(a, n);
for (i=n-2; i>=0; i--)
if (a[i] < a[i+1]) break;
if (i==-1) break;
for (j=n-1; j>i; j--)
if (a[j] > a[i]) break;
swap(a[i],a[j]);
reverse(a,i+1,n-1);
}
}
热心网友
时间：2022-06-17 04:45
如果N不大,用递归就可以了
热心网友
时间：2022-06-17 04:46
{
int i;
char t;
if (m<n-1) {
permutation(a, m+1, n);
for (i=m+1;i<n;i++) {
t=a[m]; a[m]=a[i]; a[i]=t;
permutation(a, m+1, n);
t=a[m]; a[m]=a[i]; a[i]=t;
}
} else
{
printf("%s\n", a);
}
}
int main() {
char a[]="ABCD";
permutation(a, 0,4);
return 0;
}
