第三届ITAT考试题 小弟从小语文就笨得很 题意有些不明白 希望大家帮帮忙啊!!!!???

Question

1、 编写一个Java应用程序，对于给定的一个字符串的集合，格式如：
　　{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}
要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出：
{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
请将制作好的源文件保存为“t1.java”。（本题60分，要求1占20分，要求2占35分，要求3占5分）
（1）分析问题，描述你解决这个问题的思路、处理流程，以及算法复杂度。
（2）编程实现题目要求的集合合并。
（3）描述可能的改进（改进的方向如效果，算法复杂度，性能等等）。
2、 在下图中的九个点上，空出中间的点，其余的点上任意填入数字1至8；1的位置保持不动，然后移动其余的数字，使1到8顺时针从小到大排列。移动的规则是：只能将数字沿线移向空白的点。请将制作好的源文件保存为“t2.java”。（本题共60分，要求1占20分，要求2占40分）要求：
（1）分析问题，并描述你的算法设计思想。
（2）编程显示数字移动过程。
    ○——○——○
│＼  │  ／│
│ ＼ │ ／ │
│  ＼│／  │
○——○——○
│  ／│＼  │
│ ／ │ ＼ │
│／  │  ＼│
○——○——○
各位大侠帮帮忙啊``??最好能给代码示例......谢谢!!

Answer 1

本来想写第一题那个的  结果写出了个outofmemoryerror

Answer 2

第一个题目一个直接想法的实现如下：用一个Map<String,Integer>来记录所有元素以及这些元素所属的集合，用一个for循环遍历所有的集合，首先取出这个元素在Map中的集合号，如果无集合号，则将集合号设置为当前的集合号（每个集合给一个序号），否则将本当前集合中的所有元素设置为从Map中取出的集合。接下来生成一个Map<Integer,Set<String>>，遍历Map<String,Integer>中的元素，如果集合号所对应的Set存在，则把当前元素加进去，否则新建再加，最终Map<String,Set<String>>中就是合并后的结果，这个算法的复杂度为NM，其中N表示集合个数，M表示每个集合中的元素个数
public class UnionTest
{

public static final int setLength = 4;

public static void init(Map<String, Integer> map, String[] set, int setNo)
{ for (String s : set)
{
Integer no = map.get(s);
if (no == null)
{
map.put(s, setNo);
}
else
{
for (String element : set)
{
map.put(element, no);
}
break;
}
}
}

/**
 * @param args
 */
public static void main(String[] args)
{ String[] set1 = new String[]
{
        "aaa", "bbb", "ccc"
};

String[] set2 = new String[]
{
        "bbb", "ddd"
};

String[] set3 = new String[]
{
        "eee", "fff"
};

String[] set4 = new String[]
{
"ggg"
};

String[] set5 = new String[]
{
        "ddd", "hhh"
};

Map<String, Integer> map = new HashMap<String, Integer>();
UnionTest.init(map, set1, 1);
UnionTest.init(map, set2, 2);
UnionTest.init(map, set3, 3);
UnionTest.init(map, set4, 4);
UnionTest.init(map, set5, 5);
Map<Integer, Set<String>> list = new HashMap<Integer, Set<String>>();

for (String s : map.keySet())
{
int no = map.get(s);
Set<String> set = list.get(no);
if (set == null)
{
set = new HashSet<String>();
list.put(no, set);
}
set.add(s);
}
for (int index : list.keySet())
{
System.out.println("Index" + index);
UnionTest.printSet(list.get(index));
}
}

public static void printSet(Set<String> set)
{ for (String s : set)
{
System.out.print(s + " ");
}
System.out.println();
}
}

Answer 3

楼主也参加ITAT了啊？我也参加了
第一个题比较简单。
第二个题其实是一个冒泡排序问题。算法比较简单，但是要用图形化的程序表示出来还挺麻烦的，我正在写这个，呵呵。

Answer 4

数组写的,就是麻烦,啰嗦...
大概就这意思,逻辑那里没写注释,慢慢看吧~~嘿嘿~
public class t2 {
int[] array = new int[8]; int center = 0; // 初始化数组
public void arrayInit() {
boolean[] cards = new boolean[8];
for (int i = 0; i < 8; i++) {
cards[i] = false;
}
java.util.Random r = new java.util.Random();
int x;
for (int i = 0; i < 8; i++) {
do {
x = java.lang.Math.abs(r.nextInt()) % 8;
} while (cards[x] != false);
cards[x] = true;
this.array[i] = x + 1;
}
} // 数组内相邻的两个数交换位置
public void exchange(int index) {
int temp;
temp = this.array[index];
this.array[index] = this.array[((index - 1 > 0) ? (index - 1) : 7)];
this.array[((index - 1 > 0) ? (index - 1) : 7)] = temp;
this.print();
} // 数组内制定位置的数组与中心点交换
public void centerChange(int index) {
int temp;
temp = this.array[index];
this.array[index] = this.center;
this.center = temp;
this.print();
} public void function() {
int begin = 0;
int end = 0;
for (int i = 0; i < 8; i++) {
if (array[i] == 1) {
begin = i;
break;
}
}
for (int i = 2; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (this.array[j] == i) {
end = j;
break;
}
}
if (((end - 1 > 0) ? (end - 1) : 7) == begin) {
begin = end;
continue;
}
this.centerChange(end);
do {
this.exchange(end);
end = ((end - 1 > 0) ? (end - 1) : 7);
} while (((end - 1 > 0) ? (end - 1) : 7) != begin);
begin = end;
this.centerChange(end);
}
} public void print() {
System.out.println(this.array[0] + "──" + this.array[1] + "──"
+ this.array[2]);
System.out.println("|╲│╱|");
System.out.println(this.array[7] + "──" + this.center + "──"
+ this.array[3]);
System.out.println("|╱│╲|");
System.out.println(this.array[6] + "──" + this.array[5] + "──"
+ this.array[4]);
System.out.println();
} public static void main(String[] args) {
t2 t2 = new t2();
t2.arrayInit();
t2.print();
t2.function();
}
}

Answer 5

更正一下..
所有((index - 1 > 0) ? (index - 1) : 7)的地方换成
[((index - 1 >= 0) ? (index - 1) : 7)] 

Answer 6

 x = java.lang.Math.abs(r.nextInt()) % 8;
这句话什么意思？