回 帖 发 新 帖 刷新版面

主题:求长度为素数的路径个数

求长度为素数的路径个数
对于正整数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个回复)

沙发

1.找路径,
2.检测路径是否质数.

对于第一步,还得请f...tw大师套个框架来用用.

板凳

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 楼

[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 楼

你为什么不试试看呢?

5 楼

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
请楼主调试一下,看看对不对?

我来回复

您尚未登录,请登录后再回复。点此登录或注册