主题:求长度为素数的路径个数
cando
[专家分:0] 发布于 2005-06-16 16:05:00
求长度为素数的路径个数
对于正整数n(3<=n<=11),可以画出n阶的回形矩阵,下面画出的分别是3阶的,4阶和7阶的回形矩阵:
1 1 1
1 2 1
1 1 1
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
1 1 1 1 1 1 1
1 2 2 2 2 2 1
1 2 3 3 3 2 1
1 2 3 4 3 2 1
1 2 3 3 3 2 1
1 2 2 2 2 2 1
1 1 1 1 1 1 1
对于n阶回形矩阵,从左上角出发,每步可以向右或向下走一格,走2*n-2步,可以到达右下角。
我们把这样的路径上所有格子中的数值之和,叫做该路径的长度。
本题要求,对于给出n值,求出n阶回形矩阵有多少路径的长度为素数?如n=3时,路径及长度有:5、6、6、6、6、5
1 1 1
1 2 1
1 1 1
1 1 1
1 2 1
1 1 1
1 1 1
1 2 1
1 1 1
1 1 1
1 2 1
1 1 1
1 1 1
1 2 1
1 1 1
因此说,3阶回形矩阵有2条路径的长度为素数。
回复列表 (共5个回复)
沙发
moz [专家分:37620] 发布于 2005-06-17 11:52:00
1.找路径,
2.检测路径是否质数.
对于第一步,还得请f...tw大师套个框架来用用.
板凳
moz [专家分:37620] 发布于 2007-08-10 18:59:00
defint a-z
input n
dim shared a0%(n,n),a1&(n),a2@(n),a3$(n)
for i=1 to n
for j=i to n-i+1
for k=i to n-i+1
a0%(j,k)=i
next k,j,i
for i=n to 1 step-1
a3$(n)=mki$(n-i+1)+mkl$(1)
for j=n-1 to 1 step-1
a3$(j)=adda$(j,a0%(i,j))
next j,i
q@=0
for i=1 to len(a3$(1))step 6
j=cvi(mid$(a3$(1),i,2))
if iszs(j)then q@=q@+cvl(mid$(a3$(1),i+2,4))
next
print q@
function adda$(j,v)
z$=a3$(j)+a3$(j+1)
lx=len(a3$(j))
i=1
do while i<len(z$)
if i<lx then
j$=mid$(z$,i,2)
k=instr(lx+1,z$,j$)
do while k>0
if k mod 6=1 then
mid$(z$,i+2,4)=mkl$(cvl(mid$(z$,i+2,4))+cvl(mid$(z$,k+2,4)))
z$=left$(z$,k-1)+mid$(z$,k+6)
k=instr(k,z$,j$)
else
k=instr(k+1,z$,j$)
end if
loop
end if
mid$(z$,i,2)=mki$(v+cvi(mid$(z$,i,2)))
i=i+6
loop
adda$=z$
end function
function iszs(a)
for i=2 to sqr(a)
if a mod i=0 then exit for
next
iszs=i>sqr(a)
end function
3 楼
QB爱好者 [专家分:370] 发布于 2007-08-13 15:02:00
[em12]
[size=6][size=5][size=4][size=5][size=6][size=5][size=4][size=3][size=2][size=3][size=4][size=5][size=6][size=5][size=4][size=5][size=6]那么13你能在30秒之内出来吗?!!![/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size][/size]
4 楼
moz [专家分:37620] 发布于 2007-08-13 20:08:00
你为什么不试试看呢?
5 楼
QB小猪 [专家分:1200] 发布于 2007-08-14 08:08:00
CLS
INPUT n
DIM d(n * 2 - 1, n), c(n * 2 - 2)
m = n - 1
FOR I = -m TO m
x = x + 1
p = n - ABS(I)
FOR j = 1 TO p
IF j > p \ 2 THEN Q = p + 1 - j ELSE Q = j
d(x, j) = Q
NEXT j, I
m = n * 2 - 2
FOR I = 0 TO 2 ^ m - 1
x = I: b$ = "": K = 0
FOR j = 1 TO m
b$ = LTRIM$(STR$(x MOD 2)) + b$
IF x MOD 2 = 1 THEN K = K + 1
x = x \ 2
NEXT j
IF K = n - 1 THEN
FOR j = 1 TO m: c(j) = VAL(MID$(b$, j, 1)): NEXT j
x = 1: S = d(1, 1)
FOR j = 1 TO n * 2 - 2
x = x + c(j)
IF j < n THEN
S = S + d(j + 1, x)
ELSE
S = S + d(j + 1, x - j - 1 + n)
END IF
NEXT j
FOR W = 2 TO SQR(S)
IF S MOD W = 0 THEN 10
NEXT W: R = R + 1
END IF
10 NEXT I
PRINT R
END
请楼主调试一下,看看对不对?
我来回复