分别用t(R) = R∪R2∪…∪Rn 和Warkshallde 算法实现求关系的闭包。(输入、输出采用文件的方式)
例如:
输入:文件input.txt,下面给出一个input.txt文件的格式样例。
A={a,b,c,d}
R={,,,}
输出:计算结果写入文件output.txt。如上input.txt文件对应的output.txt如下。
算法一:
t(R)={,,,,,,,,}
执行时间:
算法二:
t(R)={,,,,,,,,}
执行时间:
谢谢了
有一道离散数学的题,帮帮我。
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- shawn.bug 2009-11-29 16:06关注
package relations;
public class Main {
public static void main(String args[]){
long time1_star = System.currentTimeMillis();System.out.println("--- R1∪R2∪R3∪....Rn --- "); new Relations(); System.out.println(); long time1_end = System.currentTimeMillis(); System.out.println("耗时:"+String.valueOf(time1_end-time1_star)+"毫秒"); long time2_star = System.currentTimeMillis(); System.out.println("--- Warkshallde --- "); new Warkshallde(); System.out.println(); long time2_end = System.currentTimeMillis(); System.out.println("耗时:"+String.valueOf(time2_end-time2_star)+"毫秒"); }
}
package relations;
public class BiList{
private Object[] data=new Object[3];
private int index=0;
private void expand(){
Object[] data2=new Object[data.length*2];
System.arraycopy(data,0,data2,0,data.length);
data=data2;
}
public void add(Object o){
if (data.length==index) expand();
data[index]=o;
index++;
}
public void add(int pos,Object o){
if (data.length==index) expand();
for(int i=index;i>pos;i--){
data[i]=data[i-1];
}
data[pos]=o;
index++;
}
public Object remove(int pos){
Object o=data[pos];
index--;
for(int i=pos;i<index;i++){
data[i]=data[i+1];
}
return o;
}
public int size(){
return index;
}
public Object get(int pos){
return data[pos];
}
public void clear(){
index=0;
}
public boolean isEmpty(){
return index==0;
}
public Object[] toArray(){
return data;
}
}package relations;
public class Binary {
private String one;
private String two;
public Binary(){}
public Binary(String one,String two){
this.one = one;
this.two = two;
}
public String getOne() {
return one;
}
public void setOne(String one) {
this.one = one;
}
public String getTwo() {
return two;
}
public void setTwo(String two) {
this.two = two;
}}
package relations;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;public class Relations {
private static BiList A = new BiList();
private static BiList R = new BiList();
private static int n=0;public Relations(){ BiList<Binary> copy = new BiList<Binary>(); readInput(); for(int i=0 ; i<R.size(); i++){ Binary b=(Binary)R.get(i); copy.add(new Binary(b.getOne(),b.getTwo())); } System.out.print("t(R)={"); operate(copy); System.out.print("}"); } public static void initA(String s,int line){ if(line==1){ String type=s.replace(" ","").replace("{", "").replace("}",""); String[] a = type.substring(2,type.length()).split(","); for(String a1:a){ A.add(new Binary(a1,a1)); } n=A.size(); /* System.out.print("A={"); for(int i=0 ; i<A.size(); i++){ Binary b=(Binary)A.get(i); System.out.print("<"+b.getOne()+","+b.getTwo()+">"); } System.out.println("}"); */ } } public static void initR(String s,int line){ if(line==2){ String type=s.replace(" ","").replace("}", "").replace("<", "").replace(",", ""); String[] a = type.substring(3,type.length()).split(">"); for(String a1:a){ R.add(new Binary(a1.substring(0,1),a1.substring(1,2))); } System.out.print("R={"); for(int i=0 ; i<R.size(); i++){ Binary b=(Binary)R.get(i); System.out.print("<"+b.getOne()+","+b.getTwo()+">"); } System.out.println("}"); } } private static BiList<Binary> operate(BiList<Binary> list){ BiList<Binary> type1 = new BiList<Binary>(); if(n==0){ for(int i=0; i<R.size(); i++){ Binary r=(Binary)R.get(i); list.add(new Binary(r.getOne(),r.getTwo())); } print(list); return list; } for(int i=0; i<list.size(); i++){ Binary r=(Binary)list.get(i); type1.add(new Binary(r.getOne(),r.getTwo())); } list.clear(); for(int i=0; i<R.size();i++){ for(int j=0; j<type1.size(); j++){ Binary r=(Binary)R.get(i); Binary r1=(Binary)type1.get(j); if(r.getTwo().equals(r1.getOne())){ list.add(new Binary(r.getOne(),r1.getTwo())); } } } print(list); for(int i=0; i<list.size();i++){ for(int j=0; j<list.size(); j++){ Binary r=(Binary)list.get(i); Binary r1=(Binary)list.get(j); if(r.getOne().endsWith(r1.getOne())&&r.getTwo().equals(r1.getTwo())){ list.remove(j); } } } for(int i=0; i<list.size();i++){ for(int j=0; j<list.size(); j++){ Binary r=(Binary)list.get(i); Binary r1=(Binary)list.get(j); if(r.getOne().endsWith(r1.getOne())&&r.getTwo().equals(r1.getTwo())){ list.remove(j); } } } n--; return operate(list); } public static void print(BiList<?> li){ for(int i=0 ; i<li.size(); i++){ Binary b=(Binary)li.get(i); System.out.print("<"+b.getOne()+","+b.getTwo()+">"); } } public static void readInput(){ try{ BufferedReader br = new BufferedReader( new FileReader("d:\\input.txt")); String line=""; int i=0; while((line=br.readLine()) !=null){ i++; initA(line,i); initR(line,i); } } catch(FileNotFoundException e){ e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } public static void main(String args[]){ new Relations(); }
}
package relations;
public class Util {
public static int praseToDigit(String s){
if(s.equals("a")){
return 1-1;
}
if(s.equals("b")){
return 2-1;
}
if(s.equals("c")){
return 3-1;
}
if(s.equals("d")){
return 4-1;
}
if(s.equals("e")){
return 5-1;
}
return -1;
}
public static String praseToABC(int i){
if(i==0){
return "a";
}
if(i==1){
return "b";
}
if(i==2){
return "c";
}
if(i==3){
return "d";
}
if(i==4){
return "e";
}
return null;
}
}package relations;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;public class Warkshallde {
private static BiList A = new BiList();
private static BiList R = new BiList();
private static int[][] matrix;
public Warkshallde(){
readInput();
matrixOperation();
System.out.print("t(R)={");
for(int i=0; i for(int j=0; j if(matrix[i][j]==1){
System.out.print("");
}
}
}
System.out.print("}");
}public static void initA(String s,int line){ if(line==1) { String type=s.replace(" ","").replace("{", "").replace("}",""); String[] a = type.substring(2,type.length()).split(","); for(String a1:a){ A.add(new Binary(a1,a1)); } matrix = new int[A.size()][A.size()]; } } public static void initR(String s,int line){ if(line==2){ String type=s.replace(" ","").replace("}", "").replace("<", "").replace(",", ""); String[] a = type.substring(3,type.length()).split(">"); for(String a1:a){ R.add(new Binary(a1.substring(0,1),a1.substring(1,2))); int row = Util.praseToDigit(a1.substring(0,1)); int col = Util.praseToDigit(a1.substring(1,2)); matrix[row][col]=1; } } } public static void print(BiList<?> list){ System.out.print("A={"); for(int i=0 ; i<list.size(); i++){ Binary b=(Binary)list.get(i); System.out.print("<"+b.getOne()+","+b.getTwo()+">"); } System.out.println("}"); } public static void matrixOperation(){ for(int i=0; i<matrix.length-1;i++){ for(int j=0; j<matrix[i].length-1; j++){ if(matrix[j][i]==1){ operate(i,j); } } } for(int i1=0; i1<matrix.length;i1++){ for(int j=0; j<matrix[i1].length; j++){ System.out.print(matrix[i1][j]+" "); } System.out.println(); } } public static void operate(int index,int add ){ int i=matrix.length-1; while(i>=0){ if(matrix[index][i]==matrix[add][i]&& matrix[index][i]==0){ matrix[add][i]=0; } matrix[add][i]=1; i--; } } public static void readInput(){ try{ BufferedReader br = new BufferedReader( new FileReader("d:\\input.txt")); String line=""; int i=0; while((line=br.readLine()) !=null){ i++; initA(line,i); initR(line,i); } } catch(FileNotFoundException e){ e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); } } public static void main(String args[]){ new Warkshallde(); }
}
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 关于#python#的问题:求帮写python代码
- ¥20 MATLAB画图图形出现上下震荡的线条
- ¥15 LiBeAs的带隙等于0.997eV,计算阴离子的N和P
- ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
- ¥15 来真人,不要ai!matlab有关常微分方程的问题求解决,
- ¥15 perl MISA分析p3_in脚本出错
- ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
- ¥15 ubuntu虚拟机打包apk错误
- ¥199 rust编程架构设计的方案 有偿
- ¥15 回答4f系统的像差计算