SDUT1293乘积最大的分解

乘积最大的分解

Time Limit: 1000MS Memory limit: 65536K

题目描述

一个正整数N(0＜ｎ＜100），可以写成若干个正整数加数之和，如6可以写成
 
6=1+2+3；
6=2+2+2；
6=2+4；
6=3+3；
6=1+5；
……

其中有一种分解方式获得的加数的乘积是所有分解方式中最大的，比如上面分解中最大的乘积是3×3＝9。

请你设计一种算法，对于任何一个输入的正整数，求出其各种分解中所得到的最大乘积。

输入

输入有多组，每组一行输入一个正整数。以0作为输入的结束。

输出

对应输入的数据，输出多行，输出所求最大分解乘积。

示例输入

6
7
0

示例输出

9
12

思路：根据规律，一个正整数n拆分成多个3或多个2的和时，它们的乘积最大

代码：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int main()
{
    int n = 0;
    double num = 0;
    double ans = 0;
    while ( scanf ("%d", &n) != EOF && n )
    {
        if ( n == 1 )
        {
            printf ("1\n");
            continue;
        }
        if ( n == 2 )
        {
            printf ( "2\n" );
            continue;
        }
        if ( n % 3 == 0 )
        {
            num = n / 3;
            ans = pow (3.0, num );
        }
        else if ( n % 3  == 1 )
        {
            num = n / 3 - 1;
            ans = pow (3.0, num) * 4.0;
        }
        else
        {
            num = n / 3;
            ans = pow (3.0, num) * 2.0;
        }
        printf ("%.0lf\n", ans);
    }
    return 0;
}