poj1833
题目连接：http://poj.org/problem?id=1833
题意：中文题目题意不多说，只是用到了STL里面的next_permutation()函数
/*
next_permutation(op1,op2)
STL中的排列函数，op1存放数组头地址，op2存放排列的长度。每运行一次该函数，op1中存放原排列的下一个排列。
最后一个排列时返回NULL
*/
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main()
{
int k;
int m,n;
int a[1025];
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&m,&n);
for(int i=0;i<m;i++)
{
scanf("%d",a+i);
}
for(int i=0;i<n;i++)
{
if(next_permutation(a,a+m)==NULL)
sort(a,a+m);
}
for(int i=0;i<m;i++)
{
if(!i)printf("%d",a[i]);
else printf(" %d",a[i]);
}
printf("\n");
}
return 0;
}
POJ1850&POJ1496
题目连接：http://poj.org/problem?id=1850 http://poj.org/problem?id=1496
题意：假定a-z分别为1-26，在此基础上得到长度不大于10的升序小写字母片段，输入一个字符片段，判断该片段在所有的片段中的序号
思想：组合数C（m，n），主要考虑从m个数中取出n个。
/****************************
1.先通过计算分别得到每一位数（这儿的位数是指字符片段的长度）对应的第一个片段的序号，在此基础上，同位数的片段是
一个递增的过程，通过计算得到int num[]= {0,26,325,2600,14950,65780,230230,657800,1562275,3124550,5311735};
2.对于题意中明确说了的升序，可以通过一个标志变量来判断，直接用片段长度即可，当片段不是升序时，使其长度变成-1
3.C(m,n)=C(n-1,m-1)+C(n-1,m);
4.把一个大的字符串分理处几个字符串，比如说字符串长度为5，那么分成两部分，第一部分为长度1到4的和，此时sum=
C(26，1)+C(26，2)+C(26，3)+C(26，4).第二部分对应于每一位下于该位符号对应的字符串个数
****************************/
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int num[]= {0,26,325,2600,14950,65780,230230,657800,1562275,3124550,5311735};
int combine(int n,int m)//组合数的计算方法
{
int ans=1;
for(int i=1; i<=m; i++)
ans=ans*(n-i+1)/i;
return ans;
}
int main()
{
freopen("C:\\Users\\Administrator\\Desktop\\in.txt" , "r" , stdin);
char str[11];//输入的片段
int len;//片段长度
int sum;//总和
int p;
while(scanf("%s",str)!=EOF)
{
sum=0;
len=strlen(str);
for(int i=1; i<len; i++)//在位数的基础上找首个片段所在
{
sum+=num[i];
if(str[i]<str[i-1])//非升序的情况
{
len=-1;
sum=0;
}
}
if(len==-1)
{
printf("0\n");
continue;
}
for(int i=0;i<len;i++)//把一个片断分离成多个片段的组成，在这儿是分成一个一个的
{
if(i)p=str[i-1]-'a'+1;
else p=0;
for(int j=p;j<str[i]-'a';j++)
{
sum+=combine(25-j,len-i-1);
}
}
cout<<sum+1<<endl;
}
return 0;
}
POJ1942
题目连接：http://poj.org/problem?id=1942
题意：找规律的题，就是一个组合数的代码，关键在于这是一个坑爹的题，用java来写会有精度的丢失，用int存不了，只能用double来，但是在输出时要注意转化为int，另外还有一点，题目说输入的两个数m，n是32位的数，但是ac代码检测只能计算到514,。
不多说，就是一个组合的公式的实现代码
这个题不推荐做，练手可以
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cstdlib>
using namespace std;
//mn应该小于515
double ans,n,m;
double mmin,mmax;
int main(){
cout<<fixed<<setprecision(0);
while(cin>>n>>m){
if(n==0 && m==0)
break;
mmin=min(m,n);
mmax=max(m,n);
ans=1;
for(unsigned i=1;i<=mmin;i++)
{
ans=ans*(mmax+i)/i;
}
cout<<ans<<endl;
}
return 0;
}
nkoj1038&poj2245
题目连接：http://acm.nankai.edu.cn/p1038.html http://poj.org/problem?id=2245
题意：给定一个n个数的序列，选择C（n，6）的组合数，并把具体的组合输出，就是一个组合数的实现
pe次数比较多的一个题 被坑了几次，注意最后一组测试数据没得换行，要额外判定一下就行
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
void combine(int a[],int n)
{
int *b=new int[6+1];
for(int i=0;i<=6;i++)
{
b[i]=i-1;// 注意这里b[0]=-1用来作为循环判断标识
}
int k=6;
bool flag=true;// 标志找到一个有效组合
while(b[0]==-1)
{
if(flag)
{
for(int i=1;i<6;i++)// 输出符合要求的组合
{
cout<<a[b[i]]<<" ";
}
cout<<a[b[6]];
cout<<endl;
flag=false;
}
b[k]++;// 在当前位置选择新的数字
if(b[k]==n)// 当前位置已无数字可选，回溯
{
b[k--]=0;
continue;
}
if(k<6)// 更新当前位置的下一位置的数字
{
b[++k]=b[k-1];
continue;
}
if(k==6)
flag=true;
}
}
int main()
{
freopen("C:\\Users\\Administrator\\Desktop\\in.txt" , "r" , stdin);
int n;
int a[14];
bool flag=true;
while(cin>>n)
{
if(n==0)break;
if(!flag)cout<<endl;
flag=false;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
combine(a,n);
}
return 0;
}
nkoj1108
题目连接http://acm.nankai.edu.cn/p1108.html
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<cstdlib>
#include<iomanip>
using namespace std;
double ans;
int n,m;
int main()
{
// cout<<fixed<<setprecision(0);
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)break;
ans=1;
if(m>n/2)m=n-m;//这儿是关键啊 不然会超时的
for(int i=1; i<=m; i++)
{
ans=ans*(n-i+1)/i;
}
printf("%.0lf\n",ans);
}
return 0;
}