找回密码
 加入
搜索
AUTOIT CN»论坛 › AU3交流 › 『 提问交流 』 › AU3编程解应用题1：输出人际关系网络
返回列表 发新帖
查看: 5355|回复: 9

[效率算法] AU3编程解应用题1：输出人际关系网络

 火 [复制链接]
pusofalse
发表于 2010-5-21 15:18:01 | 显示全部楼层 |阅读模式
本帖最后由 pusofalse 于 2010-5-25 02:01 编辑

某小镇上有n个人（2<=n<=50），他们从0至n-1编号。在小镇中，一些人认识另一些人，这种认识关系是单向的（即，如果a认识b和c，那么b和c必然不认识a；如果c不认识d和e，那么d和e可能认识c，也可能不认识c）。
题1，编程输出这种人际网络。

前提条件如上。另外，小镇上有一个名人，当且仅当所有人都认识他，而除他自己之外的n-1个人，他都不认识。而你只能用诸如“a是否认识b？”、“d是否认识a？”的询问，判断出谁是名人。
题2，用不超过100次的询问找出这个名人的编号。

题目要求：
尽量不生成任何临时文件，代码简洁并高效。
可以用Random函数赋一个随机编号给名人，但不能直接输出这个随机值。

题1不受题2干扰。
人际关系, 输出, 网络, 应用

相关帖子
回复

举报

Au3代码高亮发贴标签： [AU3] 你的代码 [/AU3]                   支持论坛的发展，请添加此》》网址导航《《为您的主页          
lanfengc
发表于 2010-5-21 17:28:21 | 显示全部楼层
本帖最后由 lanfengc 于 2010-5-21 19:47 编辑

计算机自动遍历查找50个人的村庄需要查询2500次。 如果你自己输入，查询50次。
;~ 分析。N个人，N>=2,N<=50    N=随即数(2,50,1)
;~ 人编号从1-N.即:MAN1,MAN2,MAN3,....,MANN
;~ 如果MAN1-->MAN2,MAN1-->MAN3, 则,MAN2--/>MAN1,MAN3--/>MAN1.
;~ 如果MAN1--/>MAN2,MAN1--/>MAN3,则,MAN2-->MAN1,MAN3-->MAN1 或 MAN2--/>MAN1,MAN3--/>MAN1

;~ MAN1~MANN--->MANMAX,  MANMAX-->MANMAX 
#include <array.au3>
Global $N=50   ;总人数
Global $XB[$N]   ;数字列表,随机出一个之后自动从该数组中删除该元素.
Global $ManNum[$N]   ;人名编号
Global $MapString=""   ;关系影射表
Local  $count=0   ;记录查询的次数
Global $RandEnd=$N-1
For $i=0 To $N-1 Step 1   ;数字列表赋值
        $XB[$i]=$i+1
Next
For $i=0 To $N-1 Step 1   ;给所有人随机编号.
        Local $j=0
        $j=Random(0,$RandEnd,1)   ;随机一个数
        $RandEnd-=1  ;随即数的最大值减一,因为数组中已经剔除了一个元素.
        $ManNum[$i]="Man"&$XB[$j]  ;从数字列表中取出随机到的元素并将其赋给人名编号数组.
        For $m=$j To $N-2 Step 1   ;从随机的元素开始,将后面的所有元素向前移位,达到剔除随机到的元素的目的.
                $XB[$m]=$XB[$m+1]
        Next        
Next
For $i=0 To $N-1 Step 1  ;生成关系影射表.
        For $j=$i To $N-1 Step 1
                ;个人认为,要是名人只需要所有人认识他就可以了.由于认识关系是单方向的,别人认识他,他肯定不认识别人.
                ;他自己如果不认识自己就是白痴了.
                ;条件影射表生成:如果MAN1-->MAN2,MAN1-->MAN3, 则,MAN2--/>MAN1,MAN3--/>MAN1. 
                If $i<>$j Then $MapString&=$ManNum[$i]&"--/>"&$ManNum[$j]&$ManNum[$j]&"-->"&$ManNum[$i]&"|"
        Next
