Δυαδικη αναζητηση

bazinga13 · 25 Μαρτίου 2014

φιλοι μου καλημερα σας,λοιπον θελω τα φωτα σας,μαθαινω τον αλγοριθμο της δυαδικης αναζητησης και εχω κανει τα εξης,οριστε ο πρωτος κωδικας

#include <stdio.h>
  
int main()
{
  int i;
  int FirstPosition,LastPosition,MiddlePosition;
  int sizeOfTheArray,SearchNumber;
  int MyArray[100];
  
  sizeOfTheArray = 0;
  SearchNumber = 0;
  i = 0;
 
   printf("Enter the size of the array\n");
   scanf("%d",&sizeOfTheArray);
 
   printf("Enter %d integers\n",sizeOfTheArray);
 
   for ( i = 0 ; i < sizeOfTheArray; i++ )
   {
      scanf("%d",&MyArray[i]);
   }
   
   printf("Enter value to find\n");
   scanf("%d",&SearchNumber);
 
   FirstPosition = 0;
   LastPosition = sizeOfTheArray - 1;
   MiddlePosition = (FirstPosition+LastPosition)/2;
 
   while(FirstPosition <= LastPosition)
   {
      if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
      }
      
      else if(MyArray[MiddlePosition] == SearchNumber) 
      {
         printf("%d found at location %d.\n", SearchNumber,MiddlePosition+1);
         break;
      }
      
      else
           LastPosition = MiddlePosition - 1;
           MiddlePosition = (FirstPosition + LastPosition)/2;
           
   }
      if (FirstPosition > LastPosition)
      {
      printf("Not found! %d is not present in the list.\n",SearchNumber);
      }
}

ο αλγοριμος τρεχει μια χαρα αλλα εχει ενα πολυ μεγαλο κουλο που δεν μπορω να το καταλαβω με τιποτα,2 μερες το πασπατευω και μ εχει πιασει πονοκεφαλος

σ αυτο εδω το σημειο ετσι οπωσ ειναι τρεχει κανονικα και βγαζει σωστα αποτελεσματα

else
           LastPosition = MiddlePosition - 1;
           MiddlePosition = (FirstPosition + LastPosition)/2;

Αμα του βαλω αγκιστρα παυει να δουλευει

else
{
           LastPosition = MiddlePosition - 1;
           MiddlePosition = (FirstPosition + LastPosition)/2;
}

Μου εφαγε ΜΙΑ ΟΛΟΚΛΗΡΗ μερα για να καταλαβω γιατι δεν δουλευει ο κωδικας

Θελω την γνωμη σας για το εξης,μια και εφτιαξα τον παραπανω αλγοριθμο και δουλευει θελησα να τον σπασω σε συναρτησεις για να εξασκηθω λιγο με τις συναρτησεις,να καλω απ τη μια συναρτηση την αλλη,να στελνω τιμες απ την μια στην αλλη κτλ κτλ,η αληθεια ειναι οτι τυρανηθηκα πολυ μεχρι να το καταφερω,τελος παντων τα αποτελεσματα που βγαζει οταν τον τρεχω ειναι σωστα,δουέυει δηλαδη αλλα δεν ειναι τοσο αυτο που μ ενδιαφερει οσο το αν ειναι προγραμματιστικα σωστο αυτο που κανω η αν ειναι μπακαλιστικος τροπος προγραμματισμου.οριστε ο κωδικας

#include <stdio.h>
#include <stdbool.h>
  
void ShowResultsFunction(int aNumber)
{
    if(aNumber > 0)
    {
        printf("the element was found\n");
    }
    
    else
    {
        printf("the element was not found\n");
    }
}

void BinarySearchFunction(int MyArray[],int SearchNumber,int sizeOfTheArray)
{
    int FirstPosition,LastPosition,MiddlePosition;
    FirstPosition = 0;
    LastPosition = sizeOfTheArray - 1;
    MiddlePosition = (FirstPosition+LastPosition)/2;
    bool found = false;
    
    
    while(FirstPosition <= LastPosition)
    {
      if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
      }
      
      else if(MyArray[MiddlePosition] == SearchNumber) 
      {
         found = true;
         ShowResultsFunction(found);
         break;
      }
      
      else
           LastPosition = MiddlePosition - 1;  //ama valeis agkistra den doulevei
           MiddlePosition = (FirstPosition + LastPosition)/2;
           
   }
      if (FirstPosition > LastPosition)
      {
          found = false;
          ShowResultsFunction(found);
      }
    
}



void GetDataFunction(int ArraySize,int SearchElement,int Array[])
{
  int i;
  
   printf("Enter the size of the array\n");
   scanf("%d",&ArraySize);
   
   printf("Enter %d integers\n",ArraySize);
 
   for ( i = 0 ; i < ArraySize; i++ )
   {
      scanf("%d",&Array[i]);
   }
   
   printf("Enter element to find\n");
   scanf("%d",&SearchElement);
   
   BinarySearchFunction(Array,SearchElement,ArraySize);
   
}

int main()
{
  int sizeOfTheArray,SearchNumber;
  int MyArray[100];
  
  GetDataFunction(sizeOfTheArray,SearchNumber,MyArray);
}

Λοιπον θελω την βοηθεια σας για μερικα πραγματα που ηθελα να κανω αλλα δεν τα καταφερα

1)θα ηθελα αφου δωσει τιμες στον πινακα ο χρηστης να κανω εναν ελεγχο για το αν ειναι ταξινομημενος ο πινακας και αν δεν ειναι να τον ταξινομησω πρωτα.,πως μπορω να το κανω αυτο?

2)Θα ηθελα στην συναρτηση ShowResultsFunction που ελεγχω αν ο αριθμος υπαρχει η οχι να εμφανισω και τον αριθμο και την θεση του

Αυτα τα ολιγα,ευχαριστω και καλη σας μερα

imitheos · 25 Μαρτίου 2014

Ωραίος. Με τη πρώτη ματιά και χωρίς να τρέξω τον κώδικα βλέπω τα εξής:

φιλοι μου καλημερα σας,λοιπον θελω τα φωτα σας,μαθαινω τον αλγοριθμο της δυαδικης αναζητησης και εχω κανει τα εξης,οριστε ο πρωτος κωδικας
int main()
{
  int FirstPosition,LastPosition,MiddlePosition;
  int sizeOfTheArray,SearchNumber;
  int MyArray[100];

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

   for ( i = 0 ; i < sizeOfTheArray; i++ )

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

   while(FirstPosition <= LastPosition)
   {
      if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
      }
      
      else
           LastPosition = MiddlePosition - 1;

      MiddlePosition = (FirstPosition + LastPosition)/2;
           
   }
}
ο αλγοριμος τρεχει μια χαρα αλλα εχει ενα πολυ μεγαλο κουλο που δεν μπορω να το καταλαβω με τιποτα,2 μερες το πασπατευω και μ εχει πιασει πονοκεφαλος

σ αυτο εδω το σημειο ετσι οπωσ ειναι τρεχει κανονικα και βγαζει σωστα αποτελεσματα
else
           LastPosition = MiddlePosition - 1;
           MiddlePosition = (FirstPosition + LastPosition)/2;
Αμα του βαλω αγκιστρα παυει να δουλευει
else
{
           LastPosition = MiddlePosition - 1;
           MiddlePosition = (FirstPosition + LastPosition)/2;
}
Μου εφαγε ΜΙΑ ΟΛΟΚΛΗΡΗ μερα για να καταλαβω γιατι δεν δουλευει ο κωδικας

Ο αλγόριθμος δουλεύει όπως θα έψαχνες και εσύ σε ένα τηλεφωνικό κατάλογο. Χωρίζεις το εύρος στα δύο και ελέγχεις το τμήμα που πρέπει. Αυτό γίνεται κάθε φορά. Ας δούμε το if σου. Όταν η μεσαία τιμή είναι μικρότερη από αυτήν που θέλεις, τότε αυξάνεις κατά ένα την αρχή δηλαδή παίρνεις το δεξιό τμήμα με τις μεγαλύτερες τιμές. Ανάλογα όταν είναι μεγαλύτερη από αυτήν που θέλεις, τότε μειώνεις κατά ένα το τέλος για να πάρεις το αριστερό τμήμα.

Στο νέο τμήμα τώρα που έφτιαξες, πάλι πρέπει να ελέγχεις την μεσαία τιμή οπότε ο υπολογισμός του MiddlePosition πρέπει να γίνεται σε κάθε βήμα. Όταν έβαζες τα άγκιστρα, αυτός ο υπολογισμός γινόταν μόνο ως μέρος του else και όχι πάντα για αυτό και δεν δούλευε. Χωρίς τα άγκιστρα δούλευε πάντα όπως ήταν και το σωστό. Έχεις δουλέψει python μήπως ? Μου φαίνεται ότι σε μπέρδεψε το identation που είχες την γραμμή. Αν δεις το quote την έβαλα πιο έξω για να φαίνεται ότι εκτελείται πάντα.

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

imitheos · 25 Μαρτίου 2014

void ShowResultsFunction(int aNumber)
{
    if(aNumber > 0)
    {
        printf("the element was found\n");
    }
    
    else
    {
        printf("the element was not found\n");
    }
}

