我要招人

去企业版

首页 > 试题广场 >

计算组合数

[编程题]计算组合数

热度指数：1048 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对于给定的非负整数r和n（r≤n），请编写程序计算组合数C(r,n) = n! / r! / (n-r)!。

（本题目用于测试的所有用例，都保证结果小于2³¹-1）

示例1

输入

2,3

输出

说明

算法知识视频讲解

牛客73799987号

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * calculate combination Number
     * @param r int整型 
     * @param n int整型 
     * @return int整型
     */
    public int combination (int r, int n) {
        // write code here
        long ans = 1L;
        int t = n - r, i = 0;
        while(i < t){
            ans *= (n-i)/(t-i);
            i++;
        }
        return (int)ans;
    }
}

有啥特殊写法吗,我这疯狂超时,第三个用例就过不去了

编辑于 2022-02-23 15:05:58 回复(1)

youngwong

public int combination (int r, int n) {
        int nh = n / 2;
        int answ = 1;
        int r1 = 1;
        if(r > nh)
            r = n -r;
        for(;r>0;) {
            r1 = r1 * r;
            answ *= n;
            if(answ % r1 == 0) {
                answ /= r1;
                r1 = 1;
            }
            n--;
            r--;
        }
        return answ;
        
    }

发表于 2021-08-31 16:58:03 回复(0)

时の中で色褪せないまま

public int combination (int r, int n) {
long ans = 1;
for(int i=1;i<r+1;i++){
ans*=n;
n-=1;

}

for(int j =1;j<r+1;j++){
ans/=j;
}
return (int)ans;
// write code here
}

发表于 2022-04-05 12:31:42 回复(1)

华为od毁我青春

这道题难点在于计算时整形溢出问题😀

发表于 2022-01-23 22:35:31 回复(0)

勤劳的小飞象在干饭

    public int combination (int r, int n) {
        // write code here
        if (n-r < r) {
            r = n-r;
        }
 
        long sum = 1;
        for (int i = 0; i < r; i++) {
            sum *= (n-i);
        }
        for (int i = 0; i < r; i++) {
            sum /= (r-i);
        }
        return (int)sum;

真的是溢出的问题！！！这个答案过了全部样例，放心食用

发表于 2022-08-21 23:10:48 回复(0)

zztznb

public int combination (int r, int n) {
// write code here
long a=1;
if(n==0)
return 1;
if(r>n/2)
r=n-r;
for(int i=n,j=1;i>n-r;i--,j++)
{
a=a*i/j;
}
return (int) a;
}

发表于 2022-03-07 15:05:04 回复(0)

溪坪人

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * calculate combination Number
     * @param r int整型 
     * @param n int整型 
     * @return int整型
     */
    public int combination (int r, int n) {
        // write code here
        if(r == n) return 1;
        if(r == 0) return 1;
        int halfN = n/2;
        if(halfN < r) r = halfN;
        int j = n,k=1;
        long a = 1L,b=1L;
        while(k<=r){
            a *= j;
            b *= k;
            if(a%b == 0){
                a /= b;
                b = 1L;
            }
            j--;
            k++;
        }
        return (int)a;
    }
}

发表于 2022-03-04 00:17:54 回复(0)

Java

牛客683954734号

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* calculate combination Number
* @param r int整型
* @param n int整型
* @return int整型
*/
public int combination (int r, int n) {
// write code here

double a = 1;
int t = r;
double b = 1;
int c = n-r;
if (r==0||c==0 ){
return 1;
}else if (r==1|| c==1){
return n;
}else
if (c<r){
r = c;
a = r;
}
for (int i = 0; i < t; i++) {
a*=r;
b*=n;

r--;
n--;
}

double v = b / a;
System.out.println(b);
int v1 = (int) v;
return v1;
}
}

发表于 2021-10-22 21:34:06 回复(0)

BUCT_Tourry

java 超时了，有没有更好的方法

 public int combination (int r, int n) {
        // write code here
       r= Math.min(r, (n - r));
        long res=1;
        for(int i=n;i>=(n-r+1);i--)
            res*=i;
        for(int i=1;i<=r;i++)
            res/=i;
        return (int)res;
    }

发表于 2021-02-04 12:47:50 回复(0)

牛客37697243号


def choose(r, n):
    num1 = 1 num2 = 1
    for i in range(1, max(r, n - r)+1):
        num1 = num1 * i
    for j in range(r, n+1):
        num2 = num2 * j
    return num2 / num1

编辑于 2020-12-28 18:00:15 回复(1)