问一算法，看谁的简单！！！(50分)

  • 主题发起人 主题发起人 ranyang
  • 开始时间 开始时间
R

ranyang

Unregistered / Unconfirmed
GUEST, unregistred user!
有许多个数字，比如：
a1,a2,a3,a4,a5,......
要求这些数字满足和为一个数（比如100）的各种可能性有多少种？
比如：
a1=100
a2+a3=100
a3+a4+a7=100
a2+a4+a8=100
.
.
.
 
关注
要是我我就笨笨的排序，剔除比给定数大的数（100），选前一半和后一半来加，然后比较，得出结果。排序一般都是o2吧，如果用什么快速排序可能会快一些，好像是o，汗……没学好数据结构，大家别笑我
遍历前半段同时有后半段的指针了，只要一个循环就能over所以时间是o
2个加起来还是o就可以搞定
是不是？我没有写程序，凭空想的
 
你说是简单，确定？！
那么用下面的最简单--思维最简单。
c语言写的
 
等下，修改修改
 
//cnt是结果
//假设为a1 a2 a3 .......a100吧
#include<stdio.h>
main()
{
int i,j,cnt,tmp,a[100];

cnt=0;
for(i=1;i<100;i++)
{
tmp=0;
for(j=i;j<100;j++)
{
tmp=tmp+a[j];

if (tmp==100)
cnt=cnt+1;
}
}
print("%d",cnt);
}
 
有什么不对，尽管提，我的机子没有安tc
所以没有调试
 
有没有用pascal写的
 
哎pascal还不是一样
首先是你看懂思维
一切好办
 
穷举法:
数字编号为a0, a1, a2, a3, a4, ..................., An-1
for i:=1 to 2的n次方do
begin
m := 0;
for j:=0 to n-1do
begin
if i and 2的j次方 = 2的j次方 then

m := m + a[j];
end;
if m=100 then

得出一个解;
end;



 
根据题意。我们在程序最开始，还应该滤掉所有大于100的数。
我有一个不成形的想法，例如选择a1作为第一个加数时，在抽选第二个加数时，应该滤掉所有大于100-a1的数，依次下去。这样应该可以迅速提高速度。不过他也有局限性，在数据较多时，可能较为适用。牵扯到快速查找的问题。
 
楼主说的是简单
没有说效率，如果要谈效率，那么要讨论的就比较多了[^]
 
其实应该要一个效率问题！我的提法有问题！！！！
 
那么楼主
先说清楚--“有许多个数字”到底大概有多少数量级的数字
 
最少200个以内，最多1000个！
 
呵呵
楼主原来在线啊
如果是你说的那样我说的算法完全可以了
还有他们说的先将大于100的踢出去，也是很好的想法
 
有可能是多个数相加得到定数！！！
 
嘿嘿！我还没有去试！感觉你的算法可以！
 
我写的哪个就是的啊
所有组合都考虑了的
 
感觉我的可以就散分了撒
我现在还有10分了[:D]
 
对了
楼主
你有没有原始数据，我想试试。
自己构造实验数据很麻烦的
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
L
大狭们看看这段代码为什么出错，delphi5.0+paradox数据库(100分)
回复
19
查看
393
libaoliang
L
T
穷的一文都没，但问题还是要问。分组分栏报表(0分)
回复
3
查看
166
ttaa
T
G
报表问题，我就350分，愿出200分加一张DELPHI 7的安装盘。谢谢 (100分)
回复
16
查看
351
gm1995
G
阿
一个菜鸟问题，请那个大侠指点呀。(0分)
回复
4
查看
341
franczx
F
后退
顶部