Ερωτήσεις για C

[defacer]

Άρα έτσι μπορώ να κάνω σούμα όλα τα στοιχεία ενός πίνακα διατρέχοντάς τον μόνο "μισή" φορά ε;

int foo[100], i, sum;
for (i = 0; i < 50; ++i) {
    sum += foo[i] + foo[99 - i];
}

Φανταστικό. Με λίγο παραπάνω δουλειά θα μπορούσα να κάνω σούμα όλα τα στοιχεία διατρέχοντας ένα οσοδήποτε μικρό τμήμα του πίνακα!

 

Το διατρέχουμε = # of iterations πρέπει να είναι καινούρια μαθηματικά, δεν τα ήξερα. Μέχρι τώρα νόμιζα διατρέχουμε = πόσα στοιχεία ακουμπάς, εφόσον μπορείς να κανονίσεις να κάνεις όσα loop iterations θέλεις εσύ χωρίς να αλλάξει ο αριθμός των στοιχείων που ακούμπησες.

[migf1]

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

[parsifal]

Ακόμη και σε αυτό θα μαλώσετε βρε σαρδανάπαλοι;

 

Η ανίχνευση παλινδρόμου σε ένα string είναι τετριμμένο CS πρόβλημα, btw. Πρώτα απ' όλα, ξεκαθαρίστε αν μιλάτε για string γνωστού από πριν μεγέθους ή όχι. Για string γνωστού από πριν μεγέθους, λύνεται με μία βοηθητική δομή δεδομένων τύπου στοίβας, με μία πλήρη διάτρεξη του string και πολυπλοκότητα O(n).

[defacer]

Ακόμη και σε αυτό θα μαλώσετε βρε σαρδανάπαλοι;

 

Η ανίχνευση παλινδρόμου σε ένα string είναι τετριμμένο CS πρόβλημα, btw. Πρώτα απ' όλα, ξεκαθαρίστε αν μιλάτε για string γνωστού από πριν μεγέθους ή όχι. Για string γνωστού από πριν μεγέθους, λύνεται με μία βοηθητική δομή δεδομένων τύπου στοίβας, με μία πλήρη διάτρεξη του string και πολυπλοκότητα O(n).

 

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

 

Technically, για string γνωστού μεγέθους και το διπλής φοράς traversing που λέμε παραπάνω θα κάνει μία μόνο πλήρη διάτρεξη του string (ή μισή με τα νέα μαθηματικά του migf1 που δεν τα καταλαβαίνω... ή και ένα οσοδήποτε μικρό ποσοστό διάτρεξης θέλεις, αφού εξαρτάται μόνο από τον αριθμό των επαναλήψεων του loop στο χέρι σου είναι). Και βέβαια είτε ξέρεις το μέγεθος του string είτε όχι πάλι O(n) είναι αφού O(2n) == O(n).

 

Αλλά αυτό με το stack που λες... δε μπορώ να φανταστώ γιατί να μπλέξει κανείς stack στην υπόθεση. Example link?

[migf1]

Ακόμη και σε αυτό θα μαλώσετε βρε σαρδανάπαλοι;

Μα δεν τον βλέπεις; Δεν φτάνει που δεν ξέρει που του πάνε τα 4, απαντάει και με ειρωνίες και το παίζει και έξυπνος. Τι είχες Γιάννη μου τι είχα πάντα, δηλαδή. Αξιώνει κιόλας να τον παίρνω στα σοβαρά και να του απαντάω κιόλας όταν κι όπως θέλει αυτός. Έχει πολύ καλαμπούρι

 

Η ανίχνευση παλινδρόμου σε ένα string είναι τετριμμένο CS πρόβλημα, btw. Πρώτα απ' όλα, ξεκαθαρίστε αν μιλάτε για string γνωστού από πριν μεγέθους ή όχι. Για string γνωστού από πριν μεγέθους, λύνεται με μία βοηθητική δομή δεδομένων τύπου στοίβας, με μία πλήρη διάτρεξη του string και πολυπλοκότητα O(n).

Το complexity είναι linear έτσι κι αλλιώς, Ο(n) επειδή το O(n/2) ισούται έτσι κι αλλιώς με O(n). Το θέμα είναι πως ο τύπος όχι μόνο δεν έχει την παραμικρή ιδέα του τι σημαίνει O(n/2), αλλά απαντάει εριστικά, το παίζει έξυπνος κι επιμένει κιόλας.

 

EDIT:

 

Α, ξέχασα... μιας και προφανώς ακούει και για 1η φορά τα περί στοίβας (που είναι τετριμμένο πρόβλημα όπως είπες κι εσύ parsifal στο CS), ας του δώσουμε και το 1ο link που βγήκε μπροστά μας στο google: http://www.careercup.com/question?id=12337721

 

