First Ann's html


Лабораторная работа по курсу
"Функциональное програмирование"
Задача "ПРОСТЫЕ ГИРИ"

Выполнил студент группы 6-19-2 Данилина А.С.

Под руководством Тарасова В.Г.


СОДЕРЖАНИЕ ОТЧЕТА

1.Постановка задачи
2.Описание алгоритма
3.Описание логики функций
4.Текст программы
5.Результаты работы программы



1. Постановка задачи

Имеются гири: 1г, 2г, ..., Nг (N<=500000). Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.


2. Описание алгоритма

Определимся с общими понятиями:

ПРОСТОЕ число
число которое делится без остатка на 1 и на само себя.
НАТУРАЛЬНОЕ число
любое целое положительное число.
Идея алгоритма заключается в следущем:
Выбириается любое натуральное число N,затем ищется первое простое число большее,чем N обозначим его M.
Первая пара будет такой ( N . M-N )
Cледущие пары строятся так ( N-2.M-N+2 ) ( N-4.M-N+4 ) ( N-2i.M-N+2i )
и т.д. до тех пор пока N-2i не будет больше,чем M-N.
Как только это условие будет выполнено,то число N-2i не рассматривается
И следущие пары строятся по тому же алгоритму, но уже для числа M-N.
до тех пор пока N-2i не будет меньше 2.


3. Описание логики функций


3.1. Функция NEXT

Функция NEXT возвращает первое простое число большее N.

Вход: L, N.
L - упорядоченный по возрастанию список простых чисел
N - число

  1. Если L - пустой список, то вернуть 0
  2. Если ГОЛОВА_L>N, то вернуть ГОЛОВА_L
    Иначе вызвать NEXT ( N ХВОСТ_L )

Выход: простое число большее N или 0

3.2. Функция TEST

Функция TEST проверяет простое ли число N.

Вход: L, N.
L - список всех простых чисел меньших чем N
N - число

  1. Если L - пустой список, то вернуть N
  2. Если N mod ГОЛОВА_=0, то вернуть 0
    Иначе вызвать TEST ( N ХВОСТ_L )

Выход:
N - если это простое число
0 - если N - число не простое

3.3. Функция PROST

Функция PROST формирует упорядоченный по возрастанию список простых чисел.

Вход: N, C, L.
C=5, L='(3) - начальные числа простого ряда
N - число

  1. Если N<ГОЛОВА_L, то вернуть перевернутый список L
  2. Если C-простое число, то вызвать PROST ( N C+2 L+C )
    Иначе вызвать PROST ( N C+2 L )

Выход: L - список простых чисел, последнее число списка большее, чем N

3.4. Функция PRINTALL

Функция PRINTALL формирует список пар натуральных чисел сумма которых равна P.

Вход: C, F, P.
C - начальное значение
F - конечное значение
P - простое число

  1. Если C<F, то вернуть NIL
    Иначе вернуть (C.(P-C)) + PRINTALL ( C-2 F P )

Выход: список точечных пар натуральных чисел сумма которых равна числу P

3.5. Функция POSL

Функция POSL формирует список пар натуральных чисел от 1 до N сумма которых есть простое число

Вход: N, L.
N - натуральное число (входной аргумент задачи)
L - упорядоченный список простых чисел, последнее число списка больше N

  1. Если N<2, то вернуть NIL
    Иначе вернуть ( PRINTALL ( N NUM-N NUM) ) + ( POSL ( NUM-N-1 L ) ),
    где NUM = NEXT ( N L )

Выход: список всех точечных пар всех натуральных чисел от 1 до N сумма которых есть простое число

3.6. Функция LAB

Функция LAB формирует список пар всех натуральных чисел от 1 до N сумма которых есть простое число

Вход: N.
N - натуральное число (входной аргумент задачи)

  1. вернуть POSL ( N PROST ( N 5 '(3) ) )

Выход: список всех пар всех натуральных чисел от 1 до N сумма которых есть простое число



4. Текст программы


      ;; функция next возвращает первое простое число большее n
      ;; l - упорядоченный по возрастанию список простых чисел

      (defun next(n l)
        (cond ((NULL l) 0)
              ((< n (car l)) (car l))
              ( T (next n (cdr l)))
        )
      )


      ;; функция test проверяет простое ли число n
      ;; l - список всех простых чисел меньших n

      (defun test(n l)
        (cond((NULL l) n)
             ((= 0 (mod n (car ))) nil)
             ( T (test n (cdr l)))
        )
      )


      ;; фунция prost формирует упорядоченный по возрастанию
      ;; список простых чисел. Последнее простое число больше n
      ;; начальные значения c=5 l='(3)

      (defun prost(n c l)
        (cond((< n (car l)) (reverse l))
             ((test c l) (prost n (+ 2 c) (cons c l)))
             ( T (prost n (+ 2 c) l))
        )
      )


      ;; функция printall формирует список пар натуральных
      ;; чисел сумма которых равна p
      ;; с - начальное значение
      ;; f - конечное значение

      (defun printall(c f p)
        (cond((< c f) nil)
             (T (cons (cons c (- p c))
                      (printall (- c 2) f p)
                )
             )
        )
      )


      ;; функция posl формирует список пар всех натуральных чисел
      ;; сумма которых есть простое число
      ;; n - наибольшее натуральное число
      ;; l - упорядоченный список простых чисел, с последним больше n

      (defun posl(n l)
         (cond((< n 2) nil)
              (T ((lambda (num)
                    ((lambda (num-n)
                       (append (printall n (num-n) num)
                            (posl (- (num-n) 1) l)
                       )
                      )(- num n))
                  )(next n l))
              )
         )
      )


      ;; функция lab формирует список пар всех натуральных чисел
      ;; сумма которых есть простое число
      ;; n - наибольшее натуральное число

      (defun lab (n)
         (posl n (prost n 5 '(3)))



5. Результаты работы программы

 >(lab 28)
 ((28 . 1) (26 . 3) (24 . 5) (22 . 7) (20 . 9) (18 . 11)
 (16 . 13) (14 . 15) (12 . 17) (10 . 19) (8 . 21) (6 . 23)
 (4 . 25) (2 . 27))

 >(lab 15)
 ((15 . 2) (13 . 4) (11 . 6) (9 . 8) (7 . 10) (5 . 12) (3 . 14))

 >(lab 47)
 ((47 . 6) (45 . 8) (43 . 10) (41 . 12) (39 . 14) (37 . 16)
  (35 . 18) (33 . 20) (31 . 22) (29 . 24) (27 . 26) (25 . 28)
  (23 . 30) (21 . 32) (19 . 34) (17 . 36) (15 . 38) (13 . 40)
  (11 . 42) (9 . 44) (7 . 46) (5 . 2) (3 . 4))



Created in Inferno-204 by Anuta Daniina
Отдельное спасибо Данилову Виктору за помощь в составлении алгоритмов и Кондратьеву Максиму за помощь в создании данного документа