不用链表实现一个算法

题目：有n个人坐成一个圈，从1开始数，数到3，3的人被剔除。按着这样继续下去。直到最后留下一个人为止。问这个人的序号是多少？
我原来用java加上链表，没有实现出来。很悲哀。
回家想了一下用以下方法实现出来：
先定义类LinkForm：
public class LinkForm {
private int inum;
private int iflag; 

public int getInum() {
return inum;
}

public void setInum(int inum) {
this.inum = inum;
}

public int getIflag() {
return iflag;
}

public void setIflag(int iflag) {
this.iflag = iflag;
}
public String toString(){
StringBuilder sb=new StringBuilder();
sb.append("inum:");
sb.append(inum<10?"0"+inum:inum);
sb.append("   ");
sb.append("iflag:");
sb.append(iflag);
sb.append("   ");

return sb.toString();
}
}
在主类中。我定义如下：
import java.util.ArrayList;
import java.util.List;

public class MathSort {

protected List<LinkForm> init(int n) {
List<LinkForm> list = new ArrayList<LinkForm>(n);
for (int i = 0; i < n; i++) {
LinkForm form = new LinkForm();
form.setIflag(1);
form.setInum(i + 1);
list.add(form);
}
return list;
}

public void print(List<LinkForm> list) {
System.out.println("********************");
for (LinkForm form : list) {
System.out.println(form.toString());
}
}

public void sort(List<LinkForm> list) {
int n = list.size();
if (n > 2) {
int m = 0;
int icount = 0;
while (n - icount >1) {
for (int i = 0; i < n; i++) {
LinkForm form = list.get(i);
if (form.getIflag()>0) {
m++;
}
if (m % 3 == 0&& m!=0 ) {
m = 0;
form.setIflag(0);
list.set(i, form);  
print(list);
icount++;
}

}
}
print(list);
for(LinkForm form:list){
if(form.getIflag()>0){
System.out.println(form.getInum());
}
}
} else {
System.out.println(n);
}
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MathSort sort = new MathSort();
List<LinkForm> list = sort.init(12);
sort.sort(list);
}

}
最终实现了题目所提出来的要求。现在回想起来，很郁闷啊。居然没有完成这个。现在记下来，以备自己将来使用。

评论

1 楼 pxjianke 2010-07-12  

修改后真正不使用链表
public class LinkForm {
private int inum;
private int iflag;

public int getInum() {
return inum;
}

public void setInum(int inum) {
this.inum = inum;
}

public int getIflag() {
return iflag;
}

public void setIflag(int iflag) {
this.iflag = iflag;
}
public String toString(){
StringBuilder sb=new StringBuilder();
sb.append("inum:");
sb.append(inum<10?"0"+inum:inum);
sb.append("   ");
sb.append("iflag:");
sb.append(iflag);
sb.append("   ");

return sb.toString();
}
}
在主类中。我定义如下：
public class MathSort {
protected LinkForm[] init(int n) {
LinkForm[] list = new LinkForm[n];
for (int i = 0; i < n; i++) {
LinkForm form = new LinkForm();
form.setIflag(1);
form.setInum(i + 1);
list[i]=form;
}
return list;
}

public void print(LinkForm[] list) {
System.out.println("********************");
for (LinkForm form : list) {
System.out.println(form.toString());
}
}

public void sort(LinkForm[] list) {
int n = list.length;
if (n > 2) {
int m = 0;
int icount = 0;
while (n - icount > 1) {
for (int i = 0; i < n; i++) {
LinkForm form = list[i];
if (form.getIflag() > 0) {
m++;
}
if (m % 3 == 0 && m != 0) {
m = 0;
form.setIflag(0);
list[i]=form;
print(list);
icount++;
}

}
}
print(list);
for (LinkForm form : list) {
if (form.getIflag() > 0) {
System.out.println(form.getInum());
}
}
} else {
System.out.println(n);
}
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MathSort sort = new MathSort();
LinkForm[] list = sort.init(12);
sort.sort(list);
}
}