论坛 › 『 提问交流 』 › AU3编程解应用题1：输出人际关系网络

pusofalse 发表于 2010-5-21 15:18:01

AU3编程解应用题1：输出人际关系网络

本帖最后由 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干扰。

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.只需要输入数组第一个元素的人名编号就可以了。
        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]

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

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

C.L 发表于 2010-5-22 03:44:12

题2：
$t = TimerInit ()
Dim $max = 50,$aRals [$max]
Dim $mingren = Random(0,$max-1,1)

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

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

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.只需要输入数组第一个元素的人名编号就可以了。
        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,"人名列表信息")

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表示通过询问获取的名人编号。

C.L 发表于 2010-5-23 21:15:49

回复 8# pusofalse

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

yejier 发表于 2010-5-26 20:45:44

顶贴、回帖、拿分、走人！url

查看完整版本: AU3编程解应用题1：输出人际关系网络