Шаг 107.
Элементы вычислительной теории чисел

На этом шаге мы рассмотрим использование LISP для решения вычислительных задач.

Многие теоремы в теории чисел были первоначально открыты индуктивно с помощью практических вычислений, и только впоследствии доказаны строго математически... Мы не должны забывать, однако, что результаты, полученные индуктивно, даже если они основаны на большом количестве экспериментов, не могут еще считаться твердо установленными. В теории чисел их законность гораздо слабее, чем в экспериментальных науках.

А.А.Френкель

Приведенные ниже примеры показывают, как можно проверять некоторые теоретико-числовые гипотезы, относящиеся к "школьной" теории чисел.

Пример 1.

   ; -------------------------------- ;
   ; Делится ли число 7^77 + 1 на 5 ? ;
   ; -------------------------------- ;
   (DEFUN P (LAMBDA (X A)
      (CAR (DIVIDE (SETQ S (+ (STEPEN X A) 1)) 5) )
      (COND
         ( (ZEROP (MOD S 5)) T )
         ( T NIL )
      )
   ))
   ; ----------------------- ;
   (DEFUN STEPEN (LAMBDA (X A)
   ; Возведение целого числа X в целую неотрицательную ;
   ; степень A                                         ;
      (COND ( (ZEROP A) 1 )
            ( (ZEROP (- A 1)) X )
            (  T  (* (STEPEN X (- A 1)) X) )
      )
   ))

Текст этой программы можно взять здесь.

Пример 2.

   ; -------------------------------------------- ;
   ; Составить список, состоящий из простых чисел ;
   ;                отрезка [2,N]                 ;
   ; -------------------------------------------- ;
   (DEFUN PAL (LAMBDA (N)
      (COND ( (EQ N 2) (CONS 2 NIL) )
            ( (ISPRIM N) (CONS N (PAL (- N 1))) )
            (    T   (PAL (- N 1)) )
      )
   ))
   ; Проверка, является ли число N простым или нет ;
   (DEFUN ISPRIM (LAMBDA (N)
      (COND ( (EQ N 1) NIL )
            (    T    (ISPR N 2) )
      )
   ))
   ; --------------------- ;
   (DEFUN ISPR (LAMBDA (N M)
      (COND ( (EQ M N)                T  )
            ( (EQ (MOD N M) 0) NIL )
            (      T            (ISPR N (+ M 1)) )
      )
   ))

Текст этой программы можно взять здесь.

Пример 3.

   ; ------------------------------------------------ ;
   ; Программа нахождения нескольких палиндромических ;
   ;               чисел меньших 10001                ;
   ; ------------------------------------------------ ;
   (DEFUN PAL (LAMBDA ()
      (SETQ N 1)
      (SETQ LST NIL)
      (LOOP
          ( (EQ N 10001) (PRIN1 "Не найдено!") )
          (COND ( (EQUAL (UNPACK N) (REVERSE (UNPACK N)))
                            (PRINT N) )
                ( T )
          )
          (SETQ N (+ N 1))
      )
   ))
   ; ------------------- ;
   (DEFUN PAL1 (LAMBDA (N)
      (COND ( (EQ N 1) (CONS 1 NIL) )
            ( (EQUAL (UNPACK N) (REVERSE (UNPACK N)))
                         (CONS N (PAL1 (- N 1))) )
            (   T   (PAL1 (- N 1)) )
      )
   ))

Текст этой программы можно взять здесь.

Пример 4.

   ; ----------------------------------------------------- ;
   ; Установить, представимо ли данное натуральное число в ;
   ;     виде суммы квадратов двух натуральных чисел.      ;
   ; ----------------------------------------------------- ;
   (DEFUN SUM (LAMBDA (N)
      (SETQ FIND NIL)
      (SETQ I1 1)
      (LOOP
          ( (> I1 N) )
          (SETQ I2 1)
          (LOOP
              ( (> I2 N) )
              ( (EQ N (+ (* I1 I1)
                         (* I2 I2))
                )
                     (SETQ FIND T) (SETQ A I1) (SETQ B I2)
              )
              (SETQ I2 (+ I2 1))
          )
          (SETQ I1 (+ I1 1))
      )
      (COND (FIND (PRIN1 A) (PRIN1 " ") (PRINT B) )
            (  T  (PRINT NO) )
      )
   ))

Текст этой программы можно взять здесь.