void BinarySearchFunction(int MyArray[],int SearchNumber,int sizeOfTheArray)
{
      else if(MyArray[MiddlePosition] == SearchNumber) 
      {
         found = true;
         ShowResultsFunction(found);
         break;
      }
      if (FirstPosition > LastPosition)
      {
          found = false;
          ShowResultsFunction(found);
      } 
}
1)θα ηθελα αφου δωσει τιμες στον πινακα ο χρηστης να κανω εναν ελεγχο για το αν ειναι ταξινομημενος ο πινακας και αν δεν ειναι να τον ταξινομησω πρωτα.,πως μπορω να το κανω αυτο?
2)Θα ηθελα στην συναρτηση ShowResultsFunction που ελεγχω αν ο αριθμος υπαρχει η οχι να εμφανισω και τον αριθμο και την θεση του

Αυτα τα ολιγα,ευχαριστω και καλη σας μερα

Για πρώτη προσπάθεια είναι καλή απλά παρέλειψε το "Function" από τα ονόματα. Είναι γνωστό σε όποιον κοιτά τον κώδικα ότι η BinarySearchFunction είναι συνάρτηση οπότε το BinarySearch αρκεί. Όταν ένα θέμα είναι πολύ γνωστό μπορείς να χρησιμοποιείς και πιο σύντομα ονόματα. Για παράδειγμα, όταν κάποιος βλέπει το i που έχεις στο for ξέρει αμέσως ότι χρησιμοποιείται σαν loop counter χωρίς να χρειάζεται να το ονομάσεις LoopCounter. Το ίδιο ισχύει και στην δυαδική αναζήτηση. Αν δεις τις συναρτήσεις που ορίζει το πρότυπο και παρέχουν οι υλοποιήσεις της C, αυτές ονομάζονται bsearch και lsearch αντίστοιχα και όλοι καταλαβαίνουν περί τίνος πρόκειται. Αυτό φυσικά είναι και πάλι υποκειμενική συμβουλή. Και το BinarySearch που έχεις είναι μια χαρά.

Για την ταξινόμηση του πίνακα μπορείς να γράψεις μια συνάρτηση που να κάνει bubble sort και στην περίπτωση που είναι ήδη ταξινομημένος δεν θα κάνει τίποτα απλά θα διατρέξει άδικα μία φορά τον πίνακα.

Για να εμφανίζεις την θέση και τον αριθμό μπορείς να αλλάξεις την δήλωση της συνάρτησης και αντί να δέχεται απλά ένα boolean όρισμα να δέχεται δύο ακεραίους που θα είναι η θέση και ο αριθμός και μετά να την καλείς ως ShowResults(MiddlePosition, SearchNumber)

bazinga13 · 25 Μαρτίου 2014

Φιλε μου την κσλημερα μου,σ ευχαριστω πολυ για τον χρονο που διεθεσες και για τις πολυτιμες συμβουλες σου/

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

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

Αυτο δεν το ειχα σκεφτει και δεν το ξερα οτι κουραζουν απλα το κανω απο θεμα γουστου,μ αρεσει αυτος ο τροπος γραφης και τα μεγαλα ονοματα,μαλλον θα πρεπει να μετακομισω προς java μερια,εκει εχω παρατηρησει οτι εχουν κστι ονοματα σιδηροδρομους Ενταξει θα το λαβω υποψην μου και θα τ αλλαξω.

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

Πολυ σωστο αυτο,δεν πηγε καν το μυαλο μου εκει,ωραιος ο παικτης,θα γινει κι αυτο

Δυστυχως δεν θελω να μπλεξω με pointers και malloc ακομα αν αυτο ενοεις,ασε που τα εχω ξεχασει τελειως αλλα θελω πριν παω εκει να ξαναθυμηθω τα πολυ βασικα,εδω χαθηκα μεσα σε 3 συναρτησεις αλλα αξιζε τον κοπο η τυραννια γιατι ξαναθυμηθηκα και ξεκαθαρισα τα ορισματα,τις παραμετρους,τα void;return κτλ κτλ

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

Ενοεις οτι σ αυτο το σημειο

 if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
      }

πρεπει να το κανω ετσι?

if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
        MiddlePosition = (FirstPosition + LastPosition)/2;
      }

Όταν έβαζες τα άγκιστρα, αυτός ο υπολογισμός γινόταν μόνο ως μέρος του else και όχι πάντα για αυτό και δεν δούλευε. Χωρίς τα άγκιστρα δούλευε πάντα όπως ήταν και το σωστό. Έχεις δουλέψει python μήπως?

Μου κανει εντυπωση αυτη η ιδιαιτεροτητα με τα αγκιστρα,δεν την ειχα ξανασυναντησει ποτε και ομολογω οτι δεν καταλαβα ακομα το γιατι δημιουργει προβλημα,δηλαδη για να καταλαβω καλυτερη πρακτικη ειναι να μην χρησιμοποιω καθολου αγκιστρα?δεν δημιουργει προβλημα πουθενα?

