约瑟夫问题c、Java语言实现

雨点打透心脏的1/2处 2022-08-11 19:28 170阅读 0赞

n个人围成一圈，从第k人个开始报数，假设数到m的人出圈，最后剩下一个，求这个人的编号？

**一、链表实现**

c 语言实现：

#include<stdio.h>
    #include<stdlib.h>
    typedef struct child
    {
        int num;
        struct child * next;
    }child;
    
    child * init_child(child * head, int n)
    {
        int i;
        child * temp, * cur;
    
        //构造一个环形链表
        for (i = 1; i <= n; i++)
        {
            temp = (child *)malloc(sizeof(child));
            temp->num = i;
            if (i == 1)   //只有一个人的时候
            {
                head = temp; //让头指针指向分配的内存空间
                head->next = temp; //指向自己
                cur = head;        //记录当前，方便下面的操作
            }
            else
            {
                cur->next = temp;
                temp->next = head;
                cur = temp;
            }
        }
        return head;
    }
    
    void show_nu(child * head)
    {
        child * cur;
        cur = head;
        printf("孩子们的编号为：\n");
        while (cur->next != head)       //在打印循环链表最后一个数时，判断成立，所以需要下面的printf()语句
        {
            printf("%d\t", cur->num);
            cur = cur->next;
        }
        printf("%d\n", cur->num);
    }
    
    /*
    target 从第几个人开始数
    num 数到编号为几的出列
    */ 
    void start_game(child * head, int target, int num)
    {
        child * tail; //跳到循环链表的最后一节点个位置, tail 的下一个节点就是head
        tail = head;
        int i;
        while (tail->next != head)
        {
            tail = tail->next;
        }
        
        //处理从第几个人开始数，让头指针head指向那个人
        for (i = 1; i < target; i++)  //头指针只需移动(target - 1)次
        {
            head = head->next;
            tail = tail->next;
        }
        
        //下面就是移动head和tail指针了，将不幸的孩子从循环链表中踢去
        //tail和head每移动一次相当于数2下，自己数不用移动;移动2次相当于数3下
        printf("被踢掉的编号为:\n");
        while (head != tail)
        {
            for (i = 1; i < num; i++)
            {
                head = head->next;
                tail = tail->next;
            }
            //移动完后，将head指向的那个删掉
           printf("%d\t", head->num);
           head = head->next;
           tail->next = head;
        }
        printf("\n最后留下的编号为: %d\n", head->num);
    }
    
    int main()
    {
        child * head;  
        int total; //小孩的总数
        int target; //出列的数字
        int num;    //数到哪个编号出列
        printf("约瑟夫问题。\n");
        printf("请输入小孩的个数？孩子会从1到n进行编号：");
        scanf("%d", &total);
        printf("从编号几开始数：");
        scanf("%d", &target);
        printf("数到哪个编号出列：");
        scanf("%d", &num);
    
        //初始化,构造一个循环链表
        head = init_child(head, total);
        //打印小孩的编号
        show_nu(head);
        //开始最重要的操作了,要出列的小孩就遭殃了
        start_game(head, target, num);
        return 0;
    }

运行结果为：

![SouthEast][]

类似的思路，Java 实现：

public class MyJoseph{
    	// 成员内部类 
    	static class Node{
    		int num;
    		Node next;
    		Node(int v){
    			num = v;
    		}
    	}
    
    	public static void main(String[] args) {
    		int total = 7; //共有10个人
    		int start = 3; // 从3开始数
    		int target = 4; // 数到四出列
    
    		//构造循环链表
    		Node head = new Node(1);  // 创建第一个结点
    		Node cur = head;          //设另一个指针指向第一个结点
    		for (int i = 2; i <= total; i++){
    			cur = (cur.next = new Node(i));
    			cur.next = head;
    		}
    
    		//从 3 开始数 让head指针指向3
    		for (int i = 0; i < start - 1; i++){
    			head = head.next;
    			cur = cur.next;
    		}
    
    		// head指针移动n次，就数到了 n+1
    		System.out.println("out of the queue is ");
    		while (head != cur){
    			for (int i = 1; i < target; i++){
    				head = head.next;
    				cur = cur.next;
    			}
    			System.out.println(head.num);
    			head = head.next;
    			cur.next = head;
    		}
    		
    		System.out.println("last num is " + head.num);
    
    
    	}
    }

**二、数组循环实现**

public class Joseph {
        public static void main(String[] args) {
            int total = 10;
            int start = 4;
            int target = 3;
            System.out.println("Last person: " + solution(total, start, target));
        }
    
        /**
         * @param total 10 个人
         * @param start 从 2 开始数
         * @param target  数到 3 出列
         * @return 返回最后出列的那个人
         */
        public static int solution(int total, int start, int target) {
            boolean[] circle = new boolean[total];
            for (int i = 0; i < total; i++) {
                circle[i] = true;
            }
            int last = -1;
            // 剩下的人数
            int remain = total;
            int index = start - 1;
            // 计数
            int count = 0;
            System.out.println("Already out: ");
            while (remain >= 1) {
                // 开始数
                if (circle[index]) {
                    count++;
                    if (count == target) {
                        // 此人出列 
                        circle[index] = false;
                        System.out.print(index + " ");
                        // 剩下的人数减 1
                        remain--;
                        if (remain == 0) {
                            last = index;
                        }
                        // 计数器归 0
                        count = 0;
                    }
    
                }
                index++;
    
                if (index == circle.length) {
                    index = 0;
                }
            }
            System.out.println();
            return last;
        }
    }

[SouthEast]: /images/20220810/3fa6a5258440490da1116e05f32cfb52.png