批处理之家 » 出题挑战 » 不限语言解决“约瑟夫问题”

老刘1号 发表于 2019-3-3 15:58

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

[i=s] 本帖最后由 老刘1号 于 2019-4-22 13:58 编辑 [/i]

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

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

[color=Red]汇编-一维数组版[/color][code];约瑟夫问题(一维数组) 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[/code][color=Red]汇编-单向循环链表版[/color][code];约瑟夫问题(单向循环链表) 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[/code]PowerShell[code][int] $total=Read-Host -Prompt "请输入人数：";
[int] $remain=Read-Host -Prompt "请输入保留人数：";
[int] $step=Read-Host -Prompt "每隔几个人？：";
$counter=$step;
$arr=[int]1..$total;
$arrcount=$arr.Count;

while($total -gt $remain)
{
        for($i=0;$i -lt $arrcount;$i++) {
        if($arr[$i] -ne 0){$counter--}
        if($counter -eq 0){
            $arr[$i]=[int] 0;
            $counter=$step;
            $total--;
        }
        if($total -le $remain){break}
    }
}

foreach($s in $arr){
    if($s -ne 0){$s}
}
pause;[/code]

ivor 发表于 2019-3-3 16:28

[i=s] 本帖最后由 ivor 于 2019-3-3 22:03 编辑 [/i]

python[code]#i：人数  j：步长  alive：存活人数
i = 41; j = 3; alive=2; index = 0; persons = list(range(1, i+1))
while len(persons) > alive:
    index += j - 1
    index %= len(persons)
    print("will to kill %s" % persons.pop(index))
    print("The living people: %s" % persons)
[/code]结果：
[quote]The living people: [16, 31][/quote]

曾经的你 发表于 2019-3-3 16:34

nice，坐等吃鸡

flashercs 发表于 2019-3-3 18:06

[i=s] 本帖最后由 flashercs 于 2019-3-3 18:08 编辑 [/i]

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

WHY 发表于 2019-3-4 01:29

[i=s] 本帖最后由 WHY 于 2019-3-4 16:33 编辑 [/i]

[code]
$i = 41; $j = 3; $k = 2;
$str = 1..$i -join ' ';
$reg = '((?:\d+\s+){' + ($j-1) + '})\d+\s*';

while ( ($str -split '\b[1-9]\d*').Count -1 -$k ) {
    $Len = ($str -split '\d+').Count - 1;
    $str = $str -replace $reg, '$1' -replace '\b0\s';
    $str = '0 ' * ($Len % $j) + $str;
}

$str -replace '\b0\s';
[console]::ReadLine()
[/code]

523066680 发表于 2019-3-4 09:46

写一个长的，单向循环链表[code]STDOUT->autoflush(1);
my $node = {};
my $size = 41;      #元素数量
my $head = $node;
my $ref = $head;
init_node( $node, $size );

while ( $size > 2 ) {
    $iter++;
    if ( $iter % 3 == 0 ) {
        $head = $ref->{next} if ($ref == $head);
        $prev->{next} = $ref->{next};
        $size--;
    }
    $prev = $ref;
    $ref = $ref->{next};
}

print_node($head, $head);

sub print_node {
    my ($ref, $head) = @_;
    do {
        printf "%d ", $ref->{v};
        $ref = $ref->{next};
    } until ( $ref == $head  );
    printf "\n";
}

# 链表初始化
sub init_node {
    my ($ref, $size) = @_;
    $ref->{v} = 1;
    for my $i ( 2 .. $size ) {
        $ref->{next} = { 'v' => $i, 'next' => $head };
        $ref = $ref->{next};
    }
}[/code]

523066680 发表于 2019-3-4 11:17

[i=s] 本帖最后由 523066680 于 2019-3-4 14:11 编辑 [/i]

C艹[code]#include <algorithm>
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> ele;
    for (int n= 1; n <= 41; n++) ele.push_back(n);
    auto it = ele.begin();
    for (int n = 1; ele.size() > 2; n++ ) {
        it = n % 3 == 0 ? ele.erase( it ) : next(it);
        if ( it == ele.end() ) it = ele.begin();
    }
    for (int n : ele ) cout << n << " ";
}
[/code]

txiceg 发表于 2020-9-26 00:18

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

459500160 发表于 2021-1-30 22:59

[b]回复 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=217862&ptid=52153]2#[/url] [i]ivor[/i] [/b]


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

查看完整版本: 不限语言解决“约瑟夫问题”