Nələrdən danışacayıq?

6 else b = b % a

7 }

8 return a + b;

9 }

Evklid alqoritmi(çıxmaya görə(I)):

Evklid alqoritmi(I) iki natural ədədin ən böyük ortaq bölənin (ƏBOB-un) hesablanması üçün nəzərdə tutulmuşdur. Orijinal Evklid alqoritmi aşağıdakı bərabərliyə əsaslanır:

ƏBOB(a, b) = ƏBOB(a - b, b) = ƏBOB(a, b - a)

Mənfi ədədlərlə işləməmək üçün alqoritmi aşağıdakı kimi ifadə etmək olar:

İki ədədin ən böyüyünü böyük və kiçik ədədlərin fərqi ilə əvəz edirik. Bu proseduru iki ədədin bir-birinə bərabər olanına kimi aparırıq. Nəticədə alınmış ədəd ƏBOB-dur.

Evklid alqoritmi(bölməyə görə(II)):

Ədədlər bir-birindən çox fərqlənəndə birinci Evklid alqoritmi(I) yavaş işləyir (məsələn, ƏBOB(2, 1998) hesablanması üçün 998 addım lazım olacaq). Buna görə də, adətən Evklid alqoritmi(II)-dən istifadə edilir. Bu alqoritm isə aşağıdakı bərabərliyə istinad edir:

ƏBOB(a, b) = ƏBOB(a % b, b) = ƏBOB(a, b % a)

İki ədədin ən böyüyünü böyük ədədin kiçik ədədə bölmə qalığı ilə əvəz edirik. Bu proseduru kiçik ədədin sıfıra bərabər olunana kimi aparırıq. Nəticədə alınmış ikinci ədəd ƏBOB-dur.

Palindrom

Palindrom – tərsinə oxunuşu da eyni olan cümlə, söz və ədədlərə deyilir. Yunan dilindəki "palindromon" sözündəndir, mənası "geri çevrilən / tərsinə dönən", "arxası-önü olmayan" deməkdir.

n rəqəmli bir cüt ədədin palindrom ola bilməsi üçün mövqeləri cəmi n+1 olan rəqəmlər bir birinə bərabər olmalıdır. Tək ədədlərdə də eyni şərt ödənməlidir, lakin burada (n+1)/2 -ci, yəni mərkəzdə duran rəqəm ixtiyari qiyməti ala bilər.

Armstronq ədədləri

n rəqəmli bir natural ədəd n-ci qüvvətdən rəqəmləri cəminə bərabərdirsə, həmin ədədə Armstronq ədədi deyilir.

‘Riyaziyyat’-da Armstronq ədədləri

Verilmiş n rəqəmli ədədi y ilə, n-ci qüvvətdən cəmlərini x ilə işarə etsək, alarıq ki,

10n-1 ≤ y ≤ 9 * (10n-1 + 10n-2 + ... + 100) ˄ 1 ≤ x ≤ n * 9n

Aydındır ki, biz y = x şərtini ödəyən y-ləri araşdırırıq.

Bu bərabərliyin ödənməsi üçün ən azından

x ∈ [10n-1, 9 * (10n-1 + 10n-2 + ... + 100)] ˄ y ∈ [1, n * 9n]

şərtləri ödənməlidir. Qısaca bizim bu araşdırmanı

An = [1, n * 9n] ⋂  [10n-1, 9 * (10n-1 + 10n-2 + ... + 100)]

çoxluqlarında aparmağımız həm daha yüngül, həm də daha məntiqli olar.

A = A1 ∪ A2 ∪ ... ∪ An işarə edib kiçik bir riyazi tədqiqat aparsaq,

A = A1 ∪ A2 ∪ ... ∪ A60 olduğu nəzərimizə çarpar.

(yəni, ∀k > 60 üçün Ak = ø (çünki ∀n > 60 üçün (min{y} / max{x}) > 1))

Bu isə o deməkdir ki, 61 və ya daha yuxarı rəqəmli heç bir Armstronq ədədi yoxdur. Konkret desək, Armstronq ədədlərinin bir sonu var. İlk 60 çoxluqda varlığı və sayı haqda isə daha dərin analizə ehtiyac duyuruq.

Riyazi görüntüsü

min{y} ≤ max{x}

10n-1 ≤ n * 9n

(10/9)n ≤ 10 * n

f(n) = (10/9)n - 10 * n ≤ 0

n ≤ log(10/9)(10 * n)

g(n) = n - log(10/9)(n) - log(10/9)(10) ≤ 0

Bu tənliyin həllər çoxluğunun

(n ∈) ℕ çoxluğu ilə kəsişməsini tapsaq,

n ∈ {1, 2 , ... , 60} alarıq.

ADNSU İTİF – Kompüter elmləri Fənn: Proqramlaşdırmanın əsasları-1 Müəllim: Sevinc Kərimova Tələbə: Babalı Elçin Mövzu: Tam ədədli alqoritmlər. ƏBOB-un tapılması (Evklid alqoritmi), sadə ədədlərin tapılması (Eratosfen xəlbiri, Armstronq ədədləri, palindromlar)