主题:求助:一道难题
烦人
[专家分:40] 发布于 2006-04-08 14:38:00
键盘输入一个数字N,用尽量少的互不重复的数字表示出1~~N之间所有的数,至少需要几个数,有多少种不同的可能。
例N=6
至少需要3个不同的数字,有2种可能:(1,2,3)和(1,2,4)。
用(1,2,3)三个数表示出1~~6之间的所有数。
1=1
2=2
3=3
4=1+3
5=2+3
6=1+2+3
或(1,2,4)
1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
回复列表 (共15个回复)
沙发
maxumi [专家分:2200] 发布于 2006-04-07 16:35:00
input n
k=1
b=0
while k<n
print k
b=b+1
k=k*2
wend
print"total:";b;" numbers."
end
板凳
烦人 [专家分:40] 发布于 2006-04-07 17:14:00
[quote]input n
k=1
b=0
while k<n
print k
b=b+1
k=k*2
wend
print"total:";b;" numbers."
end[/quote]
输出时B的值应该减1吧。
还有NUMBERS呢,怎么求?
3 楼
moz [专家分:37620] 发布于 2006-04-08 09:59:00
我 不知所云
4 楼
飞鸟12 [专家分:2830] 发布于 2006-04-09 08:54:00
INPUT "N=", n
FOR i = 1 TO n
FOR j = i + 1 TO n - i
k = n - i - j
IF i < j AND j < k THEN
PRINT n; "="; i; "+"; j; "+"; k
END IF
NEXT j
NEXT i
END
下面是运行结果
N=6
6 = 1 + 2 + 3
N=15
15 = 1 + 2 + 12
15 = 1 + 3 + 11
15 = 1 + 4 + 10
15 = 1 + 5 + 9
15 = 1 + 6 + 8
15 = 2 + 3 + 10
15 = 2 + 4 + 9
15 = 2 + 5 + 8
15 = 2 + 6 + 7
15 = 3 + 4 + 8
15 = 3 + 5 + 7
15 = 4 + 5 + 6
5 楼
烦人 [专家分:40] 发布于 2006-04-10 15:28:00
不是啊,哥哥,是要能表示出 1 到 N 之间所有的数,不是只表示一个N
6 楼
codepk [专家分:2800] 发布于 2006-05-02 08:44:00
抛砖引玉,来个暴力版的
DECLARE SUB myprint (n%, v%())
DECLARE SUB mytest (b%, e%, s%, v%())
DIM n, m, k, t, i AS INTEGER
DIM v(34) AS INTEGER
m% = 1
v%(1) = 1
t% = 1
INPUT n%
WHILE m% < n%
t% = t% + 1
v%(t%) = m% + 1
m% = m% + m% + 1
WEND
k% = m% - n%
IF t% <= 2 THEN CALL myprint(t%, v%()) ELSE CALL mytest(3, t%, k%, v%())
SUB myprint (n%, v%())
DIM i AS INTEGER
FOR i% = 1 TO n%
PRINT v%(i%);
NEXT
PRINT
END SUB
SUB mytest (b%, e%, s%, v%())
DIM k, l, x, i AS INTEGER
l% = 1
FOR i% = 1 TO e% - b%
l% = l% * 2
NEXT
k% = s% \ l%
FOR i% = k% TO 0 STEP -1
x% = s% - l% * i%
IF v%(b%) - i% > v%(b% - 1) THEN
v%(b%) = v%(b%) - i%
IF b% = e% THEN CALL myprint(e%, v%()) ELSE CALL mytest(b% + 1, e%, x%, v%())
v%(b%) = v%(b%) + i%
END IF
NEXT
END SUB
7 楼
moz [专家分:37620] 发布于 2006-05-02 20:48:00
还是不知所云
8 楼
diylym [专家分:30] 发布于 2006-07-26 12:42:00
你这个抛砖引玉看着非常棒可惜我看不懂因为我是一个初学者。你能帮帮我吗我很喜欢QB。
9 楼
rickone [专家分:15390] 发布于 2006-08-03 11:54:00
楼主没说清楚,输入一个数n,找得到m个数a1,a2,a3,...am,从这m个数中取一些的组合相加来表示1,2,...n的每一个数,求满足这样要求的最小的m。
我只知道至少m>=[ln(n+1)/ln2]向上取整,或许都可以取到这个最小值。
10 楼
rickone [专家分:15390] 发布于 2006-08-03 12:04:00
嗨,当然取得到,一时糊涂,就以二进制形式表示,设a(i)=1 << i,那a(0),a(1),...a(n-1)这n个数就可以表示0,1,2,...2^n-1个数,于是就达到了那个最小值。
程序是:(好久没用QB了,希望没错)
dim n,m
input n
m=log(n+1)/log(2)
if not int(m)=m then m=int(m)+1
print m
剩下的一个问题,有多少种不同的可能就麻烦点了,用深搜吧
我来回复