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