Самое оригинальное решение вычисления факториала на С++.

Форум » C/C++ » Самое оригинальное решение вычисления факториала на С++. » Ответить

Самое оригинальное решение вычисления факториала на С++.

Сыроежка: Я придумал оригинальное вычисление факториала, которое еще нигде по крайней мере мне не встречалось. Изюминка предложенного мною решения состоит не в том, что это самый эффективный метод, напротив, это не эффективный метод, а в том, что никто еще кроме меня о таком решении не додумался! Обычно распространены два метода решения. Первый - это написание рекурсивной функции. Например, [pre2]#include <iostream> unsigned long long factorial( unsigned long n ) { return ( ( n > 1 ) ? n * factorial( n - 1 ) : 1 ); } int main() { for ( unsigned long i = 0; i < 6; i++ ) { std::cout << factorial( i ) << std::endl; } }[/pre2] Этот вариант решения любят использовать преподаватели по программированию, когда объясняют рекурсию. Естественно при больших значениях n применении данной функции может привести к переполнению стека. Второй вариант связан с заменой рекурсивного вызова функции циклом внутри тела функции. [pre2]#include <iostream> unsigned long long factorial( unsigned long n ) { unsigned long long p = 1; while( 1 < n ) p *= n--; return ( p ); } int main() { for ( unsigned long i = 0; i < 6; i++ ) { std::cout << factorial( i ) << std::endl; } }[/pre2] Этот вариант решения значительно эффективнее первого предложенного варианта и часто встречается в профессиональных программах. Обычно этими двумя вариантами подход к рещению задачи вычисления факториала и заканчивается. А ттеперь мой вариант который я сам придумал и нигде до сих пор не встречал. Он забавен тем, что полностью построен на использовании библиотеки С++ STL. Метод Сыроежки вычисления факториала: [pre2]#include <iostream> #include <numeric> #include <functional> #include <vector> unsigned long long factorial( unsigned long n ) { unsigned long long p = 1; if ( n != 0 ) { std::vector<unsigned long> v( n ); std::iota( v.begin(), v.end(), 1 ); p = std::accumulate( v.begin(), v.end(), p, std::multiplies<unsigned long long>() ); } return ( p ); } int main() { for ( unsigned long i = 0; i < 6; i++ ) { std::cout << factorial( i ) << std::endl; } }[/pre2] Конечно он не эффективен, но зато ничего лишнего кроме использования стандартных алгоритмов в нем нет!

Ответов - 17

Вася: unsigned long fact(unsigned long i) { const unsigned long values[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600ULL}; if (i >= 0 && i < sizeof(values)/sizeof(values[0])) return values; throw std::runtime_error("Can't calculate factorial"); }

Сыроежка: Вася пишет: unsigned long fact(unsigned long i) { const unsigned long values[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600ULL}; if (i >= 0 && i < sizeof(values)/sizeof(values[0])) return values; throw std::runtime_error("Can't calculate factorial"); } Очень хорошо, что вы привели этот вариант. Он у меня как-то из головы вылетел, когда я хотел представить свой метод с помощью стандартных алгоритмов. Я заметил, что похоже, что теги форматирования искажают код. То есть скорей всего вы правильно написали return values[ i ];, но при форматировании квадтратные скобки с индексом возможно были "съедены"". У меня такое уже случалось.. Я просто вставляю пробелы внутри скобок вокруг индекса, и тогда текст при форматировании не исчезает. Теперь некоторые замечания по коду.Значения типа unsigned long всегда больше или равны 0. Поэтому проверку индекса [pre2]if (i >= 0 && i < sizeof(values)/sizeof(values[0])) [/pre2] можно упростить: [pre2]if ( i < sizeof(values)/sizeof(values[0])) [/pre2] В качестве значения исключения мне представляется лучше использовать исключение std::out_of_range. Оно более информативно. А в целом спасибо за предложенный вариант. Если будут еще варианты, то пишите. Соберем коллекцию функций вычисления факториалов. Мне, глядя на ваш вариант, пришла одна идея, как еще можно написать такую функцию. Если реализую, то здесь продемонстрнрую.

