Elektroda.pl
Elektroda.pl
X

Wyszukiwarki naszych partnerów

Wyszukaj w ofercie 200 tys. produktów TME
Europejski lider sprzedaży techniki i elektroniki.
Proszę, dodaj wyjątek elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Przeszukiwanie binarne w Turbo Pascal i C++.

zbigniew 10123 07 Mar 2010 22:22 4580 23
  • #1 07 Mar 2010 22:22
    zbigniew 10123
    Poziom 12  

    Witam Chodzi mi programy z algorytmem poszukiwania przez połowienie a oto temat:

    Cytat:
    Korzystając z algorytmu poszukiwania przez połowienie:
    1. Napisz program, który:
    - wprowadzi podane przez użytkownika liczby uporządkowane niemalejąco,
    - wprowadzi podaną przez użytkownika poszukiwaną liczbę,
    - wyprowadzi pozycję poszukiwanej liczby w podanym wcześniej zbiorze liczb lub poinformuje o jej braku
    Program ma być zapisany w języku Pascal i C++.
    2. Przedstaw w postaci schematu blokowego algorytm zastosowany w programie.

    Algorytm ma napisany tylko muszę go zbudować aby tutaj przedstawić.
    Programy najlepiej jakby były metodą iteracyjną bo tak zrobiłem algorytm.Nie znalazłem programu podobnego w necie aby go przedstawić.Jeden ma w C++ ale jest
    rekurencyjnie to go mogę umieścić,aby z waszą pomocą przerobić.
    Pozdrawiam

    0 23
  • #2 08 Mar 2010 07:52
    chudybyk
    Poziom 26  

    Witam!
    Jeśli masz algorytm to go zaprezentuj. Nikt za Ciebie nie będzie robił prostego zadanka.
    Jeszcze jedna prośba - postaraj się budować poprawne zdania w języku polskim.
    Pozdrawiam!

    0
  • #3 08 Mar 2010 15:51
    zbigniew 10123
    Poziom 12  

    Tą pracę robię na zaliczenie, a co do tematu pracy to nie wiem o co chodzi gdyż nie przerabiałem na zajęciach o tablicach i w tym jest problem.I nie wiem od czego zacząć? Mam programik w C++ w końcu coś jest i algorytm,tylko jest problem:kod się kompiluje dobrze, program uruchamia się i czarne oko system zgłasza błąd.

    To jest kod źródówy:

    Code:
     #include <cstdlib>
    
    #include <iostream>

    using namespace std;

    int main( )
    {
       
        int x,ip,ik,isr,m;
        int a[m];
        cout<<"Podaj liczbe elementow tablicy: ";
        cin>>m;
        cin.ignore();
        cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
        for(int k=0;k<m;k++)
        {
                cin>>a[k];
                cin.ignore();
        }
        cout<<"Podaj element do wyszukania: ";
        cin>>x;
        cin.ignore();
        ip=0;
        ip=m-1;
        while(ip<=ik)
        {
                   isr=(ip+ik)/2;
                   if(a[isr]==x)
                   {
                              cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<endl;
                              getchar();
                              return 0;
                   }
                   if(a[isr]<x)
                             ip=isr+1;
                   else
                       ik=isr-1;
        }
        cout<<"Nie znaleziono elementu "<<x<<endl;
        getchar();
        return 0;
    }

       



    Po moich domysłach uważam że powinna być gdzieś zadeklarowana tablica,ale nie wiem gdzie ?


    I tak samo ale w TP nie wiem też może prosiłbym o podpowiedz w linku gdzie są tego typu zadania-oczywiście też szukałem i sporo znalazłem do innych sortowań ale nie przez podział. Jeśli znajdę może inny programik to dopnę dla ułatwienia.

    0
  • #4 09 Mar 2010 07:43
    chudybyk
    Poziom 26  

    1. tablica int a[m] nie może być tak zadeklarowana. Parametr 'm' jest nieznany w fazie kompilacji, więc nie można ustalić wielkości tablicy. Trzeba zadeklarować bardzo dużą, żeby pomieścić maksymalną ilość danych, lub utworzyć tablicę operatorem 'new' po ustaleniu jej wielkości.
    2. Do czego ma służyć funkcja "cin.ignore(); "? Czy program nie będzie pomijał liczb?
    3. Przed pętlą główną zamiast ip=m-1; powinno być ik=m-1;
    4. Program oczywiście nie jest rekurencyjny.
    5. Przepisanie go do Pascala to prosta sprawa. Budowa kodu będzie taka sama, różnice w wersjach będą wynikać tylko z odmiennej gramatyki i składni języka. Największa różnica - zamiast obiektów cin i cout należy użyć funkcji writeln() i readln().
    6. Programu nie kompilowałem. Daj znać jeśli znowu utkniesz.

    0
  • #6 09 Mar 2010 21:43
    zbigniew 10123
    Poziom 12  

    FirstStep-chciałbym koledze podziękować za materiał pomocny w .pdf.
    Kod poprawiłem,kompiluje się i uruchamia, a gdy przejdzie do "Podaj element do wyszukania: " po wpisaniu wartości zamyka okno i koniec nie przechodzi do dalszych instrukcji. Gdzie tkwi problem ?
    Podaję kod do poprawy i działanie programu po uruchomieniu.

    Code:
     #include <cstdlib>
    
     #include <iostream>
     //#include<conio.h>

    using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
       
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     int a[m];
      for(int k=0;k<m;k++)
       {
        cin>>a[k];
             
        }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
       {
        ip=0;
        ik=m-1;
        getchar();
        return 0;
        while(ip<=ik)   

           isr=(ip+ik)/2;
           if(a[isr]==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<endl;
             getchar();
             return 0;
            }
              if(a[isr]<x)
              ip=isr+1;
               else
                ik=isr-1;
        }
        cout<<"Nie znaleziono elementu "<<x<<endl;
        getchar();
        return 0;
        }

       



    Powinien działać bo sprawdzałem.

    Dodano po 6 [minuty]:

    Przeszukiwanie binarne w Turbo Pascal i C++.
    Tak wygląda działający nie do końca program.I tu się właśnie kończy działanie programu.

    Dodano po 2 [godziny] 47 [minuty]:





    Podczas ciężkich prób stworzyłem kod w Turbo Pascalu.
    Błędy to:kompiluje się i uruchamia,ale źle wylicza wartości i nie podaje pozycji.
    Umieszczam poniżej kod i uruchomiony program.
    Code:
    program podz;
    
      uses crt;
       var
         p,n,y,i,q:integer;
          a: Array [0..1000] of integer;
     begin

       clrscr;
       writeln('Wprowadz liczbe wyrazow ciagu: ');
       readln(n);
       writeln('Wprowadz szukana liczbe wyrazow ciagu: ');
       readln(y);

         for i:= 0 to n-1 do
         begin
           writeln('Wprowadz',' i ', 'wyraz ciagu: ');
           read(a[i]);
           end;
            p:=0;
            q:=n-1;
               while (p<>q) do
            begin
               if(y<=(A[q+p] div 2)) then
              begin
                q:=(q+p)div 2;
                if (y=A[q]) then
                begin
                writeln('Szukana liczba wystepuje na miejscu: ', q );
                end;
                end
            else
                    p:=1+(q+p) div 2;
            end;
                    if (A[p]=y)then
                      writeln('Szukana liczba wystepuje na miejscu: ', p )
                       else
                        writeln('Szukana liczba nie wyst©puje w danym ciagu liczb.');
                     readln;
                     readkey;
                    end.

    Przeszukiwanie binarne w Turbo Pascal i C++.
    I tu się pojawia problem, próbowałem za mieniać zmienne między "0 i 1" wyniki wychodziły takie same.
    Pozdrawiam :cry: i czekam na konkretne propozycje

    0
  • #7 10 Mar 2010 01:52
    bomkallo
    Poziom 11  

    twoje int a[m] nadal jest blednie uzyte...
    zrob sobie int a[2048]; nie sadze, zebys chcial wpisywac tyle liczb::P
    w tym przypadku M jest tylko liczba argumentow, o ktore program zapyta, wiec ta tablica w takim rozmiarze cie usatysfakcjonuje...
    nastepnie w kodzie ni stad ni zowad pojawia sie return 0.... w samym srodku:P to zapewne wylacza ci nagle program:)

    pozatym jak na szukanie indeksu danej liczby i nie majacy nic wspolnego z "binarnymi" danymi jest wyjatkowo skomplikowanie napisany:P Wyszukanie liczby w tablicy i zwrocenie jej indeksu to 3 linijki jakos...

    0
  • #8 10 Mar 2010 19:16
    zbigniew 10123
    Poziom 12  

    Pozmieiałem kod i się nie zamyka ale nie do końca analizuje instrukcje.Nie wiem jak napisać z tą tablicą.
    Czy mógłby ktoś sprawdzić umieszczony kod w Turbo Pascalu wstawiony wcześniej.
    Podaję kod i zrzut w C++.

    Code:

     #include <iostream>
     #include<cstdio>
    using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     int a[m];
      for(int k=0;k<m;k++)
       {
        cin>>a[k];
             
        }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
          cin.ignore();
       {
        ip=0;
        ik=m-1;
        getchar();
        return 0;
        while(ip<=ik)   
               
           isr=(ip+ik)/2;
           
           if(a[ik]==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<endl;
             getchar();
             return 0;
            }
              if(a[isr]<x)
              ip=isr+1;
               else
                ik=isr-1;
        }
        cout<<"Nie znaleziono elementu "<<x<<endl;
        getchar();
        return 0;
        }

       

    Przeszukiwanie binarne w Turbo Pascal i C++.
    Program nie przechodzi dalej ,po naciśnięciu ' ENTER ' zamyka okno.

    0
  • #9 10 Mar 2010 20:00
    FirstStep
    Poziom 12  

    Code:

     #include<iostream>
     #include<cstdio>
    using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     int* a= new int[m];
     
     for(int k=0;k<m;k++)
     {
        cin>>a[k];
     }       
     
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
          cin.ignore();
       
        ip=0;
        ik=m;

       isr=(ip+ik)/2;

        while(ip<=ik)
       {                 
           
           if(a[isr]==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<". Pamietaj ze numerujemy od 0"<<endl;
             getchar();
             return 0;
          }
           
          if(a[isr]<x)
          {
              ip=isr+1;
          }
          else
          {
                ik=isr-1;
          
          }

          if(ip==ik) break;


       }
          
          cout<<"Nie znaleziono elementu "<<x<<endl;
          
          getchar();   
          delete a;
          return 0;
    }


    Napisz jak czegoś nie rozumiesz.

    0
  • #10 10 Mar 2010 21:06
    zbigniew 10123
    Poziom 12  

    Poprawiłem kod na samym końcu dodałem klamrę brakowało sam porównaj,ale działa tylko na liczbę '2'

    Na innych liczbach jest jak wcześniej.Przeszukiwanie binarne w Turbo Pascal i C++.

    Code:

     #include <iostream>
     #include<cstdio>
    using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     int* a= new int[m];
      for(int k=0;k<m;k++)
       {
        cin>>a[k];
             
        }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
          cin.ignore();
       {
        ip=0;
        ik=m;
         
        isr=(ip+ik)/2;
       
        while(ip<=ik)
        {
           if(a[ik]==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<"Numerujemy od 0"<<endl;
             getchar();
             return 0;
            }
              if(a[isr]<x)
            {
              ip=isr+1;
            } 
            else
            {
                ik=isr-1;
            }
            if(ip==ik) break;
     }
        cout<<"Nie znaleziono elementu "<<x<<endl;
        getchar();
        delete a;
        return 0;
       }
    }
       



    Dodano po 5 [minuty]:

    Podstawiałem inne cyfry narastająco ale nic kompiluje się a dalej ani rusz. :cry:
    Ta funkcja
    Code:
    int* a= new int[m]; 
    to chyba wskaźnik? Aby tylko działał bo to na pracę kontrolną,

    Dodano po 19 [minuty]:

    Acha kolego jeśli znasz się na TP to zobacz ten kod.Bo już mi te zadania czubkiem głowy wychodzą po prostu już mi brak cierpliwości a do piątku muszę zrobić.
    Pozdrawiam :cry:

    Dodano po 1 [minuty]:

    Acha kolego jeśli znasz się na TP to zobacz ten kod.Bo już mi te zadania czubkiem głowy wychodzą po prostu już mi brak cierpliwości a do piątku muszę zrobić.
    Pozdrawiam :cry:

    0
  • #11 10 Mar 2010 21:57
    FirstStep
    Poziom 12  

    Faktycznie wcześniej pomieszałem coś :] Teraz już działa. Problem był z indeksowaniem tablicy, uporządkowany kod:

    Code:

     #include<iostream>
     #include<cstdio>
    using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     
     cin>>m;
     cin.ignore();

     int* a= new int[m]; // Dynamiczna alokacja pamieci dla tablicy o m-elementach
     int tmp; //pomocnicza zmienna przechowujaca:  tmp = a[isr+1];
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     
     
     for(int k=1;k<=m;k++)
     {
        cin>>a[k+1];
     }       
     
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
         
       
        ip=1;
        ik=m;
       

        while(ip<=ik)
       {              
          isr=(ip+ik)/2; 
          tmp = a[isr+1];
          
           if(tmp==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<"."<<endl;
             break;
          }
           
          if(x<tmp)
          {
            ik=isr-1;
             
          }
          else
          {
            ip=isr+1;           
         
          }

       
       }
         
          system("pause");
          getchar();   
          delete a;
          return 0;
    }


    Cytat:

    int* a= new int[m];


    Tak to jest wskaźnik, który otrzymał od operatora "new" adres utworzonej tablicy. Na koniec trzeba zawsze usunąć taki wskaźnik -> "delete".

    TP nie pamiętam już ;-)

    Cheers

    0
  • #12 10 Mar 2010 23:41
    zbigniew 10123
    Poziom 12  

    Jest mały problem,przepisałem.Program kompiluje się ale na końcu zamyka okno i nie wyświetla rezultatów.Widzę że kod zmienił strukturę w innym kierunku:

    Code:

     #include <iostream>
     #include<cstdio>
     using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
      cin.ignore();
     
      int* a= new int[m];// Dynamiczna alokacja pamieci dla tablicy o m-elementach
      int tmp; //pomocnicza zmienna przechowujaca:  tmp = a[isr+1]; 
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     
      for(int k=1;k<=m;k++)
       {
        cin>>a[k+1];
             
        }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
         
       
        ip=1;
        ik=m;
       
         while(ip<=ik)
        { 
          isr=(ip+ik)/2;
          tmp = a[isr+1];
       
         
           if(tmp==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<"Numerujemy od 0"<<endl;
             break;
            }
             
              if(x<tmp)
            {
              ip=isr-1;
            } 
            else
              {
                ip=isr+1;
              }
         
       }
        //cout<<"Nie znaleziono elementu "<<x<<endl;
        system("pause");
        getchar();
        delete a;
       
        return 0;
       
       }

       


    Oczywiście 'brak elementu ' musi być , umieściłem w komentarz aby sprawdzić czy działa.

    0
  • #13 11 Mar 2010 12:51
    FirstStep
    Poziom 12  

    Wywal getchar() i delete a, tak dla sprawdzenia i zobacz czy dalej sie zamyka okno.

    0
  • #14 11 Mar 2010 23:25
    zbigniew 10123
    Poziom 12  

    Code:

     #include <iostream>
     #include<cstdio>
     #include<conio.h>
     using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
      cin.ignore();
     
      int* a= new int[m];// Dynamiczna alokacja pamieci dla tablicy o m-elementach
      int tmp; //pomocnicza zmienna przechowujaca:  tmp = a[isr+1]; 
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     
      for(int k=1;k<=m;k++)
       {
        cin>>a[k+1];
             
        }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
         
       
        ip=1;
        ik=m;
       
         while(ip<=ik)
        { 
          isr=(ip+ik)/2;
          tmp = a[isr+1];
       
         
           if(tmp==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<"Numerujemy od 0"<<endl;
              break;
             
            }
             
              if(x<tmp)
            {
              ip=isr-1;
            } 
            else
              {
                ip=isr+1;
              }
         
       }
        //cout<<"Nie znaleziono elementu "<<x<<endl;
        system("pause");
        //getchar();
       
        //delete a;
        return 0;
       
       }

       


    Nadal zamyka okno, podejrzewam że może brakować jakiejś biblioteki do
    Code:
    getchar();
    ,powinien działć robiłem inne zadanie i ta funkcja działała i okno nie zamakł w konsoli a tu nie.Wstawiałem w inne miejsce,ale to samo.Trochę to dziwne bo w prostym kodzie, w którym próbowałem nie zamka okna ,a tu jest i lipa.Jak uważasz? Dopisałem bibliotekę
    Code:
    #include<cstdio>
    do obsługi
    Code:
    getchar();
    i nie działa? :cry:

    Dodano po 2 [godziny] 31 [minuty]:

    W czasie zmagań coś jest ale:Przeszukiwanie binarne w Turbo Pascal i C++.
    do '5' elementów tablicy naciśnięciu ENTER zamyka okno.Gdy wpiszę '10 ' elementową tablicę wyświetla z błędem.Przeszukiwanie binarne w Turbo Pascal i C++.

    Dodano po 18 [minuty]:

    Zacząłem szukać innego rozwiązania i to są działania programu przez "Debug" w Dev-C++Przeszukiwanie binarne w Turbo Pascal i C++. Nie chcę się zamknąć po naciśnięciu ENTER.

    Dodano po 18 [minuty]:

    Przeszukiwanie binarne w Turbo Pascal i C++.
    Code:
    cout<<"Nie znaleziono elementu "<<x<<endl;  
    Musi być jeśli brak liczby
    Code:
    //getchar();
    
           //delete a;
    nie działa próbowałem Przeszukiwanie binarne w Turbo Pascal i C++. >Inny sposób z liczbami. :cry:

    Dodano po 13 [minuty]:

    Co jest tu zgrane że z głównego okna nie działa prawidłowo tylko przez "Debug",czy to winna zmiennych? :cry: Podaje dla ułatwienia kod:
    Code:

     #include <iostream>
     #include<cstdio>
     #include<conio.h>
     using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     cin.ignore();
     
      int* a= new int[m];// Dynamiczna alokacja pamieci dla tablicy o m-elementach
      int tmp; //pomocnicza zmienna przechowujaca:  tmp = a[isr+1]; 
     cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
     
      for(int k=1;k<=m;k++)
       {
        cin>>a[k+1];     
       }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
         
       
        ip=1;
        ik=m;
       
         while(ip<=ik)
        { 
          isr=(ip+ik)/2;
          tmp = a[isr+1];
       
         
           if(tmp==x)
            {
             cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<endl;
              break;
             
            }
             
              if(x<tmp)
              {
               
               ik=isr-1;
              } 
            else
              {
                ip=isr+1;
               
              }
         
       
          }
          cout<<"Nie znaleziono elementu "<<x<<endl;     
          system("pause");
         //getchar();
        //delete a;
        return 0;
       
      }



       

    Zwłaszcz że
    Code:
    //getchar(); //delete a;
    nie daje różnicy ? Gdzie
    może być ten błąd. :cry: czekam na pomoc.
    Pozdrawiam

    Dodano po 5 [godziny] 43 [minuty]:

    Mimo braku odpowiedzi od kolegi więc pisałem i myślałem, aż zmodyfikowałem kod min:zmieniłem indeksowanie od ' 0 ' i warunek w pętli
    Code:
    for(int k=0;k<m;k++)
    i na końcu dopisałem
    Code:
    if(ip>ik)
    gdy brak elementu, a tak wygląda cały kod:
    Code:

     #include <iostream>
     #include<cstdio>
     #include<conio.h>
     using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     cin.ignore();
     
      int *a= new int[m];// Dynamiczna alokacja pamieci dla tablicy o m-elementach
      int tmp; //pomocnicza zmienna przechowujaca:  tmp = a[isr+1]; 
      cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
      cout<<"****************************************"<<endl;
      for(int k=0;k<m;k++)
       {
       
        cin>>a[k+1];     
       }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
         
       
        ip=0;
        ik=m;

         while(ip<=ik)
        { 
          isr=(ip+ik)/2;
          tmp = a[isr+1];
       
         
           if(tmp==x)
            {
            cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<" Numerujemy od 0 !!"<<endl;
              break;
             
            }
             
              if(x<tmp)
              {
               
               ik=isr-1;
              } 
            else
              {
                ip=isr+1;
               
              }
         
       
          }
          if(ip>ik)
         
          cout<<"Nie znaleziono elementu "<<x<<endl;     
          system("pause");
          getchar();
          delete a;
          return 0;
       
      }


    Przeszukiwanie binarne w Turbo Pascal i C++.Przeszukiwanie binarne w Turbo Pascal i C++. Przeszukiwanie binarne w Turbo Pascal i C++. Przeszukiwanie binarne w Turbo Pascal i C++.
    Tak działa program bez błędów w C++. Mógłby to kolega ocenić chyba dobrze ??
    A teraz jeszcze Turbo Pascal-koszmar cd...Kod podany w ty poście jest.Mógłby ktoś sprawdzić kto się zna ? :cry:
    Pozdrawiam :D

    Dodano po 35 [minuty]:

    Przeszukiwanie binarne w Turbo Pascal i C++.
    Code:

     #include <iostream>
     #include<cstdio>
     #include<conio.h>
     using namespace std;
     

    int main( )
    {
       
    int x,ip,ik,isr,k,m;
     
     cout<<"Podaj liczbe elementow tablicy: ";
     cin>>m;
     cin.ignore();
     
      int *a= new int[m];// Dynamiczna alokacja pamieci dla tablicy o m-elementach
      int tmp; //pomocnicza zmienna przechowujaca:  tmp = a[isr+1]; 
      cout<<"Wpisz wartosci tablicy (od najmniejszego): "<<endl;
      cout<<"****************************************"<<endl;
      for(int k=0;k<m;k++)
       {
        cout<< "a[ "<< k << "]= "<<endl; // dodałem koljność indeksu
        cin>>a[k+1];     
       }
          cout<<"Podaj element do wyszukania: ";
          cin>>x;
         
       
        ip=0;
        ik=m;

         while(ip<=ik)
        { 
          isr=(ip+ik)/2;
          tmp = a[isr+1];
       
         
           if(tmp==x)
            {
            cout<<"Odnaleziono element "<<x<<" pod indeksem "<<isr<<" Numerujemy od 0 !!"<<endl;
              break;
             
            }
             
              if(x<tmp)
              {
               
               ik=isr-1;
              } 
            else
              {
                ip=isr+1;
               
              }
         
       
          }
          if(ip>ik)
         
          cout<<"Nie znaleziono elementu "<<x<<endl;     
          system("pause");
          getchar();
          delete a;
          return 0;
       
      }


    Trochę go upiększyłem w przejrzysty.Wiadomo o co chodzi.

    0
  • #15 14 Mar 2010 16:19
    bomkallo
    Poziom 11  

    Code:

               int i;
       int *arr;
       int elems;
       int to_find;
       bool found = false;

       cout << "Podaj liczbe elementow: ";
       cin >> elems;

       arr = new int[elems];
       cout << "Wprowadz liczby (od najmniejszej)" << endl;

       for (i = 0; i < elems; i++)
          cin >> arr[i];

       cout << "Wprowadz liczbe do wyszukania: ";
       cin >> to_find;

       for (i = 0; i < elems; i++)
             if (arr[i] == to_find)
           {
               cout << "Element " << to_find << " znaleziony pod indexem " << i << endl;
                       found = true;
               break;
           }

       if (!found)
           cout << "Nie odnaleziono szukanego elementu." << endl;

       delete arr;
       return 0;


    nie prosciej?:P fakt, ze nie jest zabezpieczony, ale nie ma bajzlu :P

    0
  • #16 16 Mar 2010 13:20
    zbigniew 10123
    Poziom 12  

    Może i prościej ale zamyka okno konsoli. :cry:

    0
  • #17 16 Mar 2010 16:29
    FirstStep
    Poziom 12  

    @ bomkallo, ale to nie jest przeszukiwanie binarne ;] Jakby tablica miała 100000 elementów, a szukany byłby na 99999 miejscu?

    @zbigniew dodaj

    Code:
    system ("pause");

    0
  • #18 16 Mar 2010 23:18
    zbigniew 10123
    Poziom 12  

    Witam i powracam do tematu.Mam ten kod źle wylicza pozycjce szukanej liczby i nie wiem co jest.Zrobiłem go na pętli wg.schematu blokowego bez wskaźnika a tu zonk.W komentarz ująłem dlatego bo to mi nie działało lub brakuje czegoś.

    Code:
    #include <cstdlib>
    
    #include <iostream>
    #include<conio.h>

    using namespace std;

    int main( )
    {
         
       int n,x,praw,sr,lew,y,k,pom; 
       cout<<"Podaj ilosc elementow w tablicy: ";
       cin>>n;
       
     
       
        //int T[n];
        //cout<<"Wprowadz kolejno liczby rosnaco - pozycja indeksu >T["<<i<<"]= Podana liczba: "<<endl;
        // cin>>T[i];
           
           
            int tab[n] ;
            for(int i=0;i<n;i++)
             {
            cout<<"Wprowadz liczby rosnaco ->tab["<<i<<"]=";
            cin>>tab[i];
             }
            getchar();   
           cout<<"Jaka liczbe szukasz ? ";
           cin>>x;
           {
             k=0;praw=n-1;pom=sr;
             while (lew<praw)
            {
                   
               //if ( x<=tab[(lew+praw)/2])
              //{
               
               /* sr=(lew+praw)/2;
                getchar();*/
                //return 0;
               
                //if(tab[sr]==x);
                           
               
                             
                   cout<<endl<<"Szukana liczba wystepuje na miejscu: "<<x<<endl;       
                         
                   //else
                    if (tab[sr]<x)
                              lew=sr+1;
                             
                        else
                             praw=sr-1;
               
                         }           
                   }
                     
                   if(k>=0)
                 
                     cout<<endl<<"Szukana liczba wystepuje na miejscu: "<<praw<<endl;
                 
                    else
                   
                     cout<<"Szukana liczba nie wystepuje w zbiorze. "<<endl;
                     getchar();
                     //return 0;
                      system("PAUSE");
                }             
             
                     
                                       

    :cry:

    0
  • #19 17 Mar 2010 07:10
    chudybyk
    Poziom 26  

    Nie obraź się. Ty w ogóle nie stosujesz tego co radzą Ci inni, a zwykle radzą dobrze.
    Znowu deklarujesz tablice o nieznanej długości - tab[n] i T[n]. Wielkość tablicy musi być znana w czasie KOMPILACJI programu, a nie po uruchomieniu i przypisaniu zmiennej. Użyj operatora new lub wielkiej tablicy i stałej wielkości
    Znowu też wstawiasz komendy return 0 - mimo, że masz po nich jakiś kod, który oczywiście nie ma szans się wykonać.
    Przede wszystkim jednak spróbuj analizować, to co piszesz i to co przepisujesz od innych. Każde słowo w programie ma jakiś znaczenie i należy wiedzieć jakie jest jego znaczenie lub działanie.
    Do analizy bardzo się przydaje uruchamianie programów w trybie krokowym - często pozwala usunąć proste błędy i obrazowo się przekonać o faktycznym przebiegu programu.
    Powodzenia!

    0
  • #20 17 Mar 2010 11:13
    zbigniew 10123
    Poziom 12  

    Jak uruchomić program w trybie krokowym do sprawdzenia w Dev C++ ? :cry:

    Dodano po 10 [minuty]:

    Przyznam się że już się w tym pogubiłem a za prawdę się nie gniewam tylko jak mam to poprawić.Tworzyłem od algorytmu, problem w tym że kompilator nie zgłasza błędu i się uruchamia program i nie wiem gdzie poprrawić składnię.

    0
  • #21 17 Mar 2010 14:56
    chudybyk
    Poziom 26  

    Środowisko Dev C++ jest trochę ubogie, ale da się coś zrobić. Użyj czegoś co się nazywa Odpluskwiacz. Praca krokowa jest możliwa w tym trybie za pomocą przycisku "Przeskocz". Pamiętaj, że trzeba zaznaczyć opcje kompilatora żeby generował informacje dla odpluskwiacza.
    Tu masz coś konkretnego do analizy. Nie testowałem tego zbytnio, więc możesz poćwiczyć. Chyba działa, ale głowy nie dam.

    Code:

    #include <cstdlib>
    #include <iostream>

    using namespace std;

    int main(int argc, char *argv[])
    {
       int n,x,praw,sr,lew,y,k,pom;
       int tab[1000];
       cout<<"Podaj ilosc elementow w tablicy: ";
       cin>>n;

       for(int i=0;i<n;i++)
       {
          cout<<"Wprowadz liczby rosnaco ->tab["<<i<<"]=";
          cin>>tab[i];
       }

       cout<<"Jaka liczbe szukasz ? ";
       cin>>x;

        praw=n-1;
        lew =0;
         
        while (lew < praw)
        {
            sr = (lew+praw)/2;
            if (tab[sr] < x) lew=sr+1;
            else praw=sr;
        }     
       
        if (tab[sr] == x)
             cout<<endl<<"Szukana liczba wystepuje pod indeksem: "<< sr <<endl;       
        else
             cout<<"Szukana liczba nie wystepuje w zbiorze. "<<endl;

        cin>>x;             // żeby zobaczyć wyniki
        return 0;
    }

    0
  • #22 17 Mar 2010 23:21
    zbigniew 10123
    Poziom 12  

    Działa trochę mi oszukuje pozamieniałem

    Code:
    praw=n;lew =1;
    i
    Code:
    if (tab[sr] < x) lew=sr+1; else praw=sr-1;
    a on z 5 elementowej tablicy nie odnajduje 4.Przeszukiwanie binarne w Turbo Pascal i C++..


    Również sprawdzałem na 10-cio elementowej od 1 do 10 i nie znalazł 1,2,5,6,8,9 resztę 3,4,7 i 10 odnalazł.Przeszukiwanie binarne w Turbo Pascal i C++.

    Dodano po 14 [minuty]:

    Zamieniałem w różny sposób ale nigdy nie odnajdywał wszystkich liczb.
    Ktore są to opcje kompilatora do odpluskiwacza w tryb krokowy bo nie wiem gdzie jest "Przeskocz". Podaję zrzut:Przeszukiwanie binarne w Turbo Pascal i C++. to w Dev C++.


    Przycisk odnalazłem i o co tutaj chodzi jak program się kompiluje i uruchamia tylko żle liczy.:cry:

    0
  • #23 18 Mar 2010 03:59
    Akane
    Poziom 27  

    Zbyszku, bezmyślne pisanie programu rodzi tylko problemy. Po co tu debugować? Nie działa? A może nie rozumiesz jak działa algorytm szukania? Raczej nie rozumiesz, nawet utrudniasz sobie kod - niewłaściwe nazwy zmiennych!

    Jak się szuka? Mamy przykładowo 32 liczby, od zera do 31
    1.
    zakresDolny = 0
    zakresGorny = 31

    2.
    pozycja = w połowie = (zakresDolny+zakresGorny)/2

    3.
    Jeżeli tablica[pozycja] == szukana to znaleziono, exit.

    Jeżeli liczba w tablicy na pozycji `pozycja` jest mniejsza od szukanej, to przesuwamy dolny zakres nad aktualną pozycję, bo szukanej liczby na pewno nie będzie niżej (zakresDolny=pozycja+1).

    Jeżeli liczba w tablicy na pozycji `pozycja` jest większa od szukanej, to znaczy że jesteśmy za wysoko, więc górna granica spada poniżej aktualnej pozycji: zakresGorny=pozycja-1.

    Jeżeli górny zakres nie jest większy od dolnego, powtórz od kroku 2.


    Jeżeli nie znaleziono liczby, to automatycznie mamy pozycję na którą można wstawić nową liczbę (przesuwając wszystkie elementy po `prawej` w `prawo` o jedną pozycję). Jest nią pozycja+x, gdzie x jest jedynką tylko wtedy, gdy ostatnie porównanie podniosło dolną granicę.

    Teraz, gdy rozumiesz jak to działa, napisz kod od nowa, nie kopiując ani jednej linijki, ani znaku z poprzednich programów.

    Code:
    On: Pomyślałem sobie liczbą od zera do 31, zgadnij jaką? (pomyślał sobie 9)
    
    Ja: (liczę...)
    zakresDolny = 0
    zakresGorny = 31
    połowa = (zakresDolny+zakresGorny)/2 = 15

    Ja: pytam czy to 15
    On: mniej

    Ja: (liczę... zostały liczby 0-14)
    zakresDolny = 0
    zakresGorny = 15-1 = 14
    połowa = (0+14)/2 = 7

    Ja: pytam czy to 7
    On: więcej

    Ja: (liczę... zostały liczby 8-14)
    zakresDolny = 7+1 = 8
    zakresGorny = 14
    połowa = (8+14)/2 = 11

    Ja: pytam czy to 11
    On: mniej

    Ja: (liczę... zostały liczby 8,9,10)
    zakresDolny = 8
    zakresGorny = 11-1 = 10
    połowa = (8+10)/2 = 9

    Ja: pytam czy to 9
    On: Tak

    0
  • #24 18 Mar 2010 08:22
    zbigniew 10123
    Poziom 12  

    Prawda jest taka że nie mogę tego zrozumieć.Kopiowałem trochę ze starego kodu ,który kiedyś napisałem. Będę próbował :cry:

    0
TME logo Szukaj w ofercie
Zamknij 
Wyszukaj w ofercie 200 tys. produktów TME
TME Logo