Ας του δώσουμε κι άλλο ένα in-place: http://crackprogramming.blogspot.gr/2012/10/find-if-data-in-single-linked-list-is.html

[defacer]

Μα δεν τον βλέπεις; Δεν φτάνει που δεν ξέρει που του πάνε τα 4

 

Αποδείξεις ότι δεν ξέρω που πάνε τα 4:

 

 

 

 

 

Αξιώνει κιόλας να τον παίρνω στα σοβαρά και να του απαντάω κιόλας όταν κι όπως θέλει αυτός.

 

Όχι, αξιώνω να υποστηρίξεις τα όσα λες αντί να κάνεις σαν κακομαθημένο. Πράγμα το οποίο είναι κι αυτό που αξιώνεις εσύ απο μένα απευθύνοντάς μου ερωτήσεις "το είπες αυτό ή όχι?". Αλλά ας μη χαλάσουμε την καρδιά μας με λεπτομέρειες.

 

Το complexity είναι linear έτσι κι αλλιώς, Ο(n) επειδή το O(n/2) ισούται έτσι κι αλλιώς με O(n). Το θέμα είναι πως ο τύπος όχι μόνο δεν έχει την παραμικρή ιδέα του τι σημαίνει O(n/2), αλλά απαντάει εριστικά, το παίζει έξυπνος κι επιμένει κιόλας.

 

Εριστική απάντηση (σε κάποιο σύμπαν):

 

Το πολύ μέχρι τη μέση αλλά και από τις 2 μεριές = το πολύ 1 πλήρη φορά = από 1 μέχρι 2 φορές συνολικά. Η αρχική version τη διέτρεχε 3 φορές. Χωρίς creative accounting.

 

Απόδειξη ότι δεν έχω ιδέα τι σημαίνει O(n/2) και πως O(n) == O(n/2) -- σε αντίθεση με άλλους φωστήρες:

 

Και βέβαια είτε ξέρεις το μέγεθος του string είτε όχι πάλι O(n) είναι αφού O(2n) == O(n).

 

 

 

Α, ξέχασα... μιας και προφανώς ακούει και για 1η φορά τα περί στοίβας (που είναι τετριμμένο πρόβλημα όπως είπες κι εσύ parsifal στο CS), ας του δώσουμε και το 1ο link που βγήκε μπροστά μας στο google: http://www.careercup.com/question?id=12337721

 

