不限语言解决“约瑟夫问题”

老刘1号

其实是个老算法题了，今天看到群里有人提起，就来发个帖子，

据说著名犹太历史学家 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 个位置，于是逃过了这场死亡
游戏。

汇编-一维数组版

1. ;约瑟夫问题(一维数组) Algo
   
2. ;Code By 老刘
   
3. ;环境：MASM32 SDK
   
4. ;编译指令：ml /coff 约瑟夫问题(一维数组).asm /link /subsystem:console
   
5. ;参数：总人数、保留人数、每n个人杀一次的n（小于总人数）。
   
6. ;参数最大值：999999。
   
7. ;参考：MHL批处理标准教程之约瑟夫问题。
   
8. 
   
9. 
   
10. Include masm32rt.inc
    
11. Main Proto
    
12. 
    
13. .Data?
    
14.         bBuffer DB 999999 Dup (?)
    
15.         dwAll DD ?
    
16.         dwPersist DD ?
    
17.         bBuffer2 DB 11 Dup (?)
    
18.         dwCrLfZero DD ?
    
19.         dwJumpPlusOne DD ?
    
20. ;End Data?
    
21. 
    
22. .Code
    
23.         Main Proc
    
24.                 ;获得参数
    
25.                 Invoke ArgClC,1,Offset bBuffer2
    
26.                 Sub Esp,4
    
27.                 Invoke atodw_ex,Offset bBuffer2
    
28.                 Add Esp,4
    
29.                 Mov dwAll,Eax
    
30.                 Invoke ArgClC,2,Offset bBuffer2
    
31.                 Sub Esp,4
    
32.                 Invoke atodw_ex,Offset bBuffer2
    
33.                 Add Esp,4
    
34.                 Mov dwPersist,Eax
    
35.                 Invoke ArgClC,3,Offset bBuffer2
    
36.                 Sub Esp,4
    
37.                 Invoke atodw_ex,Offset bBuffer2
    
38.                 Add Esp,4
    
39.                 Mov dwJumpPlusOne,Eax
    
40.                
    
41.                 ;开始标记
    
42.                 Lea Ebx,bBuffer
    
43.                 Add Ebx,dwAll
    
44.                 Mov Edx,dwAll
    
45.                 Lea Esi,bBuffer
    
46.                 Mov Edi,Esi
    
47.                 Xor Eax,Eax
    
48.                 .While Edx != dwPersist
    
49.                         Mov Ecx,dwJumpPlusOne
    
50.                         .Repeat
    
51.                                 LodSB
    
52.                                 Add Ecx,Eax
    
53.                                 .If Esi == Ebx
    
54.                                         Mov Esi,Edi
    
55.                                 .EndIf
    
56.                         .UntilCxZ
    
57.                         .If Esi == Edi
    
58.                                 Mov Byte Ptr [Ebx-1],1
    
59.                         .Else
    
60.                                 Dec Esi
    
61.                                 Mov Byte Ptr [Esi],1
    
62.                                 Inc Esi
    
63.                         .EndIf
    
64.                         Dec Edx
    
65.                 .EndW
    
66.                
    
67.                 ;输出
    
68.                 Mov dwCrLfZero,000D0AH
    
69.                 Xor Ecx,Ecx
    
70.                 Lea Esi,bBuffer
    
71.                 Dec Esi
    
72.                 .While Ecx != dwAll
    
73.                         Inc Ecx
    
74.                         .If Byte Ptr [Esi+Ecx] == 0
    
75.                                 Pushad
    
76.                                 Invoke dw2a,Ecx,Offset bBuffer2
    
77.                                 Invoke StdOut,Offset bBuffer2
    
78.                                 Invoke StdOut,Offset dwCrLfZero
    
79.                                 Popad
    
80.                         .EndIf
    
81.                 .EndW
    
82.                
    
83.                 Ret
    
84.         Main EndP
    
85.        
    
86.         Start:
    
87.                 Call Main
    
88.                 Invoke ExitProcess,NULL
    
89.         End Start
    
90. End

复制代码

汇编-单向循环链表版

1. ;约瑟夫问题(单向循环链表) Algo
   
2. ;Code By 老刘
   
3. ;环境：MASM32 SDK
   
4. ;编译指令：ml /coff 约瑟夫问题(单向循环链表).asm /link /subsystem:console
   
5. ;参数：总人数、保留人数、每n个人杀一次的n（小于总人数）。
   
6. ;参数最大值：1227。
   
7. ;参考：MHL批处理标准教程之约瑟夫问题。
   
8. 
   
9. 
   
10. Include masm32rt.inc
    
11. Main Proto
    
12. 
    