Сыроежка: Вот решение, на которое меня вдохновило решение, предложенное Вася . То есть я просто решил значения массива писать не вручную, так как можно допустить ошибку, а позволить это сделать компилятору. [pre2]#include <iostream> #include <stdexcept> template <unsigned long n> struct f { enum { v = f<n-1>::v * n }; }; template <> struct f<0> { enum { v = 1 }; }; unsigned long long factorial( unsigned long n ) { const unsigned long long value[] = { f<0>::v, f<1>::v, f<2>::v, f<3>::v, f<4>::v, f<5>::v, f<6>::v, f<7>::v, f<8>::v, f<9>::v, f<10>::v, f<11>::v, f<12>::v }; if ( n < sizeof( value ) / sizeof( *value ) ) return ( value[n] ); throw ( std::out_of_range( "factorial" ) ); } int main() { for ( unsigned long i = 0; i < 13; i++ ) { std::cout << factorial( i ) << std::endl; } }[/pre2] Если опечаток при вводе кода не сделал, то должно работать. В принципе сама функция factorial не нужна, так как можно непосредственно в код, там где требуется значение факториала, вставлять выражение вида f::v<10> Я в своем решении опирался на пример из книги Брюс Эккель и Чак Эллисон "Философия С++. Практическое программирование", которая оказалась под рукой. Попутно замечу, что похоже, MS VC++ 2010 не распознает макрос __func__, который введен в новом стандарте, так как у меня не получилось вставить этот макрос в строку с throw для генерации исключения. То есть вместо throw ( std::out_of_range( "factorial" ) ); я хотел написать просто throw ( std::out_of_range( __func__ ) );, но компилятор сообщил, что __func__ - неизвестный идентификатор.

Сыроежка: Следует добавить, что с появлением в новом стандарте С++ спецификатора constexpr наверное самое лучшее решение - это будет решение с рекурсивным вызовом функции вычисления факториала. Определение функции будет выглядеть следующим образом: [pre2] #include <iostream> constexpr unsigned long long factorial( size_t n ) { return ( ( n > 1 ) ? n * factorial( n - 1 ) : 1 ); } int main() { for ( unsigned long i = 0; i < 6; i++ ) { std::cout << factorial( i ) << std::endl; } }[/pre2] При таком определении функции она может вызываться на этапе компиляции для константных выражений.

ололеша: 2Сыроежка Изюминка предложенного мною решения состоит не в том, что это самый эффективный метод, напротив, это не эффективный метод, а в том, что никто еще кроме меня о таком решении не додумался! надулся как индюк. я первый, я первый... то, что ты реализовал это на быдлоязыке не значит, что ты придумал сам метод. этот метод очень популярен. мы в матлабе постоянно так находили факториал. prod(1:5) prod - обычная редуктивная функция, подобная приплюснутой accumulate, но уже заточена под накопление произведение. 1:5 генерирует массив. этот метод настолько популярен, что в матлабе даже нет специальной функции по вычислению факториала :) у вас с++ головного мозга, батенька. дальше собственного носа уже не видите. но давайте же посмотрим на плюсовское решение unsigned long long factorial( unsigned long n ) { unsigned long long p = 1; if ( n != 0 ) { std::vector<unsigned long> v( n ); std::iota( v.begin(), v.end(), 1 ); p = std::accumulate( v.begin(), v.end(), p, std::multiplies<unsigned long long>() ); } return ( p ); } наблюдается функциональный подход в абсолютно непригодном для этого стиля языке. как бы это выглядело в настоящем функциональном языке (define (fact n) (apply * (iota n 1))) (fact 6) ровно 2 строки, третью с вызовом не считаем. вообще очень весело наблюдать, как поклонники плюсов радуются фишкам нового стандарта. та же iota и в scheme, и в cl была с незапамятных времен. разработчики крестов не думая, тащат все популярные фичи из других языков, превратив и без того уродливый язык в помойку. Естественно при больших значениях n применении данной функции может привести к переполнению стека. очень резонное замечание. учитывая, что переполнение переменной произойдет в тысячи раз быстрее, чем переполнение стека. да и хвостовую рекурсию никто не отменял. Сыроежка, я тебе КРАЙНЕ РЕКОМЕНДУЮ присмотреться к языку D. КРАЙНЕ. для плюсанутого он идеален. вот пример "твоего метода" вычисления факториала на D import std.stdio; import std.range; import std.algorithm; size_t fact(size_t n) { return reduce!("a * b")(1, iota(1, n + 1)); } void main() { size_t f = fact(6); writeln(f); } вот тут уже более функциональный подход. учитывая, что D предназначен как для системного, так и для прикладного программирования, у него огромные преимущества перед крестами по синтаксису, стандартной библиотеке. и еще. если хочется посчитать факториал в компайл тайме, совсем не нужно переписывать алгоритм, достаточно вызвать функцию так: void main() { static size_t f = fact(6); writeln(f); } отличия от constexpr есть. 1. в в constexpr функции разрешено только return выражение. (хотя в моем примере тоже return выражение, функция fact могла быть сколь угодно сложной). по сути constexpr функция это синтаксический сахар над обычными рекурсивными шаблонами, которые применялись в c++98 для организации рекурсии. 2. если constexpr функции подать на вход неконстантные данные, она тихо-молча превращается в рантайм функцию. т.е constexpr просто пытается выполнить расчеты в компайлтайме. в D же, если бы я написал так void main() { size_t n = 6; static size_t f = fact(n); writeln(f); } компилятор бы отказался это компилировать, аргументируя соответствующей ошибкой. ПС: посмотрел ман по крестовой iota. они ее даже реализовать нормально не могли)))))) где шаг? где версия с range?

