Алгоритмдерді талдау
Тиімді, жылдам жұмыс істейтін алгоритмдер құрудың практикалық есептер шығаруда бірінші дәрежелі болмаса да, үлкен мәні бар. Бірнеше алгоритмдердің ішінен жылдам жұмыс істейтін алгоритмді таңдау үшін олардың жұмыс уақытын салыстырып үйрену қажет. Дегенмен, жұмыс уақытын дәл есептеу мүмкін емес. Бұл уақыт алдымен программа орындалатын компьютердің шынайы сипаттамасына тәуелді болуы мүмкін. Әдетте алгоритмнің орындалуы уақыты тек жуықтап қана есептеледі. Сонымен бірге жұмыс уақытына арналған формула мәндері тек тәжірибелік жолмен анықталатын қандай да бір сандық тұрақтылардан тұрады. Мұндай бағалаудың өзі көбінесе ең тиімді бір алгоритмді ғана таңдауға мүмкіндік береді. Басқа жағдайларда жұмыс уақытын бағалаудың көмегімен баяу жұмыс істейтін алгоритмдерді шығарып тастауға болады, ал қалғандарынан программаның шынайы жұмыс уақытын өлшеудің көмегімен таңдауға болады.
Енді жоғарыда айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да бір n саннан құрылған тізбекті өңдеу қажет болсын. Мұндағы n өзгеріп отыратын болсын. Осы есепті шығаруға екі программа берілсін, олардың жұмыс уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- тұрақтылар, олар n-ге тәуелсіз. N үлкен болған жағдайда бірінші программа жылдам жұмыс істейді, ал n аз шама болғанда программа баяу жұмыс істейді. Бұл С1 > С2 екенін көрсетеді. С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n мен C2n2-ты салыстыра отырып, n>5 болғандағы программаның жұмыс уақытының баяу, ал n<5 болғанда екінші программаның жылдам жұмыс істейтінін байқауға болады. Мұндағы n =5 бағалау уақытының шектік мәні де жуықтап тағайындалады.
Бұдан екі тұжырым жасауға болады. Біріншіден, «тұрақтыға дейінгі дәлдікпен» жуықтап бағалаудың өзі алгоритмдерді салыстыруда пайдалы болып табылады. Екініден, есеп шығарудың бір алгоритмі өте жылдам деп айтуға болмайды. Қандай да бір алғашқы мәліметтер жиынтығы үшін кейбір алгоритм екіншісінен тиімді болуы мүмкін.
Енді программаның жұмыс уақытын анықтайтын алғашқы мәліметтердің мұндай сипаттамасын таңдау мәселесіне тоқталайық. Мұндай сипаттама есептің өлшемі деп аталады. Әртүрлі есептерді шығару уақытына алғашқы мәліметтердің әртүрлі қасиеті әсер етеді. Мысалы, минимумды іздеу немесе әрбір сан бір бүтін сан ретінде қарастырылатын берілген сандарды іріктеу типті есептер үшін алғашқы сандар мөлшері есептер мөлшері болып табылады. Қарапайым көбейткіштерге жіктеу есебі үшін санның шамасы мөлшері болып есептеледі. Есеептің мөлшерін таңдау қандай да бір шығару алгоритмі туралы жалпы ұғымға негізделеді. 2n дәрежесін есептеу алгоритмін қарастырайық. Дәрежелеудің санның бірінен соң бірі көбейтілетінін ескере отырып, өлшем ретінде n дәреже көрсеткішті аламыз. Өлшемді сипаттаудың тағы бір тәсілі нәтижедегі цифр сан ыболып табылады. 2n дәрежесіндегі цифр саны n-ге пропорционал, сондықтан екі өлшем де эквивалентті.
Енді жоғарыда айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да бір n саннан құрылған тізбекті өңдеу қажет болсын. Мұндағы n өзгеріп отыратын болсын. Осы есепті шығаруға екі программа берілсін, олардың жұмыс уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- тұрақтылар, олар n-ге тәуелсіз. N үлкен болған жағдайда бірінші программа жылдам жұмыс істейді, ал n аз шама болғанда программа баяу жұмыс істейді. Бұл С1 > С2 екенін көрсетеді. С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n мен C2n2-ты салыстыра отырып, n>5 болғандағы программаның жұмыс уақытының баяу, ал n<5 болғанда екінші программаның жылдам жұмыс істейтінін байқауға болады. Мұндағы n =5 бағалау уақытының шектік мәні де жуықтап тағайындалады.
Бұдан екі тұжырым жасауға болады. Біріншіден, «тұрақтыға дейінгі дәлдікпен» жуықтап бағалаудың өзі алгоритмдерді салыстыруда пайдалы болып табылады. Екініден, есеп шығарудың бір алгоритмі өте жылдам деп айтуға болмайды. Қандай да бір алғашқы мәліметтер жиынтығы үшін кейбір алгоритм екіншісінен тиімді болуы мүмкін.
Енді программаның жұмыс уақытын анықтайтын алғашқы мәліметтердің мұндай сипаттамасын таңдау мәселесіне тоқталайық. Мұндай сипаттама есептің өлшемі деп аталады. Әртүрлі есептерді шығару уақытына алғашқы мәліметтердің әртүрлі қасиеті әсер етеді. Мысалы, минимумды іздеу немесе әрбір сан бір бүтін сан ретінде қарастырылатын берілген сандарды іріктеу типті есептер үшін алғашқы сандар мөлшері есептер мөлшері болып табылады. Қарапайым көбейткіштерге жіктеу есебі үшін санның шамасы мөлшері болып есептеледі. Есеептің мөлшерін таңдау қандай да бір шығару алгоритмі туралы жалпы ұғымға негізделеді. 2n дәрежесін есептеу алгоритмін қарастырайық. Дәрежелеудің санның бірінен соң бірі көбейтілетінін ескере отырып, өлшем ретінде n дәреже көрсеткішті аламыз. Өлшемді сипаттаудың тағы бір тәсілі нәтижедегі цифр сан ыболып табылады. 2n дәрежесіндегі цифр саны n-ге пропорционал, сондықтан екі өлшем де эквивалентті.
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 44 бет
Таңдаулыға:
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 44 бет
Таңдаулыға:
Лекция № Алгоритмдерді талдау .
Тиімді, жылдам жұмыс істейтін алгоритмдер құрудың практикалық есептер
шығаруда бірінші дәрежелі болмаса да, үлкен мәні бар. Бірнеше
алгоритмдердің ішінен жылдам жұмыс істейтін алгоритмді таңдау үшін олардың
жұмыс уақытын салыстырып үйрену қажет. Дегенмен, жұмыс уақытын дәл есептеу
мүмкін емес. Бұл уақыт алдымен программа орындалатын компьютердің шынайы
сипаттамасына тәуелді болуы мүмкін. Әдетте алгоритмнің орындалуы уақыты тек
жуықтап қана есептеледі. Сонымен бірге жұмыс уақытына арналған формула
мәндері тек тәжірибелік жолмен анықталатын қандай да бір сандық
тұрақтылардан тұрады. Мұндай бағалаудың өзі көбінесе ең тиімді бір
алгоритмді ғана таңдауға мүмкіндік береді. Басқа жағдайларда жұмыс уақытын
бағалаудың көмегімен баяу жұмыс істейтін алгоритмдерді шығарып тастауға
болады, ал қалғандарынан программаның шынайы жұмыс уақытын өлшеудің
көмегімен таңдауға болады.
Енді жоғарыда айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да
бір n саннан құрылған тізбекті өңдеу қажет болсын. Мұндағы n өзгеріп
отыратын болсын. Осы есепті шығаруға екі программа берілсін, олардың жұмыс
уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- тұрақтылар, олар n-ге
тәуелсіз. N үлкен болған жағдайда бірінші программа жылдам жұмыс істейді,
ал n аз шама болғанда программа баяу жұмыс істейді. Бұл С1 С2 екенін
көрсетеді. С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n мен
C2n2-ты салыстыра отырып, n5 болғандағы программаның жұмыс уақытының
баяу, ал n5 болғанда екінші программаның жылдам жұмыс істейтінін байқауға
болады. Мұндағы n =5 бағалау уақытының шектік мәні де жуықтап
тағайындалады.
Бұдан екі тұжырым жасауға болады. Біріншіден, тұрақтыға дейінгі
дәлдікпен жуықтап бағалаудың өзі алгоритмдерді салыстыруда пайдалы болып
табылады. Екініден, есеп шығарудың бір алгоритмі өте жылдам деп айтуға
болмайды. Қандай да бір алғашқы мәліметтер жиынтығы үшін кейбір алгоритм
екіншісінен тиімді болуы мүмкін.
Енді программаның жұмыс уақытын анықтайтын алғашқы мәліметтердің мұндай
сипаттамасын таңдау мәселесіне тоқталайық. Мұндай сипаттама есептің өлшемі
деп аталады. Әртүрлі есептерді шығару уақытына алғашқы мәліметтердің
әртүрлі қасиеті әсер етеді. Мысалы, минимумды іздеу немесе әрбір сан бір
бүтін сан ретінде қарастырылатын берілген сандарды іріктеу типті есептер
үшін алғашқы сандар мөлшері есептер мөлшері болып табылады. Қарапайым
көбейткіштерге жіктеу есебі үшін санның шамасы мөлшері болып есептеледі.
Есеептің мөлшерін таңдау қандай да бір шығару алгоритмі туралы жалпы ұғымға
негізделеді. 2n дәрежесін есептеу алгоритмін қарастырайық. Дәрежелеудің
санның бірінен соң бірі көбейтілетінін ескере отырып, өлшем ретінде n
дәреже көрсеткішті аламыз. Өлшемді сипаттаудың тағы бір тәсілі нәтижедегі
цифр сан ыболып табылады. 2n дәрежесіндегі цифр саны n-ге пропорционал,
сондықтан екі өлшем де эквивалентті.
Жұмыс уақытын бағалау мезетіндегі маңызды кезең – орындалу барысында
барлық жұмыс уақытының негізгі бөлігін алатын программа бөлігін іздеу болып
табылады. Көптеген программалар үшін экспериментті түрде дәлелденген факт:
жұмыс уақытының негізгі бөлігі программа мәтінінің шағын бөлігін орындауға
кетеді. Программаның мұндай бөлігі цикл деп аталады. Көпшілік жағдайда
жұмыс уақытын жуықтап бағалау талап етіледі, сондықтан программаның қалған
бөлігінің орындалу уақытын ескермеуге болады, тек ішкі циклдың орындалуын
қарастыруға болады.
Егер программа бірінің ішіне бірі орналасқан бірнеше программадан
тұратын болса, онда ішкі циклды табу жеңіл. Әрине, алдымен, бәрінен бұрын
барлық циклға қатысты программа бөлігі орындалады, ал бұл қалған барлық
циклдардың ішіндегі және ішінде басқа цикл болмайтын циклдар болып
табылады. Бұл бақылау программаның жиі орындалатын бөлігі үшін ішкі цикл
деген атауды дәлелдей түседі.
Егер ішкі циклды қамтымайтын бірнеше цикл болса, олардың әрқайсысының
қайталану санын есептеуге болады. Егер бір циклдың қайталану саны
басқаларымен салыстырғанда айтарлықтай үлкен болатын болса, онда басқа
циклдардың жұмыс уақытын ескермеуге болады; кері жағдайда соңғы формулада
жұмыс уақыты үшін бірнеше циклдардың орындалу уақытын ескеруге тура келеді.
Параметрлі қайталану командасындағы қайталану саны For операторы үшін
төмендегі формуламен есептеледі:
Циклдың басы For i:=A to B
Егер B=A-1 болса, онда қайталану саны B - A +1 –ге тең;
Егер BA болса, онда нөлге тең;
(1)
For i:=A downto B циклі үшін А мен В-ның орындарын ауыстыру қажет.
Егер программада цикл бір рет орындалатын болса, онда бұл формула
ақиқат болып есептеледі. Енді бұл циклдың басқа циклдың ішінде бірнеше рет
қайталанып орындалған жағдайын қарастырайық. Цикл ішіндегі қайталану санын
шартты түрде цикл денесінің орындалу санының саны деп атайық. Барлық
циклдың орындалу санын цикл тақырыбының орындалу саны деп атайық. Сөйтіп,
цикл тақырыбының бір рет орындалуы цикл денесінің қанша рет орындалатынын
көрсетеді. Бірінші формула оның тақырыбы цикл денесінің бір рет
орындалуындағы цикл денесінің орындалу санын береді. Егер қарастырылып
отырған цикл басқа циклдың ішінде орналасқан болса, онда онда оның тақырыбы
бірнеше рет орындалады да, цикл денесінің орындалуының жалпы санын табу
үшін осы цикл тақырыбының барлық орындалуы барысындағы (1) формуламен
алынған сандарды қосу қажет.
Бұл формуланы қолданудың қарапайым мысалы ретінде төмендегі программа
фрагментін талдайық:
For j:=1 to n do
Begin (*1-цикл *)
For k:=1 to M do (* 2-цикл денесі*)
For l:=n downto j do (* 3-цикл денесі*)
End;
Екінші және үшінші цикл денелерінде ішкі цикл жоқ, ал, M және N –
қандай да бір үлкен тұрақтылар. 2 және 3-циклдардың қайталану санын
бағалайық. Екеуі де бірінші циклдың ішінде орналасқан, олардың қай талану
саны (1) формула бойынша оңай есептеледі; ол N-1+1=N-ге тең. Бұл
қайталанулардың әрқайсысында 2-цикл денесі М-1+1=М рет орындалады. М саны
тұрақты болғандықтан 2-цикл денесінің жалпы орындалу саны N2= N∙М тең. 3-
цикл денесі 1-цикл денесінің әрбір орындалуында N-J+1 рет орындалады. Бұл
санның М санынан айырмашылығы 1-циклдың орындалуы барысында өзгеріп
отырады; сондықтан екі санды тек көбейте салуға болмайды:3-цикл денесінің
барлық орындалу санын қосу қажет. Бұдан 1-циклдың орындалуында J айнымалысы
1-ден N-ге дейінгі барлық мәндерді қабылдайды (міне дәл осы 1-цикл
тақырыбында жазылған. Сөйтіп, 3-цикл денесінің жалпы орындалу саны:
Бұл арифметикалық прогрессияны ңқосындысы; ол (N+1) ∙ N2 тең. Уақыт
жуықтап есептелінетіндіктен N-мен салыстыруға жүгібей-ақ, формуланы
жеңілдетуге болады: N3 жуықтап N22 тең. N2 мен N3-ті салыстыра отырып, бұл
сандардың біреуі екіншісінен әлдеқайда артық деп айта алмаймыз. Керісінше,
қандай да бір N мен М үшін олар бір ретте болады. Мысалы, егер М= N, онда
N2 шамамен N3-тен 2 есе үлкен болады. Сондықтан жұмыс уақыты үшін формулаға
екі циклға да жауап беретін екі қосылғыш қосуға тура келеді. Цикл
денелерінің бір реттік орындалу уақытын есептей отырып, тұрақтыларды Т2
және Т3 арқылы белгілеп, жалпы жұмыс уақытын есептеу үшін төмендегідей
жуықтатылған формуланы аламыз:
Т =М∙N∙Т2+(N22) ∙Т3.
Егер цикл денелерінің орындалу уақытын тұрақты деп есептемейтін болса
(мысалы, онда шартты оператор немесе процедураны шақыру болса), онда
алдымен денелердің орындалу уақытын талдап, одан кейін оларды қосу қажет.
Жұмыс уақыты жөнінде бұдан да дәл ақпаратты әртүрлі алғашқы мәліметтер
бойынша программа программа жұмысының шынайы уақытын өлшеу нәтижесі бойынша
алуға болады. Бұл эксперименттердің көмегімен формулаға кіретін белгісіз
тұрақтыларды (біздің жағдайда Т2 және Т3) бағалауға болады.
Енді нақты программа жұмысын талдауға көшейік, 2N дәрежесін есептеуді
қарастырайық. Программа жұмысы циклды қамтитын екі ірі бөліктен тұрады. Ол
2N дәрежесін есептеу және баспаға шығару. Программаның жұмыс уақытын
бағалауда әдетте, баспаға шығару уақытын емес, тек есептеуге кететін уақыт
ескеріледі. Бұл көптеген есепті шығару алгоритмі үшін басу уақыты өте аз
болғандықтан ескерілмейді. Сонымен қатар, өте үлкен N үшін есептеу уақыты
аз болғандықтан ескермеуге де болады. Басып шығаруды және циклған
кірмейтіндерді шығарып тастағаннан кейін төмендегідей программма аламыз:
For K:=1 To N Do Begin (*1-цикл*)
For I:=еңҮлкенҰзындық DownTo XБасы Do Begin
(*2-цикл *)
Құрамында циклы жоқ әрекеттер
End;
Құрамында циклы жоқ әрекеттер
End;
Бір цикл, дәлірек айтсақ, 2-циклға басқа цикл кірмейді.Ол ішкі цикл
болып қалады. Енді оның денесінің қайталану санын есептейік. 2-цикл
денесінің орындалу саны МАХұзындық-Хбасы+1-ге тең, жұмыс барысында ХБасы
мәнінің өзгеруінің есебінен өзгереді. Мұнда ХБасы мәнінің 1-циклды
басқаратын К мәніне қаншалықты тәуелді екенін біз білмейміз. 2-цикл
денесінің орындалу санын N2(К) арқылы белгілей отырып, төмендегідей
қосындыны есептеу қажеттілігіне көз жеткіземіз:
N2(К) функциясын табу үшін алгоритмді мазмұны жағынан талдау қажет.
(1) формуланы тікелей қолдану ыңғайсыз. Мұның орнына 2-цикл тақырыбының
әрбір орындалуында оның денесінің орындалу саны екі еселенген цифрларының
санына тең екенін байқаймыз. Программа мәтінінен байқалғанындай екі
еселенген сан 2К-1 –не тең. Кез келген натурал санның цифрларының саны
оның ондық логарифмінің бір бүтін бөлігіне көбейтіндісіне тең, 2К-1 –нің
ондық логарифмі (К-1)*lg2-ге тең, мұндағы lg2 жуықтап 0,3-ке тең. Сөйтіп,
N2(К) үшін төмендегідей формуланы аламыз:
N2(К) = 1+[(K+1)Lg2].
Мұндайжалпы мүшесі бар қосындыны есептеу қиын. Есептеуді жеңілдету үшін
жуықтатылған санға көшеміз. Санның бүтін бөлігі өзінен 1-ге жуық
ажырыатылатынын байқаймыз. Бұл айырмашылықты ескермей, логарифмнің бүтін
бөлігіні логарфимнің өзімен алмастырамыз. Жалпы мүшесі 1+[(K+1)Lg2] болатын
арифметикалық прогрессияның қосындысын табу қажет. Қосынды төмендегі
формуламен есептеледі:
Соңғы шамаға көшу барысында N* Lg2-мен салыстырғанда шамасы кіші
болатын 2- Lg2 қосылғышын ескермедік. Сондай-ақ, қорытынды нәтижені де
бірден алуға болатын еді, егер і+(К-1) Lg2 шамасын К* Lg2-ге жуықтап
алмастырса, ал, арифметикалық прогрессияның қосындысын табуға арналған
формулада прогрессияның алғашқы мүшесін алмауға болады. Барлық бұл
ауыстырулардың қателігі бір ретті және жуықтап қорытынды нәтиженің 1N
бөлігін құрайды.
Сөйтіп, 2-циклдың орындалуының қорытынды уақыты барлық программа
бойынша есептеудің негізгі бөлігін құрайды, ол:
N2∙ Lg22∙Т2≈0,15∙N2∙Т2 тең.
Мұндағы Т2-цикл денесінің бір рет орындалу уақыты.
Сөйтіп, біз 2N дәрежесін есептеу программасының жұмыс уақытын бағалауды
жүргіздік. Жұмыс уақытын бағалау барлық уақытта қажет және оны программаны
құру кезінде орындау қажет.
Енді WHILE-DO типті қайталану алгоритмінің жұмыс уақытын талдау мысалын
қарастырайық. Бүтін санды натурал санға дәрежелеу функциясының жұмыс
уақытын талдайық. Мұны есептеу функциясының мәтінеі төмендегідей:
Function Dareje (M,N:integer):integer;
{М – дәреженің негізі, N – дәреже көрсеткіш}
Var M1,N1,P:integer; {Р –нәтижені есептейтін айнымалы}
Begin
P:=1; M1:=M; N1:=N;
WHILE N10 do {сыртқы цикл}
Begin
WHILE N1 mod 2 =0 do
Begin {ішкі цикл}
N1:=N1 div 2; M1:=M1*M1;
{N1 дәрежелі М1-дің мәні өзгерген жоқ}
End; {ішкі циклдың соңы}{}
N1:=N1-1; P:=P*M1 {Нәтижеге N дәрежелі М меншіктеледі}
End; {Сыртқы циклдың соңы}
Dareje:=P;
END;
Есептің өлшемі қызметін N дәреже көрсеткішінің мәні атқарады. Уақыттың
негізгі бөлігі циклды орындауға кетеді. Дегенмен, ішкі циклды орындауға
кететін уақыт сыртқы циклды орындауға кететін уақыттан айтарлықтай көп
деген тұжырым жасауға болмайды, өйткені тақ N1 үшін ішкі цикл денес
іорындалмайды. Сыртқы цикл денесінің бір рет орындалу уақытын Т1, сыртқы
цикл денесінің орындалу санын К1 арқылы белгілейік. Ал, Т2 және К2 –
сәйкес ішкі циклдың сипаттамалары.Функцияның жалпы жұмыс уақыты Т(N)
жуықтап Т(N) = Т1 ∙ К1 + Т2 ∙ К2 тең. К1 мен К2-ні бағалау үшін N1-дің
кему процесін қадағалайық. Dareje функциясы N1-дің жұптығын, 2-ге
бөлінетіндігін тексеру операциясын қамтиды. Бұл алгоритмді талдау үшін N1-
дің мәнінің екілік санау жүйесіндегі жазылуын қарастыру қажет деген ойға
жетелейді. (А санының негізі b болатын позициялық санау жүйесіндегі аmam-
1...a1a0 цифрларымен жазылуы:
-ге тең.
B=2 болғанда 0 және 1 цифрлары арқылы жазылған санның екілі жүйедегі
жазылуын аламыз. Мысалы, екілік жүйедегі 1001 саны ондық жүйедегі 9 санының
жазылуы. К1 және К2-ні табу үшін N1 мәніндегі бір ең кіші екілік цифрды
өңдеу барысында ішкі және сыртқы циклдардың қанша рет орындалатынын есептеу
қажет. Мұнда үш түрлі жағдай қарастырылуы мүмкін.
1. N1=1. Ішкі цикл орындалмайды; ал сыртқы цикл бір рет орындалады; N1
0-ге дейін кеміп, циклдан шығады.
2. N11, N1 нөлмен аяқталады (яғни жұп). Ішкі цикл бір рет
орындалғаннан кейін N1 2-ге бөлінеді. Екілік жүйеде екіге бөлу ең кіші
цифрды шығарып тастағанмен бірдей. Сөйтіп, ең кіші нөлді өңдеу үшін ішкі
циклдың бір рет орындалуы жеткілікті.
3. N1≤1, N1 бірмен аяқталады (тақ). Ішкі цикл орындалмайды, сыртқы
циклда N1-ден 1-алып тастайды, яғни N1 жұп болып қалады. Сөйтіп, 2-жағдайға
келеміз. Ең кіші бірлікті өңдеу үшін ішкі және сыртқы циклдың бір реттен
орындалуы талап етіледі.
Бірінен соң бірі өңделіп, N1 цифрының барлық екілік цифрлары шығарылып
тасталынады. Сонымен, бастапқы N1= N жағдайды ескере отырып,
К1 = N-нің екілік жазылуындағы берліктер саны,
К2 = (N-нің екілік жазылуындағы цифрлар саны)-1
екенін аламыз.
N-нің екілік жазылуындағы цифрлар саны N-нің екілік логарифмінің бүтін
бөлігін 1-ге арттырғанмен бірдей, яғни
К2 = [log2N].
К2 үшін мұндай қарапайым формуланы жаза алмаймыз, сондықтан К1 –ді
жоғарыдан ғана бағалай аламыз. Бірліктер саны цифрлар санынан көп
болмайтыны белгілі,
К1 ≤1+[log2N].
Бұдан
Т(N) ≤ (1+[log2N]) ∙ Т1 + [log2N] ∙Т2 =( Т1 + Т2) ∙ [log2N] + Т1 .
Теңдік N екілік жүйеде тек 1-лермен жазылған жағдайда ғана теңдік
орындалады, яғни екінің дәрежесі 1-ге кем. N екілік жүйедегі жазылуында
бірліктер қаншалықты аз болса, онда Dareje функциясы соншалықты жылдам
жұмыс істейді. Егер N екінің дәрежесі болса, К1 минимумға жетеді, ал жалпы
уақыт
Т(N) = Т1 + log2N ∙Т2 .
Енді Dareje функциясын tyzusyzykty функциясымен салыстырып көрейік.
Function tyzusyzykty (M,N:integer):integer;
{М – дәреженің негізі, N – дәреже көрсеткіш}
Var M1,N1,P:integer; {Р –нәтижені есептейтін айнымалы}
Begin
P:=1; M1:=M; N1:=N;
WHILE N10 do
Begin
N1:=N1-1; P:=P* M1;
End;
Tyzusyzykty:=P;
END;
Бұл функцияның жұмыс уақытын ТС(N), ал циклдың бір рет орындалуын ТС1
арқылы белгілейік.
ТС(N)≈ N · ТС1 болсын. N –мен салыстырғанда log2N баяу өсетіндіктен, N-
нің шамасы өте үлкен болған жағдайларда Т(N) ТС(N) болады, N-нің шамасы
артқан сайын жылдамдық та артады. Енді қаншасыншы N-нен бастап Dareje
функциясы жылдам жұмыс істейтінін қарастырайық.
Әрбір циклда негізгі уақыт көбейтуге кететіндіктен ТС1 ≈Т1 ≈Т2 деп
есептеуге болады. Бұдан,
Т(N)≤ ТС1 ·(2∙ [log2N]+1)
екені шығады. 2∙ [log2N]+1N теңсіздігін шеше отырып, N5 екенін табамыз. N-
нің шекаралық мәнін іздеуде T(N) үшін жоғарыдан бағалауды пайдаландық. N-
нің 1-ден 5-ке дейінгі мәндерін жеке зерттеуге болады. N=1,2,3 мәндері
үшін Dareje функциясы tyzusyzykty функциясы тәрізді көбейтуді орындайды, ал
N=4,5 мәндерінде көбейту аз орындалады. Бұл N-нің барлық мәндері үшін
Dareje функциясын пайдалануға болатынын көрсетеді.
Талдауды қорытындылайтын болсақ, егер FOR циклында қайталану саны
айнымалы болып, программада есептелсе онда, жұмыс уақытын бағалауға
формальды әдістерді қолдануға келмейді, программа жұмысын мазмұнды талдауды
талап етеді. Ал, While-Do және Repeat-Until қайталанулар одан да үлкен
қиындық әкеледі. Бұл қайталанулар үшін қайталанудың жалпы формуласын жазуға
келмейді. Бұдан барлық уақытта барлық қиындықтарды жеңіп, жұмыс уақытын
есептеудің жуықтатылған формуласын табу мүмкін бола бермейді. Алгоритмді
бағалауда кейде құрғақ ақпаратпен шектелуге тура келеді. Мұндай жағдай
барлық мүмкін болатын көбейткіштерді таңдауға негізделген санды қарапайым
көбейткіштерге жіктеу алгоритмінде орын алады. Сонымен бірге, сан жай сан
болса, таңдауды соңына дейін жүргізуге тура келеді, алдымен санның жай сан
екеніне көз жеткізу қажет. Бұл алгоритм үшін жұмыс уақытын жоғарыдан
бағалау міндеті қойылады, осындай TMAX(N) шамасы N өлшемді есеп үшін шынайы
жұмыс уақыты TMAX(N)-нан артпайды және кейде осы шаманың өзіне тең болады.
Жұмыс уақытын есептеуге арналған формуламен алгоритмді салыстырумен қатар,
өлшенген жұмыс уақытын басқа есептің өлшеміне экстрополяциялау үшін
пайдалануға болады. Мысалы, 210000 дәрежесін есептеу қажет болсын. Мұның
едәуір уақыт алатынын алдын-ала айтуға болады. Ол үшін 21000дәрежесін
есептеп, есептеу уақытын өлшейміз. Мысалы, ол 30 секундқа тең болсын. Онда
210000-ін есептеу 10*10=100 есе көп болады, 3000 секундты, яғни 50 минутты
құрайды. Бұл 210000 дәрежесін есептеу одан да жылдам алгоритм іздеуді талап
етеді.
Рекурентті тізбектерді өңдеу
U(1), ..., U(K) тізбегінің алғашқы К-сыншы мүшелері берілген болса, онда
U(1), U(2), ...,U(N) тізбегінің элементтері К ретті рекурентті тізбекті
құрайды делінеді, ал NК үшін
U(N)=F(U(N-1),...,U(N-K))
теңдеуi орындалады. Мұндағы Ғ – К аргументтің қандай да бір функциясы.
Екінші ретті пекуррентті тізбекті белгілі мысалы Фибоначчи сан тізбегі
болып табылады., оның
U(1)=U(2)=1, ал N2 үшін
U(N)=U(N-1)+U(N-2).
Бірінші ретті рекуррентті тізбектің мысалы – а санынан квадрат түбірді
Ньютон әдісі бойынша есептеуге арналған тізбек: U(1)=a+1, ал N1 үшін
U(N)=0.5*(U(N-1)+aU(N-1)).
Рекуррентті тізбектерге қатысты төмендегідей есептер қойылады.
1. Тізбектің N-ші элементін есептеу.
2. Берілген G(U(N), U(N-),...,U(N-K)) логикалық функциясының ең кіші
нөмірлі элементін есептеу.
Бұл екі есепті шығару үшін тізбектің К+1 элементін жадыда сақтау қажет.
К1=К+1. Онда К+1 элементті жадыға сақтауға арналған массив былай
сипатталады:
VAR T:ARRAY[1..k1] OF тізбектегі элементтер типі тізбектегі
есептелген элементтердің соңғысы T[K+1] элементінде сақталады.
Екі есепті шығаруда екі негізгі кезеңге бөлінеді:бастапқы шар және
тізбек бойынша орындау. Бастапқы шартты төмендегідей жазуға болады:
T[2]:=U(1);...;T[K+1]:=U(K);
Ал тізбек болйынша бір элементке алға қарай орындауда:
FOR I:=1 TO K DO T[I]:=T[I+1];
T[K+1]:=F(T[K],...,T[1]);
Т массивінің әрбір элементі біріншісінен бастап, мәнді келесі элменттен
бастап алады. Соңғы элементтен мәнін алғаннан кейін, F рекурренттік
формуласын қолдана отырып, жаңа мән қабылдайды. Келесі есептеуге әсер
етпейтіндіктен T[1]-дің ескі мәні қажет болмай қалады.
1 және 2-есептер тізбек бойынша болатын орын ауыстырулар қаншалықты
орындалатынымен ажыратылады. 1-есепте жылжу N-K-ға тең, өйткені T[K+1]
алғашқы шарттан кейін тізбектің К-элементін сақтайды, бірақ N-элементті
алу керек. Жылжуды қайталау үшін FOR қайталануын пайдаланған ыңғайлы:
FOR J:=K+1 TO N DO
BEGIN
FOR I:=1 TO K DO T[I]:=T[I+1];
T[K+1]:=F(T[K],...,T[1]);
{T[K+1]:=U(J)}
END;
{T[K+1]:=U(N)}
2-есепте G функциясының мәні ақиқат болған мезеттежылжуды аяқтау қажет.
Бұл жағдайда жылжуды қайталау үшін REPEAT-UNTIL қайталануын пайдаланған
ыңғайлы:
REPEAT
FOR I:=1 TO K DO T[I]:=T[I+1];
T[K+1]:=F(T[K],...,T[1]);
UNTIL G(T[K+1],...,T[1]);
1-есепті шығаруға мысал ретінде N-Фибоначчи санын есептеу функциясын
қарастырайық:
Function FIBONACHI_SANY (N:integer):integer;
{ N – ізделінді элементтің нөмірі,
ол N0 деп есептелінеді}
Var I,J:integer;
T:ARRAY[1..3] OF INTEGER;
Begin
{бастапқы шарт}
T2:=1; T3:=1
{жылжуды қайталау}
FOR J:=3 TO N DO
Begin
FOR I:=1 TO 2 DO
T[I]:=T[I+1];
T[3]:=T[2]+T[1];
END;
FIBONACHI_SANY:=T[3];
END;
Рекуррентті тізбек айтарлықтай үлкен болмаса, массивті пайдаланбай-ақ,
тізбек элементтері сақталған айнымалыларды жеке атаулармен бөліп көрсетуге
болады.Бұл жағдайда тізбек бойынша жылжуда FOR қайталануы К меншіктеулермен
алмастырылады. 2-есепті шығару мысалы ретінде А санынан берілген дәлдікпен
квадрат түбірді есептейтін функциянвы қарастырайық. ТЕК айнымалысы түбірге
ағымдағы жуықтатылған мәнді, ал АР айнымалысы алдыңғы мәнді сақтау үшін
пайдаланылсын.
ABS(U(N)-U(N-1))KATE
өрнегі G ретінде алынады.
Function KVADRAT_TUBIR (A,KATE:REAL):REAL;
{ A – Түбір алынатын сан,
KATE- қажеттті жуықтау дәлдігі}
Var TEK,AP:REAL;
{ТЕК – квадрат түбірге жуықтатылатын ағымдағы мән,
АР – алдыңғы жуықтау}
Begin
{бастапқы шарт}
TEK:=A+1;
{жылжуды қайталау}
REPEAT
AP:=TEK;
TEK:=0.5*(AP+AAP)
UNTIL ABS(TEK-AP)KATE;
KVADRAT_TUBIR:=TEK;
END;
Рекуррентті тізбекті анықтаубіршама жалпылауға мүмкіндік береді, егер
элементтерді нөмірлесе, оны 1-ден бастау міндет емес, F функциясының N-нен
тәуелділігін алуға болады. Мұндай тізбектермен жұмыс істеуде бастапқы нөмір
меншіктелетін бастапқы шартты қосу керек және әрбір жылжуда тізбек бойынша
нөмірді 1-ге арттырып отыру қажет. Мұндай жалпылаудан тек 2-цикл ғана
аздапкүрделенеді. Сол нөмірлі элементті есептеуде FOR циклы бәрін
орындайтындықтан 1-цикл өзгермейді.
Енді осы айтылғанды мысалмен түсіндірейік. Кейбір есептер рекуррентті
тізбектерді өңдеуге келтіріледі. С коэффициентпен берілген массивтегі М
дәрежелі көпмүшеліктің мәнін есептеу қажет болсын:
VAR C:ARRAY[0..M] OF REAL;
X айнымалысының мәнін берілген деп есептейміз. Көпмүшеліктің мәнін
есептеу үшін Горнер схемасы пайдаланылатыны белгілі. Көпмүшелікті мына
түрде жазуға болады:
(...(C[0]·X+C[1]) ·X+...+C[M-1]) ·X+C[M].
U(N) бірінші ретті рекуррентті тізбекті төмендегідей анықтайық:
U(0)=C[0],
U(N)=U(N-1) ·X+ C[N], 1≤N≤M
(бұл жағдайда тізбек элементтерін 0-ден бастап нөмірлеген ыңғайлы).
U(M) көпмүшеліктің мәні екенін көрсету қиын емес. Жоғарыда келтірілген
әдістемені U(M)-ді табу үшін қолданамыз. Бұл тізбек элементтерін нөмірі
бойынша есептеу есебі. Егер жалпы схема бойынша қарастырсақ, SAP және STEK
екі айнымалыларын енгізу керек және жылжуды төмендегідей жүргіземіз:
FOR J:=1 TOM DO BEGIN
SAP:=STEK;
STEK:=SAP*X+C[J];
END;
Мұнда SAP айнымалысының қажет емес екені көрінеді, өйткені STEK
айнымалысының жаңа мәнін есептеуде осы айнымалының алдыңғы мәнін
пайдалануға болады. Сөйтіп, элемент нөмірі бойынша бірінші ретті
рекуррентті тізбекті есептеуде бір айнымалыны пайдалану жеткілікті, нәтиже
сол айнымалыға меншіктеліп отырады. Берілген шартты қанағаттандыратын
тізбектің элементін есептеу есебі үшін де ақиқат болып табылады, егер G
функциясы тек U(N)-нен тәуелді болатын болса. Сондай-ақ, циклдың алдындағы
бастапқы шартты тізбектің бірінші элементі басқаларымен тең
есептелінетіндей етіп, ұйымдастыруға болады. Нәтижесінде төмендегідей
функцияны аламыз:
CONST M=...,
TYPE KOEF=ARRAY[0..M] OF REAL;
...
Function GORNER (VAR C:KOEF; X:REAL):REAL;
{ С коэффициентті массивпен, Х айнымалысының
мәні
берілген, бір айнымалыдан тәуелді
көпмүшеліктің мәнін
Горнер схемасы бойынша есептейтін функция}
Var S:REAL; J:INTEGER;
{ S айнымалысына көпмүшеліктің мәні есептеледі}
Begin S:=0;
FOR J:=1 TO M DO
S:=S*X+C[J];
GORNER:=S;
END;
Рекуррентті қатынастармен жұмыс істеу техникасы сондай-ақ, тізбектерді
өңдеу программаларын құруда, әсіресе, жалпы формула бойынша әрбір мүшені
есептемей, алдыңғының мәнін біле отырып, кезекті элементті алуда тиімді.
Қатардың қосындысын табу есебін қарастырайық.
1+11!+12!+...+1N!+...
(бұл е санын есептеуге арналған қатар). Қосындыны табуды кезекті
қосылғыш алдын-ала берілген КАТЕ шамасынан кіші болғанша жүргізу керек.
Әрине, әрбір N үшін N!-ды қайтадан есептеу керек. Қосындыны табу уақыты
C1m2 өрнегімен беріледі, мұндағы m - қатардың қосынды табылған мүшелерінің
саны. Егер N!=N·(N-1)! қатынасын пайдалансақ, есептеуді жеделдетуге болады.
Қатардың қосылғыштарын бірінші ретті рекуррентті тізбектің көмегімен
анықтауға болады:
U(0)=1, U(N)=U(N-1)N,N0.
Енді U(N)KATE шартын қанағаттандыратын тізбектің элементін табамыз.
Сонымен қатар, есетелгнен элементтерді қосамыз, сонда қосу уақыты C2m-ге
дейін азаяды:
Function CHISLO_E (KATE:REAL):REAL;
Var N:INTEGER; U,S:REAL;
{ N – қосылғыш нөмірі;
U – кезекті қосылғыш;
S – алғашқы N элементтің қосындысы}
Begin N:=0; U:=1; S:=U;
REPEAT
N:=N+1;
U:=UN; {U:=1N!}
S:=S+U;
{S=1+11!+...+1N!}
UNTIL UKATE;
CHISLO_E:=S;
END;
Қосынды берілген шартты қанағаттандыратын рекуррентті тізбектің
элементін есептеумен бірге жүргізіледі.
Сонымен, уақыттың көп бөлігін машина циклды, алдыңғы кезекте ішкі
циклды орындауға жұмсайды. Берілген қайталану саны бойынша циклды орындау
уақыты циклға кіретін әрекеттер санына тәуелді. Цикл қаншалықты қарапайым
болса, яғни әрекеттер саны қанша аз болса, соншалықты программа жылдам
орындалады. Сондықтан, программаның ішкі циклын жеңілдету шараларын қолдану
қажет.
Сонымен қатар, программаның жұмыс уақытына негізгі әсер ететін таңдалған
алгоритм болып табылады. Алдымен, есепті шығарудың мүмкін болатын
алгоритмдерін талдау қажет, оның ішінен ең жылдам орындалатын алгоритмін
таңдап, ондағы ішкі циклды анықтап, ішкі циклды жеңілдетуге әрекет жасау
қажет.
Лекция № Алгоритм ұғымы, қасиеттері. Жазылу тәсілдері
Есеп шығару алгоритмі деп есептің нәтижесін алуға бағытталған нақты
әрекеттер тізбегін атау қабылданған. Мұндағы есептің жауабы берілген
алғашқы мәліметтер бойынша бар немесе жоқ болуы мүмкін. Жалпы жағдайда,
есептер тек керекті ақпаратты алу ғана емес, әртүрлі болады. Мысалы, көше
қиылысынан светоформен өту, тағамдар дайындау есебі және т.с.с есептер.
Мұндай есептерді шығару алгоритмдерін тұрмвстық деп атайды. Шындығында,
адамның өмірі өмірлік тәжірибелер мен қоғамдық заңдылықтардан туындайтын
кешенді әрекеттер алгоритмімен сипатталады.
Алгоритмнің дәл, нақты математикалық анықтамасы жоқ, көптеген
оқулықтарда алгоритмнің анықтамасы жылдар бойы жинақталған түсініктермен
тұжырымдалады. Сонымен, алгоритм дегеніміз – алға қойылған мақсатқа жетуге
бағытталған (берілген есептің шешімін табу үшін), қандайда бір орындаушыға
арналған (адам немесе компьютер), орындалу тәртібі ұйымдастырылған
түсінікті, ықшамды, қадамдар саны шектелген нұсқаулар тізбегін түсінеміз.
Алгоритмді қандай да бір операндалармен жалпыланған операция ретінде
қарастырып, оны былай белгілеуге болады:
F(x1,x2,...,xn,y1,y2,...,ym) (1)
Мұндағы Ғ – осы операцияның шартты белгісі, x1,x2,...,xn – алғашқы
мәліметтер, біз оны алгоритмнің аргументтері деп атаймыз, y1,y2,...,ym –
операндалары алгоритмнің орындалу нәтижелерін белгілейді, бұл алгоритмнің
нәтижелері деп аталады.
Алгоритм ұғымы есепті шығару әдісі ұғымымен тығыз байланысты. Әдіс
алғашқы мәліметтер бойынша сол есепті қайда қолдануға болатынын, яғни
есептің класын анықтау мақсатында қатаң түрде негізделген және құрылған
тәсілмен зерттелген есепті шығару тәсілін жасау болып табылады.
Ал, алгоритм есепті шығару және оны практикалық қолдану әдісінің
сипатталуы болып табылады. Ол әдістің зерттелу нәтижесі бойынша құрылады.
Дәлірек айтсақ, алгоритм есепті шығаруға арналған әрекеттердің қатаң түрде
жазылған тізбегі болып табылады. Бұл әрекеттер есепті шығару әдісінен
шығады.
Алгоритмнің аса маңызды бір қасиеті атқарушыдан есепті шығару әдісін
түсіну талап етілмейді. Атқарушыдан өзіне арналып жазылған әрекеттерді
орындай білу іскерлігі мен жазылған инструкцияны (команданы) түсіну талап
етіледі. Сонымен, атқарушы инструкция-командаларды қадағалай отырып,
алгоритмді механикалық түрде орындайды.
Алгоритм белгілі бір атқарушыға, оның командалар жүйесіне арналып
жазылады. Ол адам, компьютер және т.б. құрылғылар болуы мүмкін. Алгоритмнің
жазылуы атқарушы түсіну үшін сол атқарушының тілінде жазылады.
Алгоритмдегі әрбір жеке нұсқау команда деп аталады немесе оны шартты түрде
алгоритм қадамы деп атаймыз. Сонымен, алгоритм дегеніміз реттелген
командалар тізбегі болып табылады. Атқарушының түсініп, орындайтын барлық
командалар жиынтығы атқарушының командалар жүйесі деп аталады. Сөйтіп,
атқарушының тілі дегеніміз атқарушының барлық әрекетін сипаттайтын
командалар жүйесі болып табылады.
Алгоритм барлық уақытта атқарушыға, оның командалар жүйесіне
бағытталады. Алгоритмді жазудың әртүрлі тәсілдері бар: формула, кесте,
сөзбен, графикалық, алгоритмдік тіл немесе программалау тілі. Алгоритмнің
графикалық түрде кескінделуі блок-схема деп аталады. Алгоритмнің
программалау тіліндегі жазылуын программа деп атаймыз. Ал, программалау
тілі дегеніміз алгоритмнің компьютер-атқарушыға арналып жазылған тілі болып
табылады. Программалау дегеніміз – программалау тілінде алгоритмнің жазылу
процесі.
Енді алгоритмнің сөзбен жазылуына тоқталайық. Алгоритмнің
орындалуындағы көшулерді көрсету үшін командалар нөмірленеді. Сондай-ақ,
алгоритмді жазуға пайдаланылатын қызметші сөздер, яғни қосымша командалар
пайдаланамыз: басы, соңы, тоқта. Мұндағы басы сөзі сәйкес алгоритмнің
басын көрсетеді; ал соңы сөзі егер алгоритмнің ары қарай орындалуы мүмкін
болмаса, аяқталуын көрсетеді; тоқта сөзі – алгоритмнің дұрыс аяқталмай,
яғни апатты аяқталуын көрсетеді.
Енді алгоритмнің сөзбен сипатталуына мысалдар келтірейік.
1-мысал. Квадрат түбірді итерациялық әдіспен есептеу. Есептің қойылысы:
нақты саны х берілген, егер түбір болса m–ге дейінгі дәлдікпен
функциясын есептеңіздер.
Алгоритмде жуықтап тізбек құрудың итерациялық әдісін пайдаланамыз:
Y0,y1,y2,...,yk,yk+1,... (2)
Ол алдын-ала e0 дәлдікпен берілген кез келген санмен X=0 болғанда
мәніне жинақталады.
Теңдеуді шығарудың жанама әдісінен К үшін (K=0,1,...) Y0=const0
болғандағы Геронның итерациялық процесі шығады:
(3)
Есептеу әдістерінде, егер түбір бар болатын болса, (2), (3) тізбектер
-тің дәл мәніне өте жылдам жинақталады. (3) теңдеудің әрбір қолданылуы
алдыңғы жуықтаудың дәл мәндерінің мөлшерін жуықтап екі еселейді.
Бұл процесс
(4)
теңсіздігі орындалғанда аяқталады, ол абсолюттік қателікті жоғарыдан
бағалау болып табылады.
(2), (3) итерациялық процестерді
, (5)
формуласы бойынша енгізу ыңғайлы. Мұндағы dYk – алдыңғы жуықтауға түзету.
Егер
(6)
шарты қанағаттандырылатын болса, итерациялық процесті тоқтатуға болады. Бұл
түзету талап етілген дәлдіктен төмен екенін көрсетеді.
(2) мен (5) аралығындағы итерациялық процесс өте қарапайым жүргізіледі:
алдымен dYk, одан кейін Yk+1 есептеліп, Е-мен салыстырылады.
(3) теңдеуден dYk-ны есептеу формуласын қорытып шығарайық:
Бұдан
(7)
Бұл қайта құрылған итерациялық процесті Y0=1, (7), (5) түбірді жуықтап
есептеу алгоритміне пайдаланамыз, бірақ жуықтауды бағалауды салыстырмалы
қателік бойынша жүргіземіз.
(8)
Бұл алынған түбірді жуықтап есептеудің m ақиқат белгісін қамтамасыз
етеді.
Алгоритмдегі аргументтер X, m, нәтиже Y. Түзету үшін d, салыстырмалы
қателікті бағалау үшін Е айнымалыларын пайдаланамыз.
Бұл алгоритмнің сөзбен жазылуы төмендегідей:
Аргументтер: X, m
Нәтиже: У
Аралық шама: d, Е
1. Басы
2. егер Х0 болса, онда 4-ге көшу
3. Тоқта, яғни түбір жоқ
4.
5. Y:=1
6.
7. Y:=Y+d
8. Егер , онда 5-ға көшу
9. Соңы.
2-мысал. Формула бойынша есептеу алгоритмі. Есептің қойылысы:
Х=с(а- b) - мәнін есептеңіз.
Енді осы алгоритмнің сөзбен жаызлуын келтірейік.
Аргументтер: a, b, с.
Нәтиже: х
Аралық шамалар: Q, P.
0. Басы
1. Q:= aҺb
2. Р:= a-b
3. Р:=РҺс
4. Х:=Р- Q
5. Соңы
3-мысал. Сандардың қосындысын есептеу. Есептің қойылысы: сандар
берілген, олардың қосындысын табу қажет.
Алдымен белгілеулер енгіземіз: n - сандар мөлшері, x1, x2,...,xn –
берілген сандар, S – нәтиже.
Сандардың қосындысын есептеу үшін сызықтық алгоритмді пайдалануға болар
еді.
1. Басы
2. S:=x1
3. S:=S+x2
...
N S:=S+xn
4. Соңы
Бірақ мұндай алгоритмдегі қадамдар саны өте көп. Егер n=1000 болса,
1002 команда жазуға тура келеді. Мұндай келеңсіздіктен құтылу үшін циклдық
алгоритм құрамыз. Ол үшін циклдың қайталану шартын қосылған сандар
мөлшерінің есептегішімен байланыстырамыз және қосылатын сандар индексін
–көрсеткішін енгіземіз. Индекстің мәні айнымалының реттік нөмірі болып
табылады, индекс үшін і айнымалысын енгіземіз. Нәтиже S айнымалысына
меншіктеледі, яғни нәтижеге әрбір кезекті сан қосылып отырады. Нәтиже
сақталатын S айнымалысының бастапқы мәні 0-ге, ал і қайталану параметрінің
бастапқы мәнін 1-ге тең деп аламыз. і:=і+1 индекстің өзгерісімен, і n-нен
артқанша алгоритмдегі негізгі операция S:=S+xі орындала береді. Бұл
жағдайда і индексі қосылған сандар мөлшерін есептейтін есептегіштің ролін
атқарып тұр. Есептегіштің мәні артып отыр, сондықтан ол тура есептегіш деп
аталады.
Сонымен қатар, сандарды қосуды кері есептегішпен де жүргізуге болады,
бұл жағдайда алдымен і= n деп аламыз да, әрбір қайталануда і-дің мәнін 1-
ге азайтып отырамыз: і:=і-1. Бұл жағдайда қайталану і0 болғанша қайталана
береді.
А) Берілген n санның қосындысын тура есептегіш бойынша есептеу
алгоритмі.
Аргументтер: n, x1, x2,...,xn
Нәтиже: S
Аралық шама: і
1. Басы
2. S:=0
3. і: = 1
4. S:=S+xі
5. і:=і+1
6. Егер і=n болса, онда 4-ке көшу
7. Соңы
ә) Берілген n санның қосындысын кері есептегіш бойынша есептеу
алгоритмі.
Аргументтер: n, x1, x2,...,xn
Нәтиже: S
Аралық шама: і
1. Басы
2. S:=0
3. і: = n
4. S:=S+xі
5. і:=і-1
6. Егер іn болса, онда 4-ке көшу
7. Соңы
4-мысал. Берілген n санның ішінен ең үлкенін табу алгоритмі. Есептің
қойылысы n саны берілген. Олардың ішіндегі ең үлкенін және оның реттік
нөмірін анықтаңдар.
Алгоритмнің сөзбен жазылуы:
Аргументтер: n, x1, x2,...,xn
Нәтижелер: R - сандардың ең үлкен мәні, m - ең үлкен санның реттік
нөмірі
Аралық шама: і
1. Басы
2. R:=x1; m:=1
3. і: =2
4. егер xі=R, онда 6-ға көшу
5. R:=xі; m: =і
6. і: =і+1
7. Егер і = n , онда 4-ке көшу
8. Соңы
Алгоритм циклдік болып табылады, тура есептегішпен басқарылады және R-
ге x1-ді, ал m-ге 1-ді меншіктеуден басталады. Циклдің есептегіші екінші
мәннен басталады, бірінші мән барлық сандар жиынының ішіндегі үлкені деп
есептелінеді. Бұл алгоритм n=2 болған жағдайда дұрыс жұмыс істейді. Мұнда
шарт n=2 болған жағдайда орындалды деп есептелінеді.
Сонымен, алгоритм құрылымы бойынша үш типке бөлінеді: сызықтық,
тармақталған және қайталану.
Алгоритмді орындаудағы негізгі мақсат – қандай да бір нәтиже алу.
Нәтижесі болмайтын есепті шешу алгоритмін құру мүмкін емес. Сондықтан әрбір
алгоритмді орындағанда міндетті түрде қандай да бір нәтиже алынуы тиіс.
Сонымен, алгоритмнің бірінші қасиеті – оның нәтижелілігі болып табылады.
Алгоритмдегі аргументтердің мәнін өзгерте отырып, әртүрлі нәтижелер
алуға болады. Бұдан құрылған алгоритмді бір типті есептер жиынтығы үшін
пайдалануға болатынын көреміз. Бұл алгоритмнің жалпылық қасиеті деп
аталады.
Алгоритмді орындау үшін алгоритмдегі аргументтер мен нәтижелер,
құрылымы, нұсқаулар мазмұны орындаушыға түсінікті болуы тиіс. Бұл
алгоритмнің түсініктілік қасиеті болып табылады.
Кез келген алгоритм шектеулі қадамдар тізбегі түрінде қарастырылады.
Оның орындалуы жеке қадамдардың орындалуымен қамтамасыз етіледі, кезекте
тұрған қадам алдындағы қадам орындалып біткеннен кейін орындалады. Осылайша
алгоритмдегі барлық қадамдар орындалады. Бұл алгоритмнің қадамының жинақы,
үздік болатынын көрсетеді және бұл оның дискреттілік қасиеті болып
саналады.
Алгоритмнің ықшамдылығы деп оның қысқалылығын, қадамдар санының аздығын
түсінеміз. Алгоритмнің ықшамдылығына n саннның қосындысын табу алгоримі
мысал болады. Бұл мысалда циклды қолдану арқылы алгоритм қадамы қысқарды.
Алгоритмнің тиімділігі оның ықшамдылығымен, алгоритмде міндетті түрде
жалпылық қасиетін сақтай отырып, есептеу мөлшерін барынша азайтумен
анықталады.
Алгоритмнің блок-схема түріндегі сипатталуы. Блок-схема деп алгоритмнің
бағытталған байланысы бар геометриялық фигуралармен сипатталып берілуін
айтамыз. Блок-схемада алгоритмнің басқарылуы жақсы көрінеді. Блок-схемада
пайдаланылатын геометриялық фигуралар символдар блогы, ал байланыстар
ағындар линиясы деп аталады. Әрбір блок-схеманың басы және соңы болады.
Оның шартты белгіленуі төмендегідей:
1-сурет
Енді 3-і мысалдағы n санының қосындысын тура есептегіш бойынша есептеу
алгоритмін блок схема түрінде көрсетейік.
Лекция №. Массивтер. Массив элементтерін іздеу және сұрыптау
алгоритмдері
Типтер қарапайым және күрделі болып бөлінеді.
Қарапайым типке – стандартты, саналатын, шектейтін типтер жатады.
Күрделі типке – массивтер, жиындар, жазулар, жолдар және файлдар жатады.
Күрделі типтің элементтері қарапайым немесе күрделі типтер болуы мүмкін.
Күрделі типті енгізу программаны күшейтеді және күрделі есептерді шешуге
мүмкіндік береді.
Тұрмыста тізбектелген сандарды, кестелерді, фамилия тізімдерін көп
пайдаланамыз, олар бір өлшемді (жатық немесе тік жол), екі өлшемді
(матрица) массив болуы немесе жиын болуы мүмкін.
Паскаль тілінде жеке айнымалыларды ғана өңдеп қоймай, айнымалылардың
жиынын (тобын) да өңдеуге болады.
Массив дегеніміз – бір типтегі берілгендер жиыны. Басқаша айтқанда,
массив – бір атауға біріктірілген айнымалылардың реттелген тізбегі.
Айнымалылардың - массив элементтерінің типтері бірдей болады. Массив бір
ғана атпен белгіленеді. Мысалы, нақты сандардан құрылған тізбекті R атаулы
массив деуге болады. Мысалы:
1.6, 14.9, -5.0, 8.5, 0.46 - ны бір өлшемді массив деп, оған А деп
атау беруге болады. Массивтің әр элементі массивтің атымен белгіленеді де,
оның индексі қойылады. Массив элементтері ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Тиімді, жылдам жұмыс істейтін алгоритмдер құрудың практикалық есептер
шығаруда бірінші дәрежелі болмаса да, үлкен мәні бар. Бірнеше
алгоритмдердің ішінен жылдам жұмыс істейтін алгоритмді таңдау үшін олардың
жұмыс уақытын салыстырып үйрену қажет. Дегенмен, жұмыс уақытын дәл есептеу
мүмкін емес. Бұл уақыт алдымен программа орындалатын компьютердің шынайы
сипаттамасына тәуелді болуы мүмкін. Әдетте алгоритмнің орындалуы уақыты тек
жуықтап қана есептеледі. Сонымен бірге жұмыс уақытына арналған формула
мәндері тек тәжірибелік жолмен анықталатын қандай да бір сандық
тұрақтылардан тұрады. Мұндай бағалаудың өзі көбінесе ең тиімді бір
алгоритмді ғана таңдауға мүмкіндік береді. Басқа жағдайларда жұмыс уақытын
бағалаудың көмегімен баяу жұмыс істейтін алгоритмдерді шығарып тастауға
болады, ал қалғандарынан программаның шынайы жұмыс уақытын өлшеудің
көмегімен таңдауға болады.
Енді жоғарыда айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да
бір n саннан құрылған тізбекті өңдеу қажет болсын. Мұндағы n өзгеріп
отыратын болсын. Осы есепті шығаруға екі программа берілсін, олардың жұмыс
уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- тұрақтылар, олар n-ге
тәуелсіз. N үлкен болған жағдайда бірінші программа жылдам жұмыс істейді,
ал n аз шама болғанда программа баяу жұмыс істейді. Бұл С1 С2 екенін
көрсетеді. С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n мен
C2n2-ты салыстыра отырып, n5 болғандағы программаның жұмыс уақытының
баяу, ал n5 болғанда екінші программаның жылдам жұмыс істейтінін байқауға
болады. Мұндағы n =5 бағалау уақытының шектік мәні де жуықтап
тағайындалады.
Бұдан екі тұжырым жасауға болады. Біріншіден, тұрақтыға дейінгі
дәлдікпен жуықтап бағалаудың өзі алгоритмдерді салыстыруда пайдалы болып
табылады. Екініден, есеп шығарудың бір алгоритмі өте жылдам деп айтуға
болмайды. Қандай да бір алғашқы мәліметтер жиынтығы үшін кейбір алгоритм
екіншісінен тиімді болуы мүмкін.
Енді программаның жұмыс уақытын анықтайтын алғашқы мәліметтердің мұндай
сипаттамасын таңдау мәселесіне тоқталайық. Мұндай сипаттама есептің өлшемі
деп аталады. Әртүрлі есептерді шығару уақытына алғашқы мәліметтердің
әртүрлі қасиеті әсер етеді. Мысалы, минимумды іздеу немесе әрбір сан бір
бүтін сан ретінде қарастырылатын берілген сандарды іріктеу типті есептер
үшін алғашқы сандар мөлшері есептер мөлшері болып табылады. Қарапайым
көбейткіштерге жіктеу есебі үшін санның шамасы мөлшері болып есептеледі.
Есеептің мөлшерін таңдау қандай да бір шығару алгоритмі туралы жалпы ұғымға
негізделеді. 2n дәрежесін есептеу алгоритмін қарастырайық. Дәрежелеудің
санның бірінен соң бірі көбейтілетінін ескере отырып, өлшем ретінде n
дәреже көрсеткішті аламыз. Өлшемді сипаттаудың тағы бір тәсілі нәтижедегі
цифр сан ыболып табылады. 2n дәрежесіндегі цифр саны n-ге пропорционал,
сондықтан екі өлшем де эквивалентті.
Жұмыс уақытын бағалау мезетіндегі маңызды кезең – орындалу барысында
барлық жұмыс уақытының негізгі бөлігін алатын программа бөлігін іздеу болып
табылады. Көптеген программалар үшін экспериментті түрде дәлелденген факт:
жұмыс уақытының негізгі бөлігі программа мәтінінің шағын бөлігін орындауға
кетеді. Программаның мұндай бөлігі цикл деп аталады. Көпшілік жағдайда
жұмыс уақытын жуықтап бағалау талап етіледі, сондықтан программаның қалған
бөлігінің орындалу уақытын ескермеуге болады, тек ішкі циклдың орындалуын
қарастыруға болады.
Егер программа бірінің ішіне бірі орналасқан бірнеше программадан
тұратын болса, онда ішкі циклды табу жеңіл. Әрине, алдымен, бәрінен бұрын
барлық циклға қатысты программа бөлігі орындалады, ал бұл қалған барлық
циклдардың ішіндегі және ішінде басқа цикл болмайтын циклдар болып
табылады. Бұл бақылау программаның жиі орындалатын бөлігі үшін ішкі цикл
деген атауды дәлелдей түседі.
Егер ішкі циклды қамтымайтын бірнеше цикл болса, олардың әрқайсысының
қайталану санын есептеуге болады. Егер бір циклдың қайталану саны
басқаларымен салыстырғанда айтарлықтай үлкен болатын болса, онда басқа
циклдардың жұмыс уақытын ескермеуге болады; кері жағдайда соңғы формулада
жұмыс уақыты үшін бірнеше циклдардың орындалу уақытын ескеруге тура келеді.
Параметрлі қайталану командасындағы қайталану саны For операторы үшін
төмендегі формуламен есептеледі:
Циклдың басы For i:=A to B
Егер B=A-1 болса, онда қайталану саны B - A +1 –ге тең;
Егер BA болса, онда нөлге тең;
(1)
For i:=A downto B циклі үшін А мен В-ның орындарын ауыстыру қажет.
Егер программада цикл бір рет орындалатын болса, онда бұл формула
ақиқат болып есептеледі. Енді бұл циклдың басқа циклдың ішінде бірнеше рет
қайталанып орындалған жағдайын қарастырайық. Цикл ішіндегі қайталану санын
шартты түрде цикл денесінің орындалу санының саны деп атайық. Барлық
циклдың орындалу санын цикл тақырыбының орындалу саны деп атайық. Сөйтіп,
цикл тақырыбының бір рет орындалуы цикл денесінің қанша рет орындалатынын
көрсетеді. Бірінші формула оның тақырыбы цикл денесінің бір рет
орындалуындағы цикл денесінің орындалу санын береді. Егер қарастырылып
отырған цикл басқа циклдың ішінде орналасқан болса, онда онда оның тақырыбы
бірнеше рет орындалады да, цикл денесінің орындалуының жалпы санын табу
үшін осы цикл тақырыбының барлық орындалуы барысындағы (1) формуламен
алынған сандарды қосу қажет.
Бұл формуланы қолданудың қарапайым мысалы ретінде төмендегі программа
фрагментін талдайық:
For j:=1 to n do
Begin (*1-цикл *)
For k:=1 to M do (* 2-цикл денесі*)
For l:=n downto j do (* 3-цикл денесі*)
End;
Екінші және үшінші цикл денелерінде ішкі цикл жоқ, ал, M және N –
қандай да бір үлкен тұрақтылар. 2 және 3-циклдардың қайталану санын
бағалайық. Екеуі де бірінші циклдың ішінде орналасқан, олардың қай талану
саны (1) формула бойынша оңай есептеледі; ол N-1+1=N-ге тең. Бұл
қайталанулардың әрқайсысында 2-цикл денесі М-1+1=М рет орындалады. М саны
тұрақты болғандықтан 2-цикл денесінің жалпы орындалу саны N2= N∙М тең. 3-
цикл денесі 1-цикл денесінің әрбір орындалуында N-J+1 рет орындалады. Бұл
санның М санынан айырмашылығы 1-циклдың орындалуы барысында өзгеріп
отырады; сондықтан екі санды тек көбейте салуға болмайды:3-цикл денесінің
барлық орындалу санын қосу қажет. Бұдан 1-циклдың орындалуында J айнымалысы
1-ден N-ге дейінгі барлық мәндерді қабылдайды (міне дәл осы 1-цикл
тақырыбында жазылған. Сөйтіп, 3-цикл денесінің жалпы орындалу саны:
Бұл арифметикалық прогрессияны ңқосындысы; ол (N+1) ∙ N2 тең. Уақыт
жуықтап есептелінетіндіктен N-мен салыстыруға жүгібей-ақ, формуланы
жеңілдетуге болады: N3 жуықтап N22 тең. N2 мен N3-ті салыстыра отырып, бұл
сандардың біреуі екіншісінен әлдеқайда артық деп айта алмаймыз. Керісінше,
қандай да бір N мен М үшін олар бір ретте болады. Мысалы, егер М= N, онда
N2 шамамен N3-тен 2 есе үлкен болады. Сондықтан жұмыс уақыты үшін формулаға
екі циклға да жауап беретін екі қосылғыш қосуға тура келеді. Цикл
денелерінің бір реттік орындалу уақытын есептей отырып, тұрақтыларды Т2
және Т3 арқылы белгілеп, жалпы жұмыс уақытын есептеу үшін төмендегідей
жуықтатылған формуланы аламыз:
Т =М∙N∙Т2+(N22) ∙Т3.
Егер цикл денелерінің орындалу уақытын тұрақты деп есептемейтін болса
(мысалы, онда шартты оператор немесе процедураны шақыру болса), онда
алдымен денелердің орындалу уақытын талдап, одан кейін оларды қосу қажет.
Жұмыс уақыты жөнінде бұдан да дәл ақпаратты әртүрлі алғашқы мәліметтер
бойынша программа программа жұмысының шынайы уақытын өлшеу нәтижесі бойынша
алуға болады. Бұл эксперименттердің көмегімен формулаға кіретін белгісіз
тұрақтыларды (біздің жағдайда Т2 және Т3) бағалауға болады.
Енді нақты программа жұмысын талдауға көшейік, 2N дәрежесін есептеуді
қарастырайық. Программа жұмысы циклды қамтитын екі ірі бөліктен тұрады. Ол
2N дәрежесін есептеу және баспаға шығару. Программаның жұмыс уақытын
бағалауда әдетте, баспаға шығару уақытын емес, тек есептеуге кететін уақыт
ескеріледі. Бұл көптеген есепті шығару алгоритмі үшін басу уақыты өте аз
болғандықтан ескерілмейді. Сонымен қатар, өте үлкен N үшін есептеу уақыты
аз болғандықтан ескермеуге де болады. Басып шығаруды және циклған
кірмейтіндерді шығарып тастағаннан кейін төмендегідей программма аламыз:
For K:=1 To N Do Begin (*1-цикл*)
For I:=еңҮлкенҰзындық DownTo XБасы Do Begin
(*2-цикл *)
Құрамында циклы жоқ әрекеттер
End;
Құрамында циклы жоқ әрекеттер
End;
Бір цикл, дәлірек айтсақ, 2-циклға басқа цикл кірмейді.Ол ішкі цикл
болып қалады. Енді оның денесінің қайталану санын есептейік. 2-цикл
денесінің орындалу саны МАХұзындық-Хбасы+1-ге тең, жұмыс барысында ХБасы
мәнінің өзгеруінің есебінен өзгереді. Мұнда ХБасы мәнінің 1-циклды
басқаратын К мәніне қаншалықты тәуелді екенін біз білмейміз. 2-цикл
денесінің орындалу санын N2(К) арқылы белгілей отырып, төмендегідей
қосындыны есептеу қажеттілігіне көз жеткіземіз:
N2(К) функциясын табу үшін алгоритмді мазмұны жағынан талдау қажет.
(1) формуланы тікелей қолдану ыңғайсыз. Мұның орнына 2-цикл тақырыбының
әрбір орындалуында оның денесінің орындалу саны екі еселенген цифрларының
санына тең екенін байқаймыз. Программа мәтінінен байқалғанындай екі
еселенген сан 2К-1 –не тең. Кез келген натурал санның цифрларының саны
оның ондық логарифмінің бір бүтін бөлігіне көбейтіндісіне тең, 2К-1 –нің
ондық логарифмі (К-1)*lg2-ге тең, мұндағы lg2 жуықтап 0,3-ке тең. Сөйтіп,
N2(К) үшін төмендегідей формуланы аламыз:
N2(К) = 1+[(K+1)Lg2].
Мұндайжалпы мүшесі бар қосындыны есептеу қиын. Есептеуді жеңілдету үшін
жуықтатылған санға көшеміз. Санның бүтін бөлігі өзінен 1-ге жуық
ажырыатылатынын байқаймыз. Бұл айырмашылықты ескермей, логарифмнің бүтін
бөлігіні логарфимнің өзімен алмастырамыз. Жалпы мүшесі 1+[(K+1)Lg2] болатын
арифметикалық прогрессияның қосындысын табу қажет. Қосынды төмендегі
формуламен есептеледі:
Соңғы шамаға көшу барысында N* Lg2-мен салыстырғанда шамасы кіші
болатын 2- Lg2 қосылғышын ескермедік. Сондай-ақ, қорытынды нәтижені де
бірден алуға болатын еді, егер і+(К-1) Lg2 шамасын К* Lg2-ге жуықтап
алмастырса, ал, арифметикалық прогрессияның қосындысын табуға арналған
формулада прогрессияның алғашқы мүшесін алмауға болады. Барлық бұл
ауыстырулардың қателігі бір ретті және жуықтап қорытынды нәтиженің 1N
бөлігін құрайды.
Сөйтіп, 2-циклдың орындалуының қорытынды уақыты барлық программа
бойынша есептеудің негізгі бөлігін құрайды, ол:
N2∙ Lg22∙Т2≈0,15∙N2∙Т2 тең.
Мұндағы Т2-цикл денесінің бір рет орындалу уақыты.
Сөйтіп, біз 2N дәрежесін есептеу программасының жұмыс уақытын бағалауды
жүргіздік. Жұмыс уақытын бағалау барлық уақытта қажет және оны программаны
құру кезінде орындау қажет.
Енді WHILE-DO типті қайталану алгоритмінің жұмыс уақытын талдау мысалын
қарастырайық. Бүтін санды натурал санға дәрежелеу функциясының жұмыс
уақытын талдайық. Мұны есептеу функциясының мәтінеі төмендегідей:
Function Dareje (M,N:integer):integer;
{М – дәреженің негізі, N – дәреже көрсеткіш}
Var M1,N1,P:integer; {Р –нәтижені есептейтін айнымалы}
Begin
P:=1; M1:=M; N1:=N;
WHILE N10 do {сыртқы цикл}
Begin
WHILE N1 mod 2 =0 do
Begin {ішкі цикл}
N1:=N1 div 2; M1:=M1*M1;
{N1 дәрежелі М1-дің мәні өзгерген жоқ}
End; {ішкі циклдың соңы}{}
N1:=N1-1; P:=P*M1 {Нәтижеге N дәрежелі М меншіктеледі}
End; {Сыртқы циклдың соңы}
Dareje:=P;
END;
Есептің өлшемі қызметін N дәреже көрсеткішінің мәні атқарады. Уақыттың
негізгі бөлігі циклды орындауға кетеді. Дегенмен, ішкі циклды орындауға
кететін уақыт сыртқы циклды орындауға кететін уақыттан айтарлықтай көп
деген тұжырым жасауға болмайды, өйткені тақ N1 үшін ішкі цикл денес
іорындалмайды. Сыртқы цикл денесінің бір рет орындалу уақытын Т1, сыртқы
цикл денесінің орындалу санын К1 арқылы белгілейік. Ал, Т2 және К2 –
сәйкес ішкі циклдың сипаттамалары.Функцияның жалпы жұмыс уақыты Т(N)
жуықтап Т(N) = Т1 ∙ К1 + Т2 ∙ К2 тең. К1 мен К2-ні бағалау үшін N1-дің
кему процесін қадағалайық. Dareje функциясы N1-дің жұптығын, 2-ге
бөлінетіндігін тексеру операциясын қамтиды. Бұл алгоритмді талдау үшін N1-
дің мәнінің екілік санау жүйесіндегі жазылуын қарастыру қажет деген ойға
жетелейді. (А санының негізі b болатын позициялық санау жүйесіндегі аmam-
1...a1a0 цифрларымен жазылуы:
-ге тең.
B=2 болғанда 0 және 1 цифрлары арқылы жазылған санның екілі жүйедегі
жазылуын аламыз. Мысалы, екілік жүйедегі 1001 саны ондық жүйедегі 9 санының
жазылуы. К1 және К2-ні табу үшін N1 мәніндегі бір ең кіші екілік цифрды
өңдеу барысында ішкі және сыртқы циклдардың қанша рет орындалатынын есептеу
қажет. Мұнда үш түрлі жағдай қарастырылуы мүмкін.
1. N1=1. Ішкі цикл орындалмайды; ал сыртқы цикл бір рет орындалады; N1
0-ге дейін кеміп, циклдан шығады.
2. N11, N1 нөлмен аяқталады (яғни жұп). Ішкі цикл бір рет
орындалғаннан кейін N1 2-ге бөлінеді. Екілік жүйеде екіге бөлу ең кіші
цифрды шығарып тастағанмен бірдей. Сөйтіп, ең кіші нөлді өңдеу үшін ішкі
циклдың бір рет орындалуы жеткілікті.
3. N1≤1, N1 бірмен аяқталады (тақ). Ішкі цикл орындалмайды, сыртқы
циклда N1-ден 1-алып тастайды, яғни N1 жұп болып қалады. Сөйтіп, 2-жағдайға
келеміз. Ең кіші бірлікті өңдеу үшін ішкі және сыртқы циклдың бір реттен
орындалуы талап етіледі.
Бірінен соң бірі өңделіп, N1 цифрының барлық екілік цифрлары шығарылып
тасталынады. Сонымен, бастапқы N1= N жағдайды ескере отырып,
К1 = N-нің екілік жазылуындағы берліктер саны,
К2 = (N-нің екілік жазылуындағы цифрлар саны)-1
екенін аламыз.
N-нің екілік жазылуындағы цифрлар саны N-нің екілік логарифмінің бүтін
бөлігін 1-ге арттырғанмен бірдей, яғни
К2 = [log2N].
К2 үшін мұндай қарапайым формуланы жаза алмаймыз, сондықтан К1 –ді
жоғарыдан ғана бағалай аламыз. Бірліктер саны цифрлар санынан көп
болмайтыны белгілі,
К1 ≤1+[log2N].
Бұдан
Т(N) ≤ (1+[log2N]) ∙ Т1 + [log2N] ∙Т2 =( Т1 + Т2) ∙ [log2N] + Т1 .
Теңдік N екілік жүйеде тек 1-лермен жазылған жағдайда ғана теңдік
орындалады, яғни екінің дәрежесі 1-ге кем. N екілік жүйедегі жазылуында
бірліктер қаншалықты аз болса, онда Dareje функциясы соншалықты жылдам
жұмыс істейді. Егер N екінің дәрежесі болса, К1 минимумға жетеді, ал жалпы
уақыт
Т(N) = Т1 + log2N ∙Т2 .
Енді Dareje функциясын tyzusyzykty функциясымен салыстырып көрейік.
Function tyzusyzykty (M,N:integer):integer;
{М – дәреженің негізі, N – дәреже көрсеткіш}
Var M1,N1,P:integer; {Р –нәтижені есептейтін айнымалы}
Begin
P:=1; M1:=M; N1:=N;
WHILE N10 do
Begin
N1:=N1-1; P:=P* M1;
End;
Tyzusyzykty:=P;
END;
Бұл функцияның жұмыс уақытын ТС(N), ал циклдың бір рет орындалуын ТС1
арқылы белгілейік.
ТС(N)≈ N · ТС1 болсын. N –мен салыстырғанда log2N баяу өсетіндіктен, N-
нің шамасы өте үлкен болған жағдайларда Т(N) ТС(N) болады, N-нің шамасы
артқан сайын жылдамдық та артады. Енді қаншасыншы N-нен бастап Dareje
функциясы жылдам жұмыс істейтінін қарастырайық.
Әрбір циклда негізгі уақыт көбейтуге кететіндіктен ТС1 ≈Т1 ≈Т2 деп
есептеуге болады. Бұдан,
Т(N)≤ ТС1 ·(2∙ [log2N]+1)
екені шығады. 2∙ [log2N]+1N теңсіздігін шеше отырып, N5 екенін табамыз. N-
нің шекаралық мәнін іздеуде T(N) үшін жоғарыдан бағалауды пайдаландық. N-
нің 1-ден 5-ке дейінгі мәндерін жеке зерттеуге болады. N=1,2,3 мәндері
үшін Dareje функциясы tyzusyzykty функциясы тәрізді көбейтуді орындайды, ал
N=4,5 мәндерінде көбейту аз орындалады. Бұл N-нің барлық мәндері үшін
Dareje функциясын пайдалануға болатынын көрсетеді.
Талдауды қорытындылайтын болсақ, егер FOR циклында қайталану саны
айнымалы болып, программада есептелсе онда, жұмыс уақытын бағалауға
формальды әдістерді қолдануға келмейді, программа жұмысын мазмұнды талдауды
талап етеді. Ал, While-Do және Repeat-Until қайталанулар одан да үлкен
қиындық әкеледі. Бұл қайталанулар үшін қайталанудың жалпы формуласын жазуға
келмейді. Бұдан барлық уақытта барлық қиындықтарды жеңіп, жұмыс уақытын
есептеудің жуықтатылған формуласын табу мүмкін бола бермейді. Алгоритмді
бағалауда кейде құрғақ ақпаратпен шектелуге тура келеді. Мұндай жағдай
барлық мүмкін болатын көбейткіштерді таңдауға негізделген санды қарапайым
көбейткіштерге жіктеу алгоритмінде орын алады. Сонымен бірге, сан жай сан
болса, таңдауды соңына дейін жүргізуге тура келеді, алдымен санның жай сан
екеніне көз жеткізу қажет. Бұл алгоритм үшін жұмыс уақытын жоғарыдан
бағалау міндеті қойылады, осындай TMAX(N) шамасы N өлшемді есеп үшін шынайы
жұмыс уақыты TMAX(N)-нан артпайды және кейде осы шаманың өзіне тең болады.
Жұмыс уақытын есептеуге арналған формуламен алгоритмді салыстырумен қатар,
өлшенген жұмыс уақытын басқа есептің өлшеміне экстрополяциялау үшін
пайдалануға болады. Мысалы, 210000 дәрежесін есептеу қажет болсын. Мұның
едәуір уақыт алатынын алдын-ала айтуға болады. Ол үшін 21000дәрежесін
есептеп, есептеу уақытын өлшейміз. Мысалы, ол 30 секундқа тең болсын. Онда
210000-ін есептеу 10*10=100 есе көп болады, 3000 секундты, яғни 50 минутты
құрайды. Бұл 210000 дәрежесін есептеу одан да жылдам алгоритм іздеуді талап
етеді.
Рекурентті тізбектерді өңдеу
U(1), ..., U(K) тізбегінің алғашқы К-сыншы мүшелері берілген болса, онда
U(1), U(2), ...,U(N) тізбегінің элементтері К ретті рекурентті тізбекті
құрайды делінеді, ал NК үшін
U(N)=F(U(N-1),...,U(N-K))
теңдеуi орындалады. Мұндағы Ғ – К аргументтің қандай да бір функциясы.
Екінші ретті пекуррентті тізбекті белгілі мысалы Фибоначчи сан тізбегі
болып табылады., оның
U(1)=U(2)=1, ал N2 үшін
U(N)=U(N-1)+U(N-2).
Бірінші ретті рекуррентті тізбектің мысалы – а санынан квадрат түбірді
Ньютон әдісі бойынша есептеуге арналған тізбек: U(1)=a+1, ал N1 үшін
U(N)=0.5*(U(N-1)+aU(N-1)).
Рекуррентті тізбектерге қатысты төмендегідей есептер қойылады.
1. Тізбектің N-ші элементін есептеу.
2. Берілген G(U(N), U(N-),...,U(N-K)) логикалық функциясының ең кіші
нөмірлі элементін есептеу.
Бұл екі есепті шығару үшін тізбектің К+1 элементін жадыда сақтау қажет.
К1=К+1. Онда К+1 элементті жадыға сақтауға арналған массив былай
сипатталады:
VAR T:ARRAY[1..k1] OF тізбектегі элементтер типі тізбектегі
есептелген элементтердің соңғысы T[K+1] элементінде сақталады.
Екі есепті шығаруда екі негізгі кезеңге бөлінеді:бастапқы шар және
тізбек бойынша орындау. Бастапқы шартты төмендегідей жазуға болады:
T[2]:=U(1);...;T[K+1]:=U(K);
Ал тізбек болйынша бір элементке алға қарай орындауда:
FOR I:=1 TO K DO T[I]:=T[I+1];
T[K+1]:=F(T[K],...,T[1]);
Т массивінің әрбір элементі біріншісінен бастап, мәнді келесі элменттен
бастап алады. Соңғы элементтен мәнін алғаннан кейін, F рекурренттік
формуласын қолдана отырып, жаңа мән қабылдайды. Келесі есептеуге әсер
етпейтіндіктен T[1]-дің ескі мәні қажет болмай қалады.
1 және 2-есептер тізбек бойынша болатын орын ауыстырулар қаншалықты
орындалатынымен ажыратылады. 1-есепте жылжу N-K-ға тең, өйткені T[K+1]
алғашқы шарттан кейін тізбектің К-элементін сақтайды, бірақ N-элементті
алу керек. Жылжуды қайталау үшін FOR қайталануын пайдаланған ыңғайлы:
FOR J:=K+1 TO N DO
BEGIN
FOR I:=1 TO K DO T[I]:=T[I+1];
T[K+1]:=F(T[K],...,T[1]);
{T[K+1]:=U(J)}
END;
{T[K+1]:=U(N)}
2-есепте G функциясының мәні ақиқат болған мезеттежылжуды аяқтау қажет.
Бұл жағдайда жылжуды қайталау үшін REPEAT-UNTIL қайталануын пайдаланған
ыңғайлы:
REPEAT
FOR I:=1 TO K DO T[I]:=T[I+1];
T[K+1]:=F(T[K],...,T[1]);
UNTIL G(T[K+1],...,T[1]);
1-есепті шығаруға мысал ретінде N-Фибоначчи санын есептеу функциясын
қарастырайық:
Function FIBONACHI_SANY (N:integer):integer;
{ N – ізделінді элементтің нөмірі,
ол N0 деп есептелінеді}
Var I,J:integer;
T:ARRAY[1..3] OF INTEGER;
Begin
{бастапқы шарт}
T2:=1; T3:=1
{жылжуды қайталау}
FOR J:=3 TO N DO
Begin
FOR I:=1 TO 2 DO
T[I]:=T[I+1];
T[3]:=T[2]+T[1];
END;
FIBONACHI_SANY:=T[3];
END;
Рекуррентті тізбек айтарлықтай үлкен болмаса, массивті пайдаланбай-ақ,
тізбек элементтері сақталған айнымалыларды жеке атаулармен бөліп көрсетуге
болады.Бұл жағдайда тізбек бойынша жылжуда FOR қайталануы К меншіктеулермен
алмастырылады. 2-есепті шығару мысалы ретінде А санынан берілген дәлдікпен
квадрат түбірді есептейтін функциянвы қарастырайық. ТЕК айнымалысы түбірге
ағымдағы жуықтатылған мәнді, ал АР айнымалысы алдыңғы мәнді сақтау үшін
пайдаланылсын.
ABS(U(N)-U(N-1))KATE
өрнегі G ретінде алынады.
Function KVADRAT_TUBIR (A,KATE:REAL):REAL;
{ A – Түбір алынатын сан,
KATE- қажеттті жуықтау дәлдігі}
Var TEK,AP:REAL;
{ТЕК – квадрат түбірге жуықтатылатын ағымдағы мән,
АР – алдыңғы жуықтау}
Begin
{бастапқы шарт}
TEK:=A+1;
{жылжуды қайталау}
REPEAT
AP:=TEK;
TEK:=0.5*(AP+AAP)
UNTIL ABS(TEK-AP)KATE;
KVADRAT_TUBIR:=TEK;
END;
Рекуррентті тізбекті анықтаубіршама жалпылауға мүмкіндік береді, егер
элементтерді нөмірлесе, оны 1-ден бастау міндет емес, F функциясының N-нен
тәуелділігін алуға болады. Мұндай тізбектермен жұмыс істеуде бастапқы нөмір
меншіктелетін бастапқы шартты қосу керек және әрбір жылжуда тізбек бойынша
нөмірді 1-ге арттырып отыру қажет. Мұндай жалпылаудан тек 2-цикл ғана
аздапкүрделенеді. Сол нөмірлі элементті есептеуде FOR циклы бәрін
орындайтындықтан 1-цикл өзгермейді.
Енді осы айтылғанды мысалмен түсіндірейік. Кейбір есептер рекуррентті
тізбектерді өңдеуге келтіріледі. С коэффициентпен берілген массивтегі М
дәрежелі көпмүшеліктің мәнін есептеу қажет болсын:
VAR C:ARRAY[0..M] OF REAL;
X айнымалысының мәнін берілген деп есептейміз. Көпмүшеліктің мәнін
есептеу үшін Горнер схемасы пайдаланылатыны белгілі. Көпмүшелікті мына
түрде жазуға болады:
(...(C[0]·X+C[1]) ·X+...+C[M-1]) ·X+C[M].
U(N) бірінші ретті рекуррентті тізбекті төмендегідей анықтайық:
U(0)=C[0],
U(N)=U(N-1) ·X+ C[N], 1≤N≤M
(бұл жағдайда тізбек элементтерін 0-ден бастап нөмірлеген ыңғайлы).
U(M) көпмүшеліктің мәні екенін көрсету қиын емес. Жоғарыда келтірілген
әдістемені U(M)-ді табу үшін қолданамыз. Бұл тізбек элементтерін нөмірі
бойынша есептеу есебі. Егер жалпы схема бойынша қарастырсақ, SAP және STEK
екі айнымалыларын енгізу керек және жылжуды төмендегідей жүргіземіз:
FOR J:=1 TOM DO BEGIN
SAP:=STEK;
STEK:=SAP*X+C[J];
END;
Мұнда SAP айнымалысының қажет емес екені көрінеді, өйткені STEK
айнымалысының жаңа мәнін есептеуде осы айнымалының алдыңғы мәнін
пайдалануға болады. Сөйтіп, элемент нөмірі бойынша бірінші ретті
рекуррентті тізбекті есептеуде бір айнымалыны пайдалану жеткілікті, нәтиже
сол айнымалыға меншіктеліп отырады. Берілген шартты қанағаттандыратын
тізбектің элементін есептеу есебі үшін де ақиқат болып табылады, егер G
функциясы тек U(N)-нен тәуелді болатын болса. Сондай-ақ, циклдың алдындағы
бастапқы шартты тізбектің бірінші элементі басқаларымен тең
есептелінетіндей етіп, ұйымдастыруға болады. Нәтижесінде төмендегідей
функцияны аламыз:
CONST M=...,
TYPE KOEF=ARRAY[0..M] OF REAL;
...
Function GORNER (VAR C:KOEF; X:REAL):REAL;
{ С коэффициентті массивпен, Х айнымалысының
мәні
берілген, бір айнымалыдан тәуелді
көпмүшеліктің мәнін
Горнер схемасы бойынша есептейтін функция}
Var S:REAL; J:INTEGER;
{ S айнымалысына көпмүшеліктің мәні есептеледі}
Begin S:=0;
FOR J:=1 TO M DO
S:=S*X+C[J];
GORNER:=S;
END;
Рекуррентті қатынастармен жұмыс істеу техникасы сондай-ақ, тізбектерді
өңдеу программаларын құруда, әсіресе, жалпы формула бойынша әрбір мүшені
есептемей, алдыңғының мәнін біле отырып, кезекті элементті алуда тиімді.
Қатардың қосындысын табу есебін қарастырайық.
1+11!+12!+...+1N!+...
(бұл е санын есептеуге арналған қатар). Қосындыны табуды кезекті
қосылғыш алдын-ала берілген КАТЕ шамасынан кіші болғанша жүргізу керек.
Әрине, әрбір N үшін N!-ды қайтадан есептеу керек. Қосындыны табу уақыты
C1m2 өрнегімен беріледі, мұндағы m - қатардың қосынды табылған мүшелерінің
саны. Егер N!=N·(N-1)! қатынасын пайдалансақ, есептеуді жеделдетуге болады.
Қатардың қосылғыштарын бірінші ретті рекуррентті тізбектің көмегімен
анықтауға болады:
U(0)=1, U(N)=U(N-1)N,N0.
Енді U(N)KATE шартын қанағаттандыратын тізбектің элементін табамыз.
Сонымен қатар, есетелгнен элементтерді қосамыз, сонда қосу уақыты C2m-ге
дейін азаяды:
Function CHISLO_E (KATE:REAL):REAL;
Var N:INTEGER; U,S:REAL;
{ N – қосылғыш нөмірі;
U – кезекті қосылғыш;
S – алғашқы N элементтің қосындысы}
Begin N:=0; U:=1; S:=U;
REPEAT
N:=N+1;
U:=UN; {U:=1N!}
S:=S+U;
{S=1+11!+...+1N!}
UNTIL UKATE;
CHISLO_E:=S;
END;
Қосынды берілген шартты қанағаттандыратын рекуррентті тізбектің
элементін есептеумен бірге жүргізіледі.
Сонымен, уақыттың көп бөлігін машина циклды, алдыңғы кезекте ішкі
циклды орындауға жұмсайды. Берілген қайталану саны бойынша циклды орындау
уақыты циклға кіретін әрекеттер санына тәуелді. Цикл қаншалықты қарапайым
болса, яғни әрекеттер саны қанша аз болса, соншалықты программа жылдам
орындалады. Сондықтан, программаның ішкі циклын жеңілдету шараларын қолдану
қажет.
Сонымен қатар, программаның жұмыс уақытына негізгі әсер ететін таңдалған
алгоритм болып табылады. Алдымен, есепті шығарудың мүмкін болатын
алгоритмдерін талдау қажет, оның ішінен ең жылдам орындалатын алгоритмін
таңдап, ондағы ішкі циклды анықтап, ішкі циклды жеңілдетуге әрекет жасау
қажет.
Лекция № Алгоритм ұғымы, қасиеттері. Жазылу тәсілдері
Есеп шығару алгоритмі деп есептің нәтижесін алуға бағытталған нақты
әрекеттер тізбегін атау қабылданған. Мұндағы есептің жауабы берілген
алғашқы мәліметтер бойынша бар немесе жоқ болуы мүмкін. Жалпы жағдайда,
есептер тек керекті ақпаратты алу ғана емес, әртүрлі болады. Мысалы, көше
қиылысынан светоформен өту, тағамдар дайындау есебі және т.с.с есептер.
Мұндай есептерді шығару алгоритмдерін тұрмвстық деп атайды. Шындығында,
адамның өмірі өмірлік тәжірибелер мен қоғамдық заңдылықтардан туындайтын
кешенді әрекеттер алгоритмімен сипатталады.
Алгоритмнің дәл, нақты математикалық анықтамасы жоқ, көптеген
оқулықтарда алгоритмнің анықтамасы жылдар бойы жинақталған түсініктермен
тұжырымдалады. Сонымен, алгоритм дегеніміз – алға қойылған мақсатқа жетуге
бағытталған (берілген есептің шешімін табу үшін), қандайда бір орындаушыға
арналған (адам немесе компьютер), орындалу тәртібі ұйымдастырылған
түсінікті, ықшамды, қадамдар саны шектелген нұсқаулар тізбегін түсінеміз.
Алгоритмді қандай да бір операндалармен жалпыланған операция ретінде
қарастырып, оны былай белгілеуге болады:
F(x1,x2,...,xn,y1,y2,...,ym) (1)
Мұндағы Ғ – осы операцияның шартты белгісі, x1,x2,...,xn – алғашқы
мәліметтер, біз оны алгоритмнің аргументтері деп атаймыз, y1,y2,...,ym –
операндалары алгоритмнің орындалу нәтижелерін белгілейді, бұл алгоритмнің
нәтижелері деп аталады.
Алгоритм ұғымы есепті шығару әдісі ұғымымен тығыз байланысты. Әдіс
алғашқы мәліметтер бойынша сол есепті қайда қолдануға болатынын, яғни
есептің класын анықтау мақсатында қатаң түрде негізделген және құрылған
тәсілмен зерттелген есепті шығару тәсілін жасау болып табылады.
Ал, алгоритм есепті шығару және оны практикалық қолдану әдісінің
сипатталуы болып табылады. Ол әдістің зерттелу нәтижесі бойынша құрылады.
Дәлірек айтсақ, алгоритм есепті шығаруға арналған әрекеттердің қатаң түрде
жазылған тізбегі болып табылады. Бұл әрекеттер есепті шығару әдісінен
шығады.
Алгоритмнің аса маңызды бір қасиеті атқарушыдан есепті шығару әдісін
түсіну талап етілмейді. Атқарушыдан өзіне арналып жазылған әрекеттерді
орындай білу іскерлігі мен жазылған инструкцияны (команданы) түсіну талап
етіледі. Сонымен, атқарушы инструкция-командаларды қадағалай отырып,
алгоритмді механикалық түрде орындайды.
Алгоритм белгілі бір атқарушыға, оның командалар жүйесіне арналып
жазылады. Ол адам, компьютер және т.б. құрылғылар болуы мүмкін. Алгоритмнің
жазылуы атқарушы түсіну үшін сол атқарушының тілінде жазылады.
Алгоритмдегі әрбір жеке нұсқау команда деп аталады немесе оны шартты түрде
алгоритм қадамы деп атаймыз. Сонымен, алгоритм дегеніміз реттелген
командалар тізбегі болып табылады. Атқарушының түсініп, орындайтын барлық
командалар жиынтығы атқарушының командалар жүйесі деп аталады. Сөйтіп,
атқарушының тілі дегеніміз атқарушының барлық әрекетін сипаттайтын
командалар жүйесі болып табылады.
Алгоритм барлық уақытта атқарушыға, оның командалар жүйесіне
бағытталады. Алгоритмді жазудың әртүрлі тәсілдері бар: формула, кесте,
сөзбен, графикалық, алгоритмдік тіл немесе программалау тілі. Алгоритмнің
графикалық түрде кескінделуі блок-схема деп аталады. Алгоритмнің
программалау тіліндегі жазылуын программа деп атаймыз. Ал, программалау
тілі дегеніміз алгоритмнің компьютер-атқарушыға арналып жазылған тілі болып
табылады. Программалау дегеніміз – программалау тілінде алгоритмнің жазылу
процесі.
Енді алгоритмнің сөзбен жазылуына тоқталайық. Алгоритмнің
орындалуындағы көшулерді көрсету үшін командалар нөмірленеді. Сондай-ақ,
алгоритмді жазуға пайдаланылатын қызметші сөздер, яғни қосымша командалар
пайдаланамыз: басы, соңы, тоқта. Мұндағы басы сөзі сәйкес алгоритмнің
басын көрсетеді; ал соңы сөзі егер алгоритмнің ары қарай орындалуы мүмкін
болмаса, аяқталуын көрсетеді; тоқта сөзі – алгоритмнің дұрыс аяқталмай,
яғни апатты аяқталуын көрсетеді.
Енді алгоритмнің сөзбен сипатталуына мысалдар келтірейік.
1-мысал. Квадрат түбірді итерациялық әдіспен есептеу. Есептің қойылысы:
нақты саны х берілген, егер түбір болса m–ге дейінгі дәлдікпен
функциясын есептеңіздер.
Алгоритмде жуықтап тізбек құрудың итерациялық әдісін пайдаланамыз:
Y0,y1,y2,...,yk,yk+1,... (2)
Ол алдын-ала e0 дәлдікпен берілген кез келген санмен X=0 болғанда
мәніне жинақталады.
Теңдеуді шығарудың жанама әдісінен К үшін (K=0,1,...) Y0=const0
болғандағы Геронның итерациялық процесі шығады:
(3)
Есептеу әдістерінде, егер түбір бар болатын болса, (2), (3) тізбектер
-тің дәл мәніне өте жылдам жинақталады. (3) теңдеудің әрбір қолданылуы
алдыңғы жуықтаудың дәл мәндерінің мөлшерін жуықтап екі еселейді.
Бұл процесс
(4)
теңсіздігі орындалғанда аяқталады, ол абсолюттік қателікті жоғарыдан
бағалау болып табылады.
(2), (3) итерациялық процестерді
, (5)
формуласы бойынша енгізу ыңғайлы. Мұндағы dYk – алдыңғы жуықтауға түзету.
Егер
(6)
шарты қанағаттандырылатын болса, итерациялық процесті тоқтатуға болады. Бұл
түзету талап етілген дәлдіктен төмен екенін көрсетеді.
(2) мен (5) аралығындағы итерациялық процесс өте қарапайым жүргізіледі:
алдымен dYk, одан кейін Yk+1 есептеліп, Е-мен салыстырылады.
(3) теңдеуден dYk-ны есептеу формуласын қорытып шығарайық:
Бұдан
(7)
Бұл қайта құрылған итерациялық процесті Y0=1, (7), (5) түбірді жуықтап
есептеу алгоритміне пайдаланамыз, бірақ жуықтауды бағалауды салыстырмалы
қателік бойынша жүргіземіз.
(8)
Бұл алынған түбірді жуықтап есептеудің m ақиқат белгісін қамтамасыз
етеді.
Алгоритмдегі аргументтер X, m, нәтиже Y. Түзету үшін d, салыстырмалы
қателікті бағалау үшін Е айнымалыларын пайдаланамыз.
Бұл алгоритмнің сөзбен жазылуы төмендегідей:
Аргументтер: X, m
Нәтиже: У
Аралық шама: d, Е
1. Басы
2. егер Х0 болса, онда 4-ге көшу
3. Тоқта, яғни түбір жоқ
4.
5. Y:=1
6.
7. Y:=Y+d
8. Егер , онда 5-ға көшу
9. Соңы.
2-мысал. Формула бойынша есептеу алгоритмі. Есептің қойылысы:
Х=с(а- b) - мәнін есептеңіз.
Енді осы алгоритмнің сөзбен жаызлуын келтірейік.
Аргументтер: a, b, с.
Нәтиже: х
Аралық шамалар: Q, P.
0. Басы
1. Q:= aҺb
2. Р:= a-b
3. Р:=РҺс
4. Х:=Р- Q
5. Соңы
3-мысал. Сандардың қосындысын есептеу. Есептің қойылысы: сандар
берілген, олардың қосындысын табу қажет.
Алдымен белгілеулер енгіземіз: n - сандар мөлшері, x1, x2,...,xn –
берілген сандар, S – нәтиже.
Сандардың қосындысын есептеу үшін сызықтық алгоритмді пайдалануға болар
еді.
1. Басы
2. S:=x1
3. S:=S+x2
...
N S:=S+xn
4. Соңы
Бірақ мұндай алгоритмдегі қадамдар саны өте көп. Егер n=1000 болса,
1002 команда жазуға тура келеді. Мұндай келеңсіздіктен құтылу үшін циклдық
алгоритм құрамыз. Ол үшін циклдың қайталану шартын қосылған сандар
мөлшерінің есептегішімен байланыстырамыз және қосылатын сандар индексін
–көрсеткішін енгіземіз. Индекстің мәні айнымалының реттік нөмірі болып
табылады, индекс үшін і айнымалысын енгіземіз. Нәтиже S айнымалысына
меншіктеледі, яғни нәтижеге әрбір кезекті сан қосылып отырады. Нәтиже
сақталатын S айнымалысының бастапқы мәні 0-ге, ал і қайталану параметрінің
бастапқы мәнін 1-ге тең деп аламыз. і:=і+1 индекстің өзгерісімен, і n-нен
артқанша алгоритмдегі негізгі операция S:=S+xі орындала береді. Бұл
жағдайда і индексі қосылған сандар мөлшерін есептейтін есептегіштің ролін
атқарып тұр. Есептегіштің мәні артып отыр, сондықтан ол тура есептегіш деп
аталады.
Сонымен қатар, сандарды қосуды кері есептегішпен де жүргізуге болады,
бұл жағдайда алдымен і= n деп аламыз да, әрбір қайталануда і-дің мәнін 1-
ге азайтып отырамыз: і:=і-1. Бұл жағдайда қайталану і0 болғанша қайталана
береді.
А) Берілген n санның қосындысын тура есептегіш бойынша есептеу
алгоритмі.
Аргументтер: n, x1, x2,...,xn
Нәтиже: S
Аралық шама: і
1. Басы
2. S:=0
3. і: = 1
4. S:=S+xі
5. і:=і+1
6. Егер і=n болса, онда 4-ке көшу
7. Соңы
ә) Берілген n санның қосындысын кері есептегіш бойынша есептеу
алгоритмі.
Аргументтер: n, x1, x2,...,xn
Нәтиже: S
Аралық шама: і
1. Басы
2. S:=0
3. і: = n
4. S:=S+xі
5. і:=і-1
6. Егер іn болса, онда 4-ке көшу
7. Соңы
4-мысал. Берілген n санның ішінен ең үлкенін табу алгоритмі. Есептің
қойылысы n саны берілген. Олардың ішіндегі ең үлкенін және оның реттік
нөмірін анықтаңдар.
Алгоритмнің сөзбен жазылуы:
Аргументтер: n, x1, x2,...,xn
Нәтижелер: R - сандардың ең үлкен мәні, m - ең үлкен санның реттік
нөмірі
Аралық шама: і
1. Басы
2. R:=x1; m:=1
3. і: =2
4. егер xі=R, онда 6-ға көшу
5. R:=xі; m: =і
6. і: =і+1
7. Егер і = n , онда 4-ке көшу
8. Соңы
Алгоритм циклдік болып табылады, тура есептегішпен басқарылады және R-
ге x1-ді, ал m-ге 1-ді меншіктеуден басталады. Циклдің есептегіші екінші
мәннен басталады, бірінші мән барлық сандар жиынының ішіндегі үлкені деп
есептелінеді. Бұл алгоритм n=2 болған жағдайда дұрыс жұмыс істейді. Мұнда
шарт n=2 болған жағдайда орындалды деп есептелінеді.
Сонымен, алгоритм құрылымы бойынша үш типке бөлінеді: сызықтық,
тармақталған және қайталану.
Алгоритмді орындаудағы негізгі мақсат – қандай да бір нәтиже алу.
Нәтижесі болмайтын есепті шешу алгоритмін құру мүмкін емес. Сондықтан әрбір
алгоритмді орындағанда міндетті түрде қандай да бір нәтиже алынуы тиіс.
Сонымен, алгоритмнің бірінші қасиеті – оның нәтижелілігі болып табылады.
Алгоритмдегі аргументтердің мәнін өзгерте отырып, әртүрлі нәтижелер
алуға болады. Бұдан құрылған алгоритмді бір типті есептер жиынтығы үшін
пайдалануға болатынын көреміз. Бұл алгоритмнің жалпылық қасиеті деп
аталады.
Алгоритмді орындау үшін алгоритмдегі аргументтер мен нәтижелер,
құрылымы, нұсқаулар мазмұны орындаушыға түсінікті болуы тиіс. Бұл
алгоритмнің түсініктілік қасиеті болып табылады.
Кез келген алгоритм шектеулі қадамдар тізбегі түрінде қарастырылады.
Оның орындалуы жеке қадамдардың орындалуымен қамтамасыз етіледі, кезекте
тұрған қадам алдындағы қадам орындалып біткеннен кейін орындалады. Осылайша
алгоритмдегі барлық қадамдар орындалады. Бұл алгоритмнің қадамының жинақы,
үздік болатынын көрсетеді және бұл оның дискреттілік қасиеті болып
саналады.
Алгоритмнің ықшамдылығы деп оның қысқалылығын, қадамдар санының аздығын
түсінеміз. Алгоритмнің ықшамдылығына n саннның қосындысын табу алгоримі
мысал болады. Бұл мысалда циклды қолдану арқылы алгоритм қадамы қысқарды.
Алгоритмнің тиімділігі оның ықшамдылығымен, алгоритмде міндетті түрде
жалпылық қасиетін сақтай отырып, есептеу мөлшерін барынша азайтумен
анықталады.
Алгоритмнің блок-схема түріндегі сипатталуы. Блок-схема деп алгоритмнің
бағытталған байланысы бар геометриялық фигуралармен сипатталып берілуін
айтамыз. Блок-схемада алгоритмнің басқарылуы жақсы көрінеді. Блок-схемада
пайдаланылатын геометриялық фигуралар символдар блогы, ал байланыстар
ағындар линиясы деп аталады. Әрбір блок-схеманың басы және соңы болады.
Оның шартты белгіленуі төмендегідей:
1-сурет
Енді 3-і мысалдағы n санының қосындысын тура есептегіш бойынша есептеу
алгоритмін блок схема түрінде көрсетейік.
Лекция №. Массивтер. Массив элементтерін іздеу және сұрыптау
алгоритмдері
Типтер қарапайым және күрделі болып бөлінеді.
Қарапайым типке – стандартты, саналатын, шектейтін типтер жатады.
Күрделі типке – массивтер, жиындар, жазулар, жолдар және файлдар жатады.
Күрделі типтің элементтері қарапайым немесе күрделі типтер болуы мүмкін.
Күрделі типті енгізу программаны күшейтеді және күрделі есептерді шешуге
мүмкіндік береді.
Тұрмыста тізбектелген сандарды, кестелерді, фамилия тізімдерін көп
пайдаланамыз, олар бір өлшемді (жатық немесе тік жол), екі өлшемді
(матрица) массив болуы немесе жиын болуы мүмкін.
Паскаль тілінде жеке айнымалыларды ғана өңдеп қоймай, айнымалылардың
жиынын (тобын) да өңдеуге болады.
Массив дегеніміз – бір типтегі берілгендер жиыны. Басқаша айтқанда,
массив – бір атауға біріктірілген айнымалылардың реттелген тізбегі.
Айнымалылардың - массив элементтерінің типтері бірдей болады. Массив бір
ғана атпен белгіленеді. Мысалы, нақты сандардан құрылған тізбекті R атаулы
массив деуге болады. Мысалы:
1.6, 14.9, -5.0, 8.5, 0.46 - ны бір өлшемді массив деп, оған А деп
атау беруге болады. Массивтің әр элементі массивтің атымен белгіленеді де,
оның индексі қойылады. Массив элементтері ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz