PTA-线性表实验（JAVA）

题目1：Josephus环的问题及算法

【实验内容】

编程实现如下功能：

题意说明：古代某法官要判决n个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第start个犯人开始数起，每数到第distance的犯人，就出列处决；再从下一个犯人开始计数，数到的犯人被处决……以此类推不断循环，直到剩下最后一个犯人予以赦免。此为Josephus环问题。

要求：采用线性表（可以为顺序表或链表）标记n个人，这n个人分别标为A、B、C……,请用Java语言编写程序，按顺序输出出列人的标记。

【实验要求】

输入格式:

输入为3个正整数，分别表示n、start、distance，均不超过1000

输出格式:

输出为一行整数，为出列人的编号。每个整数后一个空格。

（1）解决思路

（2）代码截图

（3）源代码

import java.util.*;
public class self_test02 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入均不超过1000");System.out.print("出列数：");int num = sc.nextInt();//出列System.out.print("开始数：");int start = sc.nextInt();//开始System.out.print("结束数：");int end = sc.nextInt();//结束ArrayList<String> list = new ArrayList<String>();for (int i = start; i <= end; i++) {list.add(String.valueOf(i));}//	第几个人，当num=reset就重置为0int reset = 0;int j = 0;//	list.size() 链表长度	数组长度是 lengthString ans = "";while (!list.isEmpty()) {Iterator it = list.iterator();while (it.hasNext()) {reset++;if (num == reset) {ans += it.next();ans += " ";reset = 0;it.remove();} else {it.next();}}}String ans1 = ans.substring(0, ans.length() - 1);System.out.println(ans1);}}
}

（4）实验结果

题目2：银行业务队列简单模拟

 【实验内容】 

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

【实验要求】

输入格式:

输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式:

按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入样例:

8 2 1 3 9 4 11 13 15

输出样例:

1 3 2 9 11 4 13 15 

 （1）解题思路

 （2）代码截图

 （3）源代码

import java.util.*;
public class self_test {public static void main(String[] args) {// TODO Auto-generated method stubScanner scanner = new Scanner(System.in);int num = scanner.nextInt();int[] arr = new int[num];
//		创建一个数组，用于存放所有输入值（除第一位）for (int i = 0; i < num; i++) {arr[i] = scanner.nextInt();}		
//		创建a,b队列ArrayDeque arr_a = new ArrayDeque();ArrayDeque arr_b = new ArrayDeque();
//		编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口for (int i = 0; i < arr.length; i++) {if (arr[i] % 2 == 0) {arr_b.add(arr[i]) ;} else {arr_a.add(arr[i]) ;}}		String str = new String();while(!arr_a.isEmpty() && !arr_b.isEmpty()) {
//			A的元素个数为偶数，则从A中取出两个元素和一个B中的元素if (arr_a.size() % 2 ==0) {str += arr_a.removeFirst()+" ";str += arr_a.removeFirst()+" ";str += arr_b.removeFirst()+" ";}else {
//				A的元素个数为奇数，则从A中取出一个元素和一个B中的元素str += arr_a.removeFirst()+" ";str += arr_b.removeFirst()+" ";}}
//		A为空时，把B的元素赋值给Aif (arr_a.isEmpty()) {arr_a = arr_b;}
//		将A中的所有元素取出，依次将它们拼接成一个字符串if (!arr_a.isEmpty()) {while(!arr_a.isEmpty()) {str+=arr_a.removeFirst()+" ";}}
//		去掉最后一个空格System.out.println(str);}
}

 （4）运行结果