Next
;输入你想查询的人的编号.
$supman=InputBox("输入人名编号","只需要输入数字就可以.","","",200,80)
FindSupperMan($supman,False)
Func FindSupperMan($num,$flg)
        For $k=0 To $N-1 Step 1  ;从关系影射表中查找必要的关系,别人认识他 他不认识别人.
                $tempstr="Man"&$num&"--/>"&$ManNum[$k]&$ManNum[$k]&"-->"&"Man"&$num
                If StringInStr($MapString,$tempstr) Then
                        $count+=1        ;如果查找到了,则查到次数加1.
                EndIf
        Next
        ;如果查到次数等于小镇人数减去他自己,那么就证明所有人都认识他, 他就是名人. 否则不是.
        ;由于本程序的限制,名人就是数组$ManNum[1].  只需要输入数组第一个元素的人名编号就可以了。
        If $flg=False Then
                If $count=$N-1 Then
                        MsgBox(0,"提示","你输入的Man"&$num&" 是名人")
                Else
                        MsgBox(0,"提示","你输入的Man"&$num&" 不是名人!")
                EndIf
        ElseIf $flg=True Then
                If $count=$N-1 Then
                        MsgBox(0,"提示","计算机自动查找到名人为:Man"&$num)
                EndIf
        EndIf                
EndFunc
;然后计算机自动查找名人.
For $i=1 To $N Step 1
        $count=0
        FindSupperMan($i,True)
                       If $count=$N-1 Then ExitLoop
Next
_ArrayDisplay($ManNum,"人名列表信息")

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？加入

×
回复

举报

小凯
发表于 2010-5-21 18:00:33 | 显示全部楼层
脑壳晕了,,,,夜深的时候再认真看看!
回复

举报

C.L
发表于 2010-5-22 03:16:42 | 显示全部楼层
题1：
$t = TimerInit ()
Dim $max = 50,$aRals [$max][2]

For $i=0 To $max-1
        $aRals[$i][0] = $i
        $knownum = Random(0,$max-1,1);随机生成认识的人数范围
        $knowman = -1
        For $j=1 To $knownum
                $knowman = Int(Random($knowman+1,$max))
                If $aRals[$i][0] <> $knowman Then                
                        If StringInStr ($aRals[$knowman][0],$aRals[$i][1]) Then ContinueLoop
                        $aRals[$i][1] &= $knowman&" "
                Else
                        $aRals[$i][1] = ""
                EndIf
                If $knowman >= $max-10 Then ExitLoop
        Next
Next

$result = ""
For $i=0 To 49
        $know = $aRals[$i][1]
        If $know == "" Then
                $result &= $aRals[$i][0]&@TAB&"一个人都不认识"& @CRLF 
        Else
                $result &= $aRals[$i][0]&@TAB&"认识"&@TAB&$know& @CRLF 
        EndIf
Next
MsgBox (0,"人际网络  用时"&TimerDiff ($t),$result)

评分

参与人数 1金钱 +30 收起 理由
pusofalse + 30 学习了。

查看全部评分

回复

举报

C.L
发表于 2010-5-22 03:44:12 | 显示全部楼层
题2：
$t = TimerInit ()
Dim $max = 50,$aRals [$max][2]
Dim $mingren = Random(0,$max-1,1)

For $i=0 To $max-1
        $aRals[$i][0] = $i
        If $i == $mingren Then ContinueLoop
        $knownum = Random(0,$max-1,1);随机生成认识的人数范围
        $knowman = -1
        $aRals[$i][1] = $mingren & "  "
        For $j=1 To $knownum
                $knowman = Int(Random($knowman+1,$max))
                If $aRals[$i][0] <> $knowman Then                
                        If StringInStr ($aRals[$knowman][0],$aRals[$i][1]) Then ContinueLoop
                        If $knowman == $mingren Then ContinueLoop
                        $aRals[$i][1] &= $knowman&" "
                Else
                        $aRals[$i][1] &= ""
                EndIf
                If $knowman >= $max-10 Then ExitLoop
        Next
