Fortran Coder

查看: 14721|回复: 11

[通用算法] 计算二维数组坐标“岛”的重心问题

[复制链接]

17

帖子

4

主题

0

精华

入门

F 币
80 元
贡献
50 点
发表于 2014-3-6 13:34:37 | 显示全部楼层 |阅读模式
我刚接触fortran没多久,现在要写一个程序来算出下面这个数组的重心
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

我想把这个数组其中所有的1的值用坐标表示出来,比如(14,15)这样子,但是我不太清楚该怎么筛选和表示,求大神指点

709

帖子

4

主题

0

精华

大师

农村外出务工人员

F 币
596 元
贡献
305 点

新人勋章爱心勋章水王勋章元老勋章热心勋章

发表于 2014-3-6 13:37:33 | 显示全部楼层
[Fortran] 纯文本查看 复制代码
Do i = 1 , n
  Do j = 1 , m
    if ( a(i,j) == 1 ) then
      !此时的 i j 即为坐标
    end if
  End Do
End Do

17

帖子

4

主题

0

精华

入门

F 币
80 元
贡献
50 点
 楼主| 发表于 2014-3-6 13:43:38 | 显示全部楼层
chuxf 发表于 2014-3-6 13:37
[mw_shl_code=fortran,true]Do i = 1 , n
  Do j = 1 , m
    if ( a(i,j) == 1 ) then

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0
如果是这样的,我想用程序判断上面的那些1把他们-20变到下面来该怎么做呢?

709

帖子

4

主题

0

精华

大师

农村外出务工人员

F 币
596 元
贡献
305 点

新人勋章爱心勋章水王勋章元老勋章热心勋章

发表于 2014-3-6 13:45:19 | 显示全部楼层
什么叫 把他们 -20 变到下面来?

17

帖子

4

主题

0

精华

入门

F 币
80 元
贡献
50 点
 楼主| 发表于 2014-3-6 13:55:14 | 显示全部楼层
chuxf 发表于 2014-3-6 13:45
什么叫 把他们 -20 变到下面来?

如果把所有的1看成一个岛,我想算这个岛重心,我想把所有的1的坐标全部相加最后除以25就是这个岛的重心,但是这是一个周期性的岛,就像第二组数组,有一部分1在上面,比如(5,20),但实际这个1是该在(5,0)这个坐标上,但是因为下面无法表示了所以这个1就被加了20跑到上面去了,但在计算重心的时候需要把这个1减掉20,就是从(5,20)变到(5,0)来计算重心

709

帖子

4

主题

0

精华

大师

农村外出务工人员

F 币
596 元
贡献
305 点

新人勋章爱心勋章水王勋章元老勋章热心勋章

发表于 2014-3-6 14:07:32 | 显示全部楼层
本帖最后由 chuxf 于 2014-3-6 14:15 编辑

这个问题可以很简单,也可以很复杂。

这取决于:
第一:整个区域内,你是否可以确定只存在一个“岛”?还是有可能有多个?
比如:
00000000000001111111100000000000
00000000000000011110000000000000
00000000000000000000000000000000
00000000110000000000000000000000
00000001111000000000000000000000
00000000000000000000000000000000
第二:岛会不会出现无限循环。
比如:
00000000000001111000000000000000
00000000000001111000000000000000
00000000001111111000000000000000
00000000000001111000000000000000
第三:岛中间是否可能出现空洞?
比如:
00000000000000000000000000000000
00000000000001111000000000000000
00000000000001111000000000000000
00000000001111001000000000000000
00000000000001111000000000000000
00000000000000000000000000000000

17

帖子

4

主题

0

精华

入门

F 币
80 元
贡献
50 点
 楼主| 发表于 2014-3-6 14:26:03 | 显示全部楼层
chuxf 发表于 2014-3-6 14:07
这个问题可以很简单,也可以很复杂。

这取决于:

只有一个岛,就是加了周期或者减了周期后就只有一个岛了,不会有2个,岛中间没有空洞,无限循环那个不太懂。

709

帖子

4

主题

0

精华

大师

农村外出务工人员

F 币
596 元
贡献
305 点

新人勋章爱心勋章水王勋章元老勋章热心勋章

发表于 2014-3-6 15:24:54 | 显示全部楼层
本帖最后由 chuxf 于 2014-3-6 19:22 编辑

我这里有个死办法,那就是如果有上下左右的联通,则移动整个区域,直到不再联通为止。(记录下 X Y 的偏移量)
最后算出重心,再把偏移量加回去。

