1、打魔兽DOTA,选英雄,M个英雄围成一圈供玩家选择,天灾军团和近卫军团交替,一边选一个,直至选完(为保证两边人数相等,M是偶数)。为了增加趣味性,制定选英雄规则如下:按照顺时针方向,两队一边选一个(选英雄不区分阵营),选中的英雄会消失,不参与下一轮选择。强制规定每次选择英雄,都只能选择与最后被选走英雄顺时针相隔两个人的英雄。你是一个具有高尚情操的玩家,于是让对方团队先选择,而你自己最后选择。同时,你又是一位很强势的玩家,你可以指定对方第一位选手选择哪个英雄。请你设计一个程序,求出如何指定对方第一位选手的选择,可以让你自己最终能够选择到“牛头人酋长”,程序语言不限。
这个主要是考算法题吧.像以前经典的约瑟夫圈问题就是类似的了,不过这里的情景换成了Dota对战游戏的双方选择英雄而已..
强制规定每次选择英雄,都只能选择与最后被选走英雄顺时针相隔两个人的英雄。
看牛头人酋长的位置。其实和DOTA没啥关系,DOTA一般是 1-2-2-2-2-1 来选择的。它只是选取了这样一个场景使大家更容易理解这个问题。
和近卫天灾什么的也没关系,因为第一个英雄被确定之后,后面的9个英雄其实也是被确定的。
问题简化第10个英雄是 牛,然后上面的9个英雄都不能为牛。第N个英雄是 p(n) = p(n-1)+3 if(p(n)>m) return p(n-1)+3-m
代码稍后奉上
不止那么多了 一个酒店就十个左右 -fun模式 还有些隐藏英雄
package com.jwh.cn;import java.util.ArrayList;public class Dota {
int position=0;
int m;
ArrayList al;
public Dota(int m){
super();
this.m = m;
al = new ArrayList();
for (int i = 1; i <= m; i++) {
al.add(i);
}
}
public int position(){
this.position+=3;
return position;
}
public int resetNum(int position){
if(position>m){
return position-m;
}
return position;
}
public void check(){
int a = position();
a = resetNum(a);
al.remove(a);
}
}这样,check N次之后剩下你想要的英雄就可以了如果check N次之后,剩下N个英雄
int position=0;
int m;
ArrayList al;
public Dota(int m){
super();
this.m = m;
al = new ArrayList();
for (int i = 1; i <= m; i++) {
al.add(i);
}
}
public int position(){
this.position+=3;
return position;
}
public int resetNum(int position){
if(position>m){
return position-m;
}
return position;
}
public void check(){
int a = position();
a = resetNum(a);
al.remove(a);
this.m-=1;
}
}这样才好
假设有M个英雄,而牛头酋长是第N个英雄,而玩家每隔1个英雄就选择一个英雄
得出
package test200911;class OnelinkNode // 单向链表的结点类
{
public int data; // 存放结点值
public OnelinkNode next; // 后继结点的引用
public OnelinkNode(int k) // 构造值为k的结点
{
data = k;
next = null;
} public OnelinkNode() // 无参数时构造值为0的结点
{
this(0);
}
}public class Josephus //单向循环链表,解约瑟夫环
{
private OnelinkNode head;
private static int num;
Josephus(int n) // 建立n个结点的单向循环链表
{ // 链表结点值为1到n
int i = 1;
OnelinkNode q, rear;
if(n > 0){
head = new OnelinkNode(i);
head.next = head;
rear = head;
while(i < n){
i++;
q = new OnelinkNode(i);
q.next = head;
rear.next = q;
rear = q;
}
}
} public void display(int s,int d) // 解约瑟夫环
{
int j = 0;
OnelinkNode p = head;
while(j < s - 1) // 计数起始点
{
j++;
p = p.next;
}
while(p.next != p) // 多于一个结点时循环
{
j = 1;
while(j < d - 1) // 计数
{
j++;
p = p.next;
}
delete(p); // 删除p的后继结点
p = p.next;
this.output();
}
} public void delete(OnelinkNode p) // 删除p的后继结点
{
OnelinkNode q = p.next; // q是p的后继结点
System.out.print("delete: " + q.data + " ");
if(q == head) // 欲删除head指向结点时,
head = q.next; // 要将head向后移动
p.next = q.next; // 删除q
} public void output() // 输出单向链表的各个结点值
{
OnelinkNode p = head;
System.out.print("data: ");
do{
System.out.print(p.data + " -> ");
p = p.next;
}while(p != head);
System.out.println();
if(p.next==p)
{
num=p.data;
}
} public static void main(String args[]){
//假设有100个英雄 牛头酋长是第52个
int n = 100, s = 1, d = 1;
int N=52;
Josephus h1 = new Josephus(n);
h1.output();
h1.display(s,d);
if(num<N)
{
s=N-num+s;
}else if(num==N){
s=s;
}else{
s=n+N-num+s;
}
System.out.println("从第"+s+"个英雄开始选起:");
h1 = new Josephus(n);
h1.output();
h1.display(s,d);
}
}
import java.util.*;
/*
因为人数是偶数,对手先选,我肯定选最后一个,也就是说,题目转化为:如何让对手开始,
才能保证我最后选的那个正好是英雄,这样不就可以满足条件了吗?
这是我的代码,大家看看对不对?
*/
public class Dota{
public static void reArrange(LinkedList temp,int i){
for(int j=0;j<i;j++){
Object obj=temp.removeFirst();
temp.addLast(obj);
}
//System.out.println(temp);
}
public static void main(String args[]){
int m=6;//总共的人数
int n=2;//英雄所在位置的索引
LinkedList list=new LinkedList();
for(int i=0;i<m;i++){
list.add(i);
}
for(int i=0;i<m;i++){
LinkedList temp=new LinkedList(list);
reArrange(temp,i);
while(temp.size()>1){
temp.removeFirst();
Object first=temp.removeFirst();
temp.addLast(first);
Object second=temp.removeFirst();
temp.addLast(second);
System.out.println(temp);
}
Integer last=(Integer)temp.removeFirst();
if(last==n){
System.out.println(i);//i就是对手开始的那个位置的索引
break;
}
}
}
}