Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Дәріс 15. Теориялық сандық алгоритмдер. Евклид алгоритмі.⇐ ПредыдущаяСтр 11 из 11
Мұ нда N мұ шелерден тұ ратын, оның ә рбірі бір элементтен тұ ратын алғ ашқ ы кө пмү шелікті қ арастырамыз. Сұ рыптау бір элементтен тұ ратын алдаң ғ ы кө пмү шеліктен басталады. Аралас кө пмү шеліктер қ ос-қ остап бірігіп, 2 элементтен тұ ратын кө пмү шелікті шығ арады, бұ л бір сұ рыптанғ ан кө пмү шелік пайда болғ анда осылай айталана береді. Кө пмү шеліктің саны ә рбір сұ рыптаудың қ адамында екіге кемиді, ал ө лшемі артады. Тө менде тізбектеліп біріккен сұ рыптауғ а мысал келтірілген. Бұ л мысалда ә рбір кезенде қ ос араласқ ан кө пмү шеліктердің келесісі сұ рыпталады жә не де бір массивтен екінші массивке қ айта жіберіледі. Алғ ашқ ы кө пмү шелік А массивінде орналасқ ан. Сұ рыптау процессінде деректер В массивке жіберіледі. Осындай кейін қ айтадан А массивіне. Осылай қ айталана береді.
Тізбектеліп бірігетін сұ рыптау ә дісіндегі кезендер мен қ айта жіберу саны: k=ББЦ(log2 N), мұ нда ББЦ – жақ ын ү лкен сан, N – кө пмү шеліктер элементтер саны. Енді осы ә дісті файлдарғ а қ арастырайық. Біз жаң а сериясы ұ лғ айып отыратын файлды қ ұ рамыз, яғ ни r1, …, rk тізімделген жазулар, мұ нда rі кілт rі+1 кілттен аспайды, Файл r1, …, rm жазбалардан қ ұ рылғ ан ұ зындығ ы k серияғ а бө лінеді, егер барлық і> 0 дерге жә не rk(i-1)+1, rk(i-1)+2, …, rk i ұ зындығ ы k болатын тізім. Егер m толық k-ғ а бө лінбесе, яғ ни m=pr+q, мұ нда q< k, онда жазбалар тізімі соң ы деп аталады, оның сериясының ұ зындығ ы q болады.
|