注册 登录
编程论坛 → C++教室

整数最优分解?????????

haohaoxue 发布于 2007-09-17 16:08， 3413 次点击

设n是一个正整数。现要求将n分解为若干个自然数的和，且使这些自然数的乘积最大。
对于给定的正整数n，编程计算最优分解方案。

# include<iostream>
using namespace std;
int main()
{
int n,m,i,j,h,d;double s=1,s1=1,k=1,max=1;double a[10000];
cin>>n;
i=1;
if(n==1)cout<<0;
else if(n==2)cout<<1;
else if(n==3)cout<<2;
else
{
while(i<=n/2)
{
m=n/i;
s=1;
k=1;
for(j=1;j<=m;j++)
s=s*i;
d=n%i;
if(d==0)s1=s;/*把数用除来分解*/
else
{
for(j=1;j<=d;j++)
{k=(s/i)*(i+1);
s=k;
}
s1=k;
}
a[i-1]=s1;
i++;

}
for(i=0;i<n/2;i++)
{ if(a[i]>=max)
{ max=a[i];
h=i;}
}
cout<<h<<" ";
cout<<max;
}
return 0;
}
不知道有没有更好的算法!这个代码是错的!~不知道错在那??????

33 回复
#2
雨中飞燕2007-09-17 16:13
不错的DP题，应该是O(n^3)，不过输入的n不可能很大（如1000的结果就很巨大了）
所以n^3也问题不大



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-17 16:17:26编辑过]
#3
HJin2007-09-17 17:05
see nku 1116

http://acm.nankai.edu.cn/p1116.html


I did this problem a few months ago and figured out you only need to consider writing

n as a sum of 2 and 3's.

Try your best and submit your code to the online judge. If you cannot pass, i will post my work tomorrow.

It is bed time now.

[此贴子已经被作者于2007-9-17 17:16:39编辑过]
#4
雨中飞燕2007-09-17 17:21
------------------------
4 5 6
2 2 2 3 2 3

7 8 9
3 4 2 6 3 6

偶习惯用DP来想问题了。。。不过DP也菜。。。
可以找出的规律是弄出尽可能多的因子3，余1的话就少拆一个3转换为一个4


by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-17 17:22:22编辑过]
#5
weishj2007-09-18 11:20
基于飞燕MM的思想，我弄了这个程序，不过超时了。等会儿吃完饭优化一下速度看
[CODE]#include <stdio.h>
#include <math.h>
int main()
{
int a,b,c,p;
while(scanf("%d",&a))
{
if(a<=0) break;
b=a/3;
c=a%3;
switch(c)
{
case 0:
p=int(pow(3,b));
break;
case 1:
p=int(pow(3,b-1)*4);
break;
case 2:
p=int(pow(3,b)*2);
break;
}
printf("%d\n",p);
}
return 0;
}[/CODE]
#6
雨中飞燕2007-09-18 11:31
不超时才怪，死循环一个



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#7
weishj2007-09-18 11:41

我用VC6输入0时就退出循环了，难道VC6不行
#8
雨中飞燕2007-09-18 11:43
以下是引用weishj在2007-9-18 11:41:33的发言：

我用VC6输入0时就退出循环了，难道VC6不行

你试过真的？？？我不信
你看看题目说的什么结束程序



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#9
HJin2007-09-18 12:06
回复：（haohaoxue）整数最优分解?????????

here is my submitted code at nku.

I implemented a BigInt * BigInt method inside --- which is not efficient. You may want to rewrite it in either C or asm.

The basic idea is as follows. Let q = n/3, r = n%3.

If r==0, then max product = 3^q;
If r==1, then max product = 3^(q-1)*4;
If r==2, then max product = 3^q * 2.


程序代码：


char a[10002];


