给定求组合数公式为：，编一程序，输入m和n的值，求的值。注意

[问答题]

给定求组合数公式为：，编一程序，输入m和n的值，求的值。注意优化算法，降低溢出可能。要求：主函数调用以下函数求组合数：

int Fabricate( int m, int n ); //返回的值

Fabricate函数内需调用Multi函数：

int Multi( int m, int n ); //返回

程序由4个文件组成。头文件用于存放函数原型，作为调用接口；其他3个cpp文件分别是main、Fabricate和Multi函数的定义。

推荐

林呼

分析计算公式得到：

m!/(n!*(m-n)!)=(m*(m-1)*…*(m-n+1)*(m-n)!)/ (n!*(m-n)!)

=(m*(m-1)*…*(m-n+1)/ (n!)

因此可以避免求较大数据m的阶乘，减少溢出的可能性。

//Fabricate.h
#ifndef FABRICATE_H
#define FABRICATE_H
int Fabricate( int m,int n );
int Multi( int m, int n );
#endif
 
//main.cpp
#include<iostream>
using namespace std;
#include "Fabricate.h"
int main()
{
int m ,n;
  cout << "input m and n:";
  cin >> m >> n;
  cout << "Fabricate(" << m << "," << n << ")=" << Fabricate( m, n ) << endl;
}
 
//Fabricate.cpp
#include "Fabricate.h"
int Fabricate( int m, int n )
{  
return Multi( m, m-n + 1 ) / Multi( n, 1 );
}
 
//Multi.cpp
int Multi( int m, int n )
{
int i, t = 1;
  for( i=n; i<=m; i++ )
     t = t * i;
  return t;
}

发表于 2018-05-07 11:39:19 回复(0)