Przeszukiwanie binarne w Turbo Pascal i C++.

Main Page -> Forum Index -> Programming Generally -> Beginners Programming -> Przeszukiwanie binarne w Turbo Pascal i C++.

Author

Message

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

07 Mar 2010 22:22

Przeszukiwanie binarne w Turbo Pascal i C++.

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

Quote:

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

chudybyk
Poziom 18

Joined: 11 Jan 2007
Posts: 459
Location: Mikołów

#2 08 Mar 2010 07:52

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

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!

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

08 Mar 2010 15:51

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

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.

chudybyk
Poziom 18

Joined: 11 Jan 2007
Posts: 459
Location: Mikołów

#4 09 Mar 2010 07:43

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

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.

FirstStep
Poziom 10

Joined: 31 Oct 2007
Posts: 48

#5 09 Mar 2010 13:44

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

http://www.if.uz.zgora.pl/~adam/materialy/algorytmy/alg_10/zajecia10.pdf

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

09 Mar 2010 21:43

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

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]:

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.

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

Google

Google Adsense

09 Mar 2010 21:43

bomkallo
Poziom 5

Joined: 13 Apr 2006
Posts: 14
Location: wroclaw

#7 10 Mar 2010 01:52

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

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...

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

10 Mar 2010 19:16

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

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;
}

Program nie przechodzi dalej ,po naciśnięciu ' ENTER ' zamyka okno.

FirstStep
Poziom 10

Joined: 31 Oct 2007
Posts: 48

#9 10 Mar 2010 20:00

Re: 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[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.

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#10

10 Mar 2010 21:06

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

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.

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:

FirstStep
Poziom 10

Joined: 31 Oct 2007
Posts: 48

#11 10 Mar 2010 21:57

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

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;
}

Quote:

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

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#12

10 Mar 2010 23:41

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

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.

FirstStep
Poziom 10

Joined: 31 Oct 2007
Posts: 48

#13 11 Mar 2010 12:51

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

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

Google

Google Adsense

# 11 Mar 2010 12:51

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#14

11 Mar 2010 23:25

Re: 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;

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:

do '5' elementów tablicy naciśnięciu ENTER zamyka okno.Gdy wpiszę '10 ' elementową tablicę wyświetla z błędem.

Dodano po 18 [minuty]:

Zacząłem szukać innego rozwiązania i to są działania programu przez "Debug" w Dev-C++

Nie chcę się zamknąć po naciśnięciu ENTER.

Dodano po 18 [minuty]:

Code:

cout<<"Nie znaleziono elementu "<<x<<endl;

Musi być jeśli brak liczby

Code:

//getchar();
//delete a;

nie działa próbowałem

>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;

}

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]:

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.

bomkallo
Poziom 5

Joined: 13 Apr 2006
Posts: 14
Location: wroclaw

#15 14 Mar 2010 16:19

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

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

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#16

16 Mar 2010 13:20

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

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

FirstStep
Poziom 10

Joined: 31 Oct 2007
Posts: 48

#17 16 Mar 2010 16:29

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

@ 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");

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#18

16 Mar 2010 23:18

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

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:

chudybyk
Poziom 18

Joined: 11 Jan 2007
Posts: 459
Location: Mikołów

#19 17 Mar 2010 07:10

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

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!

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#20

17 Mar 2010 11:13

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

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ę.

Google

Google Adsense

17 Mar 2010 11:13

chudybyk
Poziom 18

Joined: 11 Jan 2007
Posts: 459
Location: Mikołów

#21 17 Mar 2010 14:56

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

Ś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;
}

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#22

17 Mar 2010 23:21

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

Działa trochę mi oszukuje pozamieniałem

Code:

praw=n;lew =1;

Code:

if (tab[sr] < x) lew=sr+1; else praw=sr-1;

a on z 5 elementowej tablicy nie odnajduje 4.

.

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ł.

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:

to w Dev C++.

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

Akane
Poziom 18

Joined: 02 Jun 2003
Posts: 544
Location: JO90, JN49

#23 18 Mar 2010 03:59

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

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

zbigniew 10123
Poziom 12

Joined: 25 Jun 2008
Posts: 87

#24

18 Mar 2010 08:22

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

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

Main Page -> Forum Index -> Programming Generally -> Beginners Programming -> Przeszukiwanie binarne w Turbo Pascal i C++.

Page 1 of 1

Page generation time: 0.127 seconds

FAQ || Administrator || Moderators || Widgets and banners || Contact