帮帮我用QBasic 求长度为素数的路径个数十万火急

主题：帮帮我用QBasic 求长度为素数的路径个数十万火急

snoopy7 [专家分：70] 发布于 2007-08-07 07:58:00

第四题  求长度为素数的路径个数
[问题描述]
对于正整数N（3<=N<=20）,可以画出N阶的回形矩阵。下面画出的分别是3阶的，4阶的和7阶的回形矩阵。

n=3
1    1    1
1    2    1
1    1    1
n=4
1    1    1    1
1    2    2    1
1    2    2    1
1    1    1    1

n=7
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时，路径及长度有：
[u]1[/u]    [u]1[/u]    [u]1[/u]
1    2    [u]1[/u]
1    1    [u]1[/u]
长度为5
[u]1[/u][u]    1[/u]    1
1    [u]2[/u]    [u]1[/u]
1    1    [u]1[/u]
长度为6
[u]1[/u][u]    1[/u]    1
1    [u]2[/u]    1
1    [u]1[/u[u]]    1[/u]
长度为6
[u]1[/u]    1    1
[u]1[/u]    [u]2[/u]    [u]1[/u]
1    1    [u]1[/u]

长度为6

[u]1[/u]    1    1
[u]1[/u]    [u]2[/u]    1
1    [u]1[/u][u]    1[/u]
长度为6
[u]1[/u]    1    1
[u]1[/u]    2    1
[u]1[/u]    [u]1[/u]    [u]1[/u]
长度为5

  因此说，3阶回形矩阵有2条路径的长度为素数。

[输入输出]
输入：
一个自然数N（3<=N<=20,不必判错）。

输出：
一个正整数，即N阶回形矩阵中长度为素数的路径个数。

[样例]
输入：
   3

输出：
   2

本帖地址： http://bbs.pfan.cn/post/245775.html

回复列表（共22个回复）

沙发

snoopy7 [专家分：70] 发布于 2007-08-07 08:20:00

拜托那位高手帮忙解一下

板凳

moz [专家分：37620] 发布于 2007-08-07 09:11:00

老旧贴里有.

3 楼

snoopy7 [专家分：70] 发布于 2007-08-07 11:46:00

请问大概是什么时间的,谢谢

4 楼

snoopy7 [专家分：70] 发布于 2007-08-07 11:53:00

我的程序速度慢,麻烦帮我改改
CLS
INPUT n
DIM a(n, n), b(n + n)
FOR i = 1 TO n
k = 1
FOR j = 1 TO n
PRINT k;
a(i, j) = k
IF i > j THEN k = k + 1
IF i + j > n THEN k = k - 1
NEXT
PRINT
NEXT
DO WHILE b(0) = 0
i = n * 2 - 2
DO WHILE b(i) = 1
b(i) = 0
i = i - 1
LOOP
b(i) = 1
s = 0
FOR j = 1 TO i
s = s + b(j)
NEXT
IF s <> n - 1 THEN 10
s = 1
q = 1: w = 1
FOR i = 1 TO n * 2 - 2
IF b(i) = 0 THEN w = w + 1 ELSE q = q + 1
s = s + a(q, w)
NEXT
IF s = 1 THEN 10
FOR j = 2 TO SQR(s)
IF s MOD j = 0 THEN 10
NEXT
t = t + 1

10 LOOP
PRINT t

5 楼

Matodied [专家分：7560] 发布于 2007-08-07 13:52:00

我们想到的算法可能是逐个试探，但这种方法效率太低。

我们先证明以下事实：
由于回形矩阵是对称的，因此只要找到了一条路径，就可以找到一条每步路都和这条路径的这一步走向相反（原来向右的向下，原来向下的向右）的路径。

假设在4阶回形矩阵里，可以找到以下路径（加粗的数字是走到的）：
[b]1[/b]  [b]1[/b]  [b]1[/b]  1
1  2  [b]2[/b]  1
1  2  [b]2[/b]  1
1  1  [b]1[/b]  [b]1[/b]
那么，根据这条路径可以找到以下路径：
[b]1[/b]  1  1  1
[b]1[/b]  2  2  1
[b]1[/b]  [b]2[/b]  [b]2[/b]  [b]1[/b]
1  1  1  [b]1[/b]
显而易见，这两条路径经过的数字都完全相同，只是方向相反，由于数字完全相同，它们经过的数字和也相同了。我们把这2条路径称为对称的路径。

因此：可以得到一种简便的试探方法：只在上三角（包括主对角线）上试探。

比如，4阶回形矩阵的上三角为：
1  1  1  1
   2  2  1
      2  1
         1

下三角为：
1
1  2
1  2  2
1  1  1  1

显然，如果能在上三角上找到一条路径，那么在下三角上也能找到和这条路径对称的一条路径。
在4阶矩阵的上三角上一共有5条路径，那么在下三角上也有5条路径，所以总共有10条。

这样只要在上三角上找到了一条数字之和为素数的路径，那么就记上，搜完后将结果乘2就行了。

程序我等会在发给你。

6 楼

moz [专家分：37620] 发布于 2007-08-07 18:02:00

[url=http://www.programfan.com/club/searchbbs.asp?keyword=%C2%B7%BE%B6&search=1&bbsid=12]搜一搜[/url]
[url=http://www.programfan.com/club/post-84580.html]第一贴[/url]
[url=http://www.programfan.com/club/post-98451.html]第二贴[/url]
但是我还没找到我写过的代码,找到了吓吓MatoDied
提醒一点:中间有一条路径重复.

7 楼

snoopy7 [专家分：70] 发布于 2007-08-07 18:15:00

我没搜到,我遇到好几道类似的问题,再帮我写写好吗,还有一道竖式问题,我马上要竞赛了,帮我解答好吗,万分感谢

8 楼

moz [专家分：37620] 发布于 2007-08-07 19:13:00

这应该是一道题目,很面熟,见它不下十次
再提醒MatoDied一下,上半三角会有路线穿越下半三角的啊.

9 楼

snoopy7 [专家分：70] 发布于 2007-08-07 19:49:00

Moz大哥哥再帮我想想好吗,
          8 0 9
     -------------
□□)  □□□□
       □□
     -------------
         □□□
         □□□
     -------------
              1
    求出□中的数字，并打印出完整的算式来

10 楼

moz [专家分：37620] 发布于 2007-08-07 23:21:00

不同问题别乱搅,竖式在另一贴Mato给你说,这一贴我就算写出来了,估计也帮不到你什么,把你老师都吓倒了,谁还相信是你写的作业?

我来回复

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

主题：帮帮我用QBasic 求长度为素数的路径个数十万火急

回复列表（共22个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：帮帮我用QBasic 求长度为素数的路径个数 十万火急

回复列表 （共22个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：帮帮我用QBasic 求长度为素数的路径个数十万火急

回复列表（共22个回复）