Sürətli dərəcəyə yüksəltmə
Çox vaxt verilmiş x və n üçün x^n-in effektiv hesablanması məsələsi ortaya çıxır, burada n müsbət tam ədəddir.
Məsələn, x^16-nı hesablamaq lazım olduğunu düşünək. Sadəcə x-dən başlayıb onu 15 dəfə x-ə vurmaq olar. Lakin eyni cavabı cəmi dörd vurma əməliyyatı ilə əldə etmək olar, əgər alınan nəticəni bir neçə dəfə kvadrata yüksəltsək, ardıcıl olaraq x^2, x^4, x^8, x^16 hesablayaraq.
Bu eyni ideya, ümumiyyətlə, istənilən n dəyərinə aşağıdakı kimi tətbiq oluna bilər. n-i ikilik say sistemində yazırıq (soldakı sıfırları çıxarırıq). Sonra hər bir "1"i SX simvolları cütü ilə, hər bir "0"ı isə "S" simvolu ilə əvəz edirik və soldakı ilk SX simvolları cütünü silirik. Nəticə x^n-in hesablanma qaydasını göstərir, burada "S" kvadrata yüksəltmə əməliyyatı, "X" isə x-ə vurma əməliyyatı kimi qəbul edilir. Məsələn, n = 23 üçün ikilik təqdimat 10111-dir. Beləliklə, SXSSXSXSX ardıcıllığını formalaşdırırıq, buradan başlanğıc SX cütünü silərək son qaydanı SSXSXSX əldə edirik. Bu qayda "kvadrata yüksəlt, kvadrata yüksəlt, x-ə vur, kvadrata yüksəlt, x-ə vur, kvadrata yüksəlt və x-ə vur" deməkdir, yəni ardıcıl olaraq x^2, x^4, x^5, x^10, x^11, x^22, x^23 dəyərlərini hesablayın.
Sizdən verilmiş n üçün x ədədini x^n dərəcəsinə sürətli yüksəltmə qaydasını formalaşdırmaq tələb olunur.
Giriş məlumatları
Bir təbii ədəd n, hansı ki, 2·10^9-u keçmir.
Çıxış məlumatları
x ədədini x^n dərəcəsinə yüksəltmə qaydası üçün bir sətir çıxarın.