批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程
[批处理文件精品]批处理版照片整理器[批处理文件精品]纯批处理备份&还原驱动在线第三方下载
返回列表 发帖

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

本帖最后由 老刘1号 于 2019-4-22 13:58 编辑

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

据说著名犹太历史学家 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. Include masm32rt.inc
  9. Main Proto
  10. .Data?
  11. bBuffer DB 999999 Dup (?)
  12. dwAll DD ?
  13. dwPersist DD ?
  14. bBuffer2 DB 11 Dup (?)
  15. dwCrLfZero DD ?
  16. dwJumpPlusOne DD ?
  17. ;End Data?
  18. .Code
  19. Main Proc
  20. ;获得参数
  21. Invoke ArgClC,1,Offset bBuffer2
  22. Sub Esp,4
  23. Invoke atodw_ex,Offset bBuffer2
  24. Add Esp,4
  25. Mov dwAll,Eax
  26. Invoke ArgClC,2,Offset bBuffer2
  27. Sub Esp,4
  28. Invoke atodw_ex,Offset bBuffer2
  29. Add Esp,4
  30. Mov dwPersist,Eax
  31. Invoke ArgClC,3,Offset bBuffer2
  32. Sub Esp,4
  33. Invoke atodw_ex,Offset bBuffer2
  34. Add Esp,4
  35. Mov dwJumpPlusOne,Eax
  36. ;开始标记
  37. Lea Ebx,bBuffer
  38. Add Ebx,dwAll
  39. Mov Edx,dwAll
  40. Lea Esi,bBuffer
  41. Mov Edi,Esi
  42. Xor Eax,Eax
  43. .While Edx != dwPersist
  44. Mov Ecx,dwJumpPlusOne
  45. .Repeat
  46. LodSB
  47. Add Ecx,Eax
  48. .If Esi == Ebx
  49. Mov Esi,Edi
  50. .EndIf
  51. .UntilCxZ
  52. .If Esi == Edi
  53. Mov Byte Ptr [Ebx-1],1
  54. .Else
  55. Dec Esi
  56. Mov Byte Ptr [Esi],1
  57. Inc Esi
  58. .EndIf
  59. Dec Edx
  60. .EndW
  61. ;输出
  62. Mov dwCrLfZero,000D0AH
  63. Xor Ecx,Ecx
  64. Lea Esi,bBuffer
  65. Dec Esi
  66. .While Ecx != dwAll
  67. Inc Ecx
  68. .If Byte Ptr [Esi+Ecx] == 0
  69. Pushad
  70. Invoke dw2a,Ecx,Offset bBuffer2
  71. Invoke StdOut,Offset bBuffer2
  72. Invoke StdOut,Offset dwCrLfZero
  73. Popad
  74. .EndIf
  75. .EndW
  76. Ret
  77. Main EndP
  78. Start:
  79. Call Main
  80. Invoke ExitProcess,NULL
  81. End Start
  82. End
