freestuff.gr αρχική σελίδα
 FAQFAQ    ΑναζήτησηΑναζήτηση   Λίστα ΜελώνΛίστα Μελών   Ομάδες ΜελώνΟμάδες Μελών   <b>Εγγραφή Μέλους</b>Εγγραφή Μέλους 
 ΠροφίλΠροφίλ   Επιλογές μέλους Επιλογές   Τα bookmarks μου Τα bookmarks μου   Προσωπικά μηνύματαΠροσωπικά μηνύματα 
  διαφήμιση  

Καλώς ήρθατε στο forum μας! Για να συμμετάσχετε στις συζητήσεις θα πρέπει να είσαστε μέλος. Γίνετε μέλος τώρα!.

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


 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Moderators:  Super-Moderators, WebDev Moderators
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [14 Μηνύματα]      Bookmarks Tags: άσκηση Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
ΑποστολέαςΜήνυμα
Erevis


Μέλος από: 12 Ιουν 2008
Μηνύματα: 56
Περιοχή: Χαλάνδρι
View users profile
ΜήνυμαΣτις: 03 Σεπ 2008 15:18    Θέμα: Άσκηση στη C με σύνθετους και πρώτους αριθμούς Απάντηση με παράθεση  Mark this post and the followings unread

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

έχω μια άσκηση στη 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(int x); //elegxei an enas ari8mos einai sun8etos
int checkGroup(int group);//elexei an uparxei omada ki an einai h omada pou psaxnoume


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

int composite(int x)
{
    int i;
    for(i=2;i<x;i++)
    {
                    if(x%i==0) return 1;
    }
return 0;
}

int checkGroup(int group)
{
    int x=0;
    int from;//deixnei apo pou 3ekinaei h omada
    int to;  //pou teleiwnei
    while(x<=N)
    {
               if(composite(x))//psaxnei tous ari8mous mexri na vre8ei sun8etos h epanalhpsh
               {
                    from = x;//molis vre8ei sun8etos kataxwreitai sthn arxh ths omadas     
                    while(composite(x))
                    {
                                       x++;//psaxnoume gia tous upoloipous sun8etous ths omadas
                   
                    }
                    to = x;//kataxwreitai o epomenos apo ton teleutaio ths omadas
                    if(to-from==group)//an to mege8os ths omadas = me auto ths omadas pou psaxnoume
                           return from; //epistrefetai o prwtos ari8mos ths omadas
                    }
               }
               x++;     
    }
    return 0; //alliws epistrefeteai 0 gia na einai pseudhs h timh ths sunarthshs
}


Το πρόβλημα ειναι όμως ότι για τιμες του Ν μεγαλύτερες του 3000 το πρόγραμμα σέρνεται(λόγω της συνάρτησης που επιστρέφει αν ενας αριθμός είναι σύνθετος ή οχι ,προφανώς)

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

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

Μέλος από: 16 Σεπ 2005
Μηνύματα: 256+

View users profile Visit posters website
blog deviantART facebook linkedin 
ΜήνυμαΣτις: 03 Σεπ 2008 18:32    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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

[edit]Μπορείς να έχεις ένα τέτοιο αποτέλεσμα (βλ. zip) ή ακόμα καλύτερο με έναν καλό αλγόριθμο[/edit]



Primes.zip
 Description:
Primes Spaces Test

Download
 Filename:  Primes.zip
 Filesize:  27.21 KB
 Downloaded:  329 Time(s)


Last edited by dva_dev on 03 Σεπ 2008 19:16, edited 1 time in total
Erevis


Μέλος από: 12 Ιουν 2008
Μηνύματα: 56
Περιοχή: Χαλάνδρι
View users profile
ΜήνυμαΣτις: 03 Σεπ 2008 19:00    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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


Μέλος από: 12 Ιουν 2008
Μηνύματα: 56
Περιοχή: Χαλάνδρι
View users profile
ΜήνυμαΣτις: 04 Σεπ 2008 03:37    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

κώδικας:
int composite(int x)
{
   int temp;
   int i;
   if (x < 4) return 0;
   if (x%2==0) return 1;
   if (((x+1)%6==0)||((x-1)%6==0))
   {
        temp =(int)sqrt((float)x);
        for(i=3;i<=temp;i+=2 )
        {   
        if(x%i==0) return 1;
        }
        return 0;
    }
    return 1;
}


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

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

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

Μέλος από: 16 Σεπ 2005
Μηνύματα: 256+

View users profile Visit posters website
blog deviantART facebook linkedin 
ΜήνυμαΣτις: 04 Σεπ 2008 08:56    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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


Μέλος από: 12 Ιουν 2008
Μηνύματα: 56
Περιοχή: Χαλάνδρι
View users profile
ΜήνυμαΣτις: 04 Σεπ 2008 14:16    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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

Μέλος από: 16 Σεπ 2005
Μηνύματα: 256+

View users profile Visit posters website
blog deviantART facebook linkedin 
ΜήνυμαΣτις: 04 Σεπ 2008 14:55    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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


Μέλος από: 18 Αυγ 2008
Μηνύματα: 53

View users profile
ΜήνυμαΣτις: 04 Σεπ 2008 17:33    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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

typedef unsigned char bool;

unsigned _bitarray[N / 16];   //(1)

void set_flag(size_t Position,bool flag){
  πηγαινε στην θεση (Position / 16) στο bit (Position % 16) και βαλε το flag    //(1c,1d)
}

bool get_flag(size_t Position){
  επεστρεψε την τιμη της θεσης (Position / 16) στο bit (Position % 16)    //(1c,1d)
}


αυτο θα σου επιτρεψει να κανεις μια μονο αναζητηση για τον καθε αριθμο αν ειναι primary ή συνθετος.

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

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


