Η σελίδα μας αναβαθμίστηκε, γι' αυτό τον λόγο τα μέλη μας θα πρέπει να ζητήσουν νέο κωδικό πρόσβασης από την υπηρεσία "Αποστολή κωδικού πρόσβασης".
Εάν το email με τον νέο κωδικό δεν έρθει στο inbox κοιτάξτε και στο spam folder. Ο server είναι φρέσκος και δεν έχει το reputation που του αξίζει.

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Erevis
Δημοσιεύσεις: 56
Εγγραφή: 12 Ιουν 2008 16:31
Τοποθεσία: Χαλάνδρι

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από Erevis » 03 Σεπ 2008 16:18

Καταρχήν καλησπέρα σας,

έχω μια άσκηση στη C στην οποία το πρόγραμμα θα πρέπει να ανιχνεύει την πρώτη εμφάνιση κάθε ομάδας σύνθετων αριθμών απο τον αριθμό 3 ως τον αριθμό N ,ο οποίος ορίζεται με την εντολή define.

πχ έστω οτι έχουμε τους αριθμούς 3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19...

το πρόγραμμα θα πρέπει να εμφανίζει:

First 1 consecutive composites from 4 to 4
First 3 consecutive composites from 8 to 10
...............................................................
..............................................................

ορίστε ο κώδικας που έχω γράψει ως τώρα

Κώδικας: Επιλογή όλων

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

#define N 2000


int composite&#40;int x&#41;; //elegxei an enas ari8mos einai sun8etos
int checkGroup&#40;int group&#41;;//elexei an uparxei omada ki an einai h omada pou psaxnoume


int main&#40;void&#41;
&#123;
    int x=0;
    int group;//trexousa omada pou psaxnoume
    int current;//mas deixnei ton prwto ari8mo ths prwths omadas pou vrhkame
    
    for&#40;group=1;x<=N;group+=2&#41;//epanalhpsh pou anixneuei thn 1h emfanish ka8e omadas
    &#123;
        if&#40;current = checkGroup&#40;group&#41;&#41;
        &#123;
                   printf&#40;"First %d consecutive composites from %d to %d\n",group,current,current+group-1&#41;;
        &#125;
        x++;          
    &#125;
    system&#40;"PAUSE"&#41;;
    return 0;
&#125;

int composite&#40;int x&#41;
&#123;
    int i;
    for&#40;i=2;i<x;i++&#41;
    &#123;
                    if&#40;x%i==0&#41; return 1;
    &#125;
return 0;
&#125;

int checkGroup&#40;int group&#41;
&#123;
    int x=0;
    int from;//deixnei apo pou 3ekinaei h omada
    int to;  //pou teleiwnei
    while&#40;x<=N&#41;
    &#123;
               if&#40;composite&#40;x&#41;&#41;//psaxnei tous ari8mous mexri na vre8ei sun8etos h epanalhpsh
               &#123;
                    from = x;//molis vre8ei sun8etos kataxwreitai sthn arxh ths omadas     
                    while&#40;composite&#40;x&#41;&#41;
                    &#123;
                                       x++;//psaxnoume gia tous upoloipous sun8etous ths omadas
                    
                    &#125;
                    to = x;//kataxwreitai o epomenos apo ton teleutaio ths omadas 
                    if&#40;to-from==group&#41;//an to mege8os ths omadas = me auto ths omadas pou psaxnoume
                           return from; //epistrefetai o prwtos ari8mos ths omadas
                    &#125;
               &#125;
               x++;     
    &#125;
    return 0; //alliws epistrefeteai 0 gia na einai pseudhs h timh ths sunarthshs
&#125;
Το πρόβλημα ειναι όμως ότι για τιμες του Ν μεγαλύτερες του 3000 το πρόγραμμα σέρνεται(λόγω της συνάρτησης που επιστρέφει αν ενας αριθμός είναι σύνθετος ή οχι ,προφανώς)

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

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

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από dva_dev » 03 Σεπ 2008 19:32

Μήπως η άσκηση σου είναι αυτή γιατί την έχουμε ξαναδεί σε αυτό το θέμα.

