Άσκηση Java

[guitarist2]

Έχω την παρακάτω άσκηση και δεν τρέχει σωστά .Δίνω και τον κώδικα που έχω γράψει,καθώς και την main που δεν είναι έτοιμη.Την insert την έχω κάνει με 2 τρόπους και κανένας δεν τρέχει .Δεν πρέπει να χρησιμοποιήσω επανάληψη για την εισαγωγή νέου στοιχείου.

class PriorityQueue{
	private int capacity = 100;
	private int[] List;
	public PriorityQueue(){
		this.List = new int[100];
	}
	public PriorityQueue(int capacity){
		this.capacity=capacity;
		this.List = new int[capacity];
	}
	public int getcapacity(){
		return capacity;
	}
	public int[] getList(){
		return List;
	}
/*	public boolean insert(int number){
		boolean x = false;
		int temp;
		for(int i=0;i<capacity;i++){
			if(List[i] == 0){
				List[i] = number;
				x = true;
				break;
			}
		}
		for(int i=0;i>List.length;i++){
			for(int j=0;j>List.length;j++){
				if (List[i] < List[j+1]){
					temp = List[j+1];
					List[j+1] = List[i];
					List[i] = temp;
					break;
				}
			}
		}
		if(x == false){
			return false;
		}
		else{
			return true;
		}
	}*/
	private int counter=1;
	public boolean insert(int number){
		if(List[0]==0){
			List[0] = number;
			return true;
		}
		else{
			if(number <List[counter-1]){
				List[counter]=number;
				counter++;
				return true;
			}
			else{
				List[counter]=List[counter-1];
				List[counter-1]=number;
				counter++;
				return true;
			}
		}
	}
	public int getMax(){
		if(List[0] != 0){	
			return List[0];
		}
		else{
			return -1;
		}
	}
	public int extractMax(){
		int Max = List[0];
		List[0] = 0;
		for(int i=1;i<List.length;i++){
			List[i-1] = List[i];
		}
		return Max;
	}
	public boolean merge(PriorityQueue other){
		if (this.List.length+other.List.length > this.List.length){
			return false;
		}
		else{
			for(int i=0;i<List.length;i++){
				for(int j=0;j<other.List.length;j++){
				if(List[i] == 0){
					List[i] = other.List[j];
					break;
				}
			}			
		}
		return false;
	}
}


/*	public String toString(){
		String output = "";
		for(int i=0;i<List.length;i++){
			output = output+List[i]+"";
		}
		return output;
	}*/

class PriorityQueueTest
{
	public static void main(String[] args){
		PriorityQueue pq1 = new PriorityQueue();
		pq1.insert(10);
		pq1.insert(2);
		pq1.insert(12);
		
		System.out.println(pq1);
		
		PriorityQueue pq2 = new PriorityQueue();
		pq2.insert(12);
		pq2.insert(10);
		pq2.insert(2);		
		
		System.out.println(pq2);
		
		if (pq1.equals(pq2)){
			System.out.println("The two queues are the same!");
		}else{
			System.out.println("The two queues are NOT the same!");
		}
		
		System.out.println(pq1);
		System.out.println(pq2);
		 
		pq1.insert(5);
		System.out.println(pq1.extractMax());
		System.out.println(pq1.getMax());
		pq1.merge(pq2);
		System.out.println(pq1);
		
		pq2.insert(2); pq2.insert(5); pq2.insert(10); pq2.insert(12);
		if (pq1.equals(pq2)){
			System.out.println("The two queues are the same!");
		}else{
			System.out.println("The two queues are NOT the same!");
		}
		
	}
}

assignment1.pdf

[M2000]

Στην Insert σου έχει περρισέψει αυτό:

		for(int i=0;i<capacity;i++){
			if(List[i] == 0){
				List[i] = number;
				x = true;
				break;
			}
		}

Δεν υπάρχει λογική να γεμίζεις έναν πίνακα εκεί που πρέπει να κάνεις Insert.

 

 

Το κόλπο είναι ότι χρειάζεται να είναι ο μεγαλύτερος στην θέση 0. ο αμέσος επόμενος όμως δεν μας λέει που θα είναι! Επίσης λέει ότι η αναζήτηση θα γίνεται σε ίσους χρόνους, δηλαδή ανεξάρτητα από τα στοιχεία στο πίνακα.

Αυτό σημαίνει ότι συγκρίνεις με το στοιχείο στη θέση 0 το αλλάζεις αν χρειάζεται και το πάς στη πρώτη ελεύθερη θέση, άρα θες μια μεταβλητή top που δηλώνει την πρώτη ελεύθερη θέση. Το ζήτημα είναι ότι αν πάρεις τη βάση, δηλαδή αφαιρέσεις τον τωρινό μέγιστο, τότε θα πρέπει να πάρεις αυτόν που είναι στο top-1 και να κατέβεις μέχρι την βάση αλλάζοντας με τον μεγαλύτερο, οπότε στη βάση (θέση 0 μένει ο μεγαλύτερος). Άρα τρως χρόνο στην αφαίρεση του τρέχοντα μέγιστου, όχι στην εισαγωγή.

Για το merge απλά αλλάζεις τις δυο βάσεις, αν χρειάζεται, και μετά αντιγράφεις στον A.top έως A.top +B.top-1 (μειον ένα γιατί στο Β.top έχουμε κενό)

 

Προφανώς δεν ζητάει η λίστα να είναι ταξινομημένη. (αν το ζήταγε τότε θα είχαμε διαφοροποίηση στην εισαγωγή, ανάλογα το μέγεθος της λίστας)

[guitarist2]

Στην Insert σου έχει περρισέψει αυτό:

		for(int i=0;i<capacity;i++){
			if(List[i] == 0){
				List[i] = number;
				x = true;
				break;
			}
		}

Δεν υπάρχει λογική να γεμίζεις έναν πίνακα εκεί που πρέπει να κάνεις Insert.

 

 

Το κόλπο είναι ότι χρειάζεται να είναι ο μεγαλύτερος στην θέση 0. ο αμέσος επόμενος όμως δεν μας λέει που θα είναι! Επίσης λέει ότι η αναζήτηση θα γίνεται σε ίσους χρόνους, δηλαδή ανεξάρτητα από τα στοιχεία στο πίνακα.

Αυτό σημαίνει ότι συγκρίνεις με το στοιχείο στη θέση 0 το αλλάζεις αν χρειάζεται και το πάς στη πρώτη ελεύθερη θέση, άρα θες μια μεταβλητή top που δηλώνει την πρώτη ελεύθερη θέση. Το ζήτημα είναι ότι αν πάρεις τη βάση, δηλαδή αφαιρέσεις τον τωρινό μέγιστο, τότε θα πρέπει να πάρεις αυτόν που είναι στο top-1 και να κατέβεις μέχρι την βάση αλλάζοντας με τον μεγαλύτερο, οπότε στη βάση (θέση 0 μένει ο μεγαλύτερος). Άρα τρως χρόνο στην αφαίρεση του τρέχοντα μέγιστου, όχι στην εισαγωγή.

Για το merge απλά αλλάζεις τις δυο βάσεις, αν χρειάζεται, και μετά αντιγράφεις στον A.top έως A.top +B.top-1 (μειον ένα γιατί στο Β.top έχουμε κενό)

 

Προφανώς δεν ζητάει η λίστα να είναι ταξινομημένη. (αν το ζήταγε τότε θα είχαμε διαφοροποίηση στην εισαγωγή, ανάλογα το μέγεθος της λίστας)

 

Ο υπόλοιπος κώδικας είναι σωστός;

[groot]

Γιατί [ ] σε Java; Χρειάζεσαι fixed elements vector; Που δεν θα αλλάζει ποτέ; 

 

 

Αντί για int [ ] βάλε List interface και αρχικοποίησέ το με ArrayList. Εάν θέλεις queue και δεν θες να το κάνεις με την queue της Java, πάλι ο array [ ] είναι λάθος επιλογή. 

[M2000]

	public int extractMax(){
		int Max = List[0];
		List[0] = 0;
		for(int i=1;i<List.length;i++){
			List[i-1] = List[i];
		}
		return Max;

Εδώ μπορείς αντί να τραβάς στο i-1 το i να πάρεις αυτό που είναι στο Top-1 (ή Level, μάλλον Level Καλύτερα, είναι η στάθμη του πίνακα) και να συγκρίνεις με τον αμέσως παρακάτω και να πάρεις το μέγιστο από αυτούς και να πας μέχρι τον 1 και μετά ότι μένει το βάζεις ως Max στη 0. Έτσι όπως το έχεις βάζεις στην List[0] ό,τι να είναι! Αν υποθέσουμε ότι έχεις ήδη ταξινομήσει τους αριθμούς τότε δεν είναι μεν ό,τι να είναι, αλλά για να το κάνεις αυτό σημαίνει ότι δεν έχεις σταθερό χρόνο εισαγωγής.

 

 

O Groot βαρέθηκε να διαβάσει το Pdf.. Το Arraylist το έχει απαγορέψει..ο καθηγητής.

[groot]

Η extract_max είναι λάθος... γενικά έχεις αρκετά θέματα. Θα πρότεινα να παραθέσεις τα λάθη που παίρνεις από το IDE σου. 

Στην ίδια method, αντί για loop καλύτερα array copy... γενικά το μόνο που έχεις αλλάξει από C είναι το συντακτικό και τίποτα άλλο. 

[guitarist2]

Γιατί [ ] σε Java; Χρειάζεσαι ; Που δεν θα αλλάζει ποτέ; 

 

 

Αντί για int [ ] βάλε List interface και αρχικοποίησέ το με ArrayList. Εάν θέλεις queue και δεν θες να το κάνεις με την queue της Java, πάλι ο array [ ] είναι λάθος επιλογή. 

Η άσκηση λέει να μην χρησιμοποιησω ArrayList και δεν εχω διδαχθει ακομα fixed elements vector

[M2000]

	private int counter=1;
	public boolean insert(int number){
		if(List[0]==0){
			List[0] = number;
			return true;
		}
		else{
			if(number <List[counter-1]){
				List[counter]=number;
				counter++;
				return true;
			}
			else{
				List[counter]=List[counter-1];
				List[counter-1]=number;
				counter++;
				return true;
			}
		}
	}

Εδώ η counter ταιριάζει με τη Level ή top, αλλά θα πρέπει να ελέγχεις το στοιχείο 0. Σε αυτό σου όρισε ο καθηγητής να έχεις το Maximum. Άρα η εισαγωγή θα δίνει εκεί αν αυτός που βάζεις είναι μεγαλύτερος (εφόσον δεν είναι ο counter=0, αν είναι το βάζεις άμεσα, δεν κάνεις σύγκριση, αυτό το πέτυχες)

 

άρα θες if(number <List[0]){ τότε στέλνεις στο counter ++ αλλιώς στέλνεις τον List[0] και μετά βάζεις στην θέση του τον Number.

 

[groot]

Ο [ ] είναι fixed. 

 

Σε κάθε περίπτωση... γράφεις C. Π.χ. αντί για "κλασικό" for, χρησιμοποίησε for each. Το shifting που κάνεις (στην extractMax) μπορείς να το κάνεις με το array copy ως εξής:

 

 

public int extractMax() {
    int toReturn = List[0];
    System.arraycopy(List, 1, List, 0, List.length - 1);
    return toReturn;
}

και το extract δεν είναι σωστό... popTop είναι καλύτερο.

Γενικά, θες να γράψεις τι υποτίθεται ότι θέλεις να κάνει η queue που έχεις φτιάξει; Γιατί, π.χ., εάν κανείς σου δώσει 101 για insert θαρρώ ότι θα πάρει error πίσω.

Τέλος, εάν με 0 σημαίνει ότι το element είναι empty τότε μπορείς να κάνεις:

public boolean insert(int number) {
  this.List[Ints.indexOf(this.List, 0)] = number;
  return true;
}

[guitarist2]

 

Ο [ ] είναι fixed. 

 

Σε κάθε περίπτωση... γράφεις C. Π.χ. αντί για "κλασικό" for, χρησιμοποίησε for each. Το shifting που κάνεις (στην extractMax) μπορείς να το κάνεις με το array copy ως εξής:

public int extractMax() {
    int toReturn = List[0];
    System.arraycopy(List, 1, List, 0, List.length - 1);
    return toReturn;
}

 

και το extract δεν είναι σωστό... popTop είναι καλύτερο.

 

Γενικά, θες να γράψεις τι υποτίθεται ότι θέλεις να κάνει η queue που έχεις φτιάξει; Γιατί, π.χ., εάν κανείς σου δώσει 101 για insert θαρρώ ότι θα πάρει error πίσω.

 

Τέλος, εάν με 0 σημαίνει ότι το element είναι empty τότε μπορείς να κάνεις:

 

public boolean insert(int number) {
  this.List[Ints.indexOf(this.List, 0)] = number;
  return true;
}

Έχω θέμα γιατί τις εντολές που αναφέρεις πρώτη φορά τις βλέπω (Arraycopy και Ints.)

[CrimsonSky_gr]

Καταλαβαινω οτι ειναι για εκπαιδευτικους σκοπους, αλλα πραγματικα οποιος σας εβαλε να γραψετε ουρα προτεραιοτητας αλλα ακομα δεν εχει διδαξει arraylist ειναι απαραδεκτος..μηπως εσυ εχασες καποια διαλεξη? Επισης ισχυει αυτο που σου λενε τα παιδια οτι γραφεις σαν να γραφεις c/c++

private int counter=1;

public boolean insert(int number){

if(List[0]==0){

List[0] = number;

return true;

}

else{

if(number <List[counter-1]){

List[counter]=number;

counter++;

return true;

}

else{

List[counter]=List[counter-1];

List[counter-1]=number;

counter++;

return true;

}

}

Θα σου ελεγα να διαβασεις μονος σου απο το reference της oracle τι συναρτησεις σου δινει η arraylist και να κατσεις να ξανασκεφτεις το ολο προβλημα, ωστε να μαθεις κατι ουσιαστικο.

Το κομματι κωδικα αυτο δεν εχει λογο υπαρξης σε java

[defacer]

Με μια γρήγορη ματιά έχεις πολλά θέματα με την άσκηση. Και όπως γίνεται συνήθως, τα προβλήματά σου ξεκινάνε από το ότι έγραψες κώδικα πριν σκεφτείς τι θα πρέπει να κάνει. Πρέπει σταδιακά να μάθεις να το κάνεις αλλιώς.

 

Παράδειγμα.

 

Η εκφώνηση λέει πως το μεγαλύτερο στοιχείο πρέπει να είναι στο μηδέν. Αυτό φαίνεται και στην extractMax:

    public int extractMax(){
        int Max = List[0];
        List[0] = 0;
        for(int i=1;i<List.length;i++){
            List[i-1] = List[i];
        }
        return Max;
    }

Τι κάνεις εδώ; Στην ουσία "βγάζεις" το πρώτο στοιχείο από τον πίνακα και το επιστρέφεις. Γιατί το πρώτο; Γιατί αυτό υποτίθεται είναι το μεγαλύτερο. Όμως, αφού καλέσεις την extractMax() τι θα γίνει αν την ξανακαλέσεις στο καπάκι; Θα βγάλεις πάλι το (δεύτερο πλέον) μεγαλύτερο στοιχείο; Όχι. Γιατί; Γιατί η extractMax() δε φρόντισε να παραμείνει σε ισχύ το invariant της κλάσης σου, ήτοι "πάντα το μεγαλύτερο στοιχείο στην πρώτη θέση".

 

 

 

Διάβασε τι είναι invariant και κατανόησέ το. Ξέροντας τι είναι, την επόμενη φορά που θα έχεις εργασία θα έχεις τη δυνατότητα να  αναγνωρίσεις τα invariants που περιγράφει η εκφώνηση και τα έχεις στο μυαλό σου. Αυτό και μόνο θα σε βοηθήσει να καταλάβεις ότι πας να κάνεις λάθη πριν τα κάνεις.

 

 

 

Επιπλέον φυσικά δε βλέπω πουθενά να ελέγχεις αν είναι άδεια η queue για να επιστρέψεις -1.

 

Θα σε συμβούλευα να γράψεις μία μία και πολύ προσεκτικά τις μεθόδους αφού πρώτα κάτσεις να σκεφτείς τις συνέπειες του κώδικα που γράφεις (όπως παραπάνω: τι θα γίνει αν την καλέσεις με άδεια queue? τι θα γίνει αν την καλέσεις δύο φορές συνέχεια?).

[guitarist2]

Καταλαβαινω οτι ειναι για εκπαιδευτικους σκοπους, αλλα πραγματικα οποιος σας εβαλε να γραψετε ουρα προτεραιοτητας αλλα ακομα δεν εχει διδαξει arraylist ειναι απαραδεκτος..μηπως εσυ εχασες καποια διαλεξη? Επισης ισχυει αυτο που σου λενε τα παιδια οτι γραφεις σαν να γραφεις c/c++

private int counter=1;

public boolean insert(int number){

if(List[0]==0){

List[0] = number;

return true;

}

else{

if(number <List[counter-1]){

List[counter]=number;

counter++;

return true;

}

else{

List[counter]=List[counter-1];

List[counter-1]=number;

counter++;

return true;

}

}

Θα σου ελεγα να διαβασεις μονος σου απο το reference της oracle τι συναρτησεις σου δινει η arraylist και να κατσεις να ξανασκεφτεις το ολο προβλημα, ωστε να μαθεις κατι ουσιαστικο.

Το κομματι κωδικα αυτο δεν εχει λογο υπαρξης σε java

Ξέρω Arraylist ,άπλα η άσκηση ζητάει να μην χρησιμοποιησουμε 

[CrimsonSky_gr]

Τωρα ειδα το pdf..

>>Τεχνικές Αντικειμενοστρεφούς Προγραμματισμού

>>java

>>Σημείωση: Στο μάθημα των Δομών θα μάθετε μια πολύ καλύτερη υλοποίηση για την Ουρά Προτεραιότητας η οποία

υποστηρίζει τις ίδιες λειτουργίες αλλά πιο γρήγορα.

Kappa

Ελα τουλαχιστον ξερει ο καθηγητης οτι σας βαζει χαμαλοδουλεια χωρις λογο, ακομα και η εκφωνηση φωναζει c++...ηξερα απο φιλους οτι στα γιαννενα ειστε λιγο alternative και ξεκινατε τη σχολη με python κλπ αλλα παραπαει. Θα κανω επεξεργασια για γνωμη πανω στον κωδικα/ λυση αργοτερα γιατι δεν ειμαι στο πσ

[groot]

Τώρα είδα το pdf...

 

Είσαι μακριά ακόμα από την άσκηση.....!!!! Κανονικά η getMax πρέπει να επιστρέφει πάντα το [0], έχεις sorting, έχεις insert.. έχεις, έχεις.

 

Δεν είναι πολύ γράψιμο... αλλά έχει ψάξιμο!