Алгоритмы и структуры данных осень 2013 лекция 1

  • Published on
    13-Jun-2015

  • View
    677

  • Download
    4

Embed Size (px)

Transcript

  • 1. 1. . . ..

2. 57 1998-2001, - 2006, .-. 2010, ABBYY 2006 .. : ABBYY Compreno ( , ), ABBYY FactExtractor ( ). 2009 .. (): (), (), Windows ( ). 2 3. 1. .2. . 1. 1. 2. 2. 3. 4 ( ). 3. 5. 4. 6. 7. 8 ( ).3. .4. -. . 5. 9. 6. 10. 11. 12 ( ). 7. 13. 8. 14. 15.. .3 4. 1 . . . . O-. n- . . ( log(n)). . . . . . . 4 5. , (input), , (output). output ( input ) { ; } () F : X Y. X , Y . 5 6. , / . : , , , .6 7. . () , . . , , , , , 7 8. 8 9. . . -, - , . B- 9 10. -. - . - - , - .10 11. . . . . . . . 11 12. --, - , , , . 12 13. 13 14. ., ., ., , . ., 2- , .: , 2005. ., C++, 1-4, , , , , .: , 2001. ., : , 2- ., . ., .: , 2004.14 15. , : , , . , .15 16. n. T(n). . M(n). . . . . - T k S n. T(n, k) n k. 16 17. ( ) , O . . g(n) (g(n)), O(g(n)) (g(n)) : = { : 1 , 2 0 , 0 1 2 0 }, = { : 0 , 0 0 }, = { : 0 , 0 0 }.. () (()) = ( ). 17 18. . = (). . . . = 2 . . . . = (log ). . = log . = . 18 19. . n- .F(0) = 1; F(1) = 1; F(n) = F(n 1) + F(n 2); 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . 19 20. // . int Fibonacci1( int n ) { if( n == 0 || n == 1 ) { return 1; } return Fibonacci1( n 1 ) + Fibonacci1( n 2 ); }20 21. // . int Fibonacci2( int n ) { if( n == 0 ) { return 1; } int prev = 1; // F(0). int current = 1; // F(1). for( int i = 2; i > 1. } return result; } 27 28. = , n, .. log(). () = (log ), () = (1).28 29. 1. (), , (). 0. 2. , . : 20341156323-120-3370123456789 29 30. . void Function1( int* arr, int count ); void Function2( const int* arr, int count );30 31. . 1. , .. , , . = , n .31 32. . 0. . (char) (wchar_t).void void void voidFunction1( Function2( Function3( Function4(char* str ); const char* str ); wchar_t* str ); const wchar_t* str );00123456789 32 33. . . // . bool HasElement( const double* arr, int count, double element ) { for( int i = 0; i < count; i++ ) { if( arr[i] == element ) { // . return true; } } return false; }33 34. . 2. , . , . , -1. . , . , . , -1. = , n .34 35. . . // , // . -1, . int FindElement( const double* arr, int count, double element ) { for( int i = 0; i < count; i++ ) { if( arr[i] == element ) { // . return i; } } return -1; } 35 36. . 3. . .. , . = , n .36 37. . . // . int MaxElement( const double* arr, int count ) { // 0. assert( count > 0 ); double currentMax = arr[0]; for( int i = 1; i < count; i++ ) { if( arr[i] > currentMax ) { // . currentMax = arr[i]; } } return currentMax; } 37 38. . . . A, , k l, < : . . -40-1201262254343711012345678938 39. . ( = ). , . , . , -1. . . () . . , 1.39 40. . . // [first, last]. int FindInsertionPoint( const double* arr, int first, int last, double element ) { if( last first == 1 ) return element

Recommended

View more >