用户注册



邮箱:

密码:

用户登录


邮箱:

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

发表随想


还能输入: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、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

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

加载中,请稍后...