写在前面
最近在学习数据机构算法知识，看到是 《算法》第四版，书里面是用 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--
}