首页 > 编程语言 > 详细

算法练习(1):约瑟夫环 josephusProblem 问题(1.3.37)

时间:2020-06-03 10:51:23      阅读:53      评论:0      收藏:0      [点我收藏+]

写在前面

最近在学习数据机构算法知识,看到是 《算法》第四版,书里面是用 Java 实现,我这里会用TypeScript 把课后习题实现一遍,放在这里记录下,记录是为了怕自己坚持不下去,通过输出倒逼学习

约瑟夫环问题

据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏

实现方式,这个用队列来实现非常方便

class Queue<T> {
    private items: T[] = [];
    isEmpty () {
        return this.items.length === 0;
    }

    enqueue (ele: T) {
        this.items.push(ele);
    }

    dequeue (): T {
        return this.items.shift();
    }

    size () {
        return this.items.length;
    }

    clear () {
        this.items = [];
    }

    [Symbol.iterator] () {
        let pointer = 0;
        const components = this.items;

        return {
            next (): IteratorResult<T> {
                if (pointer < components.length) {
                    return {
                        done: false,
                        value: components[pointer++]
                    };
                } else {
                    return {
                        done: true,
                        value: null
                    };
                }
            }
        };
    }
}

function josephusProblem (numberOfPerson: number, personOrder: number) {
    const queue = new Queue<number>()

    for (let index = 1; index <= numberOfPerson; index++) {
        queue.enqueue(index)
    }
    console.log(‘队列大小:‘, queue.size())
    while (numberOfPerson > 0) {
        for (let index = 1; index < personOrder; index++) {
            queue.enqueue(queue.dequeue())
        }
        console.log(‘当前人数:‘, numberOfPerson, ‘自杀的人:‘, queue.dequeue())
        numberOfPerson--
    }
}
josephusProblem(41, 3)

算法练习(1):约瑟夫环 josephusProblem 问题(1.3.37)

原文:https://www.cnblogs.com/chromedev/p/13035187.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!