好友
阅读权限10
听众
最后登录1970-1-1
|
老刘
发表于 2019-4-22 15:23
据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占
领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，
39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方
式：41 个人围成一个圆圈，由第 1 个人开始报数，报数到第 3 个人，
该人就必须自杀，然后再由下一个重新报数，报数到的第 3 个人，该
人又自杀...直到所有人都自杀身亡为止，然而 Josephus 和他的朋友
并不想遵从。
一开始有 i 个人，数 j 去 1，最后剩余 k 个人。首先从一个人开
始，越过 j-1 个人，并杀掉第 j 个人；接着再越过 j-1 个人，并杀掉
第 j 个人...这个过程沿着圆圈一直进行，直到最终只剩下 k 个人，这
k 个人就可以继续活着。问题是，给定了 i、j、k 值，一开始要站在
什么地方才能避免被处决？聪明的Josephus要他的朋友先假装遵从，
他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡
游戏。
[Asm] 纯文本查看 复制代码 ;约瑟夫问题(一维数组) Algo
;Code By 老刘
;环境：MASM32 SDK
;编译指令：ml /coff 约瑟夫问题(一维数组).asm /link /subsystem:console
;参数：总人数、保留人数、每n个人杀一次的n（小于总人数）。
;参数最大值：999999。
;参考：MHL批处理标准教程之约瑟夫问题。
Include masm32rt.inc
Main Proto
.Data?
bBuffer DB 999999 Dup (?)
dwAll DD ?
dwPersist DD ?
bBuffer2 DB 11 Dup (?)
dwCrLfZero DD ?
dwJumpPlusOne DD ?
;End Data?
.Code
Main Proc
;获得参数
Invoke ArgClC,1,Offset bBuffer2
Sub Esp,4
Invoke atodw_ex,Offset bBuffer2
Add Esp,4
Mov dwAll,Eax
Invoke ArgClC,2,Offset bBuffer2
Sub Esp,4
Invoke atodw_ex,Offset bBuffer2
Add Esp,4
Mov dwPersist,Eax
Invoke ArgClC,3,Offset bBuffer2
Sub Esp,4
Invoke atodw_ex,Offset bBuffer2
Add Esp,4
Mov dwJumpPlusOne,Eax
;开始标记
Lea Ebx,bBuffer
Add Ebx,dwAll
Mov Edx,dwAll
Lea Esi,bBuffer
Mov Edi,Esi
Xor Eax,Eax
.While Edx != dwPersist
Mov Ecx,dwJumpPlusOne
.Repeat
LodSB
Add Ecx,Eax
.If Esi == Ebx
Mov Esi,Edi
.EndIf
.UntilCxZ
.If Esi == Edi
Mov Byte Ptr [Ebx-1],1
.Else
Dec Esi
Mov Byte Ptr [Esi],1
Inc Esi
.EndIf
Dec Edx
.EndW
;输出
Mov dwCrLfZero,000D0AH
Xor Ecx,Ecx
Lea Esi,bBuffer
Dec Esi
.While Ecx != dwAll
Inc Ecx
.If Byte Ptr [Esi+Ecx] == 0
Pushad
Invoke dw2a,Ecx,Offset bBuffer2
Invoke StdOut,Offset bBuffer2
Invoke StdOut,Offset dwCrLfZero
Popad
.EndIf
.EndW
Ret
Main EndP
Start:
Call Main
Invoke ExitProcess,NULL
End Start
End
[Asm] 纯文本查看 复制代码 ;约瑟夫问题(单向循环链表) Algo
;Code By 老刘
;环境：MASM32 SDK
;编译指令：ml /coff 约瑟夫问题(单向循环链表).asm /link /subsystem:console
;参数：总人数、保留人数、每n个人杀一次的n（小于总人数）。
;参数最大值：1227。
;参考：MHL批处理标准教程之约瑟夫问题。
Include masm32rt.inc
Main Proto
OneWayLinkedList Struct
Data DWord ?
Next DWord ?
OneWayLinkedList EndS
.Data?
dwAll DD ?
dwPersist DD ?
dwJump DD ?
bBuffer2 DB 11 Dup (?)
dwCrLfZero DD ?
dwLinkedListHead DD ?
;End Data?
.Code
Main Proc
;获得并处理参数
Invoke ArgClC,1,Offset bBuffer2
Sub Esp,4
Invoke atodw_ex,Offset bBuffer2
Add Esp,4
Mov dwAll,Eax
Invoke ArgClC,2,Offset bBuffer2
Sub Esp,4
Invoke atodw_ex,Offset bBuffer2
Add Esp,4
Mov dwPersist,Eax
Invoke ArgClC,3,Offset bBuffer2
Sub Esp,4
Invoke atodw_ex,Offset bBuffer2
Add Esp,4
Dec Eax
Mov dwJump,Eax
;创建链表
Assume Ebx:Ptr OneWayLinkedList
Assume Eax:Ptr OneWayLinkedList
Invoke Alloc,SizeOf OneWayLinkedList
Mov dwLinkedListHead,Eax
Mov Ecx,dwAll
Dec Ecx
Xor Edx,Edx
.Repeat
Mov Ebx,Eax
Inc Edx
Push Ecx
Push Edx
Invoke Alloc,SizeOf OneWayLinkedList
Pop Edx
Pop Ecx
Mov [Ebx].Next,Eax
Mov [Ebx].Data,Edx
.UntilCxZ
Mov Ebx,Eax
Inc Edx
Push dwLinkedListHead
Pop [Ebx].Next ;指向链表结点1
Mov [Ebx].Data,Edx
;此时Ebx指向尾结点
;开始标记
Mov Edx,dwAll
.While Edx != dwPersist
Mov Ecx,dwJump
.If Ecx != 0
.Repeat
Mov Ebx,[Ebx].Next
.UntilCxZ
.EndIf
Mov Eax,[Ebx].Next
Mov Ecx,[Eax].Next
Mov [Ebx].Next,Ecx
Push Edx
Invoke Free,Eax
Pop Edx
Dec Edx
.EndW
;遍历链表并输出
Mov dwCrLfZero,000D0AH
Mov Ecx,Ebx
.Repeat
Pushad
Invoke dw2a,[Ebx].Data,Offset bBuffer2
Invoke StdOut,Offset bBuffer2
Invoke StdOut,Offset dwCrLfZero
Popad
Mov Ebx,[Ebx].Next
.Until Ebx == Ecx
Assume Ebx:Nothing
Assume Eax:Nothing
Ret
Main EndP
Start:
Call Main
Invoke ExitProcess,NULL
End Start
End
同时欢迎大家回帖分享自己的代码！ |
免费评分
-
查看全部评分
|
|
发表于 2019-4-22 16:52