[Fortran] 纯文本查看 复制代码
Program www_fcode_cn
  Implicit None
  Integer , parameter :: N = 4
  Integer , parameter :: M = 4
  real :: gx , gy
  Integer :: a( M , N )
  Open( 12 , File = '文件名' )
  Read( 12 , * ) a
  Close( 12 )
  call IslandGravity( a , N , M , gx , gy )
  write(*,*) gx , gy
 
contains

  Subroutine IslandGravity( d , n , m , gx , gy )
    Integer :: n , m
    Integer :: d( m , n ) , a( m , n )
    integer :: i , j , c , iShiftX , iShiftY
    Real :: gx , gy
    Logical :: blink
    a = d !// 复制一份 a

    iShiftX = 0
    iShiftY = 0
    Do  !// 向上滚动,直到没有上下链接为止
      blink = Check_Y_Link( a , n , m )
      if ( blink ) then
        call RollUp( a , n , m )
        iShiftY = iShiftY + 1
      else
        Exit
      end if
    End Do
    Do  !// 向左滚动,直到没有左右链接为止
      blink = Check_X_Link( a , n , m )
      if ( blink ) then
        call RollLeft( a , n , m )
        iShiftX = iShiftX + 1
      else
        Exit
      end if
    End Do
    gx = 0.
    gy = 0.
    c = 0
    Do i = 1 , N
      Do j = 1 , M
        if ( a(j,i) == 1 ) then
          gx = gx + j
          gy = gy + i
          c = c + 1
        end if
      End Do
    End Do
    gx = ( gx / c ) + iShiftX !// 最后再把偏移量加上去
    if ( gx > m ) gx = gx - m
    gy = ( gy / c ) + iShiftY
    if ( gy > n ) gy = gy - n
  End Subroutine IslandGravity
  
  Subroutine RollUp( a , n , m ) !// 区域向上滚动
    Integer :: n , m
    Integer :: a( m , n ) , t( m )
    t(:) = a( : , 1 )
    a(:,1:n-1) = a(:,2:n)
    a(:,n) = t(:)
  End Subroutine RollUp
  
  Subroutine RollLeft( a , n , m ) !// 区域向左滚动
    Integer :: n , m
    Integer :: a( m , n ) , t( n )
    t(:) = a( 1 , : )
    a(1:m-1,:) = a(2:m,:)
    a(m,:) = t(:)
  End Subroutine RollLeft
  
  Logical Function Check_Y_Link( a , n , m ) !// 检查是否有上下链接
    Integer :: n , m
    Integer :: a( m , n )
    integer :: i
    Check_Y_Link = .false.
    Do i = 1 , m
      if ( ( a(i,1) == 1 ) .and. ( a(i,n) == 1 ) ) then
        Check_Y_Link = .true.
        return
      end if
    End Do
  End Function Check_Y_Link
  
  Logical Function Check_X_Link( a , n , m ) !// 检查是否有左右链接
    Integer :: n , m
    Integer :: a( m , n )
    integer :: i
    Check_X_Link = .false.
    Do i = 1 , n
      if ( ( a(1,i) == 1 ) .and. ( a(m,i) == 1 ) ) then
        Check_X_Link = .true.
        return
      end if
    End Do
  End Function Check_X_Link
  
End Program www_fcode_cn  

3

帖子

1

主题

0

精华

新人

F 币
27 元
贡献
13 点
发表于 2014-3-6 19:01:55 | 显示全部楼层
不清楚这里重心的意义为何,感觉有一点点问题:
例如:
1101
1101
0000
1101
重心按个人理解应该是1即坐标(1,1),算出来的结果应该是(5,5),超出了范围。

709

帖子

4

主题

0

精华

大师

农村外出务工人员

F 币
596 元
贡献
305 点

新人勋章爱心勋章水王勋章元老勋章热心勋章

发表于 2014-3-6 19:23:39 | 显示全部楼层
joejimming 发表于 2014-3-6 19:01
不清楚这里重心的意义为何,感觉有一点点问题:
例如:
1101

感谢楼上指正。

已增加两行代码解决这一问题

[Fortran] 纯文本查看 复制代码
 gx = ( gx / c ) + iShiftX !// 最后再把偏移量加上去
 if ( gx > m ) gx = gx - m
 gy = ( gy / c ) + iShiftY
  if ( gy > n ) gy = gy - n
您需要登录后才可以回帖 登录 | 极速注册

本版积分规则

捐赠本站|Archiver|关于我们 About Us|小黑屋|Fcode ( 京ICP备18005632-2号 )

GMT+8, 2024-3-29 19:22

Powered by Tencent X3.4

© 2013-2024 Tencent

快速回复 返回顶部 返回列表