Сыроежка: Думаю, что вы представили очень полезный и познавательный материал. Естественно я писал про факториал в рамках языка С++, так как этот раздел посвящен С/С++. Очевидно, что алгоритм iota перешел в С++ из других языков. В этом ничего плохого нет, что разработчики стандарта стремятся включить в С++ те идеи, которые прошли проверку практикой в других языках. Это "сближает" мышление программистов. Часть стандарта С++, относящаяся к алгоритмам, очевидно представляется неполной и какой-то ущербной. Если вы смотрели мои темы, то я постоянно здесь указываю на их недостатки. Но ситуация не такая простая. На мои попытки внести изменения в этот раздел стандарта я встретил яростное сопротивление со стороны некоторых программистов, чаще всего российских. Главный аргумент состоит в том, что раздувается стандарт. Я не вижу в этом большой проблемы, так как эта часть стандарта носит скорее краткий справочный характер и нисколько не усложняет семантику самого языка. Эта часть стандарта может быть сколь угодно большой, так как к ней обычно обращаются по надобности лишь чтобы посмотреть синтаксис того или иного алгоритма и подобрать тот алгоритм, который наиболее выразительно раскрывает замысел кода программиста. Тем не менее мне предоставили карт-бланш на подготовку предложения по изменению стандарта в части алгоритмов. Я разбил свое предложение на две части. Одна часть касается алгоритма iota из заголовочного файла numeric. А вторая часть будет касаться всех остальных алгоритмов описанных в algorithm. По крайней мере будет, так сказать, предмет для обсуждения. Я собираюсь ввести три новых алгоритма iota - это iona_n, reverse_iota и reverse_iota_n. reverse-вресия этого адгоритма удобна, когда, например, имеешь дело с однонаправленным списком std:;forward_list. Так как для этого списка новые эелементы вставляются только в начало списка, то нужно иметь реверсивную iota, чтобы в конечном итоге получить список с элементами, значения которых изменяются по возрастанию от первого до последнего. Что касается рекомендуемого вами языка D, то я все никак не могу разобраться с С++. Когда наступит некоторый период насыщенности этим языком, то, я думаю, посмотрю и другие языки, включая D.

ололеша : 2Сыроежка то я все никак не могу разобраться с С++ жизнь не настолько длинная. Когда наступит некоторый период насыщенности этим языком, то, я думаю, посмотрю и другие языки, включая D. как ты тонко завуалировал словосочетание "когда начну блевать через нос". Естественно я писал про факториал в рамках языка С++, так как этот раздел посвящен С/С++. это не дает тебе право заявлять, что ты придумал метод, до которого никто не додумался. пс. профиль на гитхабе есть?

Сыроежка: ололеша пишет: это не дает тебе право заявлять, что ты придумал метод, до которого никто не додумался. Это я действительно сам додумался, так как не встречал этот метод ни на одном сайте, посвящященном С/С++. ололеша пишет: профиль на гитхабе есть? А это где? Наверное, раз я не знаю, что это такое, то нет.

ололеша: 2Сыроежка Это я действительно сам додумался, так как не встречал этот метод ни на одном сайте, посвящященном С/С++. я пытаюсь сказать, что в методе ничего нового нет. я тоже не встречал, чтоб кто-то в плюсах описывал итеративный процесс через рекурсивные функции. это же не значит, что никто не додумался до этого. просто неоптимально, когда есть ключевые слова для описания итераций. и высказывание а в том, что никто еще кроме меня о таком решении не додумался! просто смешно. поэтому я и сказал - надулся, как индюк. А это где? Наверное, раз я не знаю, что это такое, то нет. https://github.com/ и еще мне вот что интересно. ты часто шлешь багрепорты (судя другим твоим темам) разрабам вижуал студии. я этого просто понять не могу. зачем? есть же отличные открытые проекты - gcc, clang. где мало того, что можно отписать багрепорт, так еще и поучаствовать в разработке. или тебе предоставляют откаты? вот хоть убей - не пойму. зачем бесплатно помогать некрософту, если можно помочь сообществу, благо у тебя и знания, и опыт. тем более что микрософт уже начали забивать на кресты (что кстати, правильно). в 2010 студии интеллисенса например уже нет. без него в плюсах не очень комфортно (visual assist не в счет, это отдельный продукт. почему я должен платить за то, что должно быть в IDE по умолчанию?).

