求解答~该如何解决

2013-09-11

求解答~产生一个最大数为n的自然数序列。按照给定的自然数m从1到m进行报数。在自然数序列中，数到第m个数时，

求解答~
产生一个最大数为n的自然数序列。按照给定的自然数m从1到m进行报数。在自然数序列中，数到第m个数时，将该数移除，并从该数的下一个自然数重新开始从1到m报数。到达序列尾部后，从序列头部接着尾部报的数进行。如此往复。请给出算法描述或者伪代码及代码实现，用以输出移除数的顺序。举例：假定n为5，m为2，则自然数序列为1, 2, 3, 4, 5，报数结束后，移除数的顺序为：2, 4, 1, 5, 3。

算法
[解决办法]

package cn.dzr.testnumber;

import java.util.Scanner;

public class NumberGet
{
static int pos = 0;
public static void main(String[] args)
{

Scanner sc =new Scanner(System.in);

System.out.println("请输入n的值:(即数组的最大元素)");

int n = sc.nextInt();


System.out.println("请输入m的值：(即报数的最大值):");
int m = sc.nextInt();

System.out.println("n: "+n + "m: "+ m);
int[] arr = new int[n];

sc.close();

for(int i =0 ;i<n; i++)
{
arr[i] = i+1;
}

//int pos = 0;
while(arr.length>0)
{
int num = getNum(arr,m);
System.out.print(num+" ");
if(arr.length==1)
{
break;
}
arr = getNewArr(arr,pos);
}
System.out.println("over");
}
private static int getNum(int[] arr, int i)
{
//获取该删除的数字的位置..
if(arr.length ==1)
{
return arr[0];
}
pos = pos+ i -1;

//当pos的位置大于数组的长度的时候，需要减去数组的长度...
while(pos>arr.length-1)
{
//当i的值大于或者等于数组的长度的时候，需要将i减去数组的长度的x倍直到i小于数组长度为止。
while(arr.length<i)
{
i = i-arr.length;
}
pos = pos + i - 1 - arr.length;
}


int num = arr[pos];
return num;
}

private static int[] getNewArr(int[] arr, int pos)
{
//该方法获取一个数组第pos个元素被删除后的新数组...
int len = arr.length;
int[] newArr = new int[len-1];

//pos之前的元素未发生变化
for(int i=0;i<pos;i++)
{
newArr[i] = arr[i];
} 
 
//pos之后的元素向前移动一位
for(int j=pos;j<len-1;j++)
{
newArr[j] = arr[j+1];
}

return newArr;
}
}

[解决办法]
约瑟夫环问题，用队列做


import java.util.concurrent.LinkedBlockingQueue;

/**
 * 产生一个最大数为n的自然数序列。按照给定的自然数m从1到m进行报数。在自然数序列中，数到第m个数时，将该数移除，
 * 并从该数的下一个自然数重新开始从1到m报数。到达序列尾部后，从序列头部接着尾部报的数进行。如此往复。
 * 请给出算法描述或者伪代码及代码实现，用以输出移除数的顺序。举例：假定n为5，m为2， 则自然数序列为1, 2, 3, 4,
 * 5，报数结束后，移除数的顺序为：2, 4, 1, 5, 3。
 * 
 * 
 */

public class Test001 {
public static void main(String[] args) {
test(5, 2);
}

static void test(int n, int m) {
if (n <= 0) return;
LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<Integer>();
for(int i = 1;i <= n;++i) queue.offer(i);
int index = 0;
while(!queue.isEmpty()) {
int value = queue.remove();
if(++index == m) {
index = 0;
System.out.println("remove:" + value);
} else {
queue.offer(value);
}
}
}
}

[解决办法]

import java.util.Vector;

public class Tests {

public static void main(String[] args) {
int n = 5;
int m = 2;
kill(m, n);
}

public static void kill(int m, int n) {
if (m < 1 
[解决办法]
 n < 1) {
System.out.println("Error");
return;
}
Vector<Integer> nodes = new Vector<Integer>();
for (int i = 1; i <= n; i++) {
nodes.add(i);
}
int index = 0;
int step = m - 1;
for (int i = 0; i < n; i++) {
index = (index + step) % (n - i);
System.out.print(nodes.get(index) + " ");
nodes.removeElementAt(index);
}
}
}

热点排行

Java相关

求解答~该如何解决