41. Деректердің динамикалық құрылымы. Графтар
жүктеу/скачать 18,9 Kb.
|
40-41 сұрақ 22-есеп
- Бұл бет үшін навигация:
- Графтар теориясы
- Граф теориясы
- 42. Итеративті және рекурсивті алгоритмдер
|
41.Деректердің динамикалық құрылымы. Графтар. Деректердің динамикалық структурасы өлшемі айнымалы, жадыдан алдын ала орын босатылмайтын, программаны орындаған сайын мәндері, мәндерінің саны өзгеріп отыратын деректер. Динамикалық деректердің элементтерінің арасында байланыс орнату үшін көрсеткіштер қолданылады. Олар әр динамикалық элементтің жадыдағы адресін көрсетіп тұрады. Динамикалық деректер структурасының элементтері екі өрістен тұрады: 1. деректер өрісі – ақпараттық өріс, ол массив, жазу, вектор т.б. бола алады. 2. байланыс өрісі - белгілі бір элементті басқа структураның элементімен байланыстыратын бір немесе бірнеше көрсеткіштер бола алады. Деректердің байланыстырылып көрінуінің жетістігі – структураларды барынша өзгерту мүмкіндігінде: структуралардың мөлшері машиналық жадының қолдануға болатын көлемімен шектеледі; структура элементтері логикалық тізбегін өзгерткенде жадыдағы деректерді ауыстырудың қажеті жоқ, оның орнына көрсеткіштер жылжиды, түзетіледі. Деректердің байланыстырылып көрінуінің кемшілігі: 3. көрсеткіштермен жұмыс жасау үшін программисттің квалификациясы жоғары болуы керек; 4. байланыс қрістеріне қосымша жады бөлінеді; 5. уақытты үнемдемейді. Ең қысқа жолды табудың алгоритмін графтар көмегімен тиімді жүзеге асыру Графтар теориясы (ағылш. graphtheory) — түйіндері нүктелер жиыны. Графтар информатикада кеңінен қолданылады, айталық, алгоритмдер схемасы немесе программалар бағытталған графтарға жатады. Қазіргі уақытта басты назар графтарды талдаудың компьютерлік алгоритмдерін жасауға жəне сипаттауға аударылып отыр. Мысалы, кез келген ғаламтор ресурсының құрылымын бағытталған граф көмегімен моделдеуге болады. Ең қысқа жолды табу бүгінгі таңда өмірлік маңызды міндет болып табылады және жердегі екі нысан арасындағы оңтайлы жолды табудан бастап (мысалы, үйден мектепке дейінгі ең қысқа жол), автопилот жүйелерінде, тасымалдау кезінде оңтайлы бағытты табуға дейін дерлік барлық жерде қолданылады, желілердегі ақпарат пакетін ауыстыру және т.б. Граф теориясы Ең қысқа жолды табудың ең тиімді үш алгоритмін қарастырамыз: Дейкстра алгоритмі; Флойд алгоритмі; Санау алгоритмдері. 42. Итеративті және рекурсивті алгоритмдер Рекурсия - бұл бағдарлама (немесе функция) өзін тікелей немесе басқа бағдарламалардан (функциялардан) шақыратын деректерді өңдеуді ұйымдастыру әдісі. Функция рекурсивті деп аталады, егер оны өңдеу кезінде басқа функциялардың қоңырау тізбегі арқылы тікелей немесе жанама түрде қайта шақыру пайда болса. Итерация - бұл кейбір әрекеттер бағдарламаларға (функцияларға) рекурсивті шақыруларға әкелмей бірнеше рет қайталанатын мәліметтерді өңдеуді ұйымдастыру әдісі. Теорема. Рекурсивті түрде жүзеге асырылған ерікті алгоритм итеративті түрде және керісінше қайта жазылуы мүмкін. Әрі қарай цикл операторларының көмегімен де, рекурсивті тәсілдің көмегімен де жүзеге асырылатын элементарлық функциялар жиынтығын қарастырайық. Кез келген бағдарламалау тілінде рекурсивті функцияларды жазбас бұрын, әдетте функциялардың қалай бағаланатынын анықтайтын рекурсивті қатынасты жазу қажет. Қайталану қатынасы кем дегенде екі шартты қамтуы керек: I) рекурсияны жалғастыру шарты (рекурсиялық қадам); II) рекурсияны тоқтату шарты. Функцияның өзін шақыру арқылы рекурсияны жүзеге асырамыз. Бұл жағдайда функцияның денесінде алдымен рекурсияны жалғастыру шартын тексеру керек. Егер бұл шын болса, функциядан шығыңыз. Әйтпесе, біз рекурсивті қадам жасаймыз. Функциялардың қайталанатын нұсқасын for циклінің операторы арқылы жүзеге асырамыз. 1. Санның факториалы. Теріс емес бүтін n санының факториалы 1-ден n-ге дейінгі барлық натурал сандардың көбейтіндісі болып табылады және n! арқылы белгіленеді. Егер f(n) = n! болса, онда қайталану қатынасы орындалады: Бірінші теңдік рекурсиялық қадамды – f(n) арқылы f(n – 1) есептеу әдісін сипаттайды. Екінші теңдік функцияны бағалау кезінде қашан тоқтату керектігін көрсетеді. Егер ол орнатылмаса, функция шексіз жұмыс істейді. Мысалы, f(3) мәнін келесідей есептеуге болады: f(3) = 3 f(2) = 3 2 f(1) = 3 2 1 f(0) = 3 2 1 1 = 6 Әлбетте, f(n) есептеу кезінде n рекурсивті шақырулар жасалуы керек. Циклдік іске асыру идеясы цикл операторының көмегімен санның факториалын тікелей есептеу болып табылады: f(n) = 1 2 3 … n 2. Сызықтық уақыттағы санның дәрежесі. Сызықтық (O(n)) уақыт бағасымен санының дәрежесін есептеуді келесі қайталанатын қатынас арқылы анықтауға болады: Итеративті нұсқада a · a · … · a (a-ның n факторы) көбейтіндісін есептеу жеткілікті. 3. Санның логарифмдік уақыттағы дәрежесі. санының дәрежесін O(log2n) уақыттық бағалаумен есептеу келесідей анықталады: Мысалы, оныншы дәрежеге дейін көтеру келесідей жүзеге асырылуы мүмкін: Квадрат бір көбейтуге эквивалент болғандықтан, a10 есептеу үшін 4 көбейту жеткілікті. 22-есеп Жол берілген. Осы жолда нүкте таңбасын (.) жойыңыз және жойылған таңбалардың санын есептеңіз. s = input('zholdy zhaz: ') count = s.count('.') s = s.replace('.', ' ') print(s) print('zhoiylgan tanbalar sany: ', count) жүктеу/скачать 18,9 Kb. Достарыңызбен бөлісу:
|