Сыроежка: У меня есть MS VC++ 2010. Поэтому естественно я обнаруживаю баги в процессе работы с ней. Это полезная информация и для других программистов, кто имеет дело с MS VC++.. Кроме того я могу ошибаться, что имеется баг. Поэтому получить отклик от разработчиков, их мнение об обнаруженном поведении компилятора также заслуживает внимания. Приведу такой интересный случай. Я послал им сообщение о баге, что в предложениях управления таких, как например, предложение for или while, в условиях нельзя использовать объявления переменных с классом памяти и в частности с классом памяти static. Я еще здесь не писал об этом баге. Так они мне прислали ответ, из которого следует, что они просто не знали, что это делать нельзя и просили указать место в стандарте, откуда это ограничение следует. То есть баг существует не из-за какой-то оплошности разработчиков, допущенной ими ошибки в виду некоторой сложной семантики языка, а просто потому, что они даже и не подозревали, что так делать нельзя.

ололеша: 2Сыроежка что мешает полностью перейти на свободные компиляторы?

Сыроежка: Для среды Windows с компилятором MS, то есть с их IDE, будет меньше заморочек, так как она включает в себя не С++, но и С#.

Сыроежка: Как говорится, век живи, век учись. Данную реализацию факториала, как функции со спецификатором constexpr можно улучшить, существенно уменьшив число рекурсивных вызовов. То есть вместо кода [pre2] constexpr unsigned long long factorial( size_t n ) { return ( ( n > 1 ) ? n * factorial( n - 1 ) : 1 ); } [/pre2] лучше использовать следующий код [pre2] constexpr unsigned long long factorial( size_t n ) { return ( ( n < 2 ) ? 1 : n * ( n - 1 ) * factorial( n - 2 ) ); } [/pre2]

ололеша : 2Сыроежка Как говорится, век живи, век учись. Данную реализацию факториала, как функции со спецификатором constexpr можно улучшить, существенно уменьшив число рекурсивных вызовов. То есть вместо кода лучше вообще использовать хвостовую рекурсию. вообще рекурсивных вызовов не будет, если компилятор нормальный и умеет оптимизировать оную.

