Forth http://fforum.winglion.ru/ |
|
Проездной билет http://fforum.winglion.ru/viewtopic.php?f=19&t=1054 |
Страница 1 из 1 |
Автор: | chess [ Вт дек 04, 2007 15:05 ] |
Заголовок сообщения: | Проездной билет |
Предыстория: Еду в автобусе, покупаю билет. Получаю из числа на билете разными способами число 100, например так: 1) 35 7 7 / + 64 + 2) 35 7 7 / 64 + + 3) 3 fact 5 + 7 7 / - 6 4 - ^ 4) 3 5 * 7 7 / + 6 * 4 + 5) 35 77 + 6 4 sqrt * - 6) 35 77 + 6 antifact 4 * - 7) 3 fact 5 - 7 7 * + 6 4 - * и т. д. А теперь условие задачи: Получить форт-исходники, построенные с использованием функций из определенного их набора, дающие определенный результат ( число 100) при преобразовании случайного 6-ти разрядного десятичного числа набор функций ~ смена знака числа (NEGATE), использование цепочек типа ~ ~ .. - запрещено + сложение - вычитание * умножение / деление - может быть использовано когда нет остатка ( 56 5 / - применить нельзя) ^ возведение в степень ( 30 0 ^ даст 1, 3 3 ^ даст 27 ) v корень n степени - может быть использован когда число является степенью ( 27 3 v даст 3) s корень квадратный - может быть использован когда число является квадратом ( 25 s даст 5 ) ! факториал i антифакториал - может быть использован когда число является факториалом ( 120 i даст 5 ) Вход - случайные 6-ти значные десятичные числа ( 564502 502564 123234 578434 708762 ...) Выход - вывод в консоль или в файл форт-исходников, дающих в результате их выполнения число 100 Основное условие - ПОРЯДОК ЦИФР В ЗАПИСИ КАЖДОГО ИСХОДНИКА ДОЛЖЕН ТОЧНО СООТВЕТСТВОВАТЬ ПОРЯДКУ ЭТИХ ЦИФР В ЗАПИСИ ВХОДНОГО ЧИСЛА Еще один пример, теперь уже в синтаксисе из заданного в наборе функций: на вход поступило число 564502 На выходе ваша программа сформировала такой например результат 56 4 - 50 2 - + 5 6 4 + * 5 0 * + 2 * 5 ~ 6 + 4 50 2 / * * 5 6 - ~ 4 50 * * 2 / 5 6 - ~ 4 50 * 2 / * 5 6 - 4 50 * 2 / ~ * количество результатов = 6 Получить общий результат для 100 случайных чисел - сумму результатов для каждого из этих 100 чисел, (допускается использовать только часть функций из их набора). Цель - получить максимальный результат(время вычисления - фактор незначимый) |
Автор: | profiT [ Ср дек 05, 2007 14:00 ] |
Заголовок сообщения: | |
--- |
Автор: | chess [ Ср дек 05, 2007 16:24 ] |
Заголовок сообщения: | |
profiT есть profiT. Во-первых: начато-сделано. Во-вторых: Раз перебор, то конечно ~profit/lib/bac4th.f. Программа работает корректно. Ограничения реализации(все они не запрещены условием задачи): 1. входные числа разбиваются только на одно и/или двух разрядные числа. 2. из заданного набора функций взяты не все функции. 3. функции используются после забрасывания всех чисел на стек Поэтому при 100 stack-ops-galore выдается результат всего в ~ 1000 вариантов. Введем понятие IQ для программ такого типа. Пусть это будет суммарный результат для N(здесь это 100) входных параметров(похоже 100 в данном случае - репрезантивно). IQ(stack-ops-galore)=1000. Это конечно далеко от максимума. Между делом вспомнил о Wormball. Такого рода варианты программ, можно заставить жить и размножаться в сетях( при этом "генетически" и "естественно-отборно" в итоге получить реализацию с максимальным IQ). Числа - пища, преобразование - ее усвоение, если усвоил выше порога - то родил(копия), не усвоил ниже другого порога - умер, сделать объем пищи общим(для конкуренции), для повышения быстродействия ввести фактор времени и т.д. и т.п. |
Автор: | profiT [ Ср дек 05, 2007 17:37 ] |
Заголовок сообщения: | |
--- |
Автор: | chess [ Ср дек 05, 2007 18:09 ] |
Заголовок сообщения: | |
Цитата: PS. Обратите внимание на применённый арсенал средств: ООП (hype3), таблицы переходов (chartable.f), бэкфорт -- работают все вместе. Не слабо - но и задачка не очень легкая. Цитата: А вот это уже знаю, по-моему тебе просто не попались такие варианты... Да - я смотрел только на результаты. Цитата: Но именно потому я их заблокировал что они очень сильно увеличивают перебор. Очень сильно. Что - все виснет - не дождаться. Может дать фикс. интервал времени и выйти. Цитата: Другие функции мне просто было лень делать -- вроде "антифакториала"...
Что так, это всего лишь дихотомия на таблице из 13 факториалов, зато IQ сильно повысит. |
Автор: | chess [ Пт дек 07, 2007 19:05 ] |
Заголовок сообщения: | |
Некоторые замечания после раскомментирования fact и ~ если операнд отрицательный, то факториал для него не существует, а ты анализ знака операнда нигде не делаешь Код: : fact DUP 2 < IF DROP 1 ELSE 1 SWAP 1+ 1 ?DO I * LOOP THEN ; -5 fact ( 1 ) CODE fact 591F20 8945FC MOV FC [EBP] , EAX 591F23 8945F8 MOV F8 [EBP] , EAX 591F26 B802000000 MOV EAX , # 2 591F2B 3B45F8 CMP EAX , F8 [EBP] 591F2E 0F9EC0 SETLE AL 591F31 83E001 AND EAX , # 1 591F34 48 DEC EAX 591F35 8D6DFC LEA EBP , FC [EBP] 591F38 0BC0 OR EAX , EAX 591F3A 8B4500 MOV EAX , 0 [EBP] 591F3D 8D6D04 LEA EBP , 4 [EBP] 591F40 0F8410000000 JE 591F56 ( fact+36 ) 591F46 8B4500 MOV EAX , 0 [EBP] 591F49 894500 MOV 0 [EBP] , EAX 591F4C B801000000 MOV EAX , # 1 591F51 E950000000 JMP 591FA6 ( fact+86 ) 591F56 8945FC MOV FC [EBP] , EAX 591F59 B801000000 MOV EAX , # 1 591F5E 8B55FC MOV EDX , FC [EBP] 591F61 8945FC MOV FC [EBP] , EAX 591F64 8BC2 MOV EAX , EDX 591F66 8D4001 LEA EAX , 1 [EAX] 591F69 8945F8 MOV F8 [EBP] , EAX 591F6C B801000000 MOV EAX , # 1 591F71 BBA61F5900 MOV EBX , # 591FA6 591F76 3B45F8 CMP EAX , F8 [EBP] 591F79 7505 JNE 591F80 591F7B 8B45FC MOV EAX , FC [EBP] 591F7E FFE3 JMP EBX 591F80 53 PUSH EBX 591F81 BB00000080 MOV EBX , # 80000000 591F86 2B5DF8 SUB EBX , F8 [EBP] 591F89 53 PUSH EBX 591F8A 03D8 ADD EBX , EAX 591F8C 53 PUSH EBX 591F8D 8B45FC MOV EAX , FC [EBP] 591F90 8945FC MOV FC [EBP] , EAX 591F93 8B0424 MOV EAX , [ESP] 591F96 2B442404 SUB EAX , 4 [ESP] 591F9A F76DFC IMUL FC [EBP] 591F9D FF0424 INC [ESP] 591FA0 71EE JNO 591F90 591FA2 8D64240C LEA ESP , C [ESP] 591FA6 C3 RET NEAR END-CODE Для скорости fact лучше сделать на ассме Код: : fact B=A $ -1 B=aB L1: *B B-- L1 JNZ ; CODE fact 591FC0 8BD8 MOV EBX , EAX 591FC2 8D5BFF LEA EBX , FF [EBX] 591FC5 F7EB IMUL EBX 591FC7 4B DEC EBX 591FC8 75FB JNE 591FC5 591FCA C3 RET NEAR END-CODE С числами-разложениями исходного числа на стеке при переборе происходят нелады(краевые д'эффекты похоже - не вникал) Код: 673219
.............................................. 6 7 3 ~ fact ~ fact ~ * fact - 2 1 9 + * * 6 7 3 ~ fact ~ fact ~ * fact - 21 9 ~ fact - * 6 7 3 ~ fact ~ fact ~ * * 2 29 ~ * ~ - ~ 6 7 3 ~ fact ~ fact ~ * * 2 29 ~ * + ~ ............................................. 6 73 2 2 * fact + - ~ 9 ~ - 6 73 2 2 * fact + - ~ 9 + 6 73 ~ fact ~ fact ~ fact - 2 7 ~ fact 9 + * * 6 73 ~ fact ~ fact ~ fact - 2 * 7 ~ fact 9 + * ............................................. 6 7 ~ 3 2 * fact + - ~ 7 / 9 ~ fact - 6 7 ~ 3 2 * fact + - ~ 7 / 9 fact ~ fact - 6 7 ~ 32 ~ fact ~ fact ~ fact ~ * + 7 * 9 + 6 7 ~ 32 ~ + ~ - 3 ~ * 9 ~ fact ~ fact + 6 7 ~ 32 ~ + ~ - 3 ~ * 9 ~ fact ~ - ............................................. и потом снова 673229 и т.д., хотя перебор функций вроде нормально при этом идет Немного насчет перебора вообще Процы Неймана и Гарварда и новые и старые не приспособлены к переборным алгоритмам Тянуть перебор программно - это дикие тормоза даже если оптимизировать код. Нужна систолическая аппаратная структура(лучше перестраиваемая из программы - под разные алгоритмы перебора, еще лучше перед этим описанная в самой программе - типа ПЛИС) в самом ядре проца. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |