当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 21 篇帖子 ]  前往页数 1, 2  下一页
作者 内容
1 楼 
 文章标题 : 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 0:40 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
引用:
最优分解问题

问题描述:

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

你的任务是对于给定的正整数n,编程计算最优分解方案。
输入:
输入有若干行,每一行上是一个整数n,(|n|£50)。
输出:
对输入中的每个整数n,如果是无效输入,那么输出“invalid input!”,否则输出最优分解方案,以从小到大的顺序排列,中间用空格阁开,在它们的后面输出最大的乘积m,格式为max=m。

输入样例:
-5
10
1001

输出样例:
invalid input!
2 3 5 max=30
invalid input!

我的算法思想是
1).把一个正整数从中间分开(如果是偶数,直接除以2;如果是奇数,分别加1除以2,减1除以2)
2).其中一部分保留在mem[]数组中(奇数的话,比较大的那一部分保留给mem[]数组),另一部分赋给temp,并重复1,2 步骤
3).最后把temp赋给mem[]数组

代码:
//11.cpp
#include<iostream>
using namespace std;

int main()
{
   const int N=50;
   int mem[N];
   int n;
   while(cin>>n)
   {
      int temp=n;
      int num=0;
      if(n<=0||n>50)
         cout<<"invalid input!"<<endl;
      else
      {
         while(temp!=1&&temp!=2&&temp!=3&&temp!=4)
         {
            if(temp%2==0)
            {
               mem[num++]=temp/2;
               temp=temp/2;
            }
            else
            {
               mem[num++]=(temp+1)/2;
               temp=(temp-1)/2;
            }
         }
         mem[num]=temp;
         if(mem[num]==mem[num-1])   //由于要求为不同的自然数,所以有了这一步
         {
            mem[num]--;
            mem[num-1]++;
         }
         int max=1;
         for(int i=0;i<=num;i++)
            max*=mem[i];
         for(int i=num;i>=0;i--)
            cout<<mem[i]<<" ";
         cout<<"max="<<max<<endl;
      }
   }
   return 0;
}


页首
 用户资料  
 
2 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 0:41 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
不知道我的这个算法对不对,谢谢大家给点意见


页首
 用户资料  
 
3 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 1:02 

注册: 2008-12-01 7:52
帖子: 307
地址: 蜀山
送出感谢: 0 次
接收感谢: 0 次
好像有点错误:
[cmdblock@wg tmp]$ ./a.out
12
2 4 6 max=48
12的最大值应该是6 6
分解成 3 3 3 3 答案该是81


页首
 用户资料  
 
4 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 11:25 

注册: 2009-09-23 20:17
帖子: 9
送出感谢: 0 次
接收感谢: 0 次
http://blog.csdn.net/Rappy/archive/2007 ... 03184.aspx
参考一下吧


页首
 用户资料  
 
5 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 11:35 

注册: 2008-05-03 23:42
帖子: 3681
送出感谢: 4
接收感谢: 6
当然是错的 不用看你的代码 数学上就不对


页首
 用户资料  
 
6 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 11:42 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
cmdblock 写道:
好像有点错误:
[cmdblock@wg tmp]$ ./a.out
12
2 4 6 max=48
12的最大值应该是6 6
分解成 3 3 3 3 答案该是81

互不相同

这题可以用动态规划


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
7 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 12:02 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
cmdblock 写道:
好像有点错误:
[cmdblock@wg tmp]$ ./a.out
12
2 4 6 max=48
12的最大值应该是6 6
分解成 3 3 3 3 答案该是81

正如ls说的,题目要求各不相同


页首
 用户资料  
 
8 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 12:29 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
有没有谁能提供一些想法


页首
 用户资料  
 
9 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 13:47 

注册: 2008-12-01 7:52
帖子: 307
地址: 蜀山
送出感谢: 0 次
接收感谢: 0 次
给你提供个思路吧
你要把数分解到最后都是2和3组成,就可以了。


页首
 用户资料  
 
10 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 13:48 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
cmdblock 写道:
给你提供个思路吧
你要把数分解到最后都是2和3组成,就可以了。


都说了,互不相同 ...


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
11 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 13:50 

注册: 2008-12-01 7:52
帖子: 307
地址: 蜀山
送出感谢: 0 次
接收感谢: 0 次
也就是可以用上面所说的动态规划算法


页首
 用户资料  
 
12 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 14:21 

注册: 2008-05-03 23:42
帖子: 3681
送出感谢: 4
接收感谢: 6
12 为例,3 4 5 显然比 2 4 6 强。“直接除以2” 是你未经证明的奇怪想法。你至少拿个小的数验证一下啊。


页首
 用户资料  
 
13 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 14:26 

注册: 2008-12-01 7:52
帖子: 307
地址: 蜀山
送出感谢: 0 次
接收感谢: 0 次
如果是互不相同的话,我给你个思路你试一试。
首先还是分解成所有的2和3
然后一个一个加,也就是说从2.,3,4,5,6,7...这样一个一个找


页首
 用户资料  
 
14 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 14:51 

注册: 2008-05-03 23:42
帖子: 3681
送出感谢: 4
接收感谢: 6
数学上,简单地累加 2+3+4+5+...+k 直到和首次超过或等于 n。
若等于n,就是答案
若超过,记和为S,则在 2,3,4,...k 的序列中去掉数 S-n 即可。
若 S-n=1,则去掉 2,k 变成 k+1


页首
 用户资料  
 
15 楼 
 文章标题 : Re: 最优分解问题,不知道我的算法思想对不对,反正我写好的这个程序提交到判题系统上是错误的
帖子发表于 : 2009-09-26 16:02 
头像

注册: 2009-03-19 8:39
帖子: 185
送出感谢: 0 次
接收感谢: 0 次
billbear 写道:
数学上,简单地累加 2+3+4+5+...+k 直到和首次超过或等于 n。
若等于n,就是答案
若超过,记和为S,则在 2,3,4,...k 的序列中去掉数 S-n 即可。
若 S-n=1,则去掉 2,k 变成 k+1

那我按ls这种算法还是提交不对,还是我哪里写错了,麻烦大家指点
代码:
//11.cpp
#include<iostream>
using namespace std;
int main()
{
   int n;
   const int N=50;
   int ch[N];
   while(cin>>n)
   {
      int su=2;          //这个变量从2开始,后面不断自加,它是用来让temp不断的加的,相当于ls说的k
      int temp=0;     //这个就是ls所说的和S
      int result=1;
      if(n<=0||n>=50)
         cout<<"invalid input!"<<endl;
      else
      {
         while(temp<n)
         {
            temp+=su;
            su++;
         }
         if(temp==n)            //case 1
         {
            for(int i=2;i<su;i++)
            {
               cout<<i<<" ";
               result*=i;
            }
            cout<<result<<endl;
         }
         else if(temp-n==1)       //case 2
            {
               for(int i=3;i<su;i++)
               {
                  ch[i-3]=i;
                  result*=i;
               }
               ch[su-4]=su;
               result=result/(su-1)*su;
               for(int i=3;i<su;i++)
                  cout<<ch[i-3]<<" ";
               cout<<result<<endl;
            }
            else                  //case 3
            {
               int a=0;
               int b=temp-n;
               for(int i=2;i<su;i++)
               {
                  if(i==b)
                     continue;
                  else
                  {
                     cout<<i<<" ";
                     result*=i;
                  }
               }
               cout<<result<<endl;
            }
      }
   }
   return 0;
}


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 21 篇帖子 ]  前往页数 1, 2  下一页

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译