Προγραμματιστική απορία πάνω σε αλγόριθμο

[Timonkaipumpa]

Καλημέρα,

έχω ένα σύστημα συντεταγμένων το οποιο αντι να το διαβασω σαν ενα δυσδιαστατο πινακα διαβαζω τις συντεταγμενες χ σε ενα μονοδιαστατο πινακα και τις συντεταγμενες y σε ενα αλλο. Γνωρίζω ότι μπορώ να το κάνω με ένα δυσδιαστατο αλλα θα εξηγήσω παρακάτω γιατί.

Στους πινακες αυτους που εχω βρισκω απο καθε σημειο την συνολικη αποσταση απο τα υπολοιπα. Ομως μετα θελω στις συντεταγμενες που εχω να βρω την ελαχιστη αποσταση.

 

Πως ομως θα αντιστοιχισω τις αποστασεις που εχω απο την παραπανω διαδικασια με το συστημα συντεταγμενων που εχω?

 

 

Θα έχεις κάτι σαν confusion matrix όπου το column και το row που θα είναι η min τιμή θα σου δίνει το index του ζεύγους που την έχει. 

 

[albNik]

Αφου στην αρχη λεει για δισδιαστατο.

Ε αν παρεις χωριστά τα x και y

[παπι]

Ε αν παρεις χωριστά τα x και y

 

Ε αν παρεις χωριστα τα χ και τα ψ, τοτε για -1,-1   1,1 θα εχεις 0.

[albNik]

Περνει απολυτες τιμες (θετικες) στις διαφορες.

[Anubis13]

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

 

Τελικά λοιπόν για ποιό λόγο σορτάρεις;

Σορταρω γιατι ειναι ευκολοτερο να υπολογισω τα αθροισματα με γραμμικη πολυπλοκοτητα.

Γιατι να τα σορταρεις?

Φτιάξε και μια τριτη στήλη με τις "αποστάσεις" και πάρε τη μικρότερη

 

Μπορεις να μου δειξεις αυτο που λες στο παραδειγμα?

 

 

2 5

3 6

1 7

5 3

[παπι]

Περνει απολυτες τιμες (θετικες) στις διαφορες.

|-1 + 1| = 0.

 

@ts, επειδη ακομα δεν εχω καταλαβει το "αποσταση". Αυτο λες http://sketchtoy.com/57054108

[albNik]

|-1 + 1| = 0.

 

@ts, επειδη ακομα δεν εχω καταλαβει το "αποσταση". Αυτο λες http://sketchtoy.com/57054108

Τη διαφορα πάρε , όχι αθροισμα  |-1 -1|=2

[παπι]

Τη διαφορα πάρε , όχι αθροισμα  |-1 -1|=2

χ1 = 1

χ2 = -1

 

|χ1 - χ2| = 0

 

απλα αντι να γραψω |-1 - +1| εγραψα |-1+ 1|

[Anubis13]

|-1 + 1| = 0.

 

@ts, επειδη ακομα δεν εχω καταλαβει το "αποσταση". Αυτο λες http://sketchtoy.com/57054108

Oχι δεν θα μετακινηθεις διαγωνια. θα μετακινηθεις τοσα βηματα πανω, κατω, δεξια, αριστερα.

http://sketchtoy.com/57054368

[παπι]

Oχι δεν θα μετακινηθεις διαγωνια. θα μετακινηθεις τοσα βηματα πανω, κατω, δεξια, αριστερα.

http://sketchtoy.com/57054368

100% δεν θα πηγαινε το μυαλο μου εκει οταν εγραφες αποσταση. 

[albNik]

 

Μπορεις να μου δειξεις αυτο που λες στο παραδειγμα?

 

 

2  5  10  (1+1+3) + (1+2+2)

3  6  10  (1+2+2) + (1+1+3)

1  7  14  (1+2+4) + (2+1+4)

5  3  18  (3+2+4) +(2+3+4)

 

@παπι

απο τον εαυτο του ειναι 0 (το 1 απο το 1)

το 1 απο το -1 ειναι 2  

 

|-1-1|=2 (οχι 0)

[Anubis13]

100% δεν θα πηγαινε το μυαλο μου εκει οταν εγραφες αποσταση. 

 

εχεις δικιο. Αλλα τοτε θα επρεπε απλα να εφαρμοσω τον τυπο της αποστασης manhattan.

[παπι]

 

@παπι

απο τον εαυτο του ειναι 0 (το 1 απο το 1)

το 1 απο το -1 ειναι 2  

 

|-1-1|=2 (οχι 0)

 

Τα μαθηματικα, δεν ειναι και το πιο δυνατο σημει μου. Αλλα αυτη την φραση | χ+y | != | χ | + | y | ισχυει.

[albNik]

Αλλα αυτη την φραση | χ+y | != | χ | + | y | ισχυει.

| χ+y | <= | χ | + | y |

[Anubis13]

2  5  10  (1+1+3) + (1+2+2)

3  6  10  (1+2+2) + (1+1+3)

1  7  14  (1+2+4) + (2+1+4)

5  3  18  (3+2+4) +(2+3+4)

 

Ναι οκ αλλα για να το κανεις αυτο χρειαζεσαι Ν^2 πραξεις