Ќазаќ мемлекеттік ќыздар педагогика институты
жүктеу/скачать 1,32 Mb.
|
аза стан Республикасыны Білім ж не ылым министрлігі аза мем
| Құрамында циклы жоқ әрекеттер
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-ге жуықтап алмастырса, ал, арифметикалық прогрессияның қосындысын табуға арналған формулада прогрессияның алғашқы мүшесін алмауға болады. Барлық бұл ауыстырулардың қателігі бір ретті және жуықтап қорытынды нәтиженің 1/N бөлігін құрайды. Сөйтіп, 2-циклдың орындалуының қорытынды уақыты барлық программа бойынша есептеудің негізгі бөлігін құрайды, ол: N2∙ Lg2/2∙Т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 N1<>0 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. N1>1, 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 N1<>0 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]+1 Талдауды қорытындылайтын болсақ, егер FOR циклында қайталану саны айнымалы болып, программада есептелсе онда, жұмыс уақытын бағалауға формальды әдістерді қолдануға келмейді, программа жұмысын мазмұнды талдауды талап етеді. Ал, While-Do және Repeat-Until қайталанулар одан да үлкен қиындық әкеледі. Бұл қайталанулар үшін қайталанудың жалпы формуласын жазуға келмейді. Бұдан барлық уақытта барлық қиындықтарды жеңіп, жұмыс уақытын есептеудің жуықтатылған формуласын табу мүмкін бола бермейді. Алгоритмді бағалауда кейде құрғақ ақпаратпен шектелуге тура келеді. Мұндай жағдай барлық мүмкін болатын көбейткіштерді таңдауға негізделген санды қарапайым көбейткіштерге жіктеу алгоритмінде орын алады. Сонымен бірге, сан жай сан болса, таңдауды соңына дейін жүргізуге тура келеді, алдымен санның жай сан екеніне көз жеткізу қажет. Бұл алгоритм үшін жұмыс уақытын жоғарыдан бағалау міндеті қойылады, осындай TMAX(N) шамасы N өлшемді есеп үшін шынайы жұмыс уақыты TMAX(N)-нан артпайды және кейде осы шаманың өзіне тең болады. Жұмыс уақытын есептеуге арналған формуламен алгоритмді салыстырумен қатар, өлшенген жұмыс уақытын басқа есептің өлшеміне экстрополяциялау үшін пайдалануға болады. Мысалы, 210000 дәрежесін есептеу қажет болсын. Мұның едәуір уақыт алатынын алдын-ала айтуға болады. Ол үшін 21000дәрежесін есептеп, есептеу уақытын өлшейміз. Мысалы, ол 30 секундқа тең болсын. Онда 210000-ін есептеу 10*10=100 есе көп болады, 3000 секундты, яғни 50 минутты құрайды. Бұл 210000 дәрежесін есептеу одан да жылдам алгоритм іздеуді талап етеді. жүктеу/скачать 1,32 Mb. Достарыңызбен бөлісу:
|