[汇编][算法实战003]约瑟夫问题
据说著名犹太历史学家 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 个位置，于是逃过了这场死亡
游戏。
;约瑟夫问题(一维数组) 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 ,1
.Else
Dec Esi
Mov Byte Ptr ,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 == 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
;约瑟夫问题(单向循环链表) 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 .Next,Eax
Mov .Data,Edx
.UntilCxZ
Mov Ebx,Eax
Inc Edx
Push dwLinkedListHead
Pop .Next ;指向链表结点1
Mov .Data,Edx
;此时Ebx指向尾结点
;开始标记
Mov Edx,dwAll
.While Edx != dwPersist
Mov Ecx,dwJump
.If Ecx != 0
.Repeat
Mov Ebx,.Next
.UntilCxZ
.EndIf
Mov Eax,.Next
Mov Ecx,.Next
Mov .Next,Ecx
Push Edx
Invoke Free,Eax
Pop Edx
Dec Edx
.EndW
;遍历链表并输出
Mov dwCrLfZero,000D0AH
Mov Ecx,Ebx
.Repeat
Pushad
Invoke dw2a,.Data,Offset bBuffer2
Invoke StdOut,Offset bBuffer2
Invoke StdOut,Offset dwCrLfZero
Popad
Mov Ebx,.Next
.Until Ebx == Ecx
Assume Ebx:Nothing
Assume Eax:Nothing
Ret
Main EndP
Start:
Call Main
Invoke ExitProcess,NULL
End Start
End
同时欢迎大家回帖分享自己的代码！ ayaoko 发表于 2019-4-22 16:15
请教一下楼主，汇编如何入门，和好的IDE
https://www.kanxue.com/book-section_list-31.htm
https://github.com/ThomasJaeger/VisualMASM 请教一下楼主，汇编如何入门，和好的IDE 太厉害了我cJAVAPython才都学了一点点阿
页:
[1]