13. OneWayLinkedList Struct
    
14.         Data DWord ?
    
15.         Next DWord ?
    
16. OneWayLinkedList EndS
    
17. 
    
18. .Data?
    
19.         dwAll DD ?
    
20.         dwPersist DD ?
    
21.         dwJump DD ?
    
22.         bBuffer2 DB 11 Dup (?)
    
23.         dwCrLfZero DD ?
    
24.         dwLinkedListHead DD ?
    
25. ;End Data?
    
26. 
    
27. .Code
    
28.         Main Proc
    
29.                 ;获得并处理参数
    
30.                 Invoke ArgClC,1,Offset bBuffer2
    
31.                 Sub Esp,4
    
32.                 Invoke atodw_ex,Offset bBuffer2
    
33.                 Add Esp,4
    
34.                 Mov dwAll,Eax
    
35.                 Invoke ArgClC,2,Offset bBuffer2
    
36.                 Sub Esp,4
    
37.                 Invoke atodw_ex,Offset bBuffer2
    
38.                 Add Esp,4
    
39.                 Mov dwPersist,Eax
    
40.                 Invoke ArgClC,3,Offset bBuffer2
    
41.                 Sub Esp,4
    
42.                 Invoke atodw_ex,Offset bBuffer2
    
43.                 Add Esp,4
    
44.                 Dec Eax
    
45.                 Mov dwJump,Eax
    
46.                
    
47.                 ;创建链表
    
48.                 Assume Ebx:Ptr OneWayLinkedList
    
49.                 Assume Eax:Ptr OneWayLinkedList
    
50.                 Invoke Alloc,SizeOf OneWayLinkedList
    
51.                 Mov dwLinkedListHead,Eax
    
52.                 Mov Ecx,dwAll
    
53.                 Dec Ecx
    
54.                 Xor Edx,Edx
    
55.                 .Repeat
    
56.                         Mov Ebx,Eax
    
57.                         Inc Edx
    
58.                         Push Ecx
    
59.                         Push Edx
    
60.                         Invoke Alloc,SizeOf OneWayLinkedList
    
61.                         Pop Edx
    
62.                         Pop Ecx
    
63.                         Mov [Ebx].Next,Eax
    
64.                         Mov [Ebx].Data,Edx
    
65.                 .UntilCxZ
    
66.                 Mov Ebx,Eax
    
67.                 Inc Edx
    
68.                 Push dwLinkedListHead
    
69.                 Pop [Ebx].Next        ;指向链表结点1
    
70.                 Mov [Ebx].Data,Edx
    
71.                 ;此时Ebx指向尾结点
    
72.                
    
73.                 ;开始标记
    
74.                 Mov Edx,dwAll
    
75.                 .While Edx != dwPersist
    
76.                         Mov Ecx,dwJump
    
77.                         .If Ecx != 0
    
78.                                 .Repeat
    
79.                                         Mov Ebx,[Ebx].Next
    
80.                                 .UntilCxZ
    
81.                         .EndIf
    
82.                         Mov Eax,[Ebx].Next
    
83.                         Mov Ecx,[Eax].Next
    
84.                         Mov [Ebx].Next,Ecx
    
85.                         Push Edx
    
86.                         Invoke Free,Eax
    
87.                         Pop Edx
    
88.                         Dec Edx
    
89.                 .EndW
    
90.                
    
91.                 ;遍历链表并输出
    
92.                 Mov dwCrLfZero,000D0AH
    
93.                 Mov Ecx,Ebx
    
94.                 .Repeat
    
95.                         Pushad
    
96.                         Invoke dw2a,[Ebx].Data,Offset bBuffer2
    
97.                         Invoke StdOut,Offset bBuffer2
    
98.                         Invoke StdOut,Offset dwCrLfZero
    
99.                         Popad
    
100.                         Mov Ebx,[Ebx].Next
     
101.                 .Until Ebx == Ecx
     
102.                 Assume Ebx:Nothing
     
103.                 Assume Eax:Nothing
     
104.                
     
105.                 Ret
     
106.         Main EndP
     
107.        
     
108.         Start:
     
109.                 Call Main
     
110.                 Invoke ExitProcess,NULL
     
111.         End Start
     
112. End

复制代码

PowerShell

1. [int] $total=Read-Host -Prompt "请输入人数：";
   
2. [int] $remain=Read-Host -Prompt "请输入保留人数：";
   
3. [int] $step=Read-Host -Prompt "每隔几个人？：";
   
4. $counter=$step;
   
5. $arr=[int]1..$total;
   
6. $arrcount=$arr.Count;
   
7. 
   
8. while($total -gt $remain)
   
