首页 > 代码库 > 蓝桥杯训练中的考新郎问题
蓝桥杯训练中的考新郎问题
国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,
叫做"考新郎",具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,
让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.最后,揭开盖头,如果找错了对象就要当众跪搓
衣板.. 假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
输入描述
N M
输出描述
可能的种数
输入样例
3 2
输出样例
3
/*分析:就是计算数学里面的组合数*/
/*再分析:这才发现自己之前都弄错了,根本不是什么组合数,但是跟组合数有关,是错排,不过跟一般错排有一点差
别,就是不是对所有的元素进行错排,只是对部分进行错排,说道对部分进行错排,那就与组合数有关系了啊,因此先
解决组合数的求法然后乘以错排数就是结果了。
先来实现组合数求解
C(n,m)=(n*(n-1)*(n-2)*…*(n-m+2)*(n-m+1))/(m!)=((n-m+1)/1)*((n-m+2)/2)*((n-m+3)/3)*…*((n-m+m)/n)
=∏((n-m+k)/k)【k=1,2,3,…,m】
以上变换是把一般数学计算中的求组合数的步骤进行变换,变化方便计算机求解的方式
*/
下面是求组合数的代码:
#include<stdio.h> int Combination(int n,int m) { int i; int sum = 1;//这里sum在之后的算式中是以乘数的形式出现的,所以不能是0,应该设置初值为1 for(i = 1;i <= m; i++) sum = (sum * (n - m + i))/i; return sum; } int main() { int n,m; int count = 0; scanf("%d%d",&n,&m); count = Combination(n,m); printf("%d\n",count); return 0; }分析:好的,现在把求组合的方法搞定了,那么接下来就是就有条件的错排了,a[i]=(i-1)*(a[i-1]+a[i-2])(a[0] = 0,a[1] = 0,a[2] = 1),在网上找到了错排的公式,剩下的就好做了
#include<stdio.h> #define M 200 double sum = 1; double Combination(int p,int q) { int i; //double sum = 1;/*这里sum在之后的算式中是以乘数的形式出现的,所以不能是0,应该设置初值为1*/ for(i = 1;i <= q; i++) sum = (sum * (p - q + i))/i; return sum; } int main() { int n,m; int j; double co = 1; double array[M] = {0,0,1}; double out = 1; scanf("%d%d",&n,&m); out = Combination(n,n - m); /*for(j = 0;j < 10; j++) printf("%.0lf ",array[j]); printf("\n");*/ for(j = 3;j <= M;j++) { array[j] =((double)(j - 1)) * (array[j - 1] + array[j - 2]); //printf("j = %d\n",j); } /*for(j = 0;j < 10; j++) printf("%.0lf ",array[j]); printf("\n");*/ //printf("ar[2] = %.0f\n",array[2]); out = array[m]*out; printf("%.0lf",out); return 0; }
赶快编译链接,都ok~~,那就没有问题了~~,果然,输入题目的数据,ok了。。so easy 是不是啊?!
只好检查错误,接下来是见证奇迹的时刻,当我把double co = 1;这句话给注释掉后,然后编译链接,最后运行,貌似都可以,但是在我输入数据后,一个回车,程序却没有了结果(可爱的是电脑的风扇却像嘲笑我似得开始努力工作起来了)。傻眼了~~~为什么啊,明明它是个无关的变量,去掉应该无所谓啊~~然后我开始了各种折腾,改double,改变量的名字...都不行,奇了怪了...想到刚才程序没有结果时电脑风扇就努力扇风的状况,我猜是有什么死循环之类的,于是就在主程序的for循环里面加了个输出,果然,是个死循环,终止条件没有起作用,看来问题在循环里面,但是为什么每次循环到200后又会重新开始循环呢?看来应该是终止条件有问题,我的终止条件是j <= M。M宏定义为200。感觉没有问题啊。于是各种试,最后,我去掉了j <= M中的等号,然后,然后,然后它就好了...虽然不知道是什么原因,自己下次注意这个问题就好了。
总结:for循环中终止条件不能为i <= M,只能为i < M
蓝桥杯训练中的考新郎问题