用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c++代码库

可重复最优分解问题

2012-09-20 作者: 神马举报

[c++]代码库

 问题描述:

n是一个正整数。现在要求将n分解为若干个自然数的和,且使这些自然数的乘积最大。

编程任务:

对于给定的正整数n,编程计算最优分解方案。

Input
每组测试数据只有一个正整数n(1<=n<=10000)

Output
输出最大乘积,每个答案一行。(提示:可能是一个非常大的整数!)

Sample Input
10

Sample Output
36

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
char res[10001];
int i, carry, len = 1;
void mutiply ( int n )
{
    carry = 0;
    char *h = res;
    for ( i = 0; i < len; i++ )
    {
        *h = *h * n + carry;
        carry = *h / 10;
        *h %= 10;
        h++;
    }
    if ( carry != 0 )
    {
        *h = carry;
        len++;
    }
}
void f ( int n )
{
    int n3, n2, i;
    if ( n %2 == 0 )
    {
        n3 = n / 6 * 2;
        n2 = n % 6 / 2;
    }
    else
    {
        n3 = ( n - 3 ) / 6 * 2 + 1;
        n2 = ( n - 3 ) % 6 / 2;
    }
    for ( i = 1; i <= n3 / 2; i++ )
    {
        mutiply ( 9 );
    }
    if ( n3 % 2 != 0 )
    {
        if ( n2 > 0 )
        {
            mutiply ( 6 );
            n2--;
        }
        else
        {
            mutiply ( 3 );
        }
    }
    if ( n2 > 0 )
    {
        mutiply ( ( int ) pow ( 2.0,n2 ) );
    }
}
int main()
{
    int n;
    res[0] = 1;
    while ( scanf ( "%d",&n ) !=EOF )
    {
        if ( n <= 3 )
        {
            printf ( "%d\n", n );
            continue;
        }
        res[0] = 1;
        len = 1;
        f ( n );
        for ( i = len - 1; i >= 0; i-- )
        {
            printf ( "%d", res[i] );
        }
        printf ( "\n" );
    }
    return 0;
}



网友评论    (发表评论)


发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...