Пример 5.

   ; --------------------------------------------------- ;
   ; Составить программу поиска среди натуральных чисел  ;
   ; n, n+1,..., 2n так называемых близнецов, т.е. двух  ;
   ; простых чисел, разность которых равна 2. Если близ- ;
   ; нецы в указанном диапазоне найдены, то вернуть 1,   ;
   ;         если близнецов нет, то вернуть 0            ;
   ; --------------------------------------------------- ;
   (DEFUN BLIZNECI (LAMBDA (X)
      (SETQ MAX (* 2 X))
      ( LOOP
           ( (> X MAX) )
           (SETQ Y (+ X 2))
           (COND ( (AND (SIMPLE X) (SIMPLE Y))
                     ((PRIN1 1) (PRIN1 " ") (PRIN1 X)
                      (PRIN1 " ") (PRINT Y))
                 )
                 (  T  0 )
           )
           (SETQ X (+ X 1))
      )
   ))
   ; --------------------- ;
   (DEFUN SIMPLE (LAMBDA (N)
      (SETQ FLAG 1)
      (COND ( (AND (EQ (MOD N 2) 0) (NOT (EQ N 2))) NIL )
            (  T  ( (SETQ J 3)
                    (LOOP
                        ( (< (CAR (DIVIDE N 2)) J) )
                        ( (EQ (MOD N J) 0)
                             (SETQ FLAG 0) )
                        ( SETQ J (+ J 2) )
                    )
                    (COND ( (EQ FLAG 0)  NIL  )
                          (   T          T    ))
                    )
            )
      )
   ))

Текст этой программы можно взять здесь.

Пример 6.

   ; --------------------------------------------------- ;
   ; Гольдбахом было высказано предположение, что каждое ;
   ; четное число, большее или равное  4, представимо  в ;
   ; виде суммы двух простых. Это предположение  до  сих ;
   ; пор не доказано  и  не опровергнуто. Написать  про- ;
   ; грамму проверки этой гипотезы для  данного  четного ;
   ; числа. Результатом выполнения программы должен быть ;
   ; вывод  самого числа, если  не  удалось  найти  пару ;
   ; простых  слагаемых, и  вывод  пары  соответствующих ;
   ;       простых чисел, если таковая пара найдена      ;
   ; --------------------------------------------------- ;
   (DEFUN SM (LAMBDA (N)
      (SETQ J 2)
      (LOOP
          ( (EQ J N) )
          ( (AND (SIMPLE J)
                 (SIMPLE (- N J)))
                 ( (PRIN1 J) (PRIN1 " ")
                   (PRINT (- N J)) )
          )
          (SETQ J (+ J 1))
      )
   ))
   ; --------------------- ;
   (DEFUN SIMPLE (LAMBDA (N)
      (SETQ FLAG 1)
      (COND ( (AND (EQ (MOD N 2) 0) (NOT (EQ N 2))) NIL )
            (  T  ( (SETQ I 3)
                    (LOOP
                         ( (< (CAR (DIVIDE N 2)) I) )
                         ( (EQ (MOD N I) 0)
                              (SETQ FLAG 0) )
                         ( SETQ I (+ I 2) )
                    )
                    (COND ( (EQ FLAG 0) NIL )
                          (   T          T  ))
                    )
            )
      )
   ))

Текст этой программы можно взять здесь.

Пример 7.

   ; ----------------------------------------------------- ;
   ; Установить является ли данное целое число  p простым, ;
   ; используя теорему Вильсона: целое  число  p  является ;
   ; простым тогда и только тогда, когда  (p-1)!+1 делится ;
   ;                            на p                       ;
   ; ----------------------------------------------------- ;
   (DEFUN PROST (LAMBDA (P)
      (COND  ( (ZEROP (MOD (FACT P) P))
                 (PRIN1 "Число простое") )
             (   T   (PRIN1 "Число не простое") )
      )
   ))
   ; --------------------- ;
   (DEFUN FACT (LAMBDA (NUM)
   ; Вычисление (NUM-1)! + 1 ;
      (SETQ ANS 1)
      (SETQ NUM (- NUM 1))
      (LOOP
          ( (EQ NUM 0) ANS )
          (SETQ ANS (* NUM ANS))
          (SETQ NUM (- NUM 1))
      )
      (SETQ ANS (+ ANS 1))
   ))

Текст этой программы можно взять здесь.

Со следующего шага мы начнем рассматривать объектно-ориентированное программирование в системе muLISP87.

Предыдущий шаг Содержание Следующий шаг