主题:这是我们的竞赛题,看你们能做出来几道
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个回复)
51 楼
Templar9d [专家分:2110] 发布于 2007-05-19 20:59:00
我的思路是把2,5分解出来单独统计,然后同时统计剩余因子的个位。
只用考虑3个:末尾是3,7或9。
整个过程就是1个数组存高精度数,几个数组存不同个数的2,3,7,9对应的末位数,然后就是一个递归进行统计。如果正确的话时间复杂度将相当低。我先验证,有结论再说。
[修改]结果出来了,还不错。发新贴讨论了。
52 楼
moz [专家分:37620] 发布于 2007-05-20 10:24:00
双精度是没有区别的,
因为对于 \ 整除 , mod 取余 等整数运算,
必须要在长整形范围内才能运算,
双精度也要转换成长整形才开始运算,
超出长整形的范围,仍然溢出.
53 楼
knate [专家分:570] 发布于 2007-05-22 19:02:00
还没有人写全?
等下我把我的库存发上来!
54 楼
knate [专家分:570] 发布于 2007-05-22 19:26:00
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)。
2:当n%2==1
n^3=n^2*n n^2%2==1;
n^3=(n^2-m)+(n^2-m+2)+..n^2+....(n^2+m) 共n个数,步长为2;
当n%2==0
(n^2-1)%2=1 (n^2+1)%2==1;
n^3=(n^2-m)+(n^2-m+2)+.n^2-1+n^2+1+....(n^2+m) 共n个
3;用贪心算法!求较佳解!
(当然可以用全排列处理,每处理一次记录检测到当前为止最佳方法,但太复杂不现实)
n太大时几乎不能实现)
4:所有n全部分解为k(可变)×2^x×5^y
所有k取k=k%10;
然后求k=(k1*k2*....)%10
所有x之和-所有y之和
remainder=k*2^(所有x之和-所有y之和)
算法实现上复杂度为log(2,n)*n*long(5,n)
第一题没意思,不作了,只要稍微使用堆栈处理一下就可以了!
55 楼
knate [专家分:570] 发布于 2007-05-22 21:17:00
int remainder(long int n)
{
int remainder=1;
int temp=0;
int sec,fif;
sec=fif=0;
for(int x=1;x<=n;x++)
{
temp=x;
for(;temp%2==0;)
{
temp/=2;
sec++;
}
for(;temp%5==0;)
{
temp/=5;
fif++;
}
temp%=10;
remainder*=temp;
remainder%=10;
sec-=fif;
fif=0;
}
for(int x=0;x<sec;x++)
{
remainder+=remainder;
remainder%=10;
}
return remainder;
}
56 楼
Matodied [专家分:7560] 发布于 2007-05-24 21:02:00
楼上的,请你把C的程序改成QB的.
57 楼
moz [专家分:37620] 发布于 2007-05-25 22:26:00
可以算到9后面14个零
print S(900000000000000@)
DEFCUR A-Z
FUNCTION s (n)
k = 476837158203125@
x = 6
FOR i = 21 TO 0 STEP -1
IF n >= k THEN
u = FIX(n / k)
n = n - u * k
SELECT CASE u
CASE 0
CASE 1: x = VAL(MID$("6248",(i+INSTR("2486",CHR$(48+x))) MOD 4+1,1))
CASE 2: x = x * 2 * (1 + 3 * (i MOD 2)) MOD 10
CASE 3: x = VAL(MID$("4268",(i+INSTR("2684",CHR$(48+x))) MOD 4+1,1))
CASE 4: x = 10 - x
END SELECT
END IF
k = k / 5
NEXT
s = x
END FUNCTION
58 楼
pengyuhui [专家分:30] 发布于 2007-05-27 09:07:00
好难
[em10][em10][em10][em10][em10]
59 楼
Lovely哆啦 [专家分:1360] 发布于 2007-07-20 22:01:00
2
CLS
INPUT n
a = n ^ 2 + n - 1
FOR i = a TO a - (n + INT(SQR(n))) + 2 STEP -2
PRINT i; "+";
NEXT i
PRINT i; "="; n ^ 3; "="; n; "^3"
60 楼
pk4321 [专家分:690] 发布于 2007-07-21 10:19:00
中学学编程就是为了做几道题!
如果学编程来做几个“有实际应用意义”的软件工程还差不多!
例如一些适合学生环境的软件:考试软件、学生成绩管理软件、课程表管理软件……
或者涉及的一些算法:用树的遍历来做分科目的成绩统计……
只不过,现在对编程授课有热忱的中学老师少了,自然对编程有爱好的中学生也少了!
我来回复