ΑΛΓΟΡΙΘΜΟΙ ΣΕ C - ΜΑΘΗΜΑ 2 - ΑΝΑΖΗΤΗΣΗ ΣΤΟΙΧΕΙΟΥ ΣΕ ΠΙΝΑΚΑ (ΕΚΤΥΠΩΣΗ)
0 likes2,189 views
1) Αναζήτηση Στοιχείου σε Πίνακα 1.1) Ορισμός του Προβλήματος 2) Σειριακή Αναζήτηση 3) Δυαδική Αναζήτηση 3.1) Με Επανάληψη 3.2) Με Αναδρομή
![C
2:
.
1.
1.
2.
3.
1. !
2.
".
! "
: 1..10
! C.
A. " #
1.
1. $ %
#! "
& « » % :
• : ' # PIN x
• #$ : ( )/*+) x
, :
, -
), : - , -
, , , -
), : . .
/ , % .
/ , % , - .
A. " #
2.
! "
$
$ !, ,
. 01 % ! % .
found=0;
for (i=0; i<N; i++)
{
if (x==PIN[i])
{
found=1;
break;
}
}
% 1: « - » , ,
PIN=[6,4,2,7,3] , x=7.
% 2: 1 linear_search.c
# # x 1 0/1
.](https://image.slidesharecdn.com/algorithmsinclesson24sl-160213001812/85/C-2-1-320.jpg)
![. " #
3. ,
1. 0 /
%! "
& (Binary Search)
1 .
' 2 : * , - !
, x - -
:
x, % !
x /
x /
! 1 !, (o , # # int
pinakas[N] % start,finish, middle % ):
. " #
3. ,
1. 0 /
&! "
start=0;
finish=N-1;
found=FALSE;
while(start<=finish)
{
middle=(start+finish)/2;
if (x==pinakas[middle])
{
found=TRUE;
break;
}
else if (x<pinakas[middle])
finish=middle-1;
else // x>pinakas[middle]
start=middle+1;
}
. " #
3. ,
1. 0 /
'! "
0 / 11 :
1 / : start=0,finish=14: middle=(0+14) div 2=7. x<A[middle]
2 / : start=0,finish=6: middle=(0+6) div 2=3. x>A[middle]
3 / : start=4,finish=6: middle=(4+6) div 2=5. x<A[middle]
4 / : start=4,finish=4: middle=(4+6) div 2=5. x==A[middle]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 5 7 11 13 17 21 23 27 31 33 37 41 43
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 5 7 11 13 17 21 23 27 31 33 37 41 43
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 5 7 11 13 17 21 23 27 31 33 37 41 43
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 5 7 11 13 17 21 23 27 31 33 37 41 43
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 3 5 7 11 13 17 21 23 27 31 33 37 41 43
start
start
start
start=finish
finish
finish
finish
. " #
3. ,
1. 0 /
(! "
% : 1 binary_search.c
# # x 1 0/1
.](https://image.slidesharecdn.com/algorithmsinclesson24sl-160213001812/85/C-2-2-320.jpg)
![& ( , , , ) ,
,
" , ,! , , .
, , / , .
. " #
3. ,
2. ,
)! "
:
• . , / .
/ , .
• 3 , , ! # ,
# # .
• % ( )
, # #
! 1 !, (o , # # int
pinakas[N] % start,finish, middle % ):
. " #
3. ,
2. ,
*+! "
int binary_search_rec(int *pinakas, int start, int finish, int x)
{
int middle;
if (start>finish)
return FALSE;
else
{
middle=(start+finish)/2;
if (x==pinakas[middle])
return TRUE;
else if (x<pinakas[middle])
return binary_search_rec(pinakas,start,middle-1,x);
else
return binary_search_rec(pinakas,middle+1,finish,x);
}
}
4.
01 1: 0 1 LinearSearch
! "
**
5 / ! C # - :
1 0/1 , 1
-1 ,
,
5 / main , ( !
)
4.
01 2: 0 1 BinarySearch
! "
*
5 / ! C , , # - :
0 1 0/1
# 1 % 1 :
-1 ,
,
5 / main , ( !
% )](https://image.slidesharecdn.com/algorithmsinclesson24sl-160213001812/85/C-2-3-320.jpg)
More Related Content
What's hot (20)
Viewers also liked (6)
More from Dimitris Psounis (20)
Recently uploaded (19)
ΑΛΓΟΡΙΘΜΟΙ ΣΕ C - ΜΑΘΗΜΑ 2 - ΑΝΑΖΗΤΗΣΗ ΣΤΟΙΧΕΙΟΥ ΣΕ ΠΙΝΑΚΑ (ΕΚΤΥΠΩΣΗ)
- 1. C 2: . 1. 1. 2. 3. 1. ! 2. ". ! " : 1..10 ! C. A. " # 1. 1. $ % #! " & « » % : • : ' # PIN x • #$ : ( )/*+) x , : , - ), : - , - , , , - ), : . . / , % . / , % , - . A. " # 2. ! " $ $ !, , . 01 % ! % . found=0; for (i=0; i<N; i++) { if (x==PIN[i]) { found=1; break; } } % 1: « - » , , PIN=[6,4,2,7,3] , x=7. % 2: 1 linear_search.c # # x 1 0/1 .
- 2. . " # 3. , 1. 0 / %! " & (Binary Search) 1 . ' 2 : * , - ! , x - - : x, % ! x / x / ! 1 !, (o , # # int pinakas[N] % start,finish, middle % ): . " # 3. , 1. 0 / &! " start=0; finish=N-1; found=FALSE; while(start<=finish) { middle=(start+finish)/2; if (x==pinakas[middle]) { found=TRUE; break; } else if (x<pinakas[middle]) finish=middle-1; else // x>pinakas[middle] start=middle+1; } . " # 3. , 1. 0 / '! " 0 / 11 : 1 / : start=0,finish=14: middle=(0+14) div 2=7. x<A[middle] 2 / : start=0,finish=6: middle=(0+6) div 2=3. x>A[middle] 3 / : start=4,finish=6: middle=(4+6) div 2=5. x<A[middle] 4 / : start=4,finish=4: middle=(4+6) div 2=5. x==A[middle] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 5 7 11 13 17 21 23 27 31 33 37 41 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 5 7 11 13 17 21 23 27 31 33 37 41 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 5 7 11 13 17 21 23 27 31 33 37 41 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 5 7 11 13 17 21 23 27 31 33 37 41 43 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 3 5 7 11 13 17 21 23 27 31 33 37 41 43 start start start start=finish finish finish finish . " # 3. , 1. 0 / (! " % : 1 binary_search.c # # x 1 0/1 .
- 3. & ( , , , ) , , " , ,! , , . , , / , . . " # 3. , 2. , )! " : • . , / . / , . • 3 , , ! # , # # . • % ( ) , # # ! 1 !, (o , # # int pinakas[N] % start,finish, middle % ): . " # 3. , 2. , *+! " int binary_search_rec(int *pinakas, int start, int finish, int x) { int middle; if (start>finish) return FALSE; else { middle=(start+finish)/2; if (x==pinakas[middle]) return TRUE; else if (x<pinakas[middle]) return binary_search_rec(pinakas,start,middle-1,x); else return binary_search_rec(pinakas,middle+1,finish,x); } } 4. 01 1: 0 1 LinearSearch ! " ** 5 / ! C # - : 1 0/1 , 1 -1 , , 5 / main , ( ! ) 4. 01 2: 0 1 BinarySearch ! " * 5 / ! C , , # - : 0 1 0/1 # 1 % 1 : -1 , , 5 / main , ( ! % )
- 4. 4. 01 3: , 6 ! " *# 5 / - , , ( , ) , - 1 4. 01 4: 0 / # # # ! " *$ 5 - ! . # ( . .) # , # # - : . # / # ( 1 for). . , , # / # ( 1 while). # / # , - ( / )