Next

$result = ""
For $i=0 To 49
        $know = $aRals[$i][1]
        If $know == "" Then
                $result = $i
                ExitLoop
        EndIf
Next
MsgBox (0,"名人号码  用时"&TimerDiff ($t),"随机生成的名人是："&$mingren & @CRLF &"查找出的名人是："&$result)

评分

参与人数 1金钱 +30 收起 理由
pusofalse + 30 学习了。

查看全部评分

回复

举报

lanfengc
发表于 2010-5-22 22:07:53 | 显示全部楼层
论坛出错了？？？  我发的优化算法后的代码呢？？？
幸好我保存了。 再发一次。
;~ 分析。N个人，N>=2,N<=50    N=随即数(2,50,1)
;~ 人编号从1-N.即:MAN1,MAN2,MAN3,....,MANN
;~ 如果MAN1-->MAN2,MAN1-->MAN3, 则,MAN2--/>MAN1,MAN3--/>MAN1.
;~ 如果MAN1--/>MAN2,MAN1--/>MAN3,则,MAN2-->MAN1,MAN3-->MAN1 或 MAN2--/>MAN1,MAN3--/>MAN1

;~ MAN1~MANN--->MANMAX,  MANMAX-->MANMAX 
#include <array.au3>
Global $N=50   ;总人数
Global $XB[$N]   ;数字列表,随机出一个之后自动从该数组中删除该元素.
Global $ManNum[$N]   ;人名编号
Global $MapString=""   ;关系影射表
Local  $count=0   ;记录查询的次数
Global $RandEnd=$N-1
For $i=0 To $N-1 Step 1   ;数字列表赋值
        $XB[$i]=$i+1
Next
For $i=0 To $N-1 Step 1   ;给所有人随机编号.
        Local $j=0
        $j=Random(0,$RandEnd,1)   ;随机一个数
        $RandEnd-=1  ;随即数的最大值减一,因为数组中已经剔除了一个元素.
        $ManNum[$i]="Man"&$XB[$j]  ;从数字列表中取出随机到的元素并将其赋给人名编号数组.
        For $m=$j To $N-2 Step 1   ;从随机的元素开始,将后面的所有元素向前移位,达到剔除随机到的元素的目的.
                $XB[$m]=$XB[$m+1]
        Next        
Next
For $i=0 To $N-1 Step 1  ;生成关系影射表.
        For $j=$i To $N-1 Step 1
                ;个人认为,要是名人只需要所有人认识他就可以了.由于认识关系是单方向的,别人认识他,他肯定不认识别人.
                ;他自己如果不认识自己就是白痴了.
                ;条件影射表生成:如果MAN1-->MAN2,MAN1-->MAN3, 则,MAN2--/>MAN1,MAN3--/>MAN1. 
                If $i<>$j Then $MapString&=$ManNum[$i]&"--/>"&$ManNum[$j]&$ManNum[$j]&"-->"&$ManNum[$i]&"|"
        Next
Next
;输入你想查询的人的编号.
$supman=InputBox("输入人名编号","只需要输入数字就可以.","","",200,80)
$Start=TimerInit()
FindSupperMan($supman,False)
Func FindSupperMan($num,$flg)
        For $k=0 To $N-1 Step 1  ;从关系影射表中查找必要的关系,别人认识他 他不认识别人.
                $tempstr="Man"&$num&"--/>"&$ManNum[$k]&$ManNum[$k]&"-->"&"Man"&$num
                If StringInStr($MapString,$tempstr) Then
                        $count+=1        ;如果查找到了,则查到次数加1.
                EndIf
                If StringInStr($MapString,"Man"&$num&"-->"&$ManNum[$k]) Then ExitLoop
        Next
        ;如果查到次数等于小镇人数减去他自己,那么就证明所有人都认识他, 他就是名人. 否则不是.
        ;由于本程序的限制,名人就是数组$ManNum[1].  只需要输入数组第一个元素的人名编号就可以了。
        If $flg=False Then
                If $count=$N-1 Then
                        MsgBox(0,"提示--耗时:"&TimerDiff($Start),"你输入的Man"&$num&" 是名人")
                Else
                        MsgBox(0,"提示--耗时:"&TimerDiff($Start),"你输入的Man"&$num&" 不是名人!")
                EndIf
        ElseIf $flg=True Then
                If $count=$N-1 Then
                        MsgBox(0,"提示--耗时:"&TimerDiff($Start),"计算机自动查找到名人为:Man"&$num)
                EndIf
        EndIf                
EndFunc
;然后计算机自动查找名人.
$Start=TimerInit()
For $i=1 To $N Step 1
        $count=0
        FindSupperMan($i,True)
        If $count=$N-1 Then ExitLoop
Next
_ArrayDisplay($ManNum,"人名列表信息")

评分

参与人数 1金钱 +30 收起 理由
pusofalse + 30 学习了。

查看全部评分

回复

举报

C.L
发表于 2010-5-23 20:29:37 | 显示全部楼层
P版的代码什么时候贴上来？贴上来学习一下思路啊。
回复

举报

pusofalse
 楼主| 发表于 2010-5-23 20:35:00 | 显示全部楼层
本帖最后由 pusofalse 于 2010-5-23 20:37 编辑

抱歉啊，这两天在忙些其他的事情，没及时上来看。
这是我的解：
Q1:
#include <Array.au3>

Local $iTimer = TimerInit(), $iMaxNumber = Random(2, 50, 1)
Local $aRelation[$iMaxNumber][$iMaxNumber]

For $i = 0 To $iMaxNumber - 1
        For $j = 0 To $iMaxNumber - 1
                If ($i <> $j) Then
                        If ($aRelation[$j][$i]) Then
                                $aRelation[$i][$j] = 0
                        Else
                                $aRelation[$i][$j] = Random(0, 1, 1)
                        EndIf
                EndIf
        Next
Next

_Arraydisplay($aRelation, TimerDiff($iTimer))
用0表示不认识，1表示认识，人际关系呈现在一个矩阵中。

Q2:
#include <Array.au3>

Local $iTimer = TimerInit()
Local $iMaxNumber = Random(2, 50, 1)
Local $aRelation[$iMaxNumber][$iMaxNumber]
Local $iFamous = Random(0, $iMaxNumber - 1, 1), $iFamousSearched = 0


For $i = 0 To $iMaxNumber - 1
        For $j = 0 To $iMaxNumber - 1
                If ($i <> $j) Then
                        If ($aRelation[$j][$i]) Then
                                $aRelation[$i][$j] = 0
                        Else
                                $aRelation[$i][$j] = Random(0, 1, 1)
                        EndIf
                EndIf
        Next
Next

For $i = 0 To $iMaxNumber - 1
        If ($i <> $iFamous) Then
                $aRelation[$iFamous][$i] = 0
                $aRelation[$i][$iFamous] = 1
        EndIf
Next

For $i = 0 To $iMaxNumber - 1
        If ($aRelation[$iFamousSearched][$i]) Then $iFamousSearched = $i
Next

_Arraydisplay($aRelation, $iFamous & " " & $iFamousSearched)
_Arraydisplay的标题中，$iFamous表示随机生成的名人编号，$iFamousSearched表示通过询问获取的名人编号。

评分

参与人数 1金钱 +30 收起 理由
C.L + 30 学习了，关系的处理部份很精彩。

查看全部评分

回复

举报

C.L
发表于 2010-5-23 21:15:49 | 显示全部楼层
回复 8# pusofalse

代码很精彩，用矩阵来处理关系，学习了。
回复

举报

yejier
发表于 2010-5-26 20:45:44 | 显示全部楼层
顶贴、回帖、拿分、走人！url
回复

举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 加入

本版积分规则

QQ|手机版|小黑屋|AUTOIT CN ( 鲁ICP备19019924号-1 )谷歌 百度

GMT+8, 2024-5-15 12:17 , Processed in 0.083787 second(s), 23 queries .

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

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