9. {
   
10.         for($i=0;$i -lt $arrcount;$i++) {
    
11.         if($arr[$i] -ne 0){$counter--}
    
12.         if($counter -eq 0){
    
13.             $arr[$i]=[int] 0;
    
14.             $counter=$step;
    
15.             $total--;
    
16.         }
    
17.         if($total -le $remain){break}
    
18.     }
    
19. }
    
20. 
    
21. foreach($s in $arr){
    
22.     if($s -ne 0){$s}
    
23. }
    
24. pause;

复制代码

ivor

python

1. #i：人数  j：步长  alive：存活人数
   
2. i = 41; j = 3; alive=2; index = 0; persons = list(range(1, i+1))
   
3. while len(persons) > alive:
   
4.     index += j - 1
   
5.     index %= len(persons)
   
6.     print("will to kill %s" % persons.pop(index))
   
7.     print("The living people: %s" % persons)
   

复制代码

结果：

The living people: [16, 31]

曾经的你

nice，坐等吃鸡

flashercs

1. /**
   
2. * delete a member in an array for every nScale numbers loop;
   
3. * @param aInput The input array with sequence members
   
4. * @param nScale The granularity of the members removation
   
5. * @param nRemained The remained members count in the array
   
6. */
   
7. function removeNO3(aInput = [1, 2, 3, 4, 5, 6], nScale = 3, nRemained = 1) {
   
8.   var i = 0;
   
9.   aOutput = aInput.slice(0);
   
10.   --nScale;
    
11.   while (aOutput.length > nRemained) {
    
12.     i = (i + nScale) % aOutput.length;
    
13.     aOutput.splice(i, 1);
    
14.   }
    
15.   return aOutput;
    
16. }

复制代码

1. removeNO3([1,2,3,4,5,6,7,8,9,10]);
   
2. removeNO3([1,2,3,4,5,6,7,8,9,10],undefined,2);
   
3. removeNO3([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],undefined,3);

复制代码

WHY

1. 
   
2. $i = 41; $j = 3; $k = 2;
   
3. $str = 1..$i -join ' ';
   
4. $reg = '((?:\d+\s+){' + ($j-1) + '})\d+\s*';
   
5. 
   
6. while ( ($str -split '\b[1-9]\d*').Count -1 -$k ) {
   
7.     $Len = ($str -split '\d+').Count - 1;
   
8.     $str = $str -replace $reg, '$1' -replace '\b0\s';
   
9.     $str = '0 ' * ($Len % $j) + $str;
   
10. }
    
11. 
    
12. $str -replace '\b0\s';
    
13. [console]::ReadLine()
    

复制代码

523066680

写一个长的，单向循环链表

1. STDOUT->autoflush(1);
   
2. my $node = {};
   
3. my $size = 41;      #元素数量
   
4. my $head = $node;
   
5. my $ref = $head;
   
6. init_node( $node, $size );
   
7. 
   
8. while ( $size > 2 ) {
   
9.     $iter++;
   
10.     if ( $iter % 3 == 0 ) {
    
11.         $head = $ref->{next} if ($ref == $head);
    
12.         $prev->{next} = $ref->{next};
    
13.         $size--;
    
14.     }
    
15.     $prev = $ref;
    
16.     $ref = $ref->{next};
    
17. }
    
18. 
    
19. print_node($head, $head);
    
20. 
    
21. sub print_node {
    
22.     my ($ref, $head) = @_;
    
23.     do {
    
24.         printf "%d ", $ref->{v};
    
25.         $ref = $ref->{next};
    
26.     } until ( $ref == $head  );
    
27.     printf "\n";
    
28. }
    
29. 
    
30. # 链表初始化
    
31. sub init_node {
    
32.     my ($ref, $size) = @_;
    
33.     $ref->{v} = 1;
    
34.     for my $i ( 2 .. $size ) {
    
35.         $ref->{next} = { 'v' => $i, 'next' => $head };
    
36.         $ref = $ref->{next};
    
37.     }
    
38. }

复制代码

523066680

C艹

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <list>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     list<int> ele;
   
8.     for (int n= 1; n <= 41; n++) ele.push_back(n);
   
9.     auto it = ele.begin();
   
10.     for (int n = 1; ele.size() > 2; n++ ) {
    
11.         it = n % 3 == 0 ? ele.erase( it ) : next(it);
    
12.         if ( it == ele.end() ) it = ele.begin();
    
13.     }
    
14.     for (int n : ele ) cout << n << " ";
    
15. }
    

复制代码

txiceg

MHL版批处理标准教程 作者是不是走了

459500160

回复 2# ivor


    所有的代码，只有这个python的看懂了，这是一个悲伤的故事。。。。。