Μέλος από: 12 Ιουν 2008
Μηνύματα: 56
Περιοχή: Χαλάνδρι
View users profile
ΜήνυμαΣτις: 08 Σεπ 2008 03:44    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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

κώδικας:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 10000

int isPrime(long x); //vriskei an enas ari8mos einai prwtos
int nextPrime(long x); //vriskei ton epomeno prwto
int SortArrays(long x[],long y[],long j[],long n); //ta3inomei tous pinakes

int main(void)
{
    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[N]={0}; //pinakas pou krataei ton prwto apo 2 diadoxikous prwtous
    long to[N]={0}; //pinakas pou krataei ton deutero apo 2 diadoxikous prwtous
    long group[N]={0}; //punakas pou krataei th diafora twn duo prwtwn
    long cGroup=1; //mas deixnei to group pou psaxnoume
   
    for(x=0;x<=N && b<N;x++)
    {
        from[x]=a;  //kataxwreitai h arxh tou group
        to[x]=b;    //to telos tou
        group[x]=b-a-1; //to mege8os tou
       
        a=b; //h arxh tou neou group einai to telos tou prohgoumeno
        b=nextPrime(b);//psaxnoume ton epomeno prwto me vash auton pou vriskomaste auth th stigmh
        if(b-a-1!=0) cnt++;      //an h diafora den einai mhden exoume mia omada
    }
    SortArrays(group,from,to,cnt); //ta3inomountai oi pinakes
   
    for(i=1;i<=cnt;i++) //emfanizei tis omades
    {
        if(group[i]==cGroup) //an to group pou psaxnoume einai iso me to group ths 8eshs tou pinaka emfanizetai to apotelesma
        {                    //etsi e3asfalizetai oti den 8a ektupw8oun group me ton idio ari8mo stoixeiwn
             printf("First %d consecutive composites from %d to %d\n",cGroup,from[i]+1,to[i]-1);
             cGroup+=2; //an vre8ei allazoume thn omada pou psaxnoume
        }           
    }
   
    system("PAUSE");
}

int nextPrime(long x)
{
    x++; //pame ston epomeno ari8mo
    while(x<=N)
    {
           if(isPrime(x)) return x; //an einai prwtos epistrefei ton ari8mo
           else x++; // an oxi pame ston epomeno ari8mo
    }
    return N;
}

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

int SortArrays(long x[],long y[],long j[],long n) //ta3inomhsh fusalidas
{
    long i,k;
    long temp;
   
    for(i=0;i<=n;i++)
    {
        for(k=0;k<=n-i-1;k++)
        {
            if(x[k+1]<x[k])
            {
                           temp=x[k+1];
                           x[k+1]=x[k];
                           x[k]=temp;
                           temp=y[k+1];
                           y[k+1]=y[k];
                           y[k]=temp;
                           temp=j[k+1];
                           j[k+1]=j[k];
                           j[k]=temp;
            }
        }
    }
}


ως προς το θέμα της ταχύτητας το πρόγραμμα έχει πολύ καλύτερη απόδοση αλλά πάλι για μεγάλες τιμές του N, όχι μόνο δεν τρέχει γρήγορα,αλλά crasharei αμέσως

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


Μέλος από: 18 Αυγ 2008
Μηνύματα: 53

View users profile
ΜήνυμαΣτις: 09 Σεπ 2008 22:33    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

οταν κανεις αιτηση μνημης απο στηβα (stack) δηλαδη αυτοματες μεταβλητες οπως
κώδικας:
long x[N];

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

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

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


Μέλος από: 18 Αυγ 2008
Μηνύματα: 53

View users profile
ΜήνυμαΣτις: 09 Σεπ 2008 23:22    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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


Μέλος από: 12 Ιουν 2008
Μηνύματα: 56
Περιοχή: Χαλάνδρι
View users profile
ΜήνυμαΣτις: 10 Σεπ 2008 02:52    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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

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

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


Μέλος από: 04 Αυγ 2005
Μηνύματα: 256+
Περιοχή: Katerini
View users profile Send email to user Visit posters website
ΜήνυμαΣτις: 10 Σεπ 2008 23:23    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

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

Μέλος από: 16 Σεπ 2005
Μηνύματα: 256+

View users profile Visit posters website
blog deviantART facebook linkedin 
ΜήνυμαΣτις: 11 Σεπ 2008 14:45    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

Λοιπόν, αν ακολουθήσεις την πρόταση του 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 μου έδωσε τον τύπο: Λ=√Ν. Οπότε το μέγιστο πιθανό πλήθος διαφορετικών συνδιασμών σε σχέση με το παραπάνω που ανέφερα επιταχύνουν πολύ τον αλγόριθμο. Τώρα αν υπάρχει κάποιος που έχει βρεί κάτι που έρχεται σε αντίθεση με την παρατήρηση μου, ή κάποιος μαθηματικός πρέπει να με διορθώσει...
Μέχρι αποδείξεως του εναντίου, ας αρκεστούμε σε αυτά.

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



Primes v2.rar
 Description:
Primes Spaces Test v2

Download
 Filename:  Primes v2.rar
 Filesize:  22.71 KB
 Downloaded:  341 Time(s)

Εμφάνιση Μηνυμάτων:   
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [14 Μηνύματα] Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Τώρα είναι 19 Ιαν 2017 18:56 | All times are UTC + 2


Email This Page to Someone! add to Favorites

     Powered by p h p B B © 2001,2005 p h p B B Group
Για άμεση επικοινωνία με τον διαχειριστή του freestuff.gr στο email: freestuff.gr(παπάκι)gmail.com


Copyright © 1999-2013 Freestuff.gr All Rights Reserved  
Version Aegean, designed by N. Tsaganos