% =============================================== % LAB9 TASK2 - СПЕЦИАЛЬНЫЕ ПРЕДИКАТЫ PROLOG % Реализация рекурсивных предикатов с комментариями % =============================================== % =============================================== % 1. ПРОИЗВЕДЕНИЕ ЦИФР ЧИСЛА % =============================================== /** * digit_product_up(+N, -Product) * Вычисляет произведение цифр числа с помощью рекурсии вверх. * * @param N - входное неотрицательное целое число (унифицированная переменная) * @param Product - произведение цифр числа (неунифицированная переменная) * * Принцип работы: * - Базовый случай: digit_product_up(0, 1) - произведение цифр нуля равно 1 * - Рекурсивный случай: произведение цифр N = последняя_цифра * произведение_цифр(N//10) * - Вычисления происходят при возврате из рекурсии */ digit_product_up(0, 1) :- !. % Базовый случай: произведение цифр 0 равно 1 digit_product_up(N, Product) :- N > 0, % N должно быть положительным (проверка унификации) Digit is N mod 10, % Digit унифицируется с последней цифрой N N1 is N // 10, % N1 унифицируется с N без последней цифры digit_product_up(N1, SubProduct), % Рекурсивный вызов (SubProduct - неунифицированная) Product is Digit * SubProduct. % Product унифицируется с произведением /** * digit_product_down(+N, -Product) * Вычисляет произведение цифр числа с помощью рекурсии вниз (с аккумулятором). * * @param N - входное неотрицательное целое число (унифицированная переменная) * @param Product - произведение цифр числа (неунифицированная переменная) * * Использует вспомогательный предикат с аккумулятором для хвостовой рекурсии. */ digit_product_down(N, Product) :- digit_product_down_helper(N, 1, Product). % Начинаем с аккумулятора = 1 /** * digit_product_down_helper(+N, +Acc, -Product) * Вспомогательный предикат для вычисления произведения цифр (рекурсия вниз). * * @param N - оставшаяся часть числа (унифицированная переменная) * @param Acc - аккумулятор произведения (унифицированная переменная) * @param Product - результат (неунифицированная переменная при вызове) * * Принцип работы: * - Базовый случай: когда N = 0, Product унифицируется с аккумулятором * - Рекурсивный случай: обновляем аккумулятор и продолжаем с N//10 */ digit_product_down_helper(0, Acc, Acc) :- !. % Product унифицируется с Acc digit_product_down_helper(N, Acc, Product) :- N > 0, % Проверка что N положительное Digit is N mod 10, % Digit унифицируется с последней цифрой N1 is N // 10, % N1 унифицируется с числом без последней цифры Acc1 is Acc * Digit, % Acc1 унифицируется с новым аккумулятором digit_product_down_helper(N1, Acc1, Product). % Хвостовая рекурсия % =============================================== % 2. МАКСИМАЛЬНАЯ ЦИФРА, НЕ ДЕЛЯЩАЯСЯ НА 3 % =============================================== /** * max_digit_not_div3_up(+N, -MaxDigit) * Находит максимальную цифру числа, которая не делится на 3 (рекурсия вверх). * * @param N - входное неотрицательное целое число (унифицированная переменная) * @param MaxDigit - максимальная цифра не делящаяся на 3, или -1 если таких нет * * Принцип работы: * - Базовый случай: для 0 возвращаем -1 (0 делится на 3) * - Рекурсивный случай: сравниваем текущую цифру с максимумом из остальных */ max_digit_not_div3_up(0, -1) :- !. % 0 делится на 3, возвращаем -1 max_digit_not_div3_up(N, MaxDigit) :- N > 0, % N должно быть положительным Digit is N mod 10, % Digit унифицируется с последней цифрой N1 is N // 10, % N1 унифицируется с числом без последней цифры max_digit_not_div3_up(N1, SubMax), % SubMax - максимум из остальных цифр combine_max_not_div3(Digit, SubMax, MaxDigit). % Комбинируем результаты /** * combine_max_not_div3(+Digit, +SubMax, -MaxDigit) * Вспомогательный предикат для комбинирования цифры и подмаксимума. * * @param Digit - текущая цифра (унифицированная переменная) * @param SubMax - максимум из остальных цифр (унифицированная переменная) * @param MaxDigit - результирующий максимум (неунифицированная переменная) */ combine_max_not_div3(Digit, SubMax, MaxDigit) :- ( Digit mod 3 =\= 0 -> % Если Digit не делится на 3 ( SubMax =:= -1 -> % Если нет других подходящих цифр MaxDigit = Digit % MaxDigit унифицируется с Digit ; MaxDigit is max(Digit, SubMax) % MaxDigit унифицируется с максимумом ) ; MaxDigit = SubMax % Если Digit делится на 3, используем SubMax ). /** * max_digit_not_div3_down(+N, -MaxDigit) * Находит максимальную цифру числа, которая не делится на 3 (рекурсия вниз). * * @param N - входное неотрицательное целое число (унифицированная переменная) * @param MaxDigit - максимальная цифра не делящаяся на 3, или -1 если таких нет */ max_digit_not_div3_down(N, MaxDigit) :- max_digit_not_div3_down_helper(N, -1, MaxDigit). % Начинаем с Max = -1 /** * max_digit_not_div3_down_helper(+N, +CurrentMax, -MaxDigit) * Вспомогательный предикат для поиска максимальной цифры (рекурсия вниз). * * @param N - оставшаяся часть числа (унифицированная переменная) * @param CurrentMax - текущий максимум (унифицированная переменная) * @param MaxDigit - результат (неунифицированная переменная при первом вызове) */ max_digit_not_div3_down_helper(0, CurrentMax, CurrentMax) :- !. % MaxDigit унифицируется с CurrentMax max_digit_not_div3_down_helper(N, CurrentMax, MaxDigit) :- N > 0, % Проверка положительности N Digit is N mod 10, % Digit унифицируется с последней цифрой N1 is N // 10, % N1 унифицируется с числом без последней цифры update_max_not_div3(Digit, CurrentMax, NewMax), % NewMax - обновленный максимум max_digit_not_div3_down_helper(N1, NewMax, MaxDigit). % Хвостовая рекурсия /** * update_max_not_div3(+Digit, +CurrentMax, -NewMax) * Обновляет текущий максимум с учетом новой цифры. * * @param Digit - новая цифра (унифицированная переменная) * @param CurrentMax - текущий максимум (унифицированная переменная) * @param NewMax - новый максимум (неунифицированная переменная) */ update_max_not_div3(Digit, CurrentMax, NewMax) :- ( Digit mod 3 =\= 0 -> % Если цифра не делится на 3 ( CurrentMax =:= -1 -> % Если это первая подходящая цифра NewMax = Digit % NewMax унифицируется с Digit ; NewMax is max(Digit, CurrentMax) % NewMax унифицируется с максимумом ) ; NewMax = CurrentMax % Если цифра делится на 3, максимум не меняется ). % =============================================== % 3. КОЛИЧЕСТВО ДЕЛИТЕЛЕЙ ЧИСЛА % =============================================== /** * divisor_count_up(+N, -Count) * Подсчитывает количество делителей числа с помощью рекурсии вверх. * * @param N - входное положительное целое число (унифицированная переменная) * @param Count - количество делителей (неунифицированная переменная) * * Принцип работы: * - Проверяем каждое число от 1 до N на то, является ли оно делителем * - Используем рекурсию для подсчета */ divisor_count_up(N, Count) :- N > 0, % N должно быть положительным divisor_count_up_helper(N, 1, Count). % Начинаем проверку с 1 /** * divisor_count_up_helper(+N, +Current, -Count) * Вспомогательный предикат для подсчета делителей (рекурсия вверх). * * @param N - число, для которого ищем делители (унифицированная переменная) * @param Current - текущий проверяемый делитель (унифицированная переменная) * @param Count - количество делителей (неунифицированная переменная) */ divisor_count_up_helper(N, Current, 0) :- Current > N, !. % Базовый случай: превысили N, делителей 0 divisor_count_up_helper(N, Current, Count) :- Current =< N, % Current не превышает N Next is Current + 1, % Next унифицируется со следующим числом divisor_count_up_helper(N, Next, RestCount), % RestCount - количество остальных делителей ( N mod Current =:= 0 -> % Если Current является делителем N Count is RestCount + 1 % Count унифицируется с RestCount + 1 ; Count = RestCount % Иначе Count унифицируется с RestCount ). /** * divisor_count_down(+N, -Count) * Подсчитывает количество делителей числа с помощью рекурсии вниз. * * @param N - входное положительное целое число (унифицированная переменная) * @param Count - количество делителей (неунифицированная переменная) */ divisor_count_down(N, Count) :- N > 0, % N должно быть положительным divisor_count_down_helper(N, 1, 0, Count). % Начинаем с делителя 1 и счетчика 0 /** * divisor_count_down_helper(+N, +Current, +Acc, -Count) * Вспомогательный предикат для подсчета делителей (рекурсия вниз). * * @param N - число, для которого ищем делители (унифицированная переменная) * @param Current - текущий проверяемый делитель (унифицированная переменная) * @param Acc - аккумулятор количества делителей (унифицированная переменная) * @param Count - результат (неунифицированная переменная при первом вызове) */ divisor_count_down_helper(N, Current, Acc, Acc) :- Current > N, !. % Базовый случай: Count унифицируется с Acc divisor_count_down_helper(N, Current, Acc, Count) :- Current =< N, % Current не превышает N ( N mod Current =:= 0 -> % Если Current является делителем Acc1 is Acc + 1 % Acc1 унифицируется с увеличенным аккумулятором ; Acc1 = Acc % Иначе Acc1 унифицируется с неизмененным Acc ), Next is Current + 1, % Next унифицируется со следующим числом divisor_count_down_helper(N, Next, Acc1, Count). % Хвостовая рекурсия % =============================================== % ОПТИМИЗИРОВАННЫЕ ВЕРСИИ (ДОПОЛНИТЕЛЬНЫЕ) % =============================================== /** * divisor_count_optimized(+N, -Count) * Оптимизированный подсчет делителей (проверяем только до sqrt(N)). * * @param N - входное положительное целое число (унифицированная переменная) * @param Count - количество делителей (неунифицированная переменная) * * Принцип оптимизации: * - Делители существуют парами: если d делит N, то N/d тоже делит N * - Достаточно проверить числа от 1 до sqrt(N) * - Для каждого найденного делителя d < sqrt(N) добавляем 2 к счетчику * - Если N - точный квадрат, sqrt(N) добавляем только один раз */ divisor_count_optimized(N, Count) :- N > 0, % N должно быть положительным Sqrt is floor(sqrt(N)), % Sqrt унифицируется с floor(sqrt(N)) divisor_count_optimized_helper(N, 1, Sqrt, 0, Count). /** * divisor_count_optimized_helper(+N, +Current, +Sqrt, +Acc, -Count) * Вспомогательный предикат для оптимизированного подсчета делителей. */ divisor_count_optimized_helper(N, Current, Sqrt, Acc, Acc) :- Current > Sqrt, !. % Базовый случай divisor_count_optimized_helper(N, Current, Sqrt, Acc, Count) :- Current =< Sqrt, % Current не превышает Sqrt ( N mod Current =:= 0 -> % Если Current является делителем ( Current * Current =:= N -> % Если Current = sqrt(N) Acc1 is Acc + 1 % Добавляем только 1 (сам делитель) ; Acc1 is Acc + 2 % Добавляем 2 (делитель и его пару) ) ; Acc1 = Acc % Если не делитель, аккумулятор не изменяется ), Next is Current + 1, % Next унифицируется со следующим числом divisor_count_optimized_helper(N, Next, Sqrt, Acc1, Count). % =============================================== % ВСПОМОГАТЕЛЬНЫЕ И ДЕМОНСТРАЦИОННЫЕ ПРЕДИКАТЫ % =============================================== /** * task_info/0 * Выводит информацию о реализованных предикатах. * Все переменные являются унифицированными константами. */ task_info :- write('РЕАЛИЗОВАННЫЕ ПРЕДИКАТЫ TASK2:'), nl, write('1. digit_product_up(+N, -Product) - произведение цифр (рекурсия вверх)'), nl, write('2. digit_product_down(+N, -Product) - произведение цифр (рекурсия вниз)'), nl, write('3. max_digit_not_div3_up(+N, -MaxDigit) - макс. цифра не дел. на 3 (рек. вверх)'), nl, write('4. max_digit_not_div3_down(+N, -MaxDigit) - макс. цифра не дел. на 3 (рек. вниз)'), nl, write('5. divisor_count_up(+N, -Count) - количество делителей (рекурсия вверх)'), nl, write('6. divisor_count_down(+N, -Count) - количество делителей (рекурсия вниз)'), nl, write('7. divisor_count_optimized(+N, -Count) - оптимизированный подсчет делителей'), nl. /** * show_examples/0 * Показывает примеры использования предикатов. */ show_examples :- write('ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ:'), nl, write('?- digit_product_up(123, P). % P = 6 (1*2*3)'), nl, write('?- digit_product_down(123, P). % P = 6'), nl, write('?- max_digit_not_div3_up(39627, M). % M = 7 (макс. не дел. на 3)'), nl, write('?- max_digit_not_div3_down(39627, M). % M = 7'), nl, write('?- divisor_count_up(12, C). % C = 6 (1,2,3,4,6,12)'), nl, write('?- divisor_count_down(12, C). % C = 6'), nl, write('?- divisor_count_optimized(12, C). % C = 6'), nl. /** * test_all_predicates/0 * Быстрое тестирование всех предикатов с примерами. */ test_all_predicates :- write('=== ТЕСТИРОВАНИЕ ВСЕХ ПРЕДИКАТОВ ==='), nl, % Тест произведения цифр write('Тест произведения цифр: '), digit_product_up(123, P1), digit_product_down(123, P2), write('digit_product_up(123) = '), write(P1), write(', digit_product_down(123) = '), write(P2), nl, % Тест максимальной цифры не делящейся на 3 write('Тест макс. цифры не дел. на 3: '), max_digit_not_div3_up(39627, M1), max_digit_not_div3_down(39627, M2), write('max_digit_not_div3_up(39627) = '), write(M1), write(', max_digit_not_div3_down(39627) = '), write(M2), nl, % Тест количества делителей write('Тест количества делителей: '), divisor_count_up(12, C1), divisor_count_down(12, C2), divisor_count_optimized(12, C3), write('divisor_count_up(12) = '), write(C1), write(', divisor_count_down(12) = '), write(C2), write(', divisor_count_optimized(12) = '), write(C3), nl, write('=== ТЕСТИРОВАНИЕ ЗАВЕРШЕНО ==='), nl. /** * compare_recursions(+N)/1 * Сравнивает результаты рекурсий вверх и вниз для заданного числа N. * * @param N - число для сравнения (унифицированная переменная) */ compare_recursions(N) :- write('Сравнение рекурсий для числа '), write(N), write(':'), nl, % Произведение цифр digit_product_up(N, P1), digit_product_down(N, P2), write(' Произведение цифр (вверх): '), write(P1), nl, write(' Произведение цифр (вниз): '), write(P2), nl, write(' Произведения равны: '), (P1 =:= P2 -> write('да') ; write('нет')), nl, % Максимальная цифра не делящаяся на 3 max_digit_not_div3_up(N, M1), max_digit_not_div3_down(N, M2), write(' Макс. цифра не дел. на 3 (вверх): '), write(M1), nl, write(' Макс. цифра не дел. на 3 (вниз): '), write(M2), nl, write(' Максимумы равны: '), (M1 =:= M2 -> write('да') ; write('нет')), nl, % Количество делителей divisor_count_up(N, C1), divisor_count_down(N, C2), divisor_count_optimized(N, C3), write(' Количество делителей (вверх): '), write(C1), nl, write(' Количество делителей (вниз): '), write(C2), nl, write(' Количество делителей (оптим.): '), write(C3), nl, write(' Все количества равны: '), ((C1 =:= C2, C2 =:= C3) -> write('да') ; write('нет')), nl. /** * benchmark_predicates(+N)/1 * Измеряет производительность предикатов для числа N. * * @param N - число для бенчмарка (унифицированная переменная) */ benchmark_predicates(N) :- write('Бенчмарк предикатов для N = '), write(N), write(':'), nl, % Бенчмарк произведения цифр get_time(T1), digit_product_up(N, _), get_time(T2), digit_product_down(N, _), get_time(T3), TimeProductUp is T2 - T1, TimeProductDown is T3 - T2, write(' Произведение цифр (вверх): '), write(TimeProductUp), write(' сек'), nl, write(' Произведение цифр (вниз): '), write(TimeProductDown), write(' сек'), nl, % Бенчмарк максимальной цифры get_time(T4), max_digit_not_div3_up(N, _), get_time(T5), max_digit_not_div3_down(N, _), get_time(T6), TimeMaxUp is T5 - T4, TimeMaxDown is T6 - T5, write(' Макс. цифра (вверх): '), write(TimeMaxUp), write(' сек'), nl, write(' Макс. цифра (вниз): '), write(TimeMaxDown), write(' сек'), nl, % Бенчмарк делителей get_time(T7), divisor_count_up(N, _), get_time(T8), divisor_count_down(N, _), get_time(T9), divisor_count_optimized(N, _), get_time(T10), TimeDivUp is T8 - T7, TimeDivDown is T9 - T8, TimeDivOpt is T10 - T9, write(' Делители (вверх): '), write(TimeDivUp), write(' сек'), nl, write(' Делители (вниз): '), write(TimeDivDown), write(' сек'), nl, write(' Делители (оптим.): '), write(TimeDivOpt), write(' сек'), nl. /** * interactive_demo/0 * Интерактивная демонстрация всех предикатов. */ interactive_demo :- write('=== ИНТЕРАКТИВНАЯ ДЕМОНСТРАЦИЯ TASK2 ==='), nl, write('Выберите операцию:'), nl, write('1. Произведение цифр числа'), nl, write('2. Максимальная цифра не делящаяся на 3'), nl, write('3. Количество делителей'), nl, write('4. Сравнение рекурсий'), nl, write('5. Бенчмарк производительности'), nl, write('6. Выход'), nl, write('Введите номер (1-6): '), read(Choice), handle_choice(Choice). /** * handle_choice(+Choice)/1 * Обрабатывает выбор пользователя в интерактивном режиме. * * @param Choice - выбор пользователя (унифицированная переменная) */ handle_choice(1) :- write('Введите число для вычисления произведения цифр: '), read(N), ( N >= 0 -> digit_product_up(N, P1), digit_product_down(N, P2), write('Произведение цифр '), write(N), write(' (рекурсия вверх) = '), write(P1), nl, write('Произведение цифр '), write(N), write(' (рекурсия вниз) = '), write(P2), nl ; write('Число должно быть неотрицательным!'), nl ), interactive_demo. handle_choice(2) :- write('Введите число для поиска максимальной цифры не делящейся на 3: '), read(N), ( N >= 0 -> max_digit_not_div3_up(N, M1), max_digit_not_div3_down(N, M2), write('Максимальная цифра '), write(N), write(' не дел. на 3 (рекурсия вверх) = '), write(M1), nl, write('Максимальная цифра '), write(N), write(' не дел. на 3 (рекурсия вниз) = '), write(M2), nl, ( M1 =:= -1 -> write('Все цифры числа делятся на 3'), nl ; true ) ; write('Число должно быть неотрицательным!'), nl ), interactive_demo. handle_choice(3) :- write('Введите число для подсчета количества делителей: '), read(N), ( N > 0 -> divisor_count_up(N, C1), divisor_count_down(N, C2), divisor_count_optimized(N, C3), write('Количество делителей '), write(N), write(' (рекурсия вверх) = '), write(C1), nl, write('Количество делителей '), write(N), write(' (рекурсия вниз) = '), write(C2), nl, write('Количество делителей '), write(N), write(' (оптимизированный) = '), write(C3), nl ; write('Число должно быть положительным!'), nl ), interactive_demo. handle_choice(4) :- write('Введите число для сравнения рекурсий: '), read(N), ( N >= 0 -> compare_recursions(N) ; write('Число должно быть неотрицательным!'), nl ), interactive_demo. handle_choice(5) :- write('Введите число для бенчмарка: '), read(N), ( N >= 0 -> benchmark_predicates(N) ; write('Число должно быть неотрицательным!'), nl ), interactive_demo. handle_choice(6) :- write('До свидания!'), nl. handle_choice(_) :- write('Неверный выбор! Попробуйте снова.'), nl, interactive_demo.