Sunday, January 20, 2013

Common Lisp: Պարզ ու կատարյալ թվերի մասին

«N թիվը կոչվում է պարզ, եթե այն բացի մեկից և իրենից այլ բաժանարարներ չունի։» Եթե թվի պարզությունը որոշող ֆունկցիան գրենք ըստ այս սահմանման, ապա պետք է որ ստանանք մոտավորապես հետևյալը․
(defun is-prime-a (num)
  (loop for k from 2 to (1- num)
        never (zerop (mod num k))))
Սա իմպերատիվ լուծում է, որտեղ ցիկլի կազմակերպմամբ բացահայտորեն նկարագրված է, թե ինչ գործողություններ պետք է անել թվի պարզությունը ստուգելու համար։ (Այս ալգորիթմի քայլերի քանակը կարելի է կրճատել, եթե ցիկլի հաշվիչի վերին սահմանը փոխարինենք (ceiling (sqrt num)) արտահայտությամբ։ Բայց սա ոճական առումով ոչ մի լավացում չի տալիս։)

Փորձենք տալ պարզ թվի մեկ այլ սահմանում՝ հիմնված առաջինի վրա․ «N թիվը կոչվում է պարզ, եթե այն ունի միայն երկու բաժանարար։» Բայց այս սահմանումը պահանջում է, որ ստուգվեն 1..N միջակայքի մոլոր թվերը։ Այս անգամ էլ միջակայքի վերին սահմանը փոխարինելով (ceiling (sqrt N)) թվով, կստանանք մի նոր սահմանում։ «N թիվը կոչվում է պարզ, եթե այն 1..(sqrt N) միջակայքում ունի միայն մեկ բաժանարար։» (Բնականաբար այդ բաժանարարը 1 թին է։)

Այս վերջին սահմանումը բառացիորեն ծրագրավորելու դեպքում կունենանք հետևյալ ֆունկցիոնալ լուծումը․
(defun is-prime-b (num)
  (= 1 (list-length
 (remove-if 
  #'(lambda (e)
      (/= 0 (mod num e)))
  (loop for i from 1 to (ceiling (sqrt num))
        collect i)))))
Այս ֆունկցիան, չնայած որ կառուցվածքով բավականին հետաքրքիր է, արտաքնապես այնքան էլ գրավիչ չէ։ Փորձենք այն տրոհել ավելի պարզ ֆունկցիաների։

Վերջին սահմանումը հուշում է երեք գործողություն․ ա) 1..(sqrt N) միջակայքի ամբողջ թվերի ցուցակի կառուցում, բ) այդ ցուցակից N թվի բաժանարարների ֆիլտրում, գ) ֆիլտրված ցուցակի երկարության համեմատում 1 թվի հետ։

[a..b] միջակայքը, որտեղ a>b, կարող ենք կառուցել և՛ ռեկուրսիվ, և՛ իտերատիվ եղանակներով։ Ռեկուրսիվ տարբերակն ահա այսպիսինն է․
(defun range (lower upper &optional (delta 1))
  (if (> lower upper)
      '()
      (cons lower (range (+ lower delta) upper))))
Իտերատիվ տարբերակը էլ ավելի պարզ կառուցվածք ունի․
(defun range (lower upper &optional (delta 1))
  (loop for i from lower to upper by delta
        collect i))
Միջակայքը կազմող թվերի ցուցակը ֆիլտրելու և միայն տրված թվի բաժանարաները թողնելու համար սահմանենք divisors ֆունկցիան։ Ֆիլտրելու համար օգտագործված է Common Lisp լեզվի remove-if ֆունկցիան, որը տրված ցուցակից հեռացնում է տրված պրեդիկատին բավարարող տարրերը։
(defun divisors-a (num)
  (remove-if #'(lambda (e) (/= 0 (mod num e)))
             (range 1 (ceiling (sqrt num)))))
Եվ վերջապես, is-prime պրեդիկատը բաժանարարների ցուցակի երկարությունը համեմատում է 1-ի հետ։
(defun is-prime (num)
  (= 1 (list-length (divisors-a num))))

* * *
«N թիվը կոչվում է կատարյալ, եթե այն հավասար է իր բաժանարարների (բացի իրենից) գումարին։» Եթե թվի պարզ լինելը ստուգելու համար բաժանարարները որոնում էինք 1..(sqrt N) միջակայքում, ապա այս դեպքում պետք է ընտրել 1..N/2 միջակայքը։ Սահմանենք մի նոր divisors ֆունկցիա․
(defun divisors (num)
  (remove-if #'(lambda (e) (/= 0 (mod num e)))
             (range 1 (ceiling num 2))))
Թվի կատարյալ լինելն էլ ստուգելու համար սահմանենք is-perfect ֆունկցիան, որը գումարում է ընտրված բաժանարարները և ամեմատում թվի հետ։
(defun is-perfect (num)
  (= num (apply #'+ (divisors num))))
Այն դեպքում, երբ պետք է որոնել տրված M թվին չգերազանցող բոլոր կատարյալ թվերի ցուցակը, կարող ենք սահմանել perfects-in-range ֆունկցիան։
(defun perfects-in-range (upper)
  (remove-if (complement #'is-perfect) (range 2 upper)))

No comments:

Post a Comment