[汇编][算法实战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 个位置，于是逃过了这场死亡
游戏。

[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

同时欢迎大家回帖分享自己的代码！

老刘

ayaoko 发表于 2019-4-22 16:15
请教一下楼主，汇编如何入门，和好的IDE

https://www.kanxue.com/book-section_list-31.htm
https://github.com/ThomasJaeger/VisualMASM

ayaoko

请教一下楼主，汇编如何入门，和好的IDE

LeiSir

太厉害了我cJAVAPython才都学了一点点阿