Πίνακας αποστάσεων

[chiossif]

Είχα δημοσιεύση τον ακόλουθο κώδικα ως λύση στο πρόβλημα (ως quiz):

 

Ας υποθέσουμε ότι έχουμε έναν πίνακα ακεραίων ΜxN, στον οποίο το 10% περίπου των στοιχείων του έχουν την τιμή μηδέν. Ζητείται να υπολογιστεί για όλα τα υπόλοιπα στοιχεία του η απόσταση σε μονάδες κελιών (pixel) από το πλησιέστερό τους μηδενικό στοιχείο.

 

>
/*
distance_map: calculates distances on a map
Copyright (C) Ch Iossif

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details at http://www.gnu.org/copyleft/gpl.html.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int n=7;
int mat[7][7]={
                 0,49,49,49,49,49, 0,
                 49,49,49,49,49,49,49,
                 49,49,49,49,49,49,49,
                 49,49,49,49,49,49,49,
                 49,49, 0,49,49,49,49,
                 49,49,49,49,49,49,49,
                 0,49,49,49,49,49,49};

void display_mat(void);
void distance(void);
int idist(int, int);

int main(void) {
   distance();
   display_mat();
   return 0;
}

void display_mat(void) {
   register int i,j;
   for (i=0;i<n;i++) {
       for (j=0;j<n;j++)
           printf(" %3d",mat[i][j]);
       printf("\n");
   }
   printf("\n");
}

void distance(void) {
   int r_mat[7][7], c_mat[7][7];
   register int i, j, k, l;

   for (i=0;i<n;i++)
       for (j=0;j<n;j++)
           r_mat[i][j]=c_mat[i][j]=mat[i][j];

   for (i=0;i<n;i++)
       for (j=0;j<n;j++)
           if (!mat[i][j]) {
               for (k=0;k<i;k++)
                   if (c_mat[k][j]>i-k)
                       c_mat[k][j]=i-k;
               for (k=i+1;k<n;k++)
                   if (c_mat[k][j]>k-i)
                       c_mat[k][j]=k-i;
               for (k=0;k<j;k++)
                   if (r_mat[i][k]>j-k)
                       r_mat[i][k]=j-k;
               for (k=j+1;k<n;k++)
                   if (r_mat[i][k]>k-j)
                       r_mat[i][k]=k-j;
           }

   for (i=0;i<n;i++)
       for (j=0;j<n;j++)
           if (mat[i][j]) {
               for (k=0;k<n;k++)
                   if((l=idist(c_mat[i][k],k-j))<mat[i][j])
                       mat[i][j]=l;
               for (k=0;k<n;k++)
                   if((l=idist(r_mat[k][j],k-i))<mat[i][j])
                       mat[i][j]=l;
           }
}

int idist(int x, int y) {
   return (int)sqrt(x*x+y*y);
}

O κώδικας μου είναι ελεύθερος.

 

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

(Όσοι έχετε τον κώδικα ή τα μυνήματά σας σε αρχείο παρακαλώ συμπληρώστε ...)

[chiossif]

Έχουμε ήδη παραπάνω λύσει αυτό:

"Ας υποθέσουμε ότι έχουμε έναν πίνακα ακεραίων ΜxN, στον οποίο το 10% περίπου των στοιχείων του έχουν την τιμή μηδέν. Ζητείται να υπολογιστεί για όλα τα υπόλοιπα στοιχεία του η απόσταση σε μονάδες κελιών (pixel) από το πλησιέστερό τους μηδενικό στοιχείο..."

 

Τώρα θα πρέπει να εμπλουτίσουμε το αποτέλεσμα με το εξής:

"...καθώς και οι αριθμοδείκτες του (indexes)."

 

Για κάθε στοιχείο οι αριθμοδείκτες γραμμής και στήλης του πλησιέστερου μπορούν να αποθηκευτούν είτε σε έναν πίνακα δομής δύο ακεραίων, είτε σε έναν πίνακα δύο επιπέδων (τριών διαστάσεων με τρίτη διάσταση 2), είτε σε δύο διδιάστατους πίνακες.

 

Θυμίζω ότι:

- οι μή μηδενικές τιμές του αρχικού πίνακα μας είναι αδιάφορες.

- οι διαστάσεις του αρχικού και άρα όλων των αποτελεσμάτων είναι συνήθως αριθμοί αρκετά μεγάλοι (~4000x4000 = 64ΜΒ) και άρα η όποια λύση πρέπει να βελτιστοποιεί την ταχύτητα (μνήμη έχουμε ).

- όσοι διάβασαν και εφάρμοσαν την λύση του πρώτου quiz θα ξέρουν τις επιδόσεις της. Δεν αποκλείεται να επιλεχθεί ΔΕΔΟΜΕΝΟ το αποτέλεσμα του πρώτου κώδικα ώστε, με πρόσθετο κώδικα φυσικά, να υπολογιστεί-λυθεί ΣΤΗΝ ΣΥΝΕΧΕΙΑ το δεύτερο. Σας έρχεται καμιά ιδέα;

 

(Λυπάμαι που εξαιτίας του προβλήματος χάθηκαν οι σκέψεις-μυνήματα φίλων.

Μην ξεχνάτε, κάθε κώδικας μου εδώ (παλαιός -όπως η λύση του 1ου- ή νέος) είναι ελεύθερος. Θα επιθυμούσα το ίδιο να ισχύει και για τους υπόλοιπους. Σε κάθε περίπτωση παρακαλώ να το δηλώνετε σαφώς.

Αν υπάρξει ενδιαφέρον, θα συμπληρωθεί η τριλογία αυτών των quiz...)

[phr0z]

lol gpl.

[smilefreeware]

Μια ερώτηση - διευκρίνηση.

 

Πως ορίζεις την απόσταση ? (Μετρά διαγωνίως ή μόνο οριζόντια-κάθετα)

Στο παρακάτω παράδειγμα πόση είναι ? (1 από 0)

 

X X X X X X X

X 0 X X X X X

X X X X 1 X X

X X X X X X X

X X X X X X X

 

(Για να μην κάνω μετάφραση. Δουλεύω σε Delphi).

[chiossif]

Η απόσταση είναι ευκλείδια δηλαδή τετραγωνική ρίζα του αθροίσματος των τετραγώνων των οριζοντίων και των καθέτων αποστάσεων σε κελιά (ακέραιοι). Το αποτέλεσμα στογγυλεύεται στον πλησιέστερο ακέραιο δηλαδή το 3,4 γίνεται 3 ενώ το 3,5 γίνεται 4.

Με βάση τα παραπάνω ισχύει στο παράδειγμά σου:

 

| 3 |

X X X X X X X

X 0 X X X X X -

X X X X 1 X X - 1

X X X X X X X

X X X X X X X

 

sqrt(3*3+1*1)=sqrt(10)=3,162277... --> 3

 

Ενώ σε αυτόν:

 

>
int mat[7][7]={
                 0,49,49,49,49,49, 0,
                 49,49,49,49,49,49,49,
                 49,49,49,49,49,49,49,
                 49,49,49,49,49,49,49,
                 49,49, 0,49,49,49,49,
                 49,49,49,49,49,49,49,
                 0,49,49,49,49,49,49};

 

δίνει:

 

>
  0   1   2   3   2   1   0
  1   1   2   3   2   1   1
  2   2   2   2   2   2   2
  2   1   1   1   2   3   3
  2   1   0   1   2   3   4
  1   1   1   1   2   3   4
  0   1   2   2   2   3   4

 

Σχόλιο:

Ο παραπάνω κώδικας δεν χρειάζεται ΜΕΤΑΦΡΑΣΗ (translation) απλά μεταγλώτιση (compilation). Μεταγλωτίζεται σε κάθε C compiler. Μήπως εννοείς ότι χρειάζεται να χρησιμοποιήσεις κάποιο κέλυφος - τερματικό (=κονσόλα=μαύρο παράθυρο=γραμμή εντολών); Ναι. Τώρα δεν γνωρίζω Defli και άρα την ορολογία τους αλλά νομίζω ότι αν ο Delfi είναι C compiler τότε ΔΕΝ ΕΧΕΙΣ ΠΡΟΒΛΗΜΑ.

 

Λοιπόν για να μην γράφω χαζομάρες (μόλις είδα ότι εκτός από αυτό http://en.wikipedia.org/wiki/Delphi υπάρχει και αυτό http://en.wikipedia.org/wiki/Object_Pascal) οπότε προφανώς από το σχόλιο δεν ισχύει τίποτε:

 

Η λέξη ΜΕΤΑΦΡΑΣΗ που χρησιμοποιείς είναι ΑΠΟΛΥΤΩΣ ΣΩΣΤΗ.

 

Δεν διόρθωσα το σχόλιο για δουν τι μπορεί να πάθουν στα καλά καθούμενα όσοι δεν ξέρουν τι είναι Delfi

Και για να έχει κάτι να γελάει και ο φίλος ο phr0z... εκτός απο την gpl...

[smilefreeware]

Την αυστηρότητά μου την εξαντλώ όσο μπορώ εκεί που χρειάζεται. (Μαθηματικά , αλγόριθμοι κλπ.)

Στο κείμενό μου προσπαθώ να είμαι πιο χαλαρός. Δηλ. το μετάφραση έπρεπε να το βάλω σε εισαγωγικά. Ηθελα να πώ ότι αντί να καταλάβω τι γράφει ο κώδικας πιο εύκολο-γρήγορο για μένα θα ήταν να μου εξηγήσουν τι γράφει.

 

Στο θέμα. Εκτός αλγόριθμου μια παρατήρηση. Η ρίζα και ο Int μαζί θα μπορούσαν να είναι φτιαγμένα έτοιμα τα αποτελέσματα στην αρχή του προγράμματος για αρκετούς αριθμούς, ώστε να μην υπολογίζονται στην διάρκεια του κεντρικού υπολογισμού.

Μιλάω για αυτό

int idist(int x, int y) {

return (int)sqrt(x*x+y*y);

 

Καθυστερεί αρκετά η ρίζα.

[chiossif]

Φίλε smilefreeware,

η πρώτη έκδοση που είχα γράψει το 1992-3 (στην εκφώνηση του 1ου quiz υπήρχε ιστορικό, δεν υπάρχει λόγος τώρα να επαναληφθεί) δεν υπολόγιζε ρίζα και αυτό είχε βελτιώσει τους χρόνους εκτέλεσης -της εποχής εκείνης- από 22 ώρες μόλις σε 8. Γινόταν με έναν διδιάστατο πίνακα με όλα τα πιθανά αποτελέσματα προϋπολογισμένα και σε βεβαιώνω έτρεχε σαν τρελό.

Δηλαδή αυτό:

 

int idist(int x, int y) {

return (int)sqrt(x*x+y*y);

 

τότε ήταν γραμμένο έτσι:

 

#define idist(a, (DISTM[a])

 

και είχε και κάτι άλλα "ψιλά" στην αρχή...

 

Αυτό ήταν και το 3ο quiz (εύκολο). Τώρα πρέπει να σκεφτώ άλλο...

Σχετικά με το ΜΕΤΑΦΡΑΣΗ το οποίο το άρπαξα πρώτος: ομολογώ ότι δεν το είχα καταλάβει και έτσι, αφού αυτορεζιλεύτηκα, έμαθα (ή ξαναέμαθα διότι το'χε πάρει πάλι κάπου το μάτι μου παλαιότερα) τι είναι τo delfi. Είχα μείνει στην TP6. Ευχαριστώ για την ευκαιρία...

[smilefreeware]

Μια πρώτη σκέψη :

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

....................0

.................1 1 1

...............2 2 2 2 2

............4 3 3 3 3 3 4

.........5 5 4 4 4 4 4 5 5

......7 6 5 5 5 5 5 5 5 6 7

...8 7 7 6 6 6 6 6 6 6 7 7 8

9 9 8 8 7 7 7 7 7 7 7 8 8 9 9

Στο παράδειγμα έβαλα τις αποστάσεις του προς τα κάτω.

Σε κάθε θέση αντικαθιστούμε τη θέση του πίνακα εφόσον βρήκαμε μικρότερο αριθμό από τον υπάρχοντα.

Πρώτα βέβαια έχουμε γεμίσει τον πίνακα με μεγάλα νούμερα.

Επίσης ελέγχουμε τα όρια του πίνακα , μην βγούμε εκτός.

Το ίδιο φυσικά θα γίνει προς τα πάνω, αριστερά και δεξιά.

 

Νομίζω έτσι καλύπτεται όλος ο πίνακας. (Σε περίπτωση μη κάλυψης θα μείνουν λίγα σε ένα τελικό έλεγχο)

Αν "παίξεις" και βρεθεί ενδιαφέρον το παραπάνω πάμε και στις λεπτομέρεις.

Δηλ. στο κάτω και στο αριστερά πχ. έχει υπολογιστεί 2 φορές η διαγώνιος (έχουν κοινά σημεία).

Επίσης έχουν υπολογιστεί 2 φορές κάποιες θέσεις μεταξύ 2 μηδενικών.

Νομίζω όμως ότι αν η κεντρική σκέψη στέκει καλά θα βρεθούν στην πορεία και οι βελτιώσεις.

 

Καλή τύχη...

[chiossif]

Συχώρεσέ με αλλά δεν κατάλαβα. Λύνεις το 1ο quiz "Υπολογισμός του πίνακα αποστάσεων"; Το έχω λύσει και έχω δώσει την λύση του. Και κάνει, σχεδόν, αυτό που λες σε γραμμές και στήλες που έχουν μηδενικά και στην συνέχεια γεμίζει τις υπόλοιπες με ευκλείδια απόσταση. Αν δεν καταλαβαίνεις την υλοποίηση σε C μπορώ να το κάνω σε pascal απλά δώσε μου μία εβδομάδα διότι παλεύω ένα άλλο πρόβλημα τώρα (quiz άλλων). Το νέο 3ο quiz επίσης θα πρέπει να περιμένει...

[smilefreeware]

Το πιο πιθανό είναι αυτό. <Λύνεις το 1ο quiz "Υπολογισμός του πίνακα αποστάσεων";> Αν και δεν ασχολήθηκα με τη λύση αλλά με την αύξηση της ταχύτητας της λύσης.

 

<μπορώ να το κάνω σε pascal>

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

Τουλάχιστον εγώ δεν βιάζομαι. Με την ησυχία σου.