acm题目及我的程序(4)——正整数n的加法组合的最大乘积(修改)

晨曦之光 发布于 2012/03/09 14:16
阅读 184
收藏 0
本博客( http://blog.csdn.net/livelylittlefish)贴出作者(三二一、小鱼)相关研究、学习内容所做的笔记,欢迎广大朋友指正!
                           
                           

题目: 

                           
                           
给定一个正整数n,则在n所有的分解式中,求因子乘积最大的一个分解及此乘积。
n=5时,有如下分解式: 
5=5 
5=4+1 
5=3+2 
5=3+1+1 
5=2+2+1 
5=2+1+1+1 
5=1+1+1+1+1  
在这些分解式中,3*2=6最大,这就是所要求的结果。  
若n = 12,最大为3*3*3*3 = 81。 
                           
                           

算法思想:

                           
                           
可以参考“acm题目及我的程序(4)——正整数n的加法组合”,不再赘述
                           
                           

代码如下:

                           
                           
/************************************************************************
 * 给定一个正整数n, 则在n所有的分解式中, 求因子乘积最大的一个分解及此乘积
 * n=5时, 则8有如下分解式:
 * 5=5
 * 5=4+1
 * 5=3+2
 * 5=3+1+1
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * 在这些分解式中,3*2=6最大,这就是所要求的结果。
 * 若n = 12,最大为3*3*3*3 = 81。
 ***********************************************************************
*/


#include 
< stdio.h >
#include 
< string .h >
#include 
< CONIO.H >
#include 
< vector >
using   namespace  std;

#define  MAXCOL 80
#define  FILENAMELENGTH 100

class  AdditionCombination
{
public:
    
int a[MAXCOL];
    
int m_number;    //条用GetCombinations函数时count的值
    long long m_lproduct;//最大乘积

public:
    AdditionCombination(
int number)
    
{
        m_lproduct
=;
        m_number
=number;
        
for(int j=;j<MAXCOL;j++)
            a[j]
=1;
    }


    
~AdditionCombination(){}

    
void Initialize()
    
{
        
for(int j=;j<m_number;j++)
            a[j]
=1;
    }


    
void Initialize(int jcol)
    
{
        
for(int j=jcol;j<m_number;j++)
            a[j]
=1;
    }


    
int GetCombinations(int n,int jcol,int col);
    
void display(int n);
}
;

// 在数组中从irow行,jcol列开始对n阶子矩阵进行
// col记录调用该函数前jcol的值
int  AdditionCombination::GetCombinations( int  n, int  jcol, int  col)
{
    
int nTotalCount=;
    
int j=,newn=;
    
int count=n;
    
    
while(count>1)
    
{
        
if(jcol==)
            Initialize();
        
else
            Initialize(jcol);
        a[jcol]
=count;
        
        
//算法优化,删除不满足的序列
        if(a[jcol]>a[col])
        
{
            count
--;
            
continue;
        }


        
for(j=jcol+1;j<jcol+count;j++)
            a[j]
=;

        newn
=n-count;
        
if(newn>1)
        
{
            
int newj=jcol+count;
            
int newcount=GetCombinations(newn,newj,jcol);
            nTotalCount
+=newcount;
        }

        
        count
--;
        display(m_number);
        nTotalCount
++;
    }


    
if(jcol==)
    
{
        Initialize();
        display(m_number);
        nTotalCount
++;
    }

    
else
        Initialize(jcol);

    
return nTotalCount;
}


void  AdditionCombination::display( int  n)
{
    
long long product=a[];
    
//printf("   %d=%d",n,a[0]);
    for(int j=1;j<n;j++)
    
{
        
if(a[j])
        
{
            
//printf("+%d",a[j]);
            product*=a[j];
        }

    }

    
if(m_lproduct<product)
        m_lproduct
=product;
}


// 将结果写入文件
void  WriteToFile(vector < vector < long   long >   >  info)
{
    
char filename[FILENAMELENGTH];

    
int size=info.size();
    
//构造文件名
    sprintf(filename,"%lld-%lld maxproduct.txt",info[][],info[size-1][]);
    FILE 
*fp=fopen(filename,"w");
    
if(fp==NULL)
    
{
        printf(
"can not wirte file!");
        exit(
);
    }


    
//写入个数
    for(int i=;i<size;i++)
        fprintf(fp,
"n=%lld    count=%lld    maxproduct=%lld ",info[i][],info[i][1],info[i][2]);

    fclose(fp);
}


// 显示菜单
void  show_menu()
{
    printf(
"--------------------------------------------- ");
    printf(
"input command to test the program ");
    printf(
"   i or I : input n to test ");
    printf(
"   t or T : get count from n1 to n2 ");
    printf(
"   q or Q : quit ");    
    printf(
"--------------------------------------------- ");
    printf(
"$ input command >");
}


void  main()
{
    
char sinput[10];
    
int n;

    show_menu();

    scanf(
"%s",sinput);
    
while(stricmp(sinput,"q")!=)
    
{
        
if(stricmp(sinput,"i")==)
        
{
            printf(
"  please input an integer:");
            scanf(
"%d",&n);

            AdditionCombination obj(n);
            
int count=obj.GetCombinations(n,,);
            printf(
"   count = %d    maxproduct=%lld ",count,obj.m_lproduct);
        }

        
else if(stricmp(sinput,"t")==)
        
{
            
int n1,n2;
            printf(
"  please input the begin number:");
            scanf(
"%d",&n1);
            printf(
"  please input the  end  number:");
            scanf(
"%d",&n2);

            printf(
"  press any key to start ... ");
            getch();

            vector
<vector<long long> > info;
            vector
<long long> line;

            AdditionCombination obj(n1);
            
for(int i=n1;i<=n2;i++)
            
{
                obj.Initialize();
                obj.m_number
=i;
                
int count=obj.GetCombinations(i,,);
                printf(
"  n=%d    count=%d    maxproduct=%lld ",i,count,obj.m_lproduct);
                line.clear();
                line.push_back(i);
                line.push_back(count);
                line.push_back(obj.m_lproduct);
                info.push_back(line);
            }

            printf(
" ");

            
//写入文件
            printf("$ write the numbers to file(Y,N)? >");
            scanf(
"%s",sinput);
            
if(stricmp(sinput,"y")==)        //写入文件
            {
                WriteToFile(info);
                printf(
"  write successfully! ");
            }

            printf(
" ");
        }


        
//输入命令
        printf("$ input command >");
        scanf(
"%s",sinput);
    }

}
                                       
                                         

运行结果如下:

                                    
                                     
n=1    count=1    maxproduct=1
n=2    count=2    maxproduct=2
n=3    count=3    maxproduct=3
n=4    count=5    maxproduct=4
n=5    count=7    maxproduct=6
n=6    count=11    maxproduct=9
n=7    count=15    maxproduct=12
n=8    count=22    maxproduct=18
n=9    count=30    maxproduct=27
n=10    count=42    maxproduct=36
n=11    count=56    maxproduct=54
n=12    count=77    maxproduct=81
n=13    count=101    maxproduct=108
n=14    count=135    maxproduct=162
n=15    count=176    maxproduct=243
n=16    count=231    maxproduct=324
n=17    count=297    maxproduct=486
n=18    count=385    maxproduct=729
n=19    count=490    maxproduct=972
n=20    count=627    maxproduct=1458
n=21    count=792    maxproduct=2187
n=22    count=1002    maxproduct=2916
n=23    count=1255    maxproduct=4374
n=24    count=1575    maxproduct=6561
n=25    count=1958    maxproduct=8748
n=26    count=2436    maxproduct=13122
n=27    count=3010    maxproduct=19683
n=28    count=3718    maxproduct=26244
n=29    count=4565    maxproduct=39366
n=30    count=5604    maxproduct=59049
n=31    count=6842    maxproduct=78732
n=32    count=8349    maxproduct=118098
n=33    count=10143    maxproduct=177147
n=34    count=12310    maxproduct=236196
n=35    count=14883    maxproduct=354294
n=36    count=17977    maxproduct=531441
n=37    count=21637    maxproduct=708588
n=38    count=26015    maxproduct=1062882
n=39    count=31185    maxproduct=1594323
n=40    count=37338    maxproduct=2125764
n=41    count=44583    maxproduct=3188646
n=42    count=53174    maxproduct=4782969
n=43    count=63261    maxproduct=6377292
n=44    count=75175    maxproduct=9565938
n=45    count=89134    maxproduct=14348907
n=46    count=105558    maxproduct=19131876
n=47    count=124754    maxproduct=28697814
n=48    count=147273    maxproduct=43046721
n=49    count=173525    maxproduct=57395628
n=50    count=204226    maxproduct=86093442
n=51    count=239943    maxproduct=129140163
n=52    count=281589    maxproduct=172186884
n=53    count=329931    maxproduct=258280326
n=54    count=386155    maxproduct=387420489
n=55    count=451276    maxproduct=516560652
n=56    count=526823    maxproduct=774840978
n=57    count=614154    maxproduct=1162261467
n=58    count=715220    maxproduct=1549681956
n=59    count=831820    maxproduct=2324522934
n=60    count=966467    maxproduct=3486784401
n=61    count=1121505    maxproduct=4649045868
n=62    count=1300156    maxproduct=6973568802
n=63    count=1505499    maxproduct=10460353203
n=64    count=1741630    maxproduct=13947137604
n=65    count=2012558    maxproduct=20920706406
n=66    count=2323520    maxproduct=31381059609
n=67    count=2679689    maxproduct=41841412812
n=68    count=3087735    maxproduct=62762119218
n=69    count=3554345    maxproduct=94143178827
n=70    count=4087968    maxproduct=125524238436
n=71    count=4697205    maxproduct=188286357654
n=72    count=5392783    maxproduct=282429536481
n=73    count=6185689    maxproduct=376572715308
n=74    count=7089500    maxproduct=564859072962
n=75    count=8118264    maxproduct=847288609443
n=76    count=9289091    maxproduct=1129718145924
n=77    count=10619863    maxproduct=1694577218886
n=78    count=12132164    maxproduct=2541865828329
n=79    count=13848650    maxproduct=3389154437772
n=80    count=15796476    maxproduct=5083731656658

原文链接:http://blog.csdn.net/livelylittlefish/article/details/2344641
加载中
返回顶部
顶部