1. | Постановка задачи |
---|---|
2. | Описание алгоритма |
3. | Описание логики функций |
4. | Текст программы |
5. | Результаты работы программы |
Имеются гири: 1г, 2г, ..., Nг (N<=500000).
Написать программу, распределяющую эти гири на
максимально возможное количество пар так, чтобы
суммарный вес гирь в каждой паре выражался
простым числом.
2. Описание алгоритма
3.1. Функция NEXT
Функция NEXT возвращает первое простое число большее N.
3.2. Функция TEST
Функция TEST проверяет простое ли число N.
3.3. Функция PROST
Функция PROST формирует упорядоченный по возрастанию
список простых чисел.
3.4. Функция PRINTALL
Функция PRINTALL формирует список пар натуральных чисел
сумма которых равна P.
3.5. Функция POSL
Функция POSL формирует список пар натуральных чисел от 1 до N
сумма которых есть простое число
3.6. Функция LAB
Функция LAB формирует список пар всех натуральных чисел от 1 до N
сумма которых есть простое число
Иначе вызвать NEXT ( N ХВОСТ_L )
Иначе вызвать TEST ( N ХВОСТ_L )
Иначе вызвать PROST ( N C+2 L )
Иначе вернуть (C.(P-C)) + PRINTALL ( C-2 F P )
Иначе вернуть ( PRINTALL ( N NUM-N NUM) ) + ( POSL ( NUM-N-1 L ) ),
где NUM = NEXT ( N L )
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
Отдельное спасибо Данилову Виктору
за помощь в составлении алгоритмов и
Кондратьеву Максиму
за помощь в создании данного документа