java-wz叙利亚之行

世事难料，旺仔特工在叙利亚进行情报侦察的时候被被IS基地组织的恐怖分子所抓。作为一名训练有素的特工，旺仔当然不会坐以待毙。他决定用智慧让自己脱离险境。由于在和恐怖分子头领交谈的过程中旺仔得知他的名字叫做“约瑟夫.sb”。于是旺仔想到约瑟夫环的问题（约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3.......分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列）。

 他决定和恐怖分子玩这个游戏，即他和恐怖分子围成一个圈，旺仔站在第一个，所以他的编号是1，其他恐怖分子依次编号2,3,4......。所以旺仔旁边的是编号为2，和n的恐怖分子。从旺仔开始数数，每数到f的人要给自己一枪，直到最后只剩下一个人，游戏结束。但是旺仔想来点花样，即想让f值是一个变量，即每死了一个人，从下面一个人开始数数，这个时候这轮的f值已经是一个新的f值了。那么每轮的f值是多少呢.....

规则如下：

默认 f[0]=1 , f[1]=2

f值变化的规则:f[n]=f[n-2]+f[n-1]

即第一轮最开始的f值是f[1],第一个人从1开始数，数到f[1]的人死了，下一个人重新从1开始数，数到f[2]的人死了，直到剩下最后一个人。

如果旺仔玩死了所有恐怖分子，能活到最后一个，输出“success!” , 反之输出“gg!”。

输入格式:

输入数据有多组，每次输入恐怖分子人数n(n<28)，n=0代表输入结束

输出格式:

如果旺仔玩死了所有恐怖分子，能活到最后一个，输出“success!” , 反之输出“gg!”

输入样例:

在这里给出一组输入。例如：

6
0

输出样例:

在这里给出相应的输出。例如：

success!

 从题目中可以很直观的观察出，该题是一道约瑟夫环问题，所以我们用环形链表来解决该类问题

1、先创建循环链表CircleList

2、实现链表初始化方法add：每个成员值按1，2，3......依次排序

3、实现链表杀人方法：用temp节点表示上一个节点，这样就能便于在成员死后，迅速把圆环连接起来,并且每次死一个人时，死亡序号又会按照斐波那契数列增大一次

4、最后判断剩下来的最后一个人是不是叫1，是的话就success，否则就gg了

import java.util.Scanner;
class Node{int val;Node next;public Node() {}public Node(int val) {this.val = val;}
}//创建环形链表
class CircleList{Node head = null;//    添加环形链表public void add(int num){if(num < 1){return;}
//        temp节点用来过渡Node temp = null;for (int i = 1; i <= num; i++) {Node node = new Node(i);
//            第一个作为头节点if(i == 1) {head = node;head.next = head;temp = head;}else {//在链表末端添加，并且返回指向头节点temp.next = node;node.next = head;temp = temp.next;}}}//    枪毙序号是按照斐波那契序列执行的
//    滚动数组求斐波那契数列public static int f(int n){int p = 1;int q = 2;int r = q;while(n-- > 0){r = p+q;p = q;q = r;}return p;}//    遍历找人出列public void circle(int n){
//        参数有误if(n < 1  || head == null){return;}
//        temp节点作为head节点的前一个节点，作用在某人出列后的环形链表拼接Node temp = head;
//        先让temp节点指向末端while(temp.next != head){temp = temp.next;}int f = 1;//斐波那契因子while (true) {
//            仅剩最后一个人时，跳出循环if(temp == head){break;}
//            temp节点与head节点同时后移for (int i = 0; i < f(f) - 1; i++) {head = head.next;temp = temp.next;}
//            下一个节点开始从一计数head = head.next;
//            节点连接temp.next = head;
//            出局序号更改f++;}
//        根据序号查看最后一个人的身份if(temp.val == 1){System.out.println("success!");}else{System.out.println("gg!");}}
}public class Main {public static void main(String[] args) {CircleList cl = new CircleList();Scanner sc = new Scanner(System.in);while (true) {int n = sc.nextInt();cl.add(n);if (n == 0) {break;}cl.circle(n);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！