這道題是問題求解和程序設(shè)計(jì)的作業(yè)題，剛拿到這道題的時(shí)候，我完全沒與遞推的概念，第一反應(yīng)完全是離散數(shù)學(xué)里面叫得容斥原理，典型的錯(cuò)排問題，一共有n對(duì)新人，有m對(duì)是錯(cuò)誤的，首先通過c(n,m)選出錯(cuò)誤的新人是哪些，然后就是算出這m對(duì)新人錯(cuò)誤排列的方法。
根據(jù)容斥原理的公式推出m對(duì)錯(cuò)誤的情況有m!-c(m,1)(m-1)!+c(m,2)(m-2)!+.....+(-1)^mc(m,m)0!;
在乘上c(n,m)就好了
化簡(jiǎn)后得a(n,m)(1-1/1!+1/2!-....+(-1)^m/m!);
算到這里我就犯愁了，這括號(hào)了的這些個(gè)東西怎么算阿，腦子完全堵住了，緩過神來才發(fā)現(xiàn)，要實(shí)現(xiàn)它并不困難
程序如下：
1
#include<stdio.h>
2__int64 f(int n,int m){
3 __int64 r,tmp1=1;
4 int i;
5 for(i=n;i>n-m;i--)
6 tmp1*=i;
7 r=tmp1;
8 for(i=1;i<=m;i++){
9 tmp1=(-tmp1)/i;
10 r+=tmp1;}
11 return r;
12}
13int main(){
14 int t,m,n;
15 __int64 result;
16 scanf("%d",&t);
17 while((t--)>0){
18 scanf("%d%d",&n,&m);
19 result=f(n,m);
20 printf("%I64d\n",result);
21 }
22 return 0;
23}
posted on 2008-03-02 17:03
zoyi 閱讀(230)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
acm