forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 22 Σεπ 2017, 20:41

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 5 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Βοήθεια σε ασκήσεις
ΔημοσίευσηΔημοσιεύτηκε: 16 Νοέμ 2008, 21:42 
Χωρίς σύνδεση

Εγγραφη: 06 Νοέμ 2008, 18:55
Δημοσ.: 2
Παιδιά αν μπορούσε κάποιος να με βοηθήσει στις παρακάτω ασκήσεις θα το εκτιμούσα ιδιαίτερα..

1. Να σχεδιασθεί και να αναλυθεί ένας αλγόριθμος διαίρεσης ακεραίων εφαρμόζοντας την τεχνική του πολλαπλασιασμού αλά ρωσικά με την αντίστροφη λογική

2. Η αρχή του κουτιού του Dirichlet. Δεδομένων n αντικειμένων και mκουτιών να αποδειχθεί οτι κάποια κουτιά περιέχουν περισσότερο απο \left\lceil\frac{n}{m}\right\rceil αντικείμενα και κάποια κουτιά περιέχουν λιγότερο απο \left\lfloor\frac{n}{m}\right
\rfloor αντικείμενα

3. Σε ένα καζίνο υπάρχει ρουλέτα με 1000 αριθμούς. Αν η ρουλέτα φέρει έναν αριθμό n που διαιρείται με την ποσότητα \left\lfloor\sqrt[3]{n}\right\rfloor τότε ο παίχτης κερδίζει 5 ευρώ αλλιώς χάνει 1 ευρώ. Ασυμπτωτικά ο παίχτης θα κερδίσει ή θα χάσει;

4.Να αποδειχθεί οτι η επόμενη έκφραση ισούτε με \left\lfloor{x}\right\rfloor ή με \left\lceil{x}\right\rceil. Πότε εμφανίζεται το κάθε αποτέλεσμα;
\left\lceil\frac{2x+1}{2}\right\rceil-\left\lceil\frac{2x+1}{4}\right\rceil=\left\lfloor\frac{2x+1}{4}\right
\rfloor

Σας ευχαριστώ.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια σε ασκήσεις
ΔημοσίευσηΔημοσιεύτηκε: 18 Νοέμ 2008, 11:30 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 628
Γιά νά τά πάρουμε από τήν αρχή...
Άσκηση 1
Γνωρίζεις πώς γίνεται ο ρώσσικος πολ/σμός?...Άν, ναί τότε εξήγησέ μας πρώτα σέ παρακαλώ πού κολλάς...να τό δούμε...


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια σε ασκήσεις
ΔημοσίευσηΔημοσιεύτηκε: 18 Νοέμ 2008, 16:13 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 628
Φίλε nikospa, επειδή θά λείψω μερικές μέρες...ορισμένες σκέψεις ...γιά να ασχοληθείς..

Άσκηση 1

Ο ρώσσικος πολ/σμός βασίζεται στήν πρόσθεση, στήν αφαίρεση καί στόν διπλασιασμό αριθμών (μιλάμε πάντα γιά φυσικούς αριθμούς)

Σχηματικά...κάπως έτσι :

m\cdot n=\begin{cases}
m & \text{ if } n=1  \\ 
 m\cdot (n-1)+m& \text{ if } n\geq 1, \pi \epsilon \varrho \iota \tau \tau o \varsigma    \\ 
2m\cdot \frac{n}{2} & \text{ if } n :  \alpha \varrho \tau \iota o \varsigma 
\end{cases}

Παράδειγμα 13\cdot 17=221 :

\begin{vmatrix}
13 & 17 & 17\\ 
6 &  34& 0\\ 
3 &  68& 68\\ 
1 &  136& 136
\end{vmatrix}

Διαιρώ στήν πρώτη στήλη μέ τό 2 καί στρογγυλοποιώ κατά κάτω
Πολ/ζω στήν δεύτερη στήλη μέ τό 2
Στήν τρίτη στήλη γράφω τό αποτέλεσμα τής δεύτερης, άν ο αριθμός τής πρώτης στήλης είναι περιττός
Αθροίζω τήν τρίτη στήλη :
17+68+136=221

Αυτός είναι ο αλγόριθμος τού ρώσσικου πολ/σμού. Μάς ενδιαφέρει επειδή ο συνδυασμός «διαιρώ διά τού 2» καί «επιλογή τών περιττών αριθμών» βρίσκει άμεση αντιστοιχία στόν τρόπο που μετατρέπουμε τόν πρώτο αριθμό σέ δυϊκή μορφή.
Παράδειγμα:
39=1\cdot 2^{5}+0\cdot 2^{4}+0\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}=100111_{2}
Άν πολ/σεις αυτό τό ανάπτυγμα μέ τό 79 πχ έχεις 39\cdot 79=3081

Λοιπόν κάνεις τό αντίστροφο μέ τήν διαίρεση....
(Θά πάρεις σταδιακά τούς εκθέτες τού 2, από μηδέν μέχρι ένα n, καί θά σταματήσεις ένα βήμα πρίν ξεπεράσεις τόν διαιρεταίο...Αυτό τό n είναι σημαντικό, διότι ακριβώς τόσες φορές θά διπλασιάσεις τόν διαιρέτη. Η λύση προκύπτει τότε από πρόσθεση από αυτούς τούς διπλασιασμένους)

Άσκηση 2

Η αρχή αυτή τού Dirichlet δέν λέει ακριβώς αυτό...Η λεπτομέρεια κάνει τήν διαφορά... Μάς λέει :
Έχω n επιστολές καί τίς μοιράζω σέ m συρτάρια, όπου m<n. Τότε ένα τουλάχιστον συρτάρι περιέχει παραπάνω από μία επιστολή.

Αυτό, είναι προφανές ...δέν σηκώνει απόδειξη...Σέ γλώσσα μαθηματικών περιγράφεται ως εξής:
Έστωσαν N καί M δύο πεπερασμένα σύνολα μέ :
|N|=n>m=|M| καί έστω f:N \rightarrow M μία συνάρτηση. Τότε υπάρχουν μερικά a \in M μέ |f^{-1}(a)|\geq 2. Προσεγγίζεται μάλιστα καλύτερα :
Υπάρχουν μερικά a \in M μέ
|f^{-1}(a)|\geq \left \lceil\frac{n}{m}\right \rceil

(Τό αντίθετο: |f^{-1}(a)|\leq \frac{n}{m},\ \forall a\in M θά σήμαινε :
n=\sum_{a\in M}|f^{-1}(a)|< m\frac{n}{m}=n, που προφανώς δέν μπορεί νά ισχύει.

Άσκηση 3

Ασυμπτωτικά καί στά πλαίσια 1000 περίπου αριθμών χάνει πάντα ο παίκτης σου....τό 5 πρός 1 είναι λίγο...θα έπρεπε να έχει 10 πρός 1 γιά νά μήν χάσει...
Άς τό δούμε μέ ένα παράδειγμα...έστω στό διάστημα 1000 μέχρι 2197. Παρατηρούμε:
10^{3}=1000
11^{3}=1331
12^{3}=1728
13^{3}=2197

Έχουμε δηλαδή τά 3 διαστήματα (1000,1330), (1331,1727) καί (1728,2196)
Στό πρώτο ο μεγαλύτερος ακέραιος που προκύπτει από τήν κυβική ρίζα είναι ο 10, στό δεύτερο ο 11 καί στό τρίτο ο 12
Άρα στό πρώτο:
1330-1000=330:10=33+1=34 φορές κερδίζει καί 297 χάνει
Στό δεύτερο:
1727-1331=36:11=36+1=37 φορές κερδίζει καί 360 χάνει
Στό τρίτο:
2196-1728=468:12=39+1=40 φορές κερδίζει καί 429 χάνει

Συνολικά (στό παράδειγμα) κερδίζει 111 φορές καί χάνει 1086

Άσκηση 4

Αυτή μού φαίνεται λίγο αστεία (άν τήν εννοώ καί σωστά)...πάρε τόν ορισμό τών floor καί ceil καί σκέψου πότε είναι ταυτόσημοι...Μήπως όταν ο χ είναι ακέραιος?

Αποκαλυπτικός


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια σε ασκήσεις
ΔημοσίευσηΔημοσιεύτηκε: 18 Νοέμ 2008, 20:10 
Χωρίς σύνδεση

Εγγραφη: 06 Νοέμ 2008, 18:55
Δημοσ.: 2
Φίλε Apokalyptike με βοήθησες αρκετα με αυτά που μου είπες.. σ' ευχαριστώ πολύ που ασχολήθηκες...


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια σε ασκήσεις
ΔημοσίευσηΔημοσιεύτηκε: 19 Νοέμ 2008, 14:29 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 628
Άσκηση 4

Φίλε nikospa, τώρα τήν κατάλαβα τήν άσκηση, μού φαίνεται....Πρέπει νά έχει λάθος όμως...Η άσκηση πρέπει νά λέει τό εξής:

Δίδεται η κάτωθι εξίσωση (αυτή που έγραψες). Πότε είναι τά δύο μέλη τής εξίσωσης ίσα μέ floor (x/2) και πότε μέ ceil (x/2) ?

Η απάντηση είναι εύκολη...
Άν τό πρώτο ψηφίο τού x μετά τήν υποδιαστολή είναι <5 έχουμε πάντα σάν αποτέλεσμα floor (x/2)
Άν όμως είναι >=5 εξαρτάται...

Παράδειγμα γιά τήν δεύτερη περίπτωση:

x=10,6
Τό δεξί μέλος τής εξίσωσης δίδει 5 = floor (x/2)
Όμως γιά
x=11,6 δίδει 6=ceil (x/2)

Πρέπει νά θέσουμε επομένως κριτήριο:

Άν : 2 * floor (2x+1 / 4) > x --> ceil ( x / 2)
Άν : 2 * floor (2x+1 / 4) < x --> floor ( x / 2)

Αποκαλυπτικός

ΥΓ
Sorry, γιά μή LATEX, ελπίζω νά αποκρυπτογραφείται καί έτσι....


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 5 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group