例题4-1 组合数
输入非负整数m,n输出组合数c(n,m).m<=n<=20
分析:从普通思维出发先算n!,再算m!,再算(n-m)!，最终我们会发现，20！以及超出整数所能表示的范围。因此此题不宜使用这种方法。经分析，我们发现n!和m!或者(n-m)!有重叠的部分，可以约去。因此得到如下解法：
代码
<strong>#include<iostream>
using namespace std;
int f(int n,int m)
{ //从n中取个的组合数
int i,j;
int res=1;
if(n-m<m) m=n-m;
for(i=n-m+1,j=1;i<=n;++i,++j){//注意此处不能用for(i=n,j=m;i>=n-m+1;i--,j--)，具体解释见下面注解
res=res*i/j;
}
return res;
}
int main()
{
int n,m;
cin>>n>>m;
cout<<f(n,m)<<endl;
return 0;
}
</strong>
注解：for(i=n-m+1,j=1;i<=n;++i,++j){ res=res*i/j;}，例如C(20,7)，按上面的算法为res=14/1*15/2*16/3*17/4*18/5*19/6*20/7,之所以能这么做是因为对j来说，分母在j个数之内肯定有能被j整除的整数出现，例如j=2时，两个数之内就有能被2整除的整数出现。所以，这个算法正确。
如果n和n+2都是素数，则称它们是孪生素数。输入m，输出两个数均不超过m的最大孪生素数。5≤m≤10000。例如m=20时答案是17、19，m=1000时答案是881、883。
分析：被1和它自身整除的、大于1的整数称为素数。由于要判断n和n+2是否是素数，所以把“判断素数”可以写成一个函数，只需调用这个函数两次就可以了。这样的“判断一个事物是否具有某一性质”的函数还有一个学术名称——谓词（predicate） 代码：
#include "stdafx.h"
#include <assert.h>
#include <math.h>
int is_primer(int x)
{//判断x是否为素数
int i;
assert(x>=0);//表达式为假时程序终止
if(x==1) return 0;
int m=floor(sqrt((double)x)+0.5);//四舍五入
for(i=2;i<=m;i++){//如果x=2，将不执行此循环，直接返回1
if(x%i==0) return 0;
}
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,m;
scanf("%d",&m);
for(i=m-2;i>=3;i--){
if(is_primer(i) && is_primer(i+2)){
printf("%d %d\n",i,i+2);
break;
}
}
return 0;
}
4.4.1 小问题锦集 首先，来编写一个函数solve，给定浮点数a,b,c,d,e,f，求解方程组ax+by=c,dx+ey=f 任务1：使用assert宏，让解不唯一时异常退出 任务2：解不唯一时仍然正常返回，但调用者有办法知道解的数量（无解、唯一解、无穷多组解） 分析：从线性代数的知识可知，当行列式det=a*e-b*d!=0时，方程有唯一解，这是任务一的思路。其次，当det=0时，方程有两种可能，有无穷解，无解。令detx=c*e-b*f，有det=detx时有无穷解，det!=detx时无解 代码： 任务1：
#include "stdafx.h"任务2：
#include <assert.h>
#include<iostream>
using namespace std;
int solve(double a,double b,double c,double d,double e,double f,double *x,double *y)
{
double det=a*e-b*d;
assert(det!=0);
double detx=c*e-b*f;
double dety=a*f-c*d;
*x=detx/det;
*y=dety/det;
cout<<det<<" "<<detx<<" "<<dety<<endl;
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
double a, b, c, d, e, f,x,y;
int res=0;
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
res=solve(a, b, c, d, e, f,&x,&y);
if(res){
printf("x=%lf y=%lf\n",x,y);
}
return 0;
}
#include "stdafx.h"
#include <assert.h>
#include<iostream>
using namespace std;
int solve(double a,double b,double c,double d,double e,double f,double *x,double *y)
{
double det=a*e-b*d;
//assert(det!=0);
double detx=c*e-b*f;
double dety=a*f-c*d;
if(det==0 && detx==det){
return 1;//代表方程有无穷解
}
if(detx==0 && detx!=det){
return -1;//代表方程无解
}
*x=detx/det;
*y=dety/det;
cout<<det<<" "<<detx<<" "<<dety<<endl;
return 0;//方程有唯一解
}
int _tmain(int argc, _TCHAR* argv[])
{
double a, b, c, d, e, f,x,y;
int res=0;
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
res=solve(a, b, c, d, e, f,&x,&y);
if(res){
printf("x=%lf y=%lf\n",x,y);
}
return 0;
}