Сыроежка: ололеша пишет: лучше вообще использовать хвостовую рекурсию. вообще рекурсивных вызовов не будет, если компилятор нормальный и умеет оптимизировать оную. Идея с хвостовой рекурсией хорошая, но я посмотрел код, который генерирует MS VC++ 2010 в релиз-версии, и к сожалению не обнаружил, чтобы компилятор использовал хвостовую рекурсию в сгенерированном коде. Вот исходный пример кода, который я проверял [pre2]#include "stdafx.h" int f( size_t i, int x ) { return ( ( i < 2 ) ? x : f( i - 1, i * x ) ); } int _tmain(int argc, _TCHAR* argv[]) { { f( 0, 1 ); } return 0; }[/pre2] А вот сгенерированный компилятором объектный код: [pre2]; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.40219.01 TITLE C:\Users\???????? ?????????\Documents\Visual Studio 2010\Projects\Book STL algorithm\factorial\factorial\factorial.cpp .686P .XMM include listing.inc .model flat EXTRN @__security_check_cookie@4:PROC PUBLIC ?f@@YAHIH@Z ; f ; Function compile flags: /Ogtp ; File c:\users\владимир григорьев\documents\visual studio 2010\projects\book stl algorithm\factorial\factorial\factorial.cpp ; COMDAT ?f@@YAHIH@Z _TEXT SEGMENT _i$ = 8 ; size = 4 _x$ = 12 ; size = 4 ?f@@YAHIH@Z PROC ; f, COMDAT ; 7 : { 00000 55 push ebp 00001 8b ec mov ebp, esp ; 8 : return ( ( i < 2 ) ? x : f( i - 1, i * x ) ); 00003 8b 4d 08 mov ecx, DWORD PTR _i$[ebp] 00006 8b c1 mov eax, ecx 00008 0f af 45 0c imul eax, DWORD PTR _x$[ebp] 0000c 49 dec ecx 0000d 83 f9 02 cmp ecx, 2 00010 72 0a jb SHORT $LN8@f 00012 50 push eax 00013 51 push ecx 00014 e8 00 00 00 00 call ?f@@YAHIH@Z ; f 00019 83 c4 08 add esp, 8 $LN8@f: ; 9 : } 0001c 5d pop ebp 0001d c3 ret 0 ?f@@YAHIH@Z ENDP ; f _TEXT ENDS PUBLIC _wmain ; Function compile flags: /Ogtp ; COMDAT _wmain _TEXT SEGMENT _argc$ = 8 ; size = 4 _argv$ = 12 ; size = 4 _wmain PROC ; COMDAT ; 14 : { ; 15 : f( 0, 1 ); ; 16 : } ; 17 : ; 18 : return 0; 00000 33 c0 xor eax, eax ; 19 : } 00002 c3 ret 0 _wmain ENDP _TEXT ENDS END[/pre2] Я выделил жирным синим шрифтом те строчки сгенерированного кода, из которых видно, что функция рекурсивно вызывается с занесением аргументов в стек, то есть никакой хвостовой рекурсии нет. Более того, похоже, что сгенерированный код вообще некорректный, так как в начале он производит перемножение параметров i на x. Если значение i равно 0, то получится неверный результат. Я послал в Майкрософт сообщение об этом баге, если конечно это действительно баг. Но я пока не вижу, что этот объектный код корректен. Так что не стоит рассчитывать на хвостовую рекурсию. Не каждый компилятор ее поддерживает. Может быть и есть такая возможность заставить компилятор MS VC++ 2010 генерировать код на основе хвостовой рекурсии, но мне она не известна.

ололеша: 2Сыроежка Идея с хвостовой рекурсией хорошая, но я посмотрел код, который генерирует MS VC++ 2010 в релиз-версии, и к сожалению не обнаружил, чтобы компилятор использовал хвостовую рекурсию в сгенерированном коде. лучше вообще использовать хвостовую рекурсию. вообще рекурсивных вызовов не будет, если компилятор нормальный и умеет оптимизировать оную. ага? #include <cstdio> int foo( size_t i, int x ) { return ( ( i < 2 ) ? x : foo( i - 1, i * x ) ); } int main() { int i = foo( 6, 1 ); printf("%d\n", i); return 0; } g++ main.cpp -O2 -S -masm=intel .file "main.cpp" .intel_syntax noprefix .text .p2align 4,,15 .globl _Z3foomi .type _Z3foomi, @function _Z3foomi: .LFB31: .cfi_startproc cmp rdi, 1 mov eax, esi jbe .L2 .p2align 4,,10 .p2align 3 .L4: imul eax, edi sub rdi, 1 cmp rdi, 1 ja .L4 .L2: rep ret .cfi_endproc .LFE31: .size _Z3foomi, .-_Z3foomi .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "%d\n" .text .p2align 4,,15 .globl main .type main, @function main: .LFB32: .cfi_startproc sub rsp, 8 .cfi_def_cfa_offset 16 mov edx, 720 mov esi, OFFSET FLAT:.LC0 mov edi, 1 xor eax, eax call __printf_chk xor eax, eax add rsp, 8 .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE32: .size main, .-main .ident "GCC: (Gentoo 4.5.3-r2 p1.5, pie-0.4.7) 4.5.3" .section .note.GNU-stack,"",@progbits вообще во время компиляции посчитал. если использовать не константу, то он инлайнит фукцию, приводя хвостовую рекурсию в линейный вид

Сыроежка: Тут возникает дилемма: то ли писать некоторый общий код, который может быть скомпилирован любым компилятором, рассчитывая на хвостовую рекурсию, то ли не надеятсья на ее применение. Дело в том, что часто тот код, который не рассчитан на хвостовую рекурсию, получается эффективнее кода с использованием хвостовой рекурсии при условии, что компилятор ее не поддерживает. То есть должна быть какая-то общая стратегия. Я не уверен, что в общем случае она должна быть в пользу хвостовой рекурсии, так как даже если некоторый компилятор поддерживает хвостовую рекурсию, то она включается лишь при определенных опциях режима компиляции, например, при некотором уровне оптимизации, который не обязательно должен вас устраивать в других отношениях.

полная версия страницы