Re: [問題] 小題目：各點之間的最小連結步數

看板Fortran作者laa7352 (Laa)時間15年前 (2009/11/06 05:39)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串2/6 (看更多)

※ 引述《yin0416 (冷色鉛筆)》之銘言： : 假設有Ｎ個點，每個點相互之間有些有連結，有些沒有連結。 : 給你一個Ｎ乘Ｎ的矩陣，代表每個點相互之間連結的有或無。 : 請算出每個點與點之間的最小連結步數， : 例如點１與點２有連結，點２與點３之間有連結，而點１與點３之間沒有直接連結， : 則點１與點３之間的最小連結步數即為２步。 : 老師並不要求我寫出來，所以我不是為了應付作業而來發問的。 : 這個程式的結構我想了很久，但沒有想出來。無聊亂寫的… 假設有九個點，各點連接的情形如下 1 : 3 5 7 9 2 : 4 6 3 : 1 6 8 4 : 2 5 7 5 : 1 4 6 : 2 3 7 9 7 : 1 4 6 8 : 1 3 9 : 1 6 現在找點2連接到點9的路徑程式如下跑到第二層就有結果 2 6 9 (其實目視就可以看出來了XD) 第三層之後我就懶得寫了整個結構只是一直不斷的代換我想應該會有比較簡單的寫法 integer var,nvar,np,ivar,ip,nstart,nend,link integer ip2,ip3,ip4 integer itemp,itemp2,itemp3 integer ilink character cf*7 parameter(nvar=9,np=5) dimension var(np,nvar),link(np) data var /3,5,7,9,0, !把點連接情形輸入到陣列中 2 4,6,0,0,0, !var(np,nvar)中的np是指共連接了幾個點 3 1,6,8,0,0, !nvar是指共有幾個點 4 2,5,7,0,0, !在陣列中的整數值，代表的是二點之間有連線 5 1,4,0,0,0, !ex：var(3,1)=7,指點1跟點7有連線 6 2,3,7,9,0, ! var(2,3)=6，指點6跟點3有連線 7 1,4,6,0,0, !而0代表的是沒有資料(沒有連線) 8 1,3,0,0,0, 9 1,6,0,0,0/ nstart=2 !開始的點 nend=9 !結束的點 cf='( I2)' c==== !第一層開始 ip=0 11 ip=ip+1 ilink=1 link(1)=nstart if(ip .gt. np)goto 12 itemp=var(ip,nstart) if(itemp .eq. 0)goto 12 if(itemp .eq. nstart)goto 11 if(itemp .eq. nend)then ilink=2 link(ilink)=nend write(cf(2:2),'(I1)')ilink write(*,cf)(link(i),i=1,ilink) goto 11 else c !第二層 print*, itemp ip2=0 21 ip2=ip2+1 ilink=2 link(ilink)=itemp if(ip2 .gt. np)goto 22 itemp2=var(ip2,itemp) if(itemp2 .eq. 0)goto 22 if(itemp2 .eq. nstart)goto 21 if(itemp2 .eq. nend)then ilink=3 link(ilink)=nend write(cf(2:2),'(I1)')ilink write(*,cf)(link(i),i=1,ilink) goto 21 else ! ! !放第三層… ! endif goto 21 22 continue endif c !第二層結束 goto 11 12 continue c==== !第一層結束 stop end -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.145.72