首页 > 试题广场 >

请以n=9，s=1，m=5为例，人工模拟Josephus的求

[问答题]

设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，......,如此反复知道所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n，s和m，求出这n个人的出局序列。请以n=9，s=1，m=5为例，人工模拟Josephus的求解过程以求得问题的解。

卫知北

while(s-1)
{
    phead=phead->next;
    s--;
}
while(n--)
{
    while(m-2)
    {
        phead=phead->next;
        m--;
    }
    cur=phead->next;
    phead->next=cur->next;
    phead=cur->next;
    printf("%d", cur->data);
    free(cur);
}

发表于 2022-11-11 16:27:41 回复(0)

TheOctopus


class Node {     int val;     Node next = null;     public Node(int val) {         this.val = val;     }

}

public class Joseph_circle {     Node tail = null;     private void add(int val) {         if (tail == null) {             tail = new Node(val);             tail.next = tail;         } else {             Node new_node = new Node(val);             new_node.next = tail.next;             tail.next = new_node;             tail = new_node;         }     }     private void output() {         // 设置一个指向尾部的指针         Node p = tail;         while (p != null) {             p = p.next;             System.out.println("输出结点值为：" + p.val);             if (p == tail) {                 break;             }         }     }     public void Joseph(int step) {         Node pNode = tail;         while (pNode != null && pNode.next != pNode) {             for (int i = 0; i < step - 1; i++) {                 pNode = pNode.next;             }             Node delete_Joseph = pNode.next;             System.out.println("当前轮被删除的是：" + delete_Joseph.val);             pNode.next = pNode.next.next;             if (delete_Joseph == tail) {                 tail = pNode;             }             output();         }     }     public static void main(String[] args) {         Joseph_circle joseph_circle = new Joseph_circle();         for (int i = 1; i < 10; i++) {             joseph_circle.add(i);         }         joseph_circle.output();         System.out.println("*********************");         joseph_circle.Joseph(5);     }
}