Java - Σχεδίαση Αλγορίθμων

[@kon_!]

Καλησπέρα παίδες!Χρειάζομαι την βοήθειά σας σε μια εργασία που έχω να κάνω στην Σχεδίαση Αλγορίθμων με χρήση Java.

Η εργασία έχει 2 σκέλη.Ουσιαστικά όμως θα λειτουργήσουν πάνω κάτω με το ίδιο σκεπτικό.

Θα πρέπει να γίνει ένα menu με 3 επιλογές.

1)Α σκέλος,2)Β σκέλος,3)Έξοδος

 

Στο Α σκέλος θα πρέπει να επιλυθεί το πρόβλημα του ευσταθούς γάμου σε χρόνο Ο(Ν^2) με στοιχεία που δίνονται από ένα αρχείο prefsA.txt και τα αποτελέσματα να αποθηκεύονται σε ένα αρχείο outputA.txt.

Έχω υλοποιήσει το menu που οδηγεί στα αντίστοιχα σκέλη.

Όσον αφορά το σκέλος Α:

>
public static void openFileA(){    // Συνάρτηση με την οποία ανοίγουμε το αρχείο prefsA.txt
        try{
   FileInputStream fstream = new FileInputStream("prefsA.txt");
   DataInputStream in = new DataInputStream(fstream);
       BufferedReader br = new BufferedReader(new InputStreamReader(in));
   String strLine;
   //Διάβασμα Αρχείου Γραμμή προς Γραμμή
   while ((strLine = br.readLine()) != null)   {
     // Εκτύπωση περιεχομένου στην κονσόλα
     System.out.println (strLine);
   }
   //Κλείσιμο του input stream
   in.close();
   }catch (Exception e){//Εμφάνιση(Catch) exception αν υπάρχει
     System.err.println("Error: " + e.getMessage());
   }
    } 

Έχω κάνει την υλοποίηση για εκτύπωση στην οθόνη.Το πρόβλημα μου όμως είναι ότι πρέπει να πάρω τα στοιχεία από το αρχείου μου και να επιλύσω τον αλγόριθμο του ευσταθούς γάμου.Αυτό είναι και το ερώτημα μου:

Έχω ψιλοέτοιμο τον αλγόριθμο με στοιχεία όμως που δίνει ο χρήστης όμως πώς μπορώ να χρησιμοποιήσω τα στοιχεία του αρχείου γραμμή προς γραμμή αντί να τα δίνει ο χρήστης για να κάνω τις αντίστοιχες πράξεις;

[@kon_!]

Δίνω μια επεξήγηση για όσους δεν γνωρίζουν αλγόριθμο που να επιλύει το πρόβλημα του ευσταθούς γάμου.

Το πρόβλημα του ευσταθούς γάμου μπορεί να επιλυθεί με τον αλγόριθμο Gale-Shapley ο οποίος είναι ο εξής:

>
while(some man is free and hasn't proposed to every woman){
 choose such a man
 w = 1st woman on m's list to whom m has not yet proposed
 if(w is free)
    assign m and w to be engaged
 else if ( w prefers m to her fiance m')
    assign m and w to be engaged and m' to be free
 else
    w rejects m
}

Στο χαρτί είναι εύκολα επιλύσιμο.Ουσιαστικά είναι 2 πίνακες nxn(στην συγκεκριμένη εργασία 5x5) με τις προτιμήσεις ανδρών και γυναικών αντίστοιχα.Αν έχεις κάποιος ιδέα πώς μπορώ να το υλοποιήσω σε java θα με βοηθούσε πολύ.

[santeron]

Δυσκολεύομαι λίγο να απαντήσω γιατι είμαι στο ipod αλλά ο αλγόριθμος μοιάζει με σενάριο τρόμου για άνδρες :Ρ

Θα το κοιτάξω σε λίγο που θα πάω σπίτι...

 

 

Sent from my iPod touch using Insomnia

[@kon_!]

@santeron Ευχαριστώ ρε φίλε.Θα είμαι online οπότε στείλε ό,τι ώρα μπορέσεις.

[santeron]

Αρχικά το input αρχείο με τι μόρφη έχει αποθηκευμένα τα δεδομένα; Για να διαβάσεις το αρχείο υπάρχει ένα tutorial εδώ. Λογικά θα κάνεις stringVariable.split(",") και στο char θα βάλεις τον χαρακτήρα που θα χωρίζει τα δεδομένα μεταξύ τους (πχ. "santeron,25,athens") το κόμμα είναι ο χαρακτήρας που τα χωρίζει. Αυτό θα σου παράγει ένα String[] array και μετά θα παίρνεις κάθε τιμή αντίστοιχα για εκεί που το θες πχ.

>name = input[0];
age = input[1]
city = input[2]

Δεν ξερω αν κατάλαβες τίποτα, πες μου αυτύ που σε ρώτησα, πάλεψε το και λίγο και ξαναρώτα

[@kon_!]

Ευχαριστώ για την απάντηση ρε φίλε.Τώρα είδα την απάντησή σου.Κατάλαβα τι εννοείς και νομίζω ότι είναι σωστό το σκεπτικό.

Αριθμοί μέσα σε αρχείο είναι.Είναι σε μορφή πίνακα με κενά ανάμεσά τους.Για να σου δείξω ακριβώς είναι:

>
5

4 5 3 2 1
1 3 2 4 5
2 5 3 4 1
1 4 3 2 5
4 3 2 1 5

5 4 3 2 1
3 4 5 2 1
3 4 5 2 1
4 5 3 2 1
1 4 3 2 5

Ο πρώτος αριθμός είναι ο αριθμός των ανδρών/γυναικών που είναι ο ίδιος.

Και από κάτω είναι 2 5x5 πίνακες με τις προτιμήσεις ανδρών και γυναικών αντίστοιχα.

[santeron]

Ok οπότε το πρώτο "5" θα το κάνεις read πριν από το loop για να πάρεις τον αριθμό των ανδρών γυναικών και θα αφήσεις μία γραμμή. Μετά θα διαβάσεις την πρώτη γραμμή του πίνακα άρα θα έχεις ένα String newLine = "4 5 3 2 1". Χρησιμοποιώντας το split με χαρακτήρα ελέγχου το κενό θα πάρεις ένα String[] = {"4","5","3","2","1"}. Θα κάνεις κάθε τιμή του String convert σε int και θα τα βάλεις αντίστοιχα σε ένα int[] array. Θα κάνεις τις δουλειές που χρειάζεται και μετά επόμενη γραμμή του πίνακα κ.ο.κ.

[virxen75]

τι σημαίνει το κάθε στοιχείο της γραμμής που διαβάζεις ανά περίπτωση?

[@kon_!]

@santeron Πώς εννοείς το δίαβασμα πριν το loop.Και δεν έχω καταλάβει πως γίνεται να βάζω σε μεταβλητή την κάθε γραμμή.

@virxen75 Λοιπόν:

Στον 1ο πίνακα έχουμε τις προτιμήσεις των ανδρών από την καλύτερη στην χειρότερη.Δηλαδή:

1ος ανδρας - Καλύτερη προτίμηση: 4η γυναίκα , Χειρότερη προτίμηση: 1η γυναίκα κ.ό.κ

 

Στον 2ο πίνακα έχουμε τις προτιμήσεις των γυναικών από την καλύτερη στην χειρότερη.Δηλαδή:

1η γυναίκα - Καλύτερη προτίμηση: 5ος άνδρας , Χειρότερη προτίμηση: 1ος άνδρας κ.ό.κ

[santeron]

@santeron Πώς εννοείς το δίαβασμα πριν το loop.Και δεν έχω καταλάβει πως γίνεται να βάζω σε μεταβλητή την κάθε γραμμή.

Εννοώ ότι θα κάνεις readLine πριν μπεις στο loop. Είναι κάτι που πρέπει να γίνει μόνο στην αρχή. Μία φορά για το "5" και μία φορά για την κενή γραμμή ώστε να φτάσεις στο σημείο που ξεκινάνε τα νούμερα.

 

>while ((strLine = br.readLine()) != null)   {
     // Εκτύπωση περιεχομένου στην κονσόλα
     System.out.println (strLine);
   }

Στον κώδικα που έβαλες στην αρχή έχεις αυτό. Με την εντολή br.readLine() διαβάζεις μία γραμμή του αρχείου σου και την αποθηκεύεις στην μεταβλητή strLine το οποίο είναι ένα String. Αν γράψεις String[] arrayName = strLine.split(" "); θα κόψει το String strLine όπου έχει κενό και θα αποθηκεύσει το κάθε κομμάτι του στο array. Οπότε θα κάνει το String "1 2 3 4 5" --> {"1","2","3","4","5"}. Για να προσπελάσεις το κάθε αντικείμενο του array χρησιμοποιείς τον δείκτη του (index) οπότε χρησιμοποιώντας arrayName[3] θα έχεις την τιμή "4" (πρόσεχε τα array ξεκινάνε από το index 0).

 

Πιστεύω ότι αν κατάλαβες την λογική μπορείς να συνεχίσεις και μόνος σου

[virxen75]

συμπλήρωσε και προσάρμοσε τον πιο κάτω κώδικα στις ανάγκες σου.

 

>
import java.util.ArrayList;
public class Testx1{
private ArrayList<Woman> women;
class Woman{
	public ArrayList<Integer> choice;
	public Woman(String choices){
		choice=new ArrayList<Integer>();
		String temp[]=choices.split(" ");
		for (int i=0;i<temp.length;i++){
			try{
				choice.add(Integer.parseInt(temp[i]));
			}catch(NumberFormatException e){
			}
		}
	}
	public void printChoices(){
		System.out.println("\nchoices");
		for (int temp:choice)
			System.out.println(temp);

	}
	public int howManyChoices(){
		return choice.size();
	}
	public int getChoiceNo(int a){
		if (a>=howManyChoices() || a<0)
			return -1;
	    return choice.get(a);
	}
}
public Testx1(){
	women=new ArrayList<Woman>();
	Woman woman1=new Woman("5 4 3 2 1");
	woman1.printChoices();
	women.add(woman1);
 	Woman woman2=new Woman("3 4 5 2 1");
	woman2.printChoices();
	women.add(woman2);	
}
public static void main(String args[]){
	new Testx1();
}
}

[@kon_!]

@santeron @virxen75 Σας ευχαριστώ πολύ για τις απαντήσεις σας!Θα τις κοιτάξω και θα σας πω τα αποτελέσματα!

 

Έκανα το εξής:

>
int count=0;
   while ((strLine = br.readLine()) != null)   {
          prefer = strLine.split(" ");
          count++;
         }

για να δοκιμάσω αν μου τα αποθηκεύει σε πίνακα.Αν βάλω να εκτυπώνει τα αποτελέσματα όμως μου βγάζει λάθος.Την μεταβλητή prefer την δήλωσα στην αρχή της main ως global.Δεν καταλαβαίνω γιατί δουλεύει λάθος.Το σκεπτικό μου είναι ότι δηλώνω μια μεταβλητή count η οποία μπαίνοντας στην loop με το while μετράει τις γραμμές και αποθηκεύει ουσιαστικά το κάθε String splitαρισμένο σε κάθε γραμμή.Καμία λύση;

[virxen75]

αν συνδυάσεις τον κώδικα που σου έστειλα με τον δικό σου δεν θα έχεις προβλήματα.

Στείλε όλο τον κώδικα σου για περαιτέρω βοήθεια

[@kon_!]

@virxen75 Δεν έχω καταλάβει πως θα συνδυάσω τον δικό σου κώδικα με τον δικό μου.Το θέμα είναι ότι πρέπει να οι προτιμήσεις των ανδρών σε έναν δισδιάστατο πίνακα και των γυναικών σε έναν άλλον δισδιάστατο πίνακα.Τον κώδικα για την υλοποίηση του ευσταθούς γάμου τον έχω έτοιμο για στοιχεία δωσμένα από πληκτρολόγιο.

[virxen75]

αφού το θες με πίνακες κάνε το έτσι

 

>
import java.util.ArrayList;
import java.io.*;

public class Testx1{
 private int[][] women,men;
 private int N;
 
 private ArrayList<Integer> getChoices(String choices){
		ArrayList<Integer> choice=new ArrayList<Integer>();
		String temp[]=choices.split(" ");
		for (int i=0;i<temp.length;i++){
			try{
				choice.add(Integer.parseInt(temp[i]));
			}catch(NumberFormatException e){
			}
		}
		return choice;
	}

public Testx1(){
   try{
   	FileInputStream fstream = new FileInputStream("prefsA.txt");
   	DataInputStream in = new DataInputStream(fstream);
       BufferedReader br = new BufferedReader(new InputStreamReader(in));
   	String strLine;
   	//Διάβασμα Αρχείου Γραμμή προς Γραμμή
   	strLine = br.readLine();//διαβάζω την 1η γραμμή του αρχείου που είναι ο αριθμός των ανδρών-γυναικών
   	try{
   		N=Integer.parseInt(strLine);//δοκιμάζω να κάνω ακέραιο αυτό που διάβασα από το αρχείο
   		strLine = br.readLine();//διαβάζω την κενή γραμμή του αρχείου
   	}catch(NumberFormatException e){//δεν είναι αριθμός το πρώτο στοιχείο του αρχείου
   		System.out.println("error reading file!");
   		System.exit(1);
   	}
   	if (strLine==null || N<1){
   		System.out.println("error reading file!");
   		System.exit(1);
   	}
       System.out.println("έχει "+N+" γυναίκες και αντρες");
       women=new int[N][N];
       men=new int[N][N];
       for (int i=0;i<N;i++){//andres.....
       	strLine = br.readLine();
       	//..............κάνε κάτι και συ.........
       }
       strLine = br.readLine();//διαβάζει την κενή γραμμή του αρχείου
       for (int i=0;i<N;i++){//γεμίζει τον πίνακα των γυναικών με στοιχεία από το αρχείο
       	strLine = br.readLine();
       	ArrayList<Integer> choices=getChoices(strLine);
       	if (choices.size()!=N){
       		System.out.println("το αρχείο είναι σε λάθος μορφή!");
       		System.exit(1);
       	}
       	for (int j=0;j<choices.size();j++)
       		women[i][j]=choices.get(j);
       }        
   	//Κλείσιμο του input stream
   	in.close();
   	for (int i=0;i<N;i++){//εκτύπωση στοιχείων πίανακα γυναικών
   		for (int j=0;j<N;j++)
   			System.out.print(women[i][j]+",");
   		System.out.println("");
   	}
   	}catch (Exception e){//Εμφάνιση(Catch) exception αν υπάρχει
     		System.err.println("Error: " + e.getMessage());
   	}
   // }
		
}
public static void main(String args[]){
	new Testx1();
}
}