void f(int k)
{
    int i=1, m=1, c, t, j;
    a[0]='1';


    for(j=1; j<=k; ++j)
    {
        c=0;
        for(i=0; i<m; ++i)
        {
            t = 3*(a[i]-'0')+c;
            a[i] = '0'+t%10;
            c = t/10;
        }
        if(c>0)
        {
            a[i]='0'+c;
            ++i;
            ++m;
        }
    }


    a[i]='\0';
}


void g(int k)
{
    int i, m, c, t;


    m=strlen(a);
    c=0;
    for(i=0; i<m; ++i)
    {
        t = k*(a[i]-'0')+c;
        a[i] = '0'+t%10;
        c = t/10;
    }
    if(c>0)
    {
        a[i]='0'+c;
        ++i;
        ++m;
    }


    a[i]='\0';
}


main()
{
    int n, q, r;
    char*b, *e, ch;


    while(scanf(\"%d\", &n)!=-1)
    {
        if(n<4)
        {
            printf(\"%d\n\", n);
            continue;
        }


        q=n/3;
        r=n%3;
        if(r==0)
            f(q);
        else if(r==1)
        {
            f(q-1);
            g(4);   
        }
        else
        {
            f(q);
            g(2);            
        }


        b = a;
        e = a+strlen(a)-1;
        while(b<e)
        {
            ch=*b;
            *b++=*e;
            *e--=ch;
        }


        printf(\"%s\n\", a);
        a[0]='\0';
    }
}
#10
weishj2007-09-18 12:08

我晕难道南开的服务器是网通的??这会进N次进不去了
TO:雨中飞燕
不试过我怎么会乱说话呢?
#11
HJin2007-09-18 12:12
回复：（weishj）基于飞燕MM的思想，我弄了这个程序，...
you got the idea, except overflow of 32-bit int.
#12
weishj2007-09-18 12:25
晕,没考虑溢出
#13
雨中飞燕2007-09-18 12:35
以下是引用weishj在2007-9-18 12:08:15的发言：

我晕难道南开的服务器是网通的??这会进N次进不去了
TO:雨中飞燕
不试过我怎么会乱说话呢?

看来你不知道EOF为何物
你不超时才怪，肯定死循环


by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-18 12:36:35编辑过]
#14
卧龙孔明2007-09-18 12:38
以前见过,vijos上的题
我在http://program.xuntan.com/dispbbs.php?boardid=2&id=65&page=1写过
vijos上AC:
#include<stdio.h>
int s[1001]={0};
int x=1000;
void cheng(int m)
{
int i;
for(i=1000;i>=x;i--) s[i]*=m;
for(i=1000;i>=x;i--) { s[i-1]+=s[i]/10; s[i]%=10; }
if(s[x-1]) x--;
}
int main(void)
{
int i,j,k;
int n;
s[x]=1;
scanf("%d",&n);
while(n>4)
{
n-=3;
cheng(3);
}
cheng(n);
for(i=x;i<1001;i++) printf("%d",s[i]);
return 0;
}
#15
weishj2007-09-18 12:39
回复：（雨中飞燕）以下是引用weishj在2007-9-18 12:0...
你没看我程序就说
即使while(scanf("%d",&a))是死循环,那下面
if(a<=0)break;
这一句呢？

说实话我每次上这论坛前都先开编译器然后开ＩＥ的，我的每一个程序都是亲自测试后发上来的,甚至我说的每一句话也是亲自检验过的。

[此贴子已经被作者于2007-9-18 12:41:17编辑过]
#16
HJin2007-09-18 12:54
回复：（weishj）回复：（雨中飞燕）以下是引用weishj...

程序代码：


#include <iostream>
using namespace std;


int main()
{
    int a;


    /** try on a windows machine:


    input 6 7 8
    and press F6 (F6 means your input is done) + enter


    you will see program hangs at 8 forever


    */
    while(scanf(\"%d\", &a))
    {
        cout<<a<<endl;


        if(a<=0)
            break;
    }


    return 0;
}
#17
HJin2007-09-18 13:04
回复：（卧龙孔明）以前见过,vijos上的题我在http://p...

submitted your code at nku (sorry, without your permission)
and it runs for 340ms.

My code above runs for 220ms.

There are some code which runs for 20ms. I would think for that we need to use assembly language to do the power and multiplication.


#include<stdio.h>
int s[10001]={0};
int x=10000;
void cheng(int m)
{
    int i;
    for(i=10000;i>=x;i--) s[i]*=m;
    for(i=10000;i>=x;i--) { s[i-1]+=s[i]/10; s[i]%=10; }
    if(s[x-1]) x--;
}
int main(void)
{
    int i,j,k;
    int n;
    s[x]=1;


   while( scanf(\"%d\",&n) != EOF)
{
    while(n>4)
    {
      n-=3;
      cheng(3);
    }
    cheng(n);
    for(i=x;i<10001;i++) printf(\"%d\",s[i]);
printf(\"\n\");


}
    return 0;
}
#18
weishj2007-09-18 13:06

你是说输入6<空格>7<空格>8
然后按F6+Enter吗?
这我试了,确实8不会显示出来,不过再按回车8会显示。
按你说这种方法输入，即使把程序改成
while(scanf("%d",&a)!=-1)
或者while(scanf("%d",&a)!=EOF)也是会在第三个数字时挂起的呀
#19
雨中飞燕2007-09-18 13:08
以下是引用weishj在2007-9-18 12:39:32的发言：
你没看我程序就说
即使while(scanf("%d",&a))是死循环,那下面
if(a<=0)break;
这一句呢？

说实话我每次上这论坛前都先开编译器然后开ＩＥ的，我的每一个程序都是亲自测试后发上来的,甚至我说的每一句话也是亲自检验过的。

遇到EOF标志你的程序就是死循环，谢谢！！！！！！！！！！！！！



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#20
weishj2007-09-18 13:12
算乘方我想可以这样稍作处理：
3^2=（2<<2）+1,
3^n=((3^2)^(n/2)),若n奇数，后面再乘3
但我不知这样会不会稍微提高效率
#21
HJin2007-09-18 13:16

i meant 6 7 8 enter
#22
HJin2007-09-18 13:21
power(a, b) can be done in O(lg b) time by squaring if a^b is in the range of your int type.

If it exceeds the range, you have to implement it differently. You can either first write a BigInt class and then apply the O(lg b) squaring algorithm, or use the O(n) algorithm for a^b listed above in my post and ZhuGeKongMing's post.
#23
weishj2007-09-18 13:32
回复：（雨中飞燕）以下是引用weishj在2007-9-18 12:3...

其它编译器我不知道，但如果你有VC6.0的话麻烦你运行一下,你可以随便输入,想怎么输入就怎么输入,要是遇到死循环的情况麻烦告诉一下,谢谢.
如果在其它编译器下确实出现死循环,那是我编译器的问题,也说明我知识面太窄。


TO Hjin:
我已经测试了一切可能发生的输入情况均没有出现死循环呀。
我在DEV C++下也试了也没出现死循环呢？
#24
雨中飞燕2007-09-18 13:36
以下是引用weishj在2007-9-18 13:32:28的发言：

其它编译器我不知道，但如果你有VC6.0的话麻烦你运行一下,你可以随便输入,想怎么输入就怎么输入,要是遇到死循环的情况麻烦告诉一下,谢谢.
如果在其它编译器下确实出现死循环,那是我编译器的问题,也说明我知识面太窄。


TO Hjin:
我已经测试了一切可能发生的输入情况均没有出现死循环呀。
我在DEV C++下也试了也没出现死循环呢？

任何编译器都可以令你死循环，谢谢！！！！！！！！！！！！！！！！
如果你不知道何为EOF，请你查资料，谢谢！！！！！！！！！！！！！！！！！！！



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#25
weishj2007-09-18 13:38

你别老EOF的说，EOF不就是-1嘛
你倒是弄出来个死循环让我看下，并把出现死循环时你的输入情况说一下呀，
我编程水平确实不行，但我根本没有试出过死循环，在发这帖子时我也一直在试
#26
雨中飞燕2007-09-18 13:38

如果你觉得我很白痴，我说的很无聊，是错的话，那你试试这个题

by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918" target="_blank">https://yzfy.org/bbs/viewthread.php?tid=329
你用你那种循环来写


by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-18 13:40:40编辑过]
#27
weishj2007-09-18 13:45
我是相信事实的，你说死循环你又不说什么情况下会死循环，我不想这样吵了。
在这个论坛上没有谁白痴不白痴的，只有事实和知识才是至高无上的。
我知识面窄，想看看事实结果你又舍不得给我举证，我无话可说
#28
雨中飞燕2007-09-18 13:49
以下是引用weishj在2007-9-18 13:45:43的发言：
我是相信事实的，你说死循环你又不说什么情况下会死循环，我不想这样吵了。
在这个论坛上没有谁白痴不白痴的，只有事实和知识才是至高无上的。
我知识面窄，想看看事实结果你又舍不得给我举证，我无话可说

我早就说了什么情况，你没听，还说我没说
EOF不是特定的数字，叫你查资料你也没查
Hjin之前也说过也不知道你看明白没有



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#29
远去的列车2007-09-18 13:58
MM说话比较冲
#30
雨中飞燕2007-09-18 14:10
以下是引用远去的列车在2007-9-18 13:58:38的发言：
MM说话比较冲

我尽量改。。。。



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#31
weishj2007-09-18 14:30

关于是否死循环的问题，只再发此一贴：
此题http://yzfy.org/bbs/viewthread.php?tid=329对输入数字没有限制，不用scanf(...)=-1将无法结束输入
但对本贴所讨论的问题中，有要求说输入是正整数，所以我仍然认为用
while(scanf("%d",&a))
{
if(a<=0)break;
......
}
不会对程序造成死循环。如果谁有办法让上述语句出现死循环的案例，请通过QQ：360956932告诉我一下，我将感激不尽。同时也非常希望与各位编程高手交个朋友
至于说EOF，我经常是用VC6，在VC6中有#define EOF -1
另外EOF相当于Ctrl+z 的效果，程序运行时按Ctrl+z也不会死循环。
再说一点，就是若用while(scanf("%d",&a)!=EOF)，用户输入的若不是数字，而是字母，那么这时才是真正的死循环。因为输入的字母破坏了输入流的正常工作，输入流中fail位被置1。
但用while(scanf("%d",&a))时，当输入流被破坏时，scanf将返回0，可以正常结束程序。
红色的部分与此贴无关，随便说说
#32
雨中飞燕2007-09-18 14:40
手动按Ctrl+Z和真正遇到EOF标志是有差别的，两者不完全等价
所以我只能告诉你，
while(scanf("%d",&a))
{
if(a<=0)break;
......
}
这种循环遇到EOF就是会死掉



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/
#33
雨中飞燕2007-09-18 14:43
此题
by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918" target="_blank">https://yzfy.org/bbs/viewthread.php?tid=329对输入数字没有限制，不用scanf(...)=-1将无法结束输入[/quote]
你完全可以假定没有负数，反正我的测试数据第一组全部是正数
你试试看。但即使有负数，也是WA，也不会出现TLE。



by 雨中飞燕 QQ:78803110 QQ讨论群:5305909

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=162918]C++编写的Windows界面游戏[/url]
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)：[/url] http://yzfy.org/

[此贴子已经被作者于2007-9-18 14:44:49编辑过]
#34
aipb20072007-09-21 13:13

讨论真激烈，

一个不优化的DP解是0（n^2）
1
©2025, BC-CN.NET
电脑版