1 2 5三个数相加等于1000，共有多少种情况？
要求行数。
写了一个三行的
for(i=1;i<500;i++)
for(j=1;j<200;j++)
if((i*2+j*5)<1000)count++;
面试官说可以两行实现，请各位高手指点指点！
langue 回复于：2007-03-23 22:36:38
.
for(i=1;i<500;i++) for(j=1;j<200;j++) if((i*2+j*5)<1000) count++;
这是一行的。
.
cugb_cat 回复于：2007-03-23 22:45:41
引用：原帖由 langue 于 2007-3-23 22:36 发表
.
for(i=1;i<500;i++) for(j=1;j<200;j++) if((i*2+j*5)<1000) count++;
这是一行的。
.
哈哈，是这么回事～～～～
C代码都可以写在一行里的
liuke432 回复于：2007-03-23 22:46:16
引用：原帖由 langue 于 2007-3-23 22:36 发表
.
for(i=1;i<500;i++) for(j=1;j<200;j++) if((i*2+j*5)<1000) count++;
这是一行的。
.
不是这个意思。 ：）
好像可以再去掉一个for循环
飞灰橙 回复于：2007-03-23 23:27:22
引用：原帖由 liuke432 于 2007-3-23 22:46 发表
不是这个意思。 ：）
好像可以再去掉一个for循环
for改while, 再去两个都没问题:mrgreen:
liuke432 回复于：2007-03-24 00:28:48
不好意思，我没有表达明白意思。
我的意思其实是要求效率再高一点。
ArXoR 回复于：2007-03-24 08:48:00
一般化一下, 设求的和为n
枚举5的个数就行了
设i个5, 则剩下的n - 5 * i 由2和1组成的种数为floor((n - 5 * i) / 2)
所求为
y = sigma{floor((n - 5 * i) / 2), 0 <= i <= floor(n / 2)}.
然后按i和n的奇偶性异同分类求和就可以得到close form了, 一个关于n的2次多项式.
[ 本帖最后由 ArXoR 于 2007-3-25 10:16 编辑 ]
liuke432 回复于：2007-03-24 19:15:12
引用：原帖由 ArXoR 于 2007-3-24 08:48 发表
一般化一下, 设求的和为n
枚举5的个数就行了
设i个5, 则剩下的n - 5 * j 由2和1组成的种数为floor((n - 5 * j) / 2)
所求为
y = sigma{floor((n - 5 * j) / 2), 0 <= i <= floor(n / 2)}.
然后 ...
恩 明白了 厉害！
这样就可以了
for(i=1;i<200;i++)
count+=(1000 - 5i)/2+1;
[ 本帖最后由 liuke432 于 2007-3-24 19:17 编辑 ]
converse 回复于：2007-03-24 23:33:35
保留本帖，方便查找。
liuke432 回复于：2007-03-25 07:26:07
感谢converse版主！ ：）
ArXoR 回复于：2007-03-25 10:24:40
引用：原帖由 converse 于 3/24/07 23:33 发表
保留本帖，方便查找。
其实这个方法并不具有一般性, 因为集合{a_i}, 0 <= i < m, 中存在一个a_k, 使得 a_k | a_i, 0 <= i < m,
这里a_k = 1.
一般的有限正整数集合的话, 生成函数才是王道...
fengwy 回复于：2007-03-25 19:03:07
ArXoR 是学数学的？
njmarshal 回复于：2007-03-26 02:14:07
for(i=1;i<200;i++)
count+=(int)((1000-5*i-1)/2);
其实这里因为是 整数除法 所以强制转换 (int) 可以不要
[ 本帖最后由 njmarshal 于 2007-3-26 02:30 编辑 ]
hake2000 回复于：2007-03-26 11:06:27
引用：原帖由 liuke432 于 2007-3-24 19:15 发表
恩 明白了 厉害！
这样就可以了
for(i=1;i<200;i++)
count+=(1000 - 5i)/2+1;
没注意边界值
hake2000 回复于：2007-03-26 11:17:37
引用：原帖由 hake2000 于 2007-3-26 11:06 发表
没注意边界值
for(k=1;k<200;k++)
{
count2+=(1000 - 5*k -1)/2;
}
此时count2的结果为 0xc1c1
for(k=1;k<200;k++)
{
count2+=(1000 - 5*k)/2;
}
此时count2的结果为 0xc224
百思不得其解，这两种情况结果应该相同亚。难道是我对除法运算还没弄明白？？？
郁闷
hake2000 回复于：2007-03-26 11:19:39
引用：原帖由 hake2000 于 2007-3-26 11:17 发表
for(k=1;k<200;k++)
{
count2+=(1000 - 5*k -1)/2;
}
此时count2的结果为 0xc1c1
for(k=1;k<200;k++)
{
count2+=(1000 - 5*k)/2;
}
此 ...
编译环境是gcc 3.2.2
hake2000 回复于：2007-03-26 11:35:46
终于知道了，晕
低级失误亚！！！ 一直以为 （1000 － 5*k）是奇数！！！！！！！！！！！！
唉
hake2000 回复于：2007-03-26 11:37:33
引用：原帖由 hake2000 于 2007-3-26 11:19 发表
编译环境是gcc 3.2.2
for(k=1;k<200;k++)
{
count2+=(1000 - 5*k)/2;
}
零个1的情况是不应该算的
njmarshal 回复于：2007-03-26 13:09:34
引用：原帖由 liuke432 于 2007-3-23 22:29 发表
1 2 5三个数相加等于1000，共有多少种情况？
要求行数。
写了一个三行的
for(i=1;i<500;i++)
for(j=1;j<200;j++)
if((i*2+j*5)<1000)count++;
面试官说可以两行实现，请各位高手指 ...
从上面的代码可以看出题目的要求是"1" ,"2","5"分别至少要有 1 个
所以我们的代码可以这样写
// a c 可以为"2","5"任何一个
// b=1
// 原来的考虑有点欠缺
// 1 是很特殊的数字。任何正整数都可以用多个1相加得到
// so b must be 1
// ok?
// 但 a,b,c 不能相等
for(i = a ; i<1000 ; i+=a) //i=a是保证至少有一个a
count += (1000-i-b) /c; //减去b是保证至少有一个b
//除以c则反映出a,b组成1000-i的b,c合法组数
或者下面这样的代码也可以
但不如上面的好
// a,c=2,5 or a,c=5,2
b=1
for(i = 1 ; i<1000/a ; i++)
count += (1000 - i*a -b) /c;
比如a=5 b=1 c=2就成了我上面的一个帖子代码
见13楼
引用：原帖由 njmarshal 于 2007-3-26 02:14 发表
for(i=1;i<200;i++)
count+=(int)((1000-5*i-1)/2);
其实这里因为是 整数除法 所以强制转换 (int) 可以不要
[ 本帖最后由 njmarshal 于 2007-3-26 17:40 编辑 ]
ArXoR 回复于：2007-03-26 13:40:50
引用：原帖由 njmarshal 于 3/26/07 13:09 发表
从上面的代码可以看出题目的要求是"1" ,"2","5"分别至少要有 1 个
所以我们的代码可以这样写
// a b c 可以为"1","2","5"任何一个 ...
不知道你在写什么, 我觉得你似乎没有明白为什么可以这样算.
njmarshal 回复于：2007-03-26 16:55:34
引用：原帖由 ArXoR 于 2007-3-26 13:40 发表
不知道你在写什么, 我觉得你似乎没有明白为什么可以这样算.
你觉得哪里不理解
我上面的代码用a b c代替了 5 2 1
是这个程序具有扩展性
可以完成任意3个正整数组合的大多数问题
ArXoR 回复于：2007-03-26 17:20:55
引用：原帖由 njmarshal 于 3/26/07 16:55 发表
你觉得哪里不理解
我上面的代码用a b c代替了 5 2 1
是这个程序具有扩展性
可以完成任意3个正整数组合的大多数问题
在你写的程序里面
b != 1 时能保证所有这些a,b,c加起来等于1000么?
换句话说, b 不一定整除 (1000 - i - b - j * c), 0 <= j*c <= 1000 - i - b.
我的之前给的方法就是基于存在一个1, 能整除2与5, 而且能整除n.
而且要求1,2,5至少都有一个也不是什么问题, 对1000-8=992 求就好了
[ 本帖最后由 ArXoR 于 2007-3-26 17:22 编辑 ]
njmarshal 回复于：2007-03-26 17:37:33
引用：原帖由 ArXoR 于 2007-3-26 17:20 发表
在你写的程序里面
b != 1 时能保证所有这些a,b,c加起来等于1000么?
换句话说, b 不一定整除 (1000 - i - b - j * c), 0 <= j*c <= 1000 - i - b.
我的之前给的方法就是基于存在一个1, 能整除2与5, ...
恩
有道理
考虑欠缺
1是很特殊的数字 ,任何整数总可以用他想加得到
确实
wuxb45 回复于：2007-03-26 18:32:23
int i;
int count=1;
for(i=1000;i;i-=5)
count+=(i/2+1);
不好意思四行
wuxb45 回复于：2007-03-26 18:34:11
关键是简化运算步骤而不是怎么写。
010320223 回复于：2007-03-26 21:28:22
for(i=200;i>=0;i--)
{
count+=floor(5*i/2)+1;
}
macer 回复于：2007-03-27 10:51:55
如果是三个数为3,5,7又该怎么考虑呢
ArXoR 回复于：2007-03-27 11:10:11
引用：原帖由 macer 于 3/27/07 10:51 发表
如果是三个数为3,5,7又该怎么考虑呢
用生成函数, 求 1 / (1 - x^3) * 1 / (1 - x^5) * 1 / (1 - x^7) 展开式中x^n的系数.
已经有系统的方法来计算了,
能不能求出close form没试不知道.
可以参考<<Concrete Mathematics>>
dbcat 回复于：2007-03-27 12:03:17
3,5,7的母函数还是写成(1+x^3+x^6+x^9+.....)(1+x^7+x^14+x^21+...)(1+x^5+x^10+x^15+...)让大家好理解些
lenky0401 回复于：2007-03-27 18:42:36
引用：原帖由 liuke432 于 2007-3-24 00:28 发表
不好意思，我没有表达明白意思。
我的意思其实是要求效率再高一点。
其实他们都懂你的意思了 只是和你开玩笑而已
macer 回复于：2007-03-28 14:10:30
怎么现在都记不起来这些了呢？昨天一收到回复就去查看了下，结果什么都记不起来啦
chen_gxing 回复于：2007-03-28 16:17:49
好贴，好问题。
Darkcoming 回复于：2007-03-31 14:53:27
对这种编程不太懂 数学学得不好 不过要我解决 我就会用公倍数作为突破点 相信效率是最高的
[ 本帖最后由 Darkcoming 于 2007-3-31 15:00 编辑 ]
王紫豪 回复于：2007-04-04 01:56:54
00000000000
gta 回复于：2007-04-06 22:05:01
好帖，留名
|