Χαριτωμένο. Αμφιβάλλω αν κατάλαβες πως, σε αντίθεση με αυτό που έγραψε ο parsifal (και γι' αυτό παραξενεύτηκα), αυτή η τεχνική χρησιμοποιείται όταν δεν μπορείς να κινηθείς "προς τα πίσω" -- δεν έχει καμία σχέση με το αν ξέρεις το μέγεθος της εισόδου ή όχι, και δεν υπάρχει κανένας απολύτως λόγος να τη χρησιμοποιήσεις όταν μπορείς να κινηθείς προς τα πίσω όπως στο παράδειγμα για το οποίο συζητάμε.

 

Από το πολύ φώς τυφλώθηκα λέμε.

[migf1]

Ότι πεις.

[defacer]

Truth is a bitch.

[migf1]

Ain't it?

[parsifal]

Κύριοι, εχει μαλλιάσει η γλώσσα μου να απευθύνω προειδοποίησεις για τα δημόσια ξεκατινιάσματα. Ρίχνετε το επίπεδο του section.

 

Μετά την επιστροφή από το ban, σας θέλω αρνάκια...

[Star_Light]

Βασικά δεν διατρέχουμε τη λέξη 2 φορές (αρχή έως τέλος και τέλος έως αρχή). Την διατρέχουμε μια φορά μονάχα για να θέσουμε έναν δείκτη στο τέλος της, και κατόπιν τη διατρέχουμε το πολύ μέχρι τη μέση της. Άρα το πολύ μέχρι 1 1/2 φορές (αν δεν είναι παλινδρομική η λέξη τη διατρέχουμε λιγότερο... από 1 έως 1 1/2 φορές, exclusive).

 

Ναι βασικα εννοουσα να την διατρέξειςαπο την αρχη ως το τελος... πηγαινοντας προς το τελος μεχρι να φτασεις στην μέση και απο το τελος πηγαινοντας προς την αρχη μεχρι να φτασεις στην μεση τεσπα το ιδιο λεμε. Ισως δεν το διατυπωσα με ακριβεια στην αρχη. Την διατρεχεις μια φορα οταν την διαβάζεις και μετα μιση και μιση . Φανταζομαι η διαφωνια σας με τον defacer εγκειται στο αν θα πρεπει να μετρησουμε την κινηση του κάθε δεικτη ξεχωριστά ή να θεωρησουμε και τις 2 μαζί σαν μισή κινηση δεν μπορω να σκεφτω κατι αλλο .  Παντως λογικα αν το σκεφτει κάποιος ο str αρχικα διατρέχει μια φορά μέχρι να φτάσει στο τελος , μετα μιση συνολικα εχει κανει κινηση 1 1/2 ενω ο last έχει κάνει 1/2 οποτε οταν θα έχει βρεθει η παλινδρομη ο str θα έχει κανει 1 + 1/2 και ο last μονο 1/2 + το 1 απο τον str οταν διαβάζαμε αρχικα την προταση. οΠΟΤΕ ολος ο αλγοριθμος ασχετα με τους δεικτες που χρησιμοποιούμε θα έχει κάνει 1 + 1/2 .  Μονο έτσι βγαίνει η αιτιολογηση του migf1 

 

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

 

P.S Εγραψα τον αλγοριθμο για να δω αν τον διατυπωνω σωστα. Αν εχει κανεις καμια καλυτερη προταση διατυπωσης του ας την παρουσιασει.

Επεξ/σία 21 Ιανουαρίου 2013 από parsifal

[parsifal]

P.S Εγραψα τον αλγοριθμο για να δω αν τον διατυπωνω σωστα. Αν εχει κανεις καμια καλυτερη προταση διατυπωσης του ας την παρουσιασει.

 

Όπως έγραψα και πιο πάνω, αν έχεις διαθέσιμη δομή δεδομένων με χαρακτηριστικά στοίβας, γνωρίζεις το μήκος του string (έστω n) και υπάρχει ήδη αποθηκευμένο σε κάποια δομή δεδομένων τύπου array/linked list, ξεκινάς να διατρέχεις το string και:

 

1. Μέχρι να φτάσεις στον (n/2)-οστό χαρακτήρα του string, κάνεις push στη στοίβα τους χαρακτήρες που συναντάς

2. Από τον (n/2) + 1 και μετά, για κάθε νέο χαρακτήρα του string που «ακουμπάς», κάνεις pop από τη στοίβα και συγκρίνεις

 

* Προφανώς, για περιττό μήκος string, ο διάμεσος χαρακτήρας δε μπαίνει στη στοίβα ούτε συγκρίνεται με κάποιον (ή τον συγκρίνουμε με τον εαυτό του, αν το θες )

[ZAKKWYLDE]

 

Όπως έγραψα και πιο πάνω, αν έχεις διαθέσιμη δομή δεδομένων με χαρακτηριστικά στοίβας, γνωρίζεις το μήκος του string (έστω n) και υπάρχει ήδη αποθηκευμένο σε κάποια δομή δεδομένων τύπου array/linked list, ξεκινάς να διατρέχεις το string και:

 

1. Μέχρι να φτάσεις στον (n/2)-οστό χαρακτήρα του string, κάνεις push στη στοίβα τους χαρακτήρες που συναντάς

2. Από τον (n/2) + 1 και μετά, για κάθε νέο χαρακτήρα του string που «ακουμπάς», κάνεις pop από τη στοίβα και συγκρίνεις

 

* Προφανώς, για περιττό μήκος string, ο διάμεσος χαρακτήρας δε μπαίνει στη στοίβα ούτε συγκρίνεται με κάποιον (ή τον συγκρίνουμε με τον εαυτό του, αν το θες )

 

Ωραίο, αλλά έχεις και το πρόβλημα των κενών π.χ. "was it a car or a cat I saw" οπότε όπου κενό το αγνοείς και δεν το pushαρεις στη στοίβα - ούτε φυσικά το συγκρίνεις.

[parsifal]

Χμμμμ. Το κενό είναι ένας χαρακτήρας σαν όλους τους άλλους και αν δεν κάνω λάθος, δεν αποτελεί ειδική περίπτωση ούτε στα παλίνδρομα. Γιατί να εισάγεις ειδική μεταχείριση γι' αυτόν; Τσάμπα θα γράφεις περισσότερο κώδικα για το σχετικό case (και θα έχεις κι ένα έστω μικρούλι perfomance hit λόγω του ελέγχου κάθε φορά)! Με την ίδια λογική, δε θα έπρεπε να κάνεις το ίδιο και για τα σημεία στίξης ξέρω γω...;

[ZAKKWYLDE]

Ναι αλλά στη περίπτωση του "was it a car or a cat I saw"

Το Ν/2 είναι το ' _ ' το οποιο (αφού αγνοήσεις το o που είναι ο ενδιάμεσος) θα το συγκρίνεις με τον επόμενο χαρακτήρα N/2 + 1 που είναι το 'r'

Άρα με τη μία θα σου βγεί false η συνθήκη, εκτός αν κάνεις κάτι άλλο για τους "περίεργους χαρακτήρες" που μου διαφεύγει.