服务器之家

服务器之家 > 正文

java编程约瑟夫问题实例分析

时间:2021-03-11 14:20     来源/作者:Mu_TQ

一、简介

约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.)

例子:

len个人围成一个圈,玩丢手绢游戏。从第k个人开始,从1开始数数,当数到m时,数m的人就退出圈子,当圈子只剩下一个人为止。

问题分析与算法设计

约瑟夫问题并不难,但求解的方法很多;题目的变化形式也很多。这里给出一种实现方法。

题目中len个人围成一圈,因而启发我们用一个循环的链来表示,可以使用结构数组来构成一个循环链。结构中有两个成员,其一为指向第一个孩子的头节点,另一个为作为判断的节点temp(负责跑龙套)。

具体代码如下:

java" id="highlighter_52376">
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package demo11;
/**
      * 约瑟夫问题, 化为丢手绢
      *
      * @author tianq 思路:建立一个Child类 一个循环列表类CyclLink
      */
public class demo11 {
    public static void main(String[] args) {
        CyclLink cyclink = new CyclLink();
        cyclink.setLen(15);
        cyclink.createLink();
        cyclink.setK(2);
        cyclink.setM(2);
        cyclink.show();
        cyclink.play();
    }
}
// 先建立一个孩子类
class Child {
    // 孩子的标识
    int no;
    Child nextChild;
    // 指向下一个孩子
    public Child(int no) {
        // 构造函数给孩子一个id
        this.no = no;
    }
}
class CyclLink {
    // 先定义一个指向链表第一个小孩的引用
    // 指向第一个小孩的引用,不能动
    Child firstChild = null;
    Child temp = null;
    int len = 0;
    // 表示共有几个小孩
    int k = 0;
    //开始的孩子
    int m = 0;
    //数到几推出
    // 设置m
    public void setM(int m) {
        this.m = m;
    }
    // 设置链表的大小
    public void setLen(int len)
      {
        this.len = len;
    }
    // 设置从第几个人开始数数
    public void setK(int k) {
        this.k = k;
    }
    // 开始play
    public void play() {
        Child temp = this.firstChild;
        // 1.先找到开始数数的人
        for (int i = 1; i < k; i++) {
            temp = temp.nextChild;
        }
        while (this.len != 1) {
            // 2.数m下
            for (int j = 1; j < m; j++) {
                temp = temp.nextChild;
            }
            // 找到要出圈的前一个小孩
            Child temp2 = temp;
            while (temp2.nextChild != temp) {
                temp2 = temp2.nextChild;
            }
            // 3.将数到m的小孩,退出
            temp2.nextChild = temp.nextChild;
            // 让temp指向下一个数数的小孩
            temp = temp.nextChild;
            // this.show();
            this.len--;
        }
        // 最后一个小孩
        System.out.println("最后出圈" + temp.no);
    }
    // 初始化环形链表
    public void createLink() {
        for (int i = 1; i <= len; i++) {
            if (i == 1) {
                // 创建第一个小孩
                Child ch = new Child(i);
                this.firstChild = ch;
                this.temp = ch;
            } else {
                if (i == len) {
                    // 创建第一个小孩
                    Child ch = new Child(i);
                    temp.nextChild = ch;
                    temp = ch;
                    temp.nextChild = this.firstChild;
                } else {
                    // 继续创建小孩
                    Child ch = new Child(i);
                    temp.nextChild = ch;
                    temp = ch;
                }
            }
        }
    }
    // 打印该环形链表
    public void show() {
        Child temp = this.firstChild;
        do {
            System.out.print(temp.no + " ");
            temp = temp.nextChild;
        }
        while (temp != this.firstChild);
    }
}

结果:

java编程约瑟夫问题实例分析

总结

以上就是本文关于java编程约瑟夫问题实例分析的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/tianqingdezhuanlan/article/details/52304263

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部