复制代码
汇编-单向循环链表版
  1. ;约瑟夫问题(单向循环链表) Algo
  2. ;Code By 老刘
  3. ;环境:MASM32 SDK
  4. ;编译指令:ml /coff 约瑟夫问题(单向循环链表).asm /link /subsystem:console
  5. ;参数:总人数、保留人数、每n个人杀一次的n(小于总人数)。
  6. ;参数最大值:1227。
  7. ;参考:MHL批处理标准教程之约瑟夫问题。
  8. Include masm32rt.inc
  9. Main Proto
  10. OneWayLinkedList Struct
  11. Data DWord ?
  12. Next DWord ?
  13. OneWayLinkedList EndS
  14. .Data?
  15. dwAll DD ?
  16. dwPersist DD ?
  17. dwJump DD ?
  18. bBuffer2 DB 11 Dup (?)
  19. dwCrLfZero DD ?
  20. dwLinkedListHead DD ?
  21. ;End Data?
  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. Dec Eax
  40. Mov dwJump,Eax
  41. ;创建链表
  42. Assume Ebx:Ptr OneWayLinkedList
  43. Assume Eax:Ptr OneWayLinkedList
  44. Invoke Alloc,SizeOf OneWayLinkedList
  45. Mov dwLinkedListHead,Eax
  46. Mov Ecx,dwAll
  47. Dec Ecx
  48. Xor Edx,Edx
  49. .Repeat
  50. Mov Ebx,Eax
  51. Inc Edx
  52. Push Ecx
  53. Push Edx
  54. Invoke Alloc,SizeOf OneWayLinkedList
  55. Pop Edx
  56. Pop Ecx
  57. Mov [Ebx].Next,Eax
  58. Mov [Ebx].Data,Edx
  59. .UntilCxZ
  60. Mov Ebx,Eax
  61. Inc Edx
  62. Push dwLinkedListHead
  63. Pop [Ebx].Next ;指向链表结点1
  64. Mov [Ebx].Data,Edx
  65. ;此时Ebx指向尾结点
  66. ;开始标记
  67. Mov Edx,dwAll
  68. .While Edx != dwPersist
  69. Mov Ecx,dwJump
  70. .If Ecx != 0
  71. .Repeat
  72. Mov Ebx,[Ebx].Next
  73. .UntilCxZ
  74. .EndIf
  75. Mov Eax,[Ebx].Next
  76. Mov Ecx,[Eax].Next
  77. Mov [Ebx].Next,Ecx
  78. Push Edx
  79. Invoke Free,Eax
  80. Pop Edx
  81. Dec Edx
  82. .EndW
  83. ;遍历链表并输出
  84. Mov dwCrLfZero,000D0AH
  85. Mov Ecx,Ebx
  86. .Repeat
  87. Pushad
  88. Invoke dw2a,[Ebx].Data,Offset bBuffer2
  89. Invoke StdOut,Offset bBuffer2
  90. Invoke StdOut,Offset dwCrLfZero
  91. Popad
  92. Mov Ebx,[Ebx].Next
  93. .Until Ebx == Ecx
  94. Assume Ebx:Nothing
  95. Assume Eax:Nothing
  96. Ret
  97. Main EndP
  98. Start:
  99. Call Main
  100. Invoke ExitProcess,NULL
  101. End Start
  102. 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. while($total -gt $remain)
  8. {
  9. for($i=0;$i -lt $arrcount;$i++) {
  10.         if($arr[$i] -ne 0){$counter--}
  11.         if($counter -eq 0){
  12.             $arr[$i]=[int] 0;
  13.             $counter=$step;
  14.             $total--;
  15.         }
  16.         if($total -le $remain){break}
  17.     }
  18. }
  19. foreach($s in $arr){
  20.     if($s -ne 0){$s}
  21. }
  22. pause;
复制代码

本帖最后由 ivor 于 2019-3-3 22:03 编辑

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]
1

评分人数

TOP

nice,坐等吃鸡
每日一问

TOP

本帖最后由 flashercs 于 2019-3-3 18:08 编辑
  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);
复制代码
1

评分人数

微信:flashercs
QQ:49908356

TOP

本帖最后由 WHY 于 2019-3-4 16:33 编辑
  1. $i = 41; $j = 3; $k = 2;
  2. $str = 1..$i -join ' ';
  3. $reg = '((?:\d+\s+){' + ($j-1) + '})\d+\s*';
  4. while ( ($str -split '\b[1-9]\d*').Count -1 -$k ) {
  5.     $Len = ($str -split '\d+').Count - 1;
  6.     $str = $str -replace $reg, '$1' -replace '\b0\s';
  7.     $str = '0 ' * ($Len % $j) + $str;
  8. }
  9. $str -replace '\b0\s';
  10. [console]::ReadLine()
复制代码
1

评分人数

TOP

写一个长的,单向循环链表
  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. while ( $size > 2 ) {
  8.     $iter++;
  9.     if ( $iter % 3 == 0 ) {
  10.         $head = $ref->{next} if ($ref == $head);
  11.         $prev->{next} = $ref->{next};
  12.         $size--;
  13.     }
  14.     $prev = $ref;
  15.     $ref = $ref->{next};
  16. }
  17. print_node($head, $head);
  18. sub print_node {
  19.     my ($ref, $head) = @_;
  20.     do {
  21.         printf "%d ", $ref->{v};
  22.         $ref = $ref->{next};
  23.     } until ( $ref == $head  );
  24.     printf "\n";
  25. }
  26. # 链表初始化
  27. sub init_node {
  28.     my ($ref, $size) = @_;
  29.     $ref->{v} = 1;
  30.     for my $i ( 2 .. $size ) {
  31.         $ref->{next} = { 'v' => $i, 'next' => $head };
  32.         $ref = $ref->{next};
  33.     }
  34. }
复制代码
1

评分人数

综合型编程论坛
Writing Code That Nobody Else Can Read.

TOP

本帖最后由 523066680 于 2019-3-4 14:11 编辑

C艹
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <list>
  4. using namespace std;
  5. int main() {
  6.     list<int> ele;
  7.     for (int n= 1; n <= 41; n++) ele.push_back(n);
  8.     auto it = ele.begin();
  9.     for (int n = 1; ele.size() > 2; n++ ) {
  10.         it = n % 3 == 0 ? ele.erase( it ) : next(it);
  11.         if ( it == ele.end() ) it = ele.begin();
  12.     }
  13.     for (int n : ele ) cout << n << " ";
  14. }
复制代码
综合型编程论坛
Writing Code That Nobody Else Can Read.

TOP

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

TOP

返回列表