主题:这是我们的竞赛题,看你们能做出来几道
Matodied
[专家分:7560] 发布于 2007-04-19 20:18:00
(各题加分:20 10 20 30)
1、字符串匹配问题:输入一个带括号的字符串,(四种括号:( ) < > [ ] { })如果
括号全部成对出现,并且顺序正确,称为匹配,否则不匹配。
示例:
匹配的字符串:(ABC[D{E}]FGH)、<ERROR>、(<[1234{5}]>)
不匹配的字符串:(34789、(A[BC)DEF]、(<6667}
如果输入的字符串没有括号,如ABCD,则让你重新输入。
2、任何一个数的三次方都能表示成一串奇数的和,如3^3=11+9+7,现输入一个数,把这串奇数打印出来。
如:输入4,输出19+17+15+13=64=4^3。
3、有N个人要接受检测,每个人检测的时间为3-7分钟,现有三个检测员同时检测,求要多长时间。
4、输入N,输出N!的最后一位非0的数字(10000<N<10000000000)。
回复列表 (共67个回复)
41 楼
moz [专家分:37620] 发布于 2007-05-12 14:09:00
不好意思,一直都很忙,而且脑袋有点迟钝,大不如前了。
至于第四题,我之前说了大半天的的理论了,
好像已经说到5的重要性了吧?
然后我又注意到,其实,每5个数的序列是相同的,
然后每5组序列,只要带头的数固定,就可以得到排尾的数。
也就是说,序列是固定的,只是不严格循环而已。
根据这个思路,我瞎忙了几天,又静思了几天,
终于写出以下代码,经过试验,得数应该是正确的。
只是达不到题目要求的范围 10 M ~ 10 G
因为长整形的数值范围2G的限制,所以只能达到5的13次方,也就是1G以内。
如果非得要扩展到10G,也是可以的,可以用字符串来替代运算过程,
只是略嫌麻烦,我就不做了。
declare function z&(a&)
declare function k5&(u&)
declare function nexts&(a&,k&,s&)
declare function next5&(a&,b&)
declare sub start()
declare sub count(a&,b&)
deflng a-z
dim shared c(16,8,5),p(3),q(8)
start
do
input a
if a=0 then exit do
print z(a)
loop
function k5(u)
do while u mod 5=0
k=k+1
u=u\5
loop
k5=k
end function
function next5(a,b)
a=a+1
u=a
k=k5(u)
next5=(p((q(b)+k)mod 4)*u)mod 10
end function
function nexts(a,k,s)
if c(k,s,0)=0 then
x=s
for i=1 to 5
c(k,s,i)=x
if i<5 then
x=next5(a,nexts(a,k-1,x))
else
c(k,s,0)=nexts(a,k-1,x)
end if
next
else
a=a+5^k-1
end if
nexts=c(k,s,0)
end function
sub start
p(0)=2:p(1)=6:p(2)=8:p(3)=4
q(2)=0:q(4)=3:q(6)=1:q(8)=2
c(1,2,0)=8: c(1,2,1)=2: c(1,2,2)=2: c(1,2,3)=4: c(1,2,4)=2: c(1,2,5)=8
c(1,4,0)=6: c(1,4,1)=4: c(1,4,2)=4: c(1,4,3)=8: c(1,4,4)=4: c(1,4,5)=6
c(1,6,0)=4: c(1,6,1)=6: c(1,6,2)=6: c(1,6,3)=2: c(1,6,4)=6: c(1,6,5)=4
c(1,8,0)=2: c(1,8,1)=8: c(1,8,2)=8: c(1,8,3)=6: c(1,8,4)=8: c(1,8,5)=2
s=2
a=5
do
s=nexts(a,k5((a)),s)
s=next5(a,s)
loop until a>1000000000
end sub
function z(a)
if a>5^13 then exit function
s=6
x=-1
for i=12 to 1 step-1
do while a>=(5^i)
x=x+5^i
a=a-5^i
s=next5((x),c(i,s,0))
loop
next
z=c(1,s,a+1)
end function
42 楼
Matodied [专家分:7560] 发布于 2007-05-12 14:10:00
moz,你的程序也太长了!
43 楼
&佑慧妹妹& [专家分:660] 发布于 2007-05-12 15:37:00
MOZ,高手编程是不是都应该用递归呢?
44 楼
moz [专家分:37620] 发布于 2007-05-12 16:30:00
你在论坛里搜一搜“递归”,有很多高手讨论过。
其实通常说来,递归是高效易于理解的,应该尽量灵活运用。
但在QB里,有空间的限制。
在更高级的对象化编程里,空间宽大了,也就不怎么顾忌了,
只有在数据量巨大的时候需要注意空间与毅然效率问题。
你只要明白了递归的原理和方法,就会知道递归的过程是怎样实现的,
就会懂得怎样避开它的软筋。
我曾经经常用数据来代替递归。
空间与速度比递归都要占优,(特别是面过对象,调用处理都占了不少时间)
只是那些代码很多时候甚至我自己都无法理解,常常看不清楚而致头晕脑涨。
45 楼
&佑慧妹妹& [专家分:660] 发布于 2007-05-12 16:38:00
哦,那您的意思是说,递归是容易并快速的方法?
46 楼
moz [专家分:37620] 发布于 2007-05-12 18:00:00
按照传统的教学与应用来说,(特别是考试),应该是的。
但要注意场合,明明for循环就能解决的简单问题,你非要用递归,那可不好看。
47 楼
PROLUN [专家分:0] 发布于 2007-05-17 21:48:00
1:CLS
10 INPUT "N$=", N$
L = LEN(N$)
Q = 0: R = 0
FOR I = 1 TO L
C$ = MID$(N$, I, 1)
IF C$ = "(" OR C$ = "<" OR C$ = "{" OR C$ = "[" THEN R = R + 1: Q = 1
IF C$ = ")" OR C$ = ">" OR C$ = "}" OR C$ = "]" THEN R = R - 1: Q = 1
NEXT
IF Q = 0 THEN 10
IF R = 0 THEN PRINT "PIPEI" ELSE PRINT "BUPIPEI"
48 楼
PROLUN [专家分:0] 发布于 2007-05-17 21:54:00
MOZ,长整形不可以,双精度不会也不行吧
49 楼
PROLUN [专家分:0] 发布于 2007-05-17 22:25:00
对第四题,我也有几句话要说。
如果扩N倍它的末位非零数字(以下简称末零)一定是以它的个位扩倍的。
例如37的末零是4,而38的末零是2
当然,这是基于非5倍数而言的。
如果是五的倍数呢?
那么它有几个质因子五就除以几个二
例如49的末零是4,50的末零是2(一个2可以抵消1个5)
最重要的一点
大于二的末零都是偶数
只要讨论个位就可以了,不是么?
程序已是手到擒来的事了。
50 楼
moz [专家分:37620] 发布于 2007-05-19 11:33:00
请楼上试试,
你看到表面了,但因为你没有下手,
所以会有某些小问题你没有看到。
我承认我的程序很可能疏忽了某种规律,
因为我还没有能力与时间去把它变成公式函数。
只讨论个位不一定正确,就拿49到50来说吧,只讨论个位能解决问题吗?
f(49)=4,我来说说我算f(50)的方法
50=5*5*2 (分解5因子)
有两个5, f(49)需要两次除2
第一次除2 4/2=2
第二次除2 2/2=6
然后与剩下的因子2相乘,6*2=2
得f(50)=2
有了f(50)=2,后面的序列可以说是有规律是固定的,因为后面的个位数字是有规律的.
2,2,4,2,8.......
我来回复