Μερικά links που θα σε βοηθήσουν στο σημείο της ταχύτητας
http://dvassil.wordpress.com/2007/11/25 ... -question/
http://fourier.math.uoc.gr/~mk/prog0001 ... ode11.html

[edit]Μπορείς να έχεις ένα τέτοιο αποτέλεσμα (βλ. zip) ή ακόμα καλύτερο με έναν καλό αλγόριθμο[/edit]
Συνημμένα
Primes.zip
Primes Spaces Test
(27.21 KiB) Μεταφορτώθηκε 329 φορές
Τελευταία επεξεργασία από το μέλος dva_dev την 03 Σεπ 2008 20:16, έχει επεξεργασθεί 1 φορά συνολικά.

Erevis
Δημοσιεύσεις: 56
Εγγραφή: 12 Ιουν 2008 16:31
Τοποθεσία: Χαλάνδρι

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από Erevis » 03 Σεπ 2008 20:00

Ναι ακριβώς,αυτή είναι! Ευχαριστώ πολύ για τα links,θα ρίξω μια ματιά να δω!

Έχω βρει διάφορους αλογορίθμους στο internet, στην wikipedia ιδίως αλλά γενικά δεν με έχουν βοηθήσει παρά ελάχιστα στο θέμα της ταχύτητας :/

Erevis
Δημοσιεύσεις: 56
Εγγραφή: 12 Ιουν 2008 16:31
Τοποθεσία: Χαλάνδρι

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από Erevis » 04 Σεπ 2008 04:37

Άλλαξα την συνάρτηση composite με την ακόλουθη

Κώδικας: Επιλογή όλων

int composite&#40;int x&#41;
&#123;
   int temp;
   int i;
   if &#40;x < 4&#41; return 0;
   if &#40;x%2==0&#41; return 1;
   if &#40;&#40;&#40;x+1&#41;%6==0&#41;||&#40;&#40;x-1&#41;%6==0&#41;&#41; 
   &#123;
        temp =&#40;int&#41;sqrt&#40;&#40;float&#41;x&#41;;
        for&#40;i=3;i<=temp;i+=2 &#41;
        &#123;    
        if&#40;x%i==0&#41; return 1;
        &#125;
        return 0;
    &#125;
    return 1;
&#125;
Αν και παρατήρησα μεγαλύτερη ταχύτητα στην εκτέλεση των αποτελεσμάτων,πάλι σταματάει οταν μου εμφανίζει την 1η ομάδα από 71 συνεχόμενους σύνθετους.

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

*edit: Επίσης,αρχικοποίησα τους ακεραίους x στη main και στη checkGroup στο 3

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από dva_dev » 04 Σεπ 2008 09:56

To Πρόβλημα είναι ότι σκανάρεις όλους τους αριθμούς κάθε φορά από την αρχή.
Εστω ότι έχεις το εξής:
Από το 1001-1080 80 σύνθετους
Από το 1101-1179 79 σύνθετους
Από το 1201-1278 78 σύνθετους
και πάει λέγοντας...
Από το 1901-19χχ χχ σύνθετους

Για να μπορέσεις να βρείς τους σύνθετους από το χχ ως το 79, περνάς κάθε φορά από την αρχή και ελέγχεις τα πάντα (το οποίο όπως θα έχεις προσέξει παίρνει κάααααμποσο χρόνο).

Δέστο λοιπόν λίγο αλλιώς. Το ότι η άσκηση σου ζητάει να τυπώνεις με συγκεκριμένη σειρά τα διαστήματα ανάλογα με το μήκος τους, δεν σε υποχρεώνει να τα ψάξεις με αυτόν τον τρόπο. Θα μπορούσες να τα βρίσκεις από το μικρότερο προς το μεγαλύτερο (όπως κάνεις), από το μεγαλύτερο προς το μικρότερο, ή να τα βρίσκεις όπως τύχει να τα βρείς.

