Paweł Kierski <n...@p...net> napisał(a):

> Czy prawda? Weź kartkę i spróbuj napisać wyszukiwanie binarne. Sprawdź
> poprawność.
>
> Serio - zdarzało mi się dawać tego typu zadania kandydatom. Dla mnie
> celem nie było zobaczenie poprawnego rozwiązania, ale sposobu pisania
> i tego, czy kandydat ma świadomość, że w 15 minut będzie prawie
> niemożliwe jest rozwiązanie bez błędów, uwzględniające wszystkie
> szczególne przypadki.

Trzy wersje procedury. Po 7 minutach miałem jakieś badziewie. Po 13 minutach
wersję z błędem. Po 20 minutach miałem napisany prosty test i wersję
z poprawionym błędem. Podczas pisania nie patrzyłem na żaden
metakod ani schemat blokowy. Ostatnio ten algorytm musiałem napisać...
dawno temu, więc z pamięci też go nie pisałem. Jakbym miał jeszcze z 10
minut to bym rozwinął rekurencje ogonową. Faktyczne w 15 minut nie
zdążyłem, ale zdaniem autora 9 zawodowych programistów na 10 nie
zdążyła w kilka godzin - wydaje się dziwne. Ale może został w moim
kodzie jakiś błąd?


#include <cstdlib>
#include <cstdio>

// 7 minut
int binary_search( const int vector[] , const int start , const int end ,
const int wanted ) {
const int size = end - start;
if( size <= 0 ) return -1;
if( size == 1 ) return vector[start] == wanted ? start : -1;
const int divided = start + ( end - start ) / 2;
const int new_start = vector[divided] <= wanted ? start : divided + 1;
const int new_end = vector[divided] <= wanted ? divided : end;
return binary_search( vector , new_start , new_end , wanted );
}

// 13 minut
int binary_search( const int vector[] , const int start , const int end ,
const int wanted ) {
const int size = end - start;
if( size < 0 ) abort();
if( size == 0 ) return vector[start] == wanted ? start : -1;

const int divided = start + ( end - start ) / 2;
if( vector[divided] <= wanted )
return binary_search( vector , start , divided , wanted );
return binary_search( vector , divided+1 , end , wanted );
}

// 20 minut
int binary_search( const int vector[] , const int start , const int end ,
const int wanted ) {
const int size = end - start;
if( size < 0 ) abort();
if( size == 0 ) return vector[start] == wanted ? start : -1;
const int divided = start + size / 2;
if( wanted <= vector[divided] )
return binary_search( vector , start , divided , wanted );
return binary_search( vector , divided+1 , end , wanted );
}


int main(int argc, char *argv[]) {
const int test1[22] = { 0 , 1 , 5 , 8 , 10 , 11 , 100 , 101 , 111 , 230 ,
1111 , 2222 , 3333 , 4001 , 4002 , 4003 ,5000 , 5500 , 5555 , 6000 , 6001 ,
6002 };
int sum = 0;
for( int i=0 ; i<=6666 ; i++ ) {
sum += binary_search( test1 , 0 , 21 , i ) != -1;
}
printf("sum: %d\n" , sum );
return 0;
}






--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/