| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1722 人关注过本帖
标题:卡特兰数
只看楼主 加入收藏
zsy142857
Rank: 1
来 自:上海
等 级:新手上路
帖 子:18
专家分:0
注 册:2017-6-3
结帖率:50%
收藏
已结贴  问题点数:28 回复次数:2 
卡特兰数
一道关于卡特兰数的问题:
#include<iostream>
using namespace std;
long long k;
void h(int a){
    int j,b;
    for(j=2;j<a;j++){
        b=j*2*(2*a-1)/(a+1);}
    cout<<a<<" "<<j<<" "<<endl;
    cout<<b<<endl;

}
int main(){
    cin>>k;
    if(k==0||k==1){
    cout<<1;
    return 0;}
    else h(k);
    return 0;
}
红色标注的地方有疑问,怎么改才正确。
搜索更多相关主题的帖子: long int cout cin return 
2017-09-13 20:54
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:28 
首先要告诉别人什么是“卡特兰数”,比如:
    卡特兰数公式:
    h(0) = 1
    h(n) = h(n-1)*(4*n-2)/(n+1);
    前几项分别是:
    h(0) = 1
    h(1) = 1
    h(2) = 2
    h(3) = 5
    h(4) = 14
    h(5) = 42
    32bits所能表示的最大结果是:h(19) = 1767263190
    64bits所能表示的最大结果是:h(36) = 11959798385860453492

其次,代码要排版,比如:
    if(k==0||k==1){
    cout<<1;
    return 0;}
    改为
    if(k==0||k==1) {
        cout<<1;
        return 0;
    }
    其它的就不一一细说了

去除编译错误和警告,比如:
    h(k) 这句报错:conversion from 'long long' to 'int', possible loss of data
    要么都改为 int,要么都改为 long long

要描述一下你想解决的问题,比如:
    输入2,期待输出2,实际报错:变量b未初始化即使用
    输入4,期待输出14,实际输出8

现在,回正题,根据公式,很简单地就写出代码:
程序代码:
unsigned long long h( unsigned n )
{
    unsigned long long r = 1;
    for( unsigned i=1; i<=n; ++i )
        r = r*(4*i-2)/(i+1);
    return r;
}

#include <iostream>
using namespace std;

int main( void )
{
    unsigned n;
    cin >> n;
    cout << h(n) << endl;
}

但这个代码差在 r = r*(4*i-2)/(i+1) 这一步,r*(4*i-2)中间值太大容易溢出。通过实际计算,在h(34)时就溢出了。
理论上能计算到h(36),但实际只能计算到h(33),这是个bug,如果是学校考试,还能打个及格;放在商业公司的话,会被老板拿刀砍死。
因此最终代码为:
程序代码:
unsigned long long gcd( unsigned long long a, unsigned long long b )
{
    while( b != 0 )
    {
        unsigned long long t = a;
        a = b;
        b = t%b;
    }
    return a;
}

unsigned long long AmBdC( unsigned long long a, unsigned long long b, unsigned long long c )
{
    unsigned long long t = gcd( a, c );
    a /= t;
    c /= t;

    t = gcd( b, c );
    b /= t;
    c /= t;

    return a*b/c;
}

#include <cassert>

unsigned long long h( unsigned n )
{
    assert( n <= 36 );
    unsigned long long r = 1;
    for( unsigned i=1; i<=n; ++i )
        r = AmBdC( r, 4*i-2, i+1 );
    return r;
}

#include <iostream>
using namespace std;

int main( void )
{
    unsigned n;
    cin >> n;
    cout << h(n) << endl;
}


2017-09-14 11:49
zsy142857
Rank: 1
来 自:上海
等 级:新手上路
帖 子:18
专家分:0
注 册:2017-6-3
收藏
得分:0 
谢谢
2017-09-20 17:49
快速回复:卡特兰数
数据加载中...
 
   



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

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