现在的位置: 首页 > 综合 > 正文

整数拆分问题

2013年07月04日 ⁄ 综合 ⁄ 共 744字 ⁄ 字号 评论关闭

问题:

    对于1个正整数N,将其拆分成几个正整数的和,如何拆分可使得其乘积最大?

csdn用户pathuang68给出的结论是:如果不在乎是否为整数的话,那么把每份平均分为e(2.71828459045...)时,所得到的乘积是最大的,
如果要是整数的话,那么就选尽可能地靠近e的整数即可,比如3。具体证明请参见

http://blog.csdn.net/pathuang68/article/details/6606605

  我的拆法方法:

    若n<=4,无需拆分,它本省就是最大的。
    若n>4, 将n表示成 3k+r(k>0, 0< = r <3)的形式,r为余数。
      case 1: r=0,可将n拆成k个3.
      case 2: r=1,将n拆成k-1个3,和1个4.
      case 3: r=2,将n拆成k个3,和1个2.

代码见下:

 

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

void print_int_split(int n)
{
    if (n<=4)
        printf("%d",n);
    else
    {
        int i,k,r;
        k=n /3, r=n % 3;
        if ( r==1)    {k--; r+=3; }
        for (i=0;i<k;i++)
            printf("3,");
        if (r>0)
            printf("%d",r);
    }
}
void main()
{
    int n;
    for (n=1;n<100;n++)
    {
        printf("split %d={",n);
        print_int_split(n);
        printf("}\n");
    }
}

说明:

   本题目来自csdn的一个帖子,见 整数拆分问题

http://topic.csdn.net/u/20120517/00/3c8fb0ed-4d12-4a62-8fc9-821d32523f0d.html

 

抱歉!评论已关闭.