数据结构中的舞伴问题。用JAVA实现

假设在周末舞会上，男士们（m人）和女士们（n人）进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则野散较颂慧氏长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。并m和n存在什么条件时，第x个（1 <=x <=m）男生才有可能和他心仪的第y个（1 <=x <=n）女生跳舞，在第几首曲子时？

*/

import java.util.ArrayList

import java.util.List

import java.io.BufferedReader

import java.io.InputStreamReader

public class Dance{

private List <String>boy=new ArrayList <String>()

private List <String>girl=new ArrayList <String>()

public Dance(int m,int n){

init(m,n)

}

public void init(int m,int n){

for(int i=0i <mi++){

boy.add("man"+i)

}

for(int i=0i <ni++){

girl.add("girl"+i)

}

}

public int getMin(){

return Math.min(boy.size(),girl.size())

}

public void go(){

String b="man1"

String g="girl2"

int count=0

int i=0

boolean bool=true

while(bool){

if(i%getMin()==0)

System.out.println("第"+(++count)+"次:")

boolean bGirl=girl.get(i%girl.size()).equals(g)

boolean bBoy=boy.get(i%boy.size()).equals(b)

bool=!(bGirl&&bBoy)

System.out.println((boy.get((i)%boy.size())).toString())

System.out.println((girl.get((i)%girl.size())).toString())

i++

}

System.out.println(b+"要在"+count+"首歌中才可以和"+g+"一起Dancing")

}

public static void main(String [] args)throws Exception{

int m

int n

System.out.println("请输入男士人数:")

m=input()

System.out.println("请碧亩输入女士人数:")

n=input()

Dance dance=new Dance(m,n)

dance.go()

}

public static int input()throws Exception{

int returnNum=0

BufferedReader br=new BufferedReader(new InputStreamReader(System.in))

String line=br.readLine()

while(!line.equalsIgnoreCase("exit")){

try{

returnNum=new Integer(line)

if(returnNum <0) throw new Exception()

break

}catch(Exception e){

System.out.println("输入数据有误!请重新输入,退出请按exit")

line=br.readLine()

}

}

return returnNum

}

}

public static void main(String[] args) {

final int M = 6// number of girls，可改动

final int N = 7// number of boys，可改动

int x = 3// some boy，可改动

int y = 5// some girl，可改动

String result = ""// 记录结果，即察激坦第二铅握个问题

// 初始化，假设队列存放男女生编号，从1开始

Queue<Integer>boys = new LinkedList<败桐Integer>()

for (int i = 1i <= Ni++) {

boys.add(i)

}

Queue<Integer>girls = new LinkedList<Integer>()

for (int i = 1i <= Mi++) {

girls.add(i)

}

// 跳舞开始

int min = boys.size() >girls.size() ? girls.size() : boys.size()

int k = 1// songs

int count = 2// 求出两个值，可改动

while (k <1000) {//为了不死循环，这里假设最多有999支舞蹈

System.out.println("***This is the " + k + "st dance:")

for (int i = 0i <mini++) {

// 跳舞，第一个问题：输出每曲配对情况

System.out.println("Boy " + boys.peek() + " <=>Girl "

+ girls.peek())

// 跳过的排到对尾

int boy = boys.remove()

boys.add(boy)

int girl = girls.remove()

girls.add(girl)

// 判断 x和y跳舞了没有

if (boy == x &&girl == y) {

result += k + ","

count--

}

}

if (count == 0)

break

// next dance

k++

}

// 结果

if (count == 0)

System.out.println("\n***Boy " + x + " and Girl " + y

+ " dance together in : " + result)//第二个问题的解答，跳了哪几支舞

else

System.out.println("\n***Boy " + x + " and Girl " + y

+ " have no chance to dance!")//第二个问题的解答，两人没机会跳舞

}