| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 677 人关注过本帖
标题:组合数运行超时
只看楼主 加入收藏
laznrbfe
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:482
专家分:1599
注 册:2011-5-22
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:11 
组合数运行超时
/*描述
求C(N, M),即求M个数中选N个数的组合方案数。
输入
第一行一个正整数T (T<=10), 表示有T组测试数据。第二行~第T+1行,每行有2个正整数N,M (1<=N, M<=20)。
输出
对于每组输入N,M,输出一行,该行有一个数,为C(N, M)值。
样例输入
2
3 5
1 20
样例输出
10
20
编程啦上面的题目
http://www.
*/
程序代码:
#include<stdio.h>
int main()
{
    int T=1;
    int N=0,M=0;
    int C(int N,int M);
    scanf("%d",&T);
    while(T>0)
    {
        scanf("%d%d",&N,&M);
        if(N==0&&M>0)
        {
            printf("0\n");
        }
        else if(N>M/2)
        {
            printf("%d\n",C(M-N,M));
        }
        else
        {
            printf("%d\n",C(N,M));
        }
        T--;
    }
    return 0;
}
int C(int N,int M)
{
    int sum=1,sum1=1,sum2=1;
    do
    {
        sum1*=M;
        sum2*=N;
        M--;
        N--;
    }while(N);
    sum=sum1/sum2;
    return sum;
}
搜索更多相关主题的帖子: 1020 正整数 编程 
2012-03-19 23:13
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
你这代码该是wa吧,手机上网,没实际测试。

重剑无锋,大巧不工
2012-03-20 00:13
jianyuling00
Rank: 3Rank: 3
来 自:琼州学院
等 级:论坛游侠
帖 子:89
专家分:177
注 册:2012-3-17
收藏
得分:0 
头像不错

我水了,呵呵
2012-03-20 01:01
laznrbfe
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:482
专家分:1599
注 册:2011-5-22
收藏
得分:0 
回复 2楼 beyondyf
不懂,求指教。
2012-03-20 10:18
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:10 
1.你对C(n,0)的值输出不对(注,此处是习惯写法,与你题目中的参数顺序是相反的)
2.你的组合算法在数稍大时就会溢出

送你段AC代码
程序代码:
#include<stdio.h>
int C(int n, int m)
{
    int i, r;
    if(n - m < m) m = n - m;
    for(r = i = 1; i <= m; r /= i++) r *= n--;
    return r;
}
int main()
{
    int t, n, m;
    for(scanf("%d", &t); t--; printf("%d\n", C(m, n))) scanf("%d%d", &n, &m);
    return 0;
}


重剑无锋,大巧不工
2012-03-20 11:42
C_戴忠意
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:575
专家分:1349
注 册:2011-10-21
收藏
得分:0 
学习了

编程之路定要走完……
2012-03-20 12:54
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:10 
我觉得还是把中间结果保存起来比较好

程序代码:
#include <stdio.h>
int dp[20][20] = {0};
int combi(int m,int n)
{
    if(dp[m][n])
        return dp[m][n];
    if(n == 1 || n == m-1)
        return (dp[m][n] = m);
    if(n == m || n == 0)
        return (dp[m][n] = 1);
    return (dp[m][n] = combi(m-1,n-1)*m/n);
}
int main()
{
    int z, m , n, y, last, r;
    scanf("%d", &z);
    while (z--){
        scanf("%d%d", &n,&m);
        printf("%d\n",combi(m,n));
    }
    return 0;
}

                                         
===========深入<----------------->浅出============
2012-03-20 14:23
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
打表是一种很实用的提高计算效率的方法,体现着动态规划的思想。不过就这道题而言,由于数据量很小,体现不出它的优越性。

还有,老杨,dp的初始化应该独立出来,之后对于每组m,n直接输出dp[m][n]。放在combi里每次都重新计算一遍其实和每次计算按公式计算一遍组合数没区别

重剑无锋,大巧不工
2012-03-20 15:43
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
  感谢杨大哥的教导

                                         
===========深入<----------------->浅出============
2012-03-20 15:50
laznrbfe
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:482
专家分:1599
注 册:2011-5-22
收藏
得分:0 
回复 5楼 beyondyf
为什么,你是代码运行需要的时间那么短?求解。
2012-03-21 08:38
快速回复:组合数运行超时
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.078480 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved