THMMY.gr

Παιδιά μήπως ξέρει κανείς πως θα χρησιμοποιήσουμε το Hashmap για να ελέγξουμε την ορθότητα του πίνακα Sudoku; Έστω κάποια συμβουλή ή link σχετικά με το mapping- hashmap.

ευχαριστώ εκ των προτέρων

Για να καταλαβεις τι παιζει μπες στο eTHMMY στο υλικο μαθηματος των δομων δεδομενων και δες την main συναρτηση που εχει φτιαξει ο Ψωμοπουλος...
Προσοχη αυτη ειναι η Main βαζει ο Ψωμοπουλος στο προγραμμα μας (περιπου) απλα για να καταλαβεις τι πρεπει να κανεις!! Εσυ θα την ενσωματωσεις μονο για να κανεις τα τεσταρισματα σου και θα την βγαλεις πριν παραδοσεις την εργασια!

Με το hashmap παντως δεν ασχολεισαι...
εσυ θεωρεις οτι εχεις δεδομενο ενα πινακα πχ sudoku[][] και δουλευεις με αυτον στις printsudokumatrix και checksudokumatrix...
ολα τα αλλα τα αφηνεις ανεπαφα.

Συμβουλη: χρησιμοποιησε JBuilder.

Υποννοείς δηλαδή πως δε πρέπει να χρησιμοποιήσουμε όλες τις μεθόδους (abstract) του Ψωμόπουλου? Διότι έχει την importSudokumatrix() η οποία απ’ότι κατάλαβα αντιστοιχεί κάθε στοιχείο του πίνακα σε ένα string-κλειδί. Φαντάζομαι αυτό το κάνει για να μας υποχρεώσει έτσι να κάνουμε έλεγχο ορθότητας(μέσω μοναδικότητας κλειδιών).Ειδάλλως μέσα από έλεγχο αθροισμάτων γραμμής,σειράς κτλ. μπορεί να ελεγχθεί ο πίνακας εύκολα.

δηλαδη: αφού έχουμε την checksudokumatrix() για τον έλεγχο, γιατί ανακατεύεται το hashmap? και... τι ρόλο παίζει η abstract υπερκλάση του καθηγητή? Προφανώς σε αυτό το μοτίβο δε μας υποχρεώνει να γράψουμε το πρόγραμμα...?

κάποια σίγουρη άποψη?

την abstract κλαση θα την κανεις extend.
Οταν κανεις μια abstract κλαση extend πρεπει να υπερβεις(?) - override ΟΛΕΣ τις μεθοδους της εκτος και αν εχει Adaptor(εδω δεν εχει).

αν κανεις extend στο jbuilder θα σου βγαλει ενα κλειδακι στα πλαγια θα το πατησεις και θα κανεις implement method!
ετσι θα σου γραψει αυτο ΟΛΕΣ τις αφηρημενες μεθοδους, μεταβλητες, κλασεις, οτιδηποτε που πρεπει να κανεις override.

αν δεν χρησιμοποιεις jbuilder τοτε πρεπει απλα να τις γραψεις με τα ιδια ονοματα και ορισματα!
ΔΕΝ ασχολεισαι με importsudokumatrix, hashmaps κλπ!

στελνω την main που πρεπει να γραψετε για να κανετε τον ελεγχο του προγραμματος.

 public static void main(String[] args)
    {
        SimpleSudoku03 sudoku = new SimpleSudoku03();
        HashMap h = new HashMap();
        int[][] aMatrix = { {5, 3, 4, 6, 7, 8, 9, 1, 2}, {6, 7, 2, 1, 9, 5, 3,
                          4, 8}, {1, 9, 8, 3, 4, 2, 5, 6, 7}, {8, 5, 9, 7, 6, 1,
                          4, 2, 3}, {4, 2, 6, 8, 5, 3, 7, 9, 1}, {7, 1, 3, 9, 2,
                          4, 8, 5, 6}, {9, 6, 1, 5, 3, 7, 2, 8, 4}, {2, 8, 7, 4,
                          1, 9, 6, 3, 5}, {3, 4, 5, 2, 8, 6, 1, 7, 9}
        };
        String[] key = {"1"};
        h.put(key[0], aMatrix);
        sudoku.importSudokuMatrix(h, key);
        sudoku.printSudokuMatrix();
        if (sudoku.checkSudokuMatrix() == 1) System.out.println(
                "Ο πινακας ΕΙΝΑΙ ενας πινακας SUDOKU!!  Γιούπιιι!!");
        else if (sudoku.checkSudokuMatrix() == 0) System.out.println(
                "Ο πινακας ΔΕΝ ειναι πινακας SUDOKU.. αλλα και παλι Γιούπιιι!!! γιατι δούλεψε!!!");
    }
}



οποτε εσυ απο εκει και περα δουλευεις τις check kai print...
Ως πινακα σου εχεις τον sudokuMatrix[][] που εχει περιληφθει στην αφηρημενη κλαση (αλλα δεν ειναι αφηρημενος και γιαυτο δεν χρειαζεται να δηλωθει στην δικια σου κλαση)!

Ναι οκ, στην ουσία η ερώτησή μου είναι τι κάνουν οι παρακάτω γραμμές


String[] key = {"1"};
        h.put(key[0], aMatrix);
        sudoku.importSudokuMatrix(h, key);

 Εδώ δεν αντιστοιχείς όλες τις τιμές του πίνακα στο κλειδί «1»? Αλλά αυτό που χρησιμέυει? Απότι διαβάζω το hashmap χρησιμοποιείται σε αναζήτηση, εδώ πως κολλάει δε καταλαβαίνω  :-[

Θα σε γελασω... :)
ισως το κανεις εσυ ετσι εδω για να σου δουλεψει αλλα ο Ψωμοπουλος μαλλον θα αντιστοιχει αλλο κλειδι στον καθενα!

Λοιπόν παιδιά, πήγα να κάνω την εργασία σουντόκου, αλλά όταν έκανα

import gr.auth.ee.dsproject.sudoku.abstractClasses.Abstr actSimpleSudoku;    ή
public class SimpleSudoku01 extends AbstractSimpleSudoku {

δε μου αναγνώριζε την AbstractSimpleSudoku..
και το πακέτο gr.auth.ee.dsproject.sudoku.abstractClasses.Abstr actSimpleSudoku το εμφάνιζε με γκρι γράμματα, σαν να μη το "βλέπει"..

Μέχρι που έκανα αριστερό κλικ (στο project pane) πάνω στο πακετάκι abstractClasses(που αρχικά μου το εμφάνιζε με τα γκρι γράμματα που είπα πριν), και έκανα new class, δήλωσα στο παράθυρο που βγαίνει το package  gr.auth.ee.dsproject.sudoku.abstractClasses
και έπειτα στην "έτοιμη" κλάση που βγάζει ο jbuilder έκανα copy-paste την κλάση του Ψωμόπουλου..
και από τότε το αναγνωρίζει..

Και σεις κάτι τέτοιο κάνατε?
Ρωτάω γιατί δεν έχω καταλάβει ακόμη πως θα γίνει η εξέταση..
Θα ρίξουν στο pc τους το φάκελο με το prοject που δημιουργήσαμε και υποτίθεται θα πρέπει να δουλέψει με τη μια χωρίς καμιά ρύθμιση?

εκανες νεο προτζεκτ?

μετα αφου σου εμφανισει τον φακελο του προτζεκτ εκει που επελεξες να το σωσεις θα αντιγραψεις τα src kai doc που δινει ο Ψωμοπουλος...
θα κανεις ενα refresh sto project pane...και λογικα θα στα εμφανισει.
θα κανεις new class θα την ονομασεις SimpleSudokuXX και για πακετο θα βαλεις  gr.auth.ee.dsproject.sudoku

μετα το Import θα σου δουλεψει
για την ακριβεια εγω δεν εβαλα gr.auth.ee.dsproject.sudoku.abstractClasses.Abstr actSimpleSudoku; αλλα gr.auth.ee.dsproject.sudoku.abstractClasses.*;

Απ'ότι βλέπω, ο jbuilder αντιγράφει αυτόματα τις abstract κλασεις (που κάνεις import) στο φάκελο crs (αλλά όχι το doc) οπότε οκ, δεν υπάρχει πρόβλημα στη μεταφορά..
Πιο απλό πάντως είναι αυτό που λες..

σου δουλεψε δλδ?

Ναι, δούλεψε, γι'αυτό αντέγραψε αυτόματα τις abstract classes στον crs..
Όταν απλά έριξα την κλάση του Ψωμόπουλου στο σκληρό δε δούλευε, αλλά όταν την έβαλα σε ένα δικό της project(οπότε δήλωσα και το package της στον project wizard) δούλεψε κανονικά(είδε το package που πρέπει να κάνουμε import), και τότε (μάλλον) έκανε και την αντιγραφή στο crs..

Στην εργασία για το sudoku ζητάει να βρεθεί η πολυπλοκότητα του αλγορίθμου, όμως ο πίνακας για το sudoku δεν θα είναι ο κλασσικός 9χ9? Οπότε από που θα βρούμε το n για τον υπολογισμό της πολυπλοκότητας? Ελπίζω να έγινα κατανοητός γιατί τα έγραψα λίγο ότι να'ναι!!

Nαι, 9x9 είναι ο πίνακας, οπότε n=9
Ή τουλάχιστο έτσι νομίζω..

Αχά! Άρα τελικά δεν θα βγάλουμε κάποια Ο(n) αλλά μια σταθερά, σωστά?
πχ n^4=9*9*9*9=6561 ?

Η εκφώνηση ζητάει την πολυπλοκότητα, όσον αφορά το πλήθος των βημάτων.

Οπότε εσύ στους υπολογισμούς που θα κάνεις, ΔΕ θα αντικαταστήσεις το Ν με το 9, οπότε θα βγάλεις ένα πολυώνυμο. Και από αυτό το πολυώνημο σημασία έχει η τάξη του.

Σαν αποτέλεσμα σε αυτό το πχ θα δόσεις Ο(n^4)

(Με κάθε επιφύλαξη πάντα, έτσι?)

Στο παράδειγμα που έδωσα γιατι Ο(n^2) κι όχι O(n^4)? Συγνώμη αν γίνομαι κουραστικός αλλά είναι το μόνο που μου έχει μείνει για να αφιερωθώ επιτέλους στα σήματα!!

Sorry!!!

Λάθος βιασύνης!
Ο(n^4)

Παιδιά, είστε σίγουροι ότι η πολυπλοκότητα είναι Ο(n^4)? Εγώ διαφωνώ εν μέρει με αυτό.

Η πολυπλοκότητα σίγουρα θα προκύψει διαφορετική αν έχεις ακολουθήσει διαφορετικό αλγόριθμο για την εξέταση του sudoku! Πόσο την υπολογίζεις εσυ?(περιέργεια!)

Ναι, τελικά μετά από λίγη σκέψη, χαρτί και μολύβι, προέκυψε ότι βγαίνει n τετράγωνο. Πάντως νομίζω ότι όλοι οι φοιτητές χρησιμοποίησαν πάνω κάτω τον ίδιο αλγόριθμο. :)

ο οποιος ειναι?
εγω ξερω οτι αλλοι χρησιμοποιησαν αθροισματογινομενα...
αλλοι ενα boolean πινακακι μονοδιαστατο με 9 κουτια...(οπως εγω)...
εσεις τι χρησιμοποιησατε τελικα..
εμενα ο κωδικας της checkSudokuMatrix βγηκε 50 γραμμες που νομιζω ειναι αρκετα ικανοποιητικο (γεια σου τρικουπη με το συμαζεμα σου! )...
εκανε κανεις καμμια τρελη πατεντα να μας την πει να τον θαυμασουμε?

Εγώ θα διατυπώσω λίγο διαφορετικά την ερώτηση.

Τι συμβολίζει το n???

Μπορεί κανένα παλικάρι να ανεβάσει την εκφώνηση της εργασίας;

Χαιρετίσματα από τα ελληνικά στρατά...
Να κοιμάστε ήσυχοι!

Ο στρατιώτης Flo

ορίστε
εργασία μέρος Α

To n λογικά συμβολίζει την διάσταση του πίνακα (δεδομένου ότι είναι τετραγωνικός)

Δηλαδή μπορούμε να πούμε ότι ένας πίνακας Sudokou με 10 γραμμές θέλει περίπου 10^2=100 πραξεις για να επαληθευτεί. Έτσι δεν είναι???

Όχι! Απλά η τάξη ενός αλγορίθμου (Ο) σου δίνει ένα μέτρο σύγκρισης μεταξύ δύο αλγορίθμων και δεν μπορείς να βγάλεις συμπεράσματα αυτού του είδους.
Για παράδειγμα ένας αλγόριθμος τάξης n^4 θα είναι χειρότερος (θέλει περισσότερο χρόνο εκτέλεσης) από έναν τάξης n^2.
Ο αριθμός των εντολών που χρειάζεται δεν είναι 100. Για να τον βρεις θα πρέπει να κάνεις πράξεις, οι οποίες θα καταλήγουν σε μία μορφή πχ 45n^2 + 10n +2345. Στην παράσταση αυτή εάν βάλεις n=10 θα βρεις τον αριθμό των εντολών που χρειάζονται για να επαληθευτεί ο πίνακας.

To παραπάνω είναι από την εργασία..
Ο πραγματικός αριθμός των βημάτων δεν είναι Ν².
Η πολυπλοκότητα είναι απλά ο βαθμός του πολυωνύμου που δίνει τον αριθμό των βημάτων.
Και μάλιστα το πολυώνυμο που βγάλαμε σε αυτή την εργασία για τον αριθμό των βημάτων είναι πολύ.."στο περίπου"
Για μικρό αριθμό πράξεων ίσως και να μην ισχύει αυτό (ή να ισχύει αλλά να μην έχει πρακτικό νόημα).
Σίγουρα όμως η πολυπλοκότητα σου δείχνει πως συμπεριφέρεται χρονικά ο αλγόριθμός σου όταν Αυξάνεται το Ν.

Εννοώ ότι για μικρό πίνακα να συμφέρει πολυπλοκότητα Ν⁴, αλλά όσο το Ν μεγαλώνει φυσικά γίνεται ασύμφορος ο αλγόριθμος, και προτιμάς κάποιον με μικρότεη πολυπλοκότητα. (προσωπική εικασία, ρίχτε ντομάτες αν θέλετε :) )

Αν κάποιος έχει διαφορετική άποψη θα ήταν ενδιαφέρον να την έλεγε..

Η μελέτη της πολυπλοκότητας αναφέρεται στη γενικότερη περίπτωση όπου τότε το Ν->οο 
Για να δεις ποιος αλγόριθμος είναι καλύτερος για συγκεκριμένο αριθμό,αρκεί να συγκρίνεις τις γραφικές παραστάσεις των πολυπλοκοτήτων των 2 αλγορίθμων.Και πάλι τα πράγματα όμως είναι σχετικά για την περιπτωση των Ο() πολυπλοκοτήτων μιας που αυτές δίνουν το άνω όριο για τον χρόνο εκτέλεσης των αλγορίθμων(στην περίπτωση δλδ που θα εκτελεστούν όλες οι εντολές).Για να συγκρίνεις 2 αλγόριθμους με συγκεκριμένο μέγεθος εισόδου,πρέπει να κάνεις μελέτη μέσης περίπτωσης και ακόμα καλύτερα να υπολογίζεις το χρόνο εκτέλεσης για διάφορες εισόδους.

Πολύ ωραία η παρατήρηση ::)

Και γω να προσθέσω το εξής παράδειγμα:

Αν ένα πρόγραμμα ελέγχει τυχαίους πίνακες nxn για το αν είναι sudoku ή όχι τότε η αντιμετώπιση της πολυπλοκότητας θα είναι εντελώς διαφορετική στην περίπτωση που ήλεγχε πίνακες οι οποίοι συμπληρώθηκαν από μία ομάδα φοιτητών του ΤΗΜΜΥ.

Με πιάνετε; :-*

Εγω άλλο ήθελα να τονισω με τις ανόητες ερωτήσεις μου για το n.

Το n δε μπορεί να πάρει κάθε ακέραια τιμή. Για το n ισχύει n= k^2 , όπου k ο αριθμός των γραμμών των υποπινάκων του Sudoku, k?Z. Οπότε η πολυπλοκότητα θα μπορούσε να πει κανείς ότι είναι n^2 =(k^2)^2=k^4

Βασικά εξαρτάται από τον τρόπο με τον οποίο ορίζεις το n. Νομίζω και οι δύο απαντήσεις είναι σωστές, εάν φυσικά η κάθε μία τεκμηριωθεί σωστά.
Πάντως σε γενικές γραμμές λέμε το ίδιο πράγμα με διαφορετικά λόγια... :)

Όντως,έτσι είναι αλλά δεν έχει νόημα να κάνεις κτ τέτοιο.Σαν n ορίζεται το μέγεθος της εισόδου που για πίνακες είναι ο αριθμός των σειρών και στηλών.Οι υποπίνακες είναι υποπρόβλημα του αρχικού προβλήματος και δε νομίζω ότι είναι λογικό να αρχίσεις τη μελέτη της πολυπλοκότητας με αναφορά τη μεταβλητή των υποπινάκων.

Συμφωνώ με τον φίλτατο lars! Κι εγώ έτσι όπως το παρουσιάζεις το έκανα, με n= αριθμό σειρών/στηλών πίνακα και όχι υποπίνακα. :)

Διαφωνώ στο ότι αν πάρεις n τον αριθμό των γραμμών των υποπινάκων μελετάς υποπρόβλημα. Με το ίδιο σκεπτικό και με το να παίρνεις τον αριθμό των στοιχείων της γραμμής πάλι υποπρόβλημα μελετάς, αν ήταν έτσι θα έπρεπε να πάρεις n τον συνολικό αριθμό των στοιχείων του πίνακα. Πάντοτε παίρνεις το n με βάση το ελάχιστο που απαιτείται για να προσδιορίσεις το πρόβλημα.
Άλλωστε αν πάρεις τα διαδοχικά προβλήματα sudoku και κάνεις γραφική παράσταση, η καμπύλη σου θα έχει μορφή n^4

Εγώ πάλι έχω την αμυδρή εντύπωση ότι πολύ το αναλύσαμε το θέμα....

oh yes........

Μα το ίδιο πράγμα είναι,εννοείται.Απλά για να έχεις ένα μέτρο σύγκρισης, αυτό εννοούσα.Και όντως πολύ το αναλύσαμε!!! :)