Δεν θα ήταν πιο γρήγορο να κάνεις μια φορά σκανάριμα από το 1 μέχρι... ...όσο πάει, και κάθε φορά που βρίσκεις μια ομάδα να το "σημειώνεις"(1) ότι βρήκες κάτι, και μετά να συνεχίζεις από εκεί που είχες μείνει. Ετσι το σκανάρισμα, στο παραπάνω παράδειγμα από το 1 ως το 1000, θα γίνει μόνο μία φορά και το να βρείς τα νούμερα από το χχ ως το 79 θα είναι 1000 φορές πιο γρήγορο από το να ψάχνεις πάντα από την αρχή.

(1)Κάθε φορά που βρίσκεις μια ομάδα θα μπορούσες να τσεκάρεις αν σε ενδιαφέρει να την χρησιμοποιήσεις ή όχι, και να σταματήσεις μόνο όταν έχεις βρεί όλες τις ομάδες που θέλεις.

Δεν σε ενδιαφέρει πλέον παρά μόνο ο αριθμός που ελέγχεις να μπορεί να χωρέσει στην int, long ή long long μεταβλητή σου και ο χρόνος που θέλεις να το αφήσεις να ψάχνει.

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

Erevis
Δημοσιεύσεις: 56
Εγγραφή: 12 Ιουν 2008 16:31
Τοποθεσία: Χαλάνδρι

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από Erevis » 04 Σεπ 2008 15:16

Ευχαριστώ πολύ για τις υποδείξεις..Μια ερώτηση, για να κάνω ταξινόμηση δε θα πρέπει να έχω αποθηκευμένες κάπου τις ομάδες που βρίσκω?Λογικά σε μια συνδεδεμένη λίστα?Γιατί με πίνακα βλέπω να είναι απίθανο να γίνει...

Επίσης αποφάσισα να αλλάξω τον τρόπο με τον οποίο βρίσκει ομάδες το πρόγραμμα χρησιμοποιώνας τον τύπο που δινει τους πρώτους (6κ+-1)

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από dva_dev » 04 Σεπ 2008 15:55

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

Άβαταρ μέλους
bxenos
Δημοσιεύσεις: 53
Εγγραφή: 18 Αύγ 2008 19:56

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από bxenos » 04 Σεπ 2008 18:33

δεν δαπανισα αρκετο χρονο να καταλαβω ολο το θεμα της ασκησης λογω βιασυνης, (δεν επιασα το πως ανακαλυπτουμε την επομενη ομαδα οταν εχουμε την τρεχουσα (πρεπει να εχει μεγαλυτερο μηκος;)) αλλα να δωσω μια ιδεα σε ενα τμημα μηπως βοηθησει:

θελεις εναν πινακα με Ν τιμες αληθεις/ψευδεις; (αν ειναι συνθετος ή οχι)
αποθηκευσε καθε τιμη σε ενα bit.
π.χ.

Κώδικας: Επιλογή όλων

typedef unsigned char bool;

unsigned _bitarray&#91;N / 16&#93;;   //&#40;1&#41;

void set_flag&#40;size_t Position,bool flag&#41;&#123;
  πηγαινε στην θεση &#40;Position / 16&#41; στο bit &#40;Position % 16&#41; και βαλε το flag    //&#40;1c,1d&#41;
&#125;

bool get_flag&#40;size_t Position&#41;&#123;
  επεστρεψε την τιμη της θεσης &#40;Position / 16&#41; στο bit &#40;Position % 16&#41;    //&#40;1c,1d&#41;
&#125;
αυτο θα σου επιτρεψει να κανεις μια μονο αναζητηση για τον καθε αριθμο αν ειναι primary ή συνθετος.

υποσημειωσεις:
(1) εδω χρειαζεται τουλαχιστον μια βελτιωση στην διαιρεση με το 16 (αριθμιος μπιτ ενος ακεραιιου).
1α) βελτιωση ωστε να λειτουργει η διαιρεση και με τιμες Ν που δεν ειναι πολλαπλασια του 16
1β) ειναι 16 ο αριθμος των bit; μπορεις να βρεις τον αριθμο και να τον χρησιμοποιεις ή σε compile time ή σε run time ή μεσω του

Κώδικας: Επιλογή όλων

#include <limits.h>
1c)οι διαιρεσεις με δυναμεις του δυο μπορουν να γινουν εκτος απο το / και με το >>.
1d)μηπως μπορεις να βρεις με ποιον τροπο γινονται τα υπολοιπα με δυναμεις του 2;
(αντι δηλαδη του %)
Τα 1c και 1d εχουν μεγαλη διαφορα ταχυτητας αν δεν χρησιμοποιηθουν τα / και %

Erevis
Δημοσιεύσεις: 56
Εγγραφή: 12 Ιουν 2008 16:31
Τοποθεσία: Χαλάνδρι

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από Erevis » 08 Σεπ 2008 04:44

Αποφάσισα να προσεγγίσω την άσκηση από την αρχή(γι'αύτο άργησα να ποστάρω τοσο :P)

ορίστε ο κώδικας

Κώδικας: Επιλογή όλων

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

#define N 10000

int isPrime&#40;long x&#41;; //vriskei an enas ari8mos einai prwtos
int nextPrime&#40;long x&#41;; //vriskei ton epomeno prwto
int SortArrays&#40;long x&#91;&#93;,long y&#91;&#93;,long j&#91;&#93;,long n&#41;; //ta3inomei tous pinakes

int main&#40;void&#41;
&#123;
    long i;
    long x;
    long cnt=0; //metraei poses omades exoume vrei
    long a=3; //1os prwtos ari8mos
    long b=5; //2os prwtos ari8mos
    long from&#91;N&#93;=&#123;0&#125;; //pinakas pou krataei ton prwto apo 2 diadoxikous prwtous
    long to&#91;N&#93;=&#123;0&#125;; //pinakas pou krataei ton deutero apo 2 diadoxikous prwtous
    long group&#91;N&#93;=&#123;0&#125;; //punakas pou krataei th diafora twn duo prwtwn
    long cGroup=1; //mas deixnei to group pou psaxnoume 
    
    for&#40;x=0;x<=N && b<N;x++&#41;
    &#123;
        from&#91;x&#93;=a;  //kataxwreitai h arxh tou group
        to&#91;x&#93;=b;    //to telos tou
        group&#91;x&#93;=b-a-1; //to mege8os tou
        
        a=b; //h arxh tou neou group einai to telos tou prohgoumeno
        b=nextPrime&#40;b&#41;;//psaxnoume ton epomeno prwto me vash auton pou vriskomaste auth th stigmh
        if&#40;b-a-1!=0&#41; cnt++;      //an h diafora den einai mhden exoume mia omada
    &#125;
    SortArrays&#40;group,from,to,cnt&#41;; //ta3inomountai oi pinakes
    
    for&#40;i=1;i<=cnt;i++&#41; //emfanizei tis omades
    &#123;
        if&#40;group&#91;i&#93;==cGroup&#41; //an to group pou psaxnoume einai iso me to group ths 8eshs tou pinaka emfanizetai to apotelesma
        &#123;                    //etsi e3asfalizetai oti den 8a ektupw8oun group me ton idio ari8mo stoixeiwn
             printf&#40;"First %d consecutive composites from %d to %d\n",cGroup,from&#91;i&#93;+1,to&#91;i&#93;-1&#41;;
             cGroup+=2; //an vre8ei allazoume thn omada pou psaxnoume
        &#125;           
    &#125;
    
    system&#40;"PAUSE"&#41;;
&#125;

int nextPrime&#40;long x&#41;
&#123;
    x++; //pame ston epomeno ari8mo
    while&#40;x<=N&#41;
    &#123;
           if&#40;isPrime&#40;x&#41;&#41; return x; //an einai prwtos epistrefei ton ari8mo
           else x++; // an oxi pame ston epomeno ari8mo
    &#125;
    return N;
&#125;

int isPrime&#40;long x&#41;
&#123;
    long y=&#40;int&#41;sqrt&#40;x&#41;;
    long i; 
    
    if&#40;x%2==0&#41; return 0; //an diaireitai me to 2 akrivws einai sun8etos
    if&#40;x%3==0&#41; return 0;//me to 3 epishs
    
    for&#40;i=5;i<=y;i+=2&#41;//de xreiazetai na 3anatsekaroune allous artious, tsekaroume tous monous mexri thn riza tou ari8mou
    &#123;                 //opou 8a vriskontai AN uparxoun ta poll/sia tou
            if&#40;x%i==0&#41; return 0;
    &#125;
return 1;
&#125;

int SortArrays&#40;long x&#91;&#93;,long y&#91;&#93;,long j&#91;&#93;,long n&#41; //ta3inomhsh fusalidas
&#123;
    long i,k;
    long temp;
    
    for&#40;i=0;i<=n;i++&#41;
    &#123;
        for&#40;k=0;k<=n-i-1;k++&#41;
        &#123;
            if&#40;x&#91;k+1&#93;<x&#91;k&#93;&#41;
            &#123;
                           temp=x&#91;k+1&#93;;
                           x&#91;k+1&#93;=x&#91;k&#93;;
                           x&#91;k&#93;=temp;
                           temp=y&#91;k+1&#93;;
                           y&#91;k+1&#93;=y&#91;k&#93;;
                           y&#91;k&#93;=temp;
                           temp=j&#91;k+1&#93;;
                           j&#91;k+1&#93;=j&#91;k&#93;;
                           j&#91;k&#93;=temp;
            &#125;
        &#125;
    &#125;
&#125;
ως προς το θέμα της ταχύτητας το πρόγραμμα έχει πολύ καλύτερη απόδοση αλλά πάλι για μεγάλες τιμές του N, όχι μόνο δεν τρέχει γρήγορα,αλλά crasharei αμέσως :(

Φίλε bxenos αφήνω προς το παρών ο,τι έχει σχέση με μεταβλητές και πράξεις binary γιατί δεν τα έχω κατανοήσει πλήρως..σ'ευχαριστώ όπως και να χει!

Άβαταρ μέλους
bxenos
Δημοσιεύσεις: 53
Εγγραφή: 18 Αύγ 2008 19:56

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από bxenos » 09 Σεπ 2008 23:33

οταν κανεις αιτηση μνημης απο στηβα (stack) δηλαδη αυτοματες μεταβλητες οπως

Κώδικας: Επιλογή όλων

long x&#91;N&#93;;
ξερεις ποση μνημη ζητας απο το φτωχο stack;
φυσικα κολαει σε μεγαλα Ν. Το stack ειναι προσωρινη μνημη για τις μεταβλητες των εκτελουμενων συναρτησεων οχι μνημη για να τη δεσμευεις και να την κρατας επ'απειρον.
ενα προβλημα ειναι λοιπον ο πολυ μεγαλος ογκος μνημης και πιο μεγαλο προβλημα που ειναι απο το stack.

αλλο προβλημα στον χρονο ειναι οτι καλεις την sqrt (η οποια κανει αρκετες διαιρεσεις οι οποιες ειναι χειροτερες απο αντιστοιχους πολλαπλασιασμους) ενω θα μπορουσες με καλυτερη λυση να εξεικονομισεις χρονο.
και ενα λογικο σφαλμα ειναι οτι το αποτελεσμα της sqrt το κανεις int αρα χανεις τιμες για μεγαλα N.

αλλο προβλημα οτι καλεις πολλες φορες isPrime(x) για το ιδιο x. ειναι χρονοβορα διαδικασια, μην την καλεις χωρις λογο.

Άβαταρ μέλους
bxenos
Δημοσιεύσεις: 53
Εγγραφή: 18 Αύγ 2008 19:56

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από bxenos » 10 Σεπ 2008 00:22

στην συναρτηση isPrime(x), ο 3 ειναι πρωτος ή οχι;

εκανα τις διορθωσεις που ανεφερα, εβαλα Ν ενα εκατομυριο και ο Pentium 4 στα 1,8GHz υπολογισε απο μια φορα και αποθηκευσε σε πινακα ολους τους πρωτους αριθμους απο 1 εως Ν σε χρονο λιγοτερο απο 1 δευτερολεπτο.
κατω απο 1 δευτερολεπτο εκανε και ο κωδικας σου για να γεμισει τους πινακες from/to.
Εκανε ομως παρα πολυ χρονο (σχεδον 2 λεπτα) στην ταξινομιση καθως εχεις διαλεξει πολυ κακη μεθοδο ταξινομησης.

Erevis
Δημοσιεύσεις: 56
Εγγραφή: 12 Ιουν 2008 16:31
Τοποθεσία: Χαλάνδρι

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από Erevis » 10 Σεπ 2008 03:52

Το ξέρω φίλε μου και συγνώμη αν το πρόγραμμα είναι κακογραμμένο με αρκετά λόγικα λάθη,είμαι αρχάριος γι'αυτό (να φανταστείς τώρα θα μπω στο πρώτο εξάμηνο σε σχολή πληροφορικής).Προσπαθώ να εξασκηθώ γιατί μ'αρέσει πολύ ο προγραμματισμός.

Η ταξινόμηση αυτή ειναι απομεινάρι της Γ'Λυκείου :D.

Τελικά το πρόγραμμα το έκανα να δουλεύει σωστά όπως λέει στην εκφώνηση...την οποία δεν είχα κατανοήσει σωστά με αποτέλεσμα να παιδεύομαι.Το πρόγραμμα εξαρχής δε θα έπρεπε να ψάχνει για 1,2,3,4,5,6,...,N αριθμούς αλλά για 1,3,5,..,N πρώτες ομάδες σύνθετων.Αποτέλεσμα ήταν να γίνονται πολλοί άσκοποι υπολογισμοί!

Ευχαριστώ για την βοήθεια σας :)

lakritidis
Δημοσιεύσεις: 401
Εγγραφή: 04 Αύγ 2005 14:35
Τοποθεσία: Katerini
Επικοινωνία:

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από lakritidis » 11 Σεπ 2008 00:23

Για την ταξινόμηση, χρησιμοποίησε την qsort που είναι υλοποιημένη στην STL.

H qsort υλοποιεί την QuickSort, με O(nlogn) average και Ο(n^2) worst case.

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Άσκηση στη C με σύνθετους και πρώτους αριθμούς

Δημοσίευση από dva_dev » 11 Σεπ 2008 15:45

Ουάου! (πέτυχα ξεκλείδωτο access point από μια καφετέρια εδώ δίπλα και ένα σημείο κοντά στο παράθυρο που έχει σήμα, οπότε ενέδωσα στον πειρασμό και συνθέθηκα! :oops: )

Λοιπόν, αν ακολουθήσεις την πρόταση του bxenos με μια μικρή τροποποίηση μπορείς να πετύχεις ακόμα καλύτερους χρόνους.

Καταρχάς αφήνεις όλους τους ελέγχους σε δεύτερη μοίρα και ψάχνεις αρχικά για το ποιοί είναι πρώτοι και ποιοί όχι. Οποιον αριθμό βρίσκεις ότι είναι πρώτος τον βάζεις σε ένα πίνακα (ή λίστα).
Αφού έχεις μαζέψει όλους τους πρώτους (π.χ. για Ν=10.000.000 βρίσκεις ότι έχεις περίπου 650.000 πρώτους - είναι τυχαίο το νούμερο). (1)

Πας τώρα να υπολογίσεις ποιές είναι οι ακολουθίες σύνθετών (το πλήθος τους βασικά). Μια καλή πρόταση είναι αυτά να τα βάλεις σε έναν πίνακα που κρατάει τα (πλήθος, από, εώς). Τι μέγεθος πρέπει να έχει αυτός ο πίνακας; Να μην είναι ούτε πολύ μεγάλος ούτε πολύ μικρός; Η απάντηση μπορεί να βρεθεί χρησιμοποιώντας απλά(;) μαθηματικά (με τα οποία θα ασχοληθούμε παρακάτω).

Αφού έχουμε τον πίνακα πως θα τον γεμίσουμε; Πάμε στη λίστα και απλώς αφαιρούμε το κάθε στοιχείο από το επόμενο του, μείον ένα, για να δούμε πόσα είναι τα νούμερα που παρεμβάλλονται.
Π.χ. θα έχουμε στη λίστα μας τα νούμερα, 1,2,3,5,7,11,13,17,...
2-1-1 = 0 (από το 1 ως το 2 δεν παρεμβάλλεται κανένας σύνθετος)
3-2-1 = 0 το ίδιο
5-3-1 = 1 παρεμβάλλεται ένας σύνθετος (το κρατάμε σαν πλήθος:1 από: 3+1, εώς 5-1)->1,4,4 στην 1η (όσο είναι το πλήθος δηλαδή) θέση του πίνακα. (δεν έχω μπορέσει με την γρήγορη αναζήτηση που έκανα να βρώ κάποια σελίδα που να αποδεικνύει γιατί δεν υπάρχει περίπτωση το πλήθος των συνεχόμενων σύνθετων σε ένα σύνολο Ν αριθμών να είναι μεγαλύτερο από την τετρ. ρίζα του Ν. Μερικές δοκιμές όμως που έκανα αυτό έδειξαν).
7-5-1 = 1 το αγνοούμε γιατί έχουμε βρεί ήδη πλήθος 1.
11-7-1 = 3 παρεμβάλλονται 3 σύνθετοι το βάζουμε στην τρίτη θέση σαν 3,7+1,11-1->3,8,10
κ.λπ.
Οπότε έχουμε στον πίνακα μας ήδη τα πλήθη με τα αντίστοιχα νούμερα ταξινομημένα ήδη. Το μόνο πρόβλημα είναι ότι μπορεί να μήν έχουμε βρεί κάποια πλήθη ένω έχουμε βρεί μεγαλύτερα. Δηλαδή αν πάρουμε σαν Ν αρκετά μεγάλο νούμερο παρότι πλήθος 71 σύνθετων στη σειρά μπορούμε να το βρούμε μέσα στις πρώτες 32000 αριθμούς για να βρούμε το αμέσως μικρότερο πλήθος των 69 σύνθετων θα πρέπει να ελέγξουμε ακόμα περίπου 140.000 αριθμούς αφού τα αντίστοιχα νούμερα βρίσκονται στα:
71 consecutive composites from 31398 to 31468
69 consecutive composites from 173360 to 173428

Πόσος μεγάλος πρέπει να είναι ο πίνακας; Πρέπει να είναι τόσο μεγάλος ώστε να χωράει τον μεγαλύτερο δυνατό συνδιασμό διαφορετικών πλήθων.
Οπότε πρέπει να χωράει πλήθος Π=1+3+5+7+9+... το οποίο αποτελείται από Λ όρους (το 1, το 3, ο 5) με το Π <= Ν. Αυτό το Λ λοιπόν πόσο είναι;
Εδώ δεν έκατσα να ψάξω στο internet για κάποια απάντηση αφού μια πολύ γρήγορη δοκιμή στο excel μου έδωσε τον τύπο: Λ=&#8730;Ν. Οπότε το μέγιστο πιθανό πλήθος διαφορετικών συνδιασμών σε σχέση με το παραπάνω που ανέφερα επιταχύνουν πολύ τον αλγόριθμο. Τώρα αν υπάρχει κάποιος που έχει βρεί κάτι που έρχεται σε αντίθεση με την παρατήρηση μου, ή κάποιος μαθηματικός πρέπει να με διορθώσει... :(
Μέχρι αποδείξεως του εναντίου, ας αρκεστούμε σε αυτά.

Μια δοκιμή πάντως με το νέο σκεπτικό (υπολογίζοντας μέχρι το ίδιο νούμερο με το προηγούμενο παράδειγμα) βελτιώνει αρκετά το χρόνο.
Συνημμένα
Primes v2.rar
Primes Spaces Test v2
(22.71 KiB) Μεταφορτώθηκε 345 φορές

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

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