Дәріс 15. Теориялық сандық алгоритмдер. Евклид алгоритмі.

Мұ нда N мұ шелерден тұ ратын, оның ә рбірі бір элементтен тұ ратын алғ ашқ ы кө пмү шелікті қ арастырамыз. Сұ рыптау бір элементтен тұ ратын алдаң ғ ы кө пмү шеліктен басталады. Аралас кө пмү шеліктер қ ос-қ остап бірігіп, 2 элементтен тұ ратын кө пмү шелікті шығ арады, бұ л бір сұ рыптанғ ан кө пмү шелік пайда болғ анда осылай айталана береді. Кө пмү шеліктің саны ә рбір сұ рыптаудың қ адамында екіге кемиді, ал ө лшемі артады. Тө менде тізбектеліп біріккен сұ рыптауғ а мысал келтірілген. Бұ л мысалда ә рбір кезенде қ ос араласқ ан кө пмү шеліктердің келесісі сұ рыпталады жә не де бір массивтен екінші массивке қ айта жіберіледі. Алғ ашқ ы кө пмү шелік А массивінде орналасқ ан. Сұ рыптау процессінде деректер В массивке жіберіледі. Осындай кейін қ айтадан А массивіне. Осылай қ айталана береді.

Тізбектеліп бірігетін сұ рыптау ә дісіндегі кезендер мен қ айта жіберу саны:

k=ББЦ(log₂ N),

мұ нда ББЦ – жақ ын ү лкен сан, N – кө пмү шеліктер элементтер саны.

Енді осы ә дісті файлдарғ а қ арастырайық. Біз жаң а сериясы ұ лғ айып отыратын файлды қ ұ рамыз, яғ ни r₁, …, r_k тізімделген жазулар, мұ нда r_і кілт r_і+1 кілттен аспайды, Файл r₁, …, r_m жазбалардан қ ұ рылғ ан ұ зындығ ы k серияғ а бө лінеді, егер барлық і> 0 дерге жә не r_k(i-1)+1, r_k(i-1)+2, …, r_{k i} ұ зындығ ы k болатын тізім. Егер m толық k-ғ а бө лінбесе, яғ ни m=pr+q, мұ нда q< k, онда жазбалар тізімі соң ы деп аталады, оның сериясының ұ зындығ ы q болады.