Οχι δεν εχω δουλεψει ποτε python,μονο λιγο C και αυτο πριν κατι αιωνες

Για την ταξινόμηση του πίνακα μπορείς να γράψεις μια συνάρτηση που να κάνει bubble sort και στην περίπτωση που είναι ήδη ταξινομημένος δεν θα κάνει τίποτα απλά θα διατρέξει άδικα μία φορά τον πίνακα.

πολυ ομορφα,το λυσαμε κι αυτο

Για να εμφανίζεις την θέση και τον αριθμό μπορείς να αλλάξεις την δήλωση της συνάρτησης και αντί να δέχεται απλά ένα boolean όρισμα να δέχεται δύο ακεραίους που θα είναι η θέση και ο αριθμός και μετά να την καλείς ως ShowResults(MiddlePosition, SearchNumber)

ειδες που σου λεω οτι ειμαι κουτσουρο τελειως σ ολο το προγραμμα αυτο κανω με τις συναρτησεις και αυτο δεν μπορεσα να το σκεφτω

Αυτα απο μενα,σ ευχαριστω και παλι και καλο μεσημερι

imitheos · 25 Μαρτίου 2014

   while(FirstPosition <= LastPosition)
   {
      if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
      }
      
      else if(MyArray[MiddlePosition] == SearchNumber) 
      {
         printf("%d found at location %d.\n", SearchNumber,MiddlePosition+1);
         break;
      }
      
      else
           LastPosition = MiddlePosition - 1;

----> MiddlePosition = (FirstPosition + LastPosition)/2;
           
   }

Μου κανει εντυπωση αυτη η ιδιαιτεροτητα με τα αγκιστρα,δεν την ειχα ξανασυναντησει ποτε και ομολογω οτι δεν καταλαβα ακομα το γιατι δημιουργει προβλημα,δηλαδη για να καταλαβω καλυτερη πρακτικη ειναι να μην χρησιμοποιω καθολου αγκιστρα?δεν δημιουργει προβλημα πουθενα?

Οχι δεν εχω δουλεψει ποτε python,μονο λιγο C και αυτο πριν κατι αιωνες

#include <stdio.h>

int main(void)
{
	int i = 0, j = 0;

	printf("Before: i = %d, j = %d\n", i, j);
	if (0) {
		i = 9;
	        j = 8;
	}
	printf("After1: i = %d, j = %d\n", i, j);
	if (0)
		i = 5;
	        j = 3;
	printf("After2: i = %d, j = %d\n", i, j);

	return 0;
}
Έξοδος:
Before: i = 0, j = 0
After1: i = 0, j = 0
After2: i = 0, j = 3

Το σώμα μιας εντολής if, while, κτλ είναι η επόμενη (και μόνο η επόμενη) δήλωση. Όταν θέλεις να έχεις περισσότερες της μιας δηλώσεις βάζεις τα άγκιστρα. Δες τον παραπάνω χαζό κώδικα. Στην αρχή οι μεταβλητές έχουν τιμή 0 λόγω του ορισμού τους. Το πρώτο if έχει άγκιστρα οπότε το σώμα του περιλαμβάνει τις δύο εντολές ανάθεσης. Λόγω της αναληθούς συνθήκης 0 δεν τρέχει καμμία από τις δύο και οι μεταβλητές συνεχίζουν να έχουν τιμή 0. Το δεύτερο if δεν έχει άγκιστρα οπότε το σώμα του είναι μόνο η πρώτη δήλωση (δηλαδή το i = 5). Η δήλωση "j = 3" δεν ανήκει στο if οπότε εκτελείται κανονικά και για αυτό το j καταλήγει να έχει τιμή 3.

Έτσι και στον αρχικό κώδικά σου η γραμμή "MiddlePosition = (FirstPosition + LastPosition)/2;" δεν ανήκει στο else και έτσι εκτελείται σε κάθε βήμα όπως είναι και το σωστό. Όταν βάζεις τα άγκιστρα την μετατρέπεις σε σώμα της else οπότε τρέχει μόνο όταν τρέχει το else που είναι λάθος.

Ενοεις οτι σ αυτο το σημειο

 if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
      }

πρεπει να το κανω ετσι?

if(MyArray[MiddlePosition] < SearchNumber)
      {
         FirstPosition = MiddlePosition + 1;    
        MiddlePosition = (FirstPosition + LastPosition)/2;
      }

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

Σύνδεση

Δυαδικη αναζητηση

Προτεινόμενες αναρτήσεις

bazinga13

imitheos

imitheos

bazinga13

imitheos

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση