Докато разглеждах темите от форума не открих тема с такова интересно заглавие. Има математически, логически задачи, конкретни проблеми за някакъв програмен език или проблеми за компилатори и интерпретатори. Надявам се да се намерят интересни идеи тук. Според мен най-подходящи за тук ще са езици като Pascal, C/C++, C#, Java или псевдокод.

И веднага към проблема който ме интересува в момента:

Факториел от голямо число. Някой може ли да ми предложи ефективен алгоритъм за намиране на факториел от голямо число (от порядъка на хиляди). Предполагам че се досещате какъв е проблема. Ще се радвам дори само на насочващи идеи.

= Никлаус Уирт Алгоритъма добре. В каква променлива ще запишеш такава стойност? Стандартните езици май не поддържат толкова големи целочислени стойности, а при реалните числа ще се загуби част от точността. Може би някой специализиран математически език ще ти свърши работа?

Редактирано 16 април 200719 г. от drahshta (преглед на промените)

Проблема е елементарен, но твърде време отнемащ. Прави се масив за цифрите на факторела и на всяка итерация се изчислява по този масив. Какво имам предвид: 0! = 1 т.е. 1 1! = 1 т.е. 1 2! = 2 т.е. 2 3! = 6 т.е. 6 4! = 42 т.е. 24 5! = 021 т.е. 120 6! = 027 т.е. 720 На всяка итерация се използва обърнат масив и постепенно се увеличават елементите на масива. И така до където си пожелаете. Ако имате търпение.

Проблема е елементарен, но твърде време отнемащ.

Прави се масив за цифрите на факторела и на всяка итерация се изчислява по този масив.

Какво имам предвид:

0! = 1 т.е. 1

1! = 1 т.е. 1

2! = 2 т.е. 2

3! = 6 т.е. 6

4! = 42 т.е. 24

5! = 021 т.е. 120

6! = 027 т.е. 720

На всяка итерация се използва обърнат масив и постепенно се увеличават елементите на масива.

И така до където си пожелаете. Ако имате търпение.

Всеки байт кодира 256 символа. Мисля, че може да се спести огромна част от изчсленията като се използва друга бройна система вместо десетичната. 100-тична например. И двумерен масив от 100x100 елемента за пресмятанията.

Проблема е елементарен, но твърде време отнемащ.

Прави се масив за цифрите на факторела и на всяка итерация се изчислява по този масив.

Какво имам предвид:

0! = 1 т.е. 1

1! = 1 т.е. 1

2! = 2 т.е. 2

3! = 6 т.е. 6

4! = 42 т.е. 24

5! = 021 т.е. 120

6! = 027 т.е. 720

На всяка итерация се използва обърнат масив и постепенно се увеличават елементите на масива.

И така до където си пожелаете. Ако имате търпение.

Първо размерът на масивите не може да се променя (освен ако не се използва някаква динамична структура), но и тогава проблемът си остава. Винаги сметките са много и размерът на получавщото се число е голям (това е особено затрудняващо. Погледнете колко голямо число например се получава от 5000!. Как да се направи умножението например на 3000 цифрено число със следващото с единица по-голямо?

За целта просто трябва да се направят така наречените "дълги числа". Да се пазят в някаква динамична структура - char* е най-простото (но и доста памет хаби). Може да се направи примерно масив от unsigned int или други разновидности и да се напише след това операцията умножение върху съответната структура. Има и един друг алгоритъм за ускорено умножение, но знам само, че го има. Добра идея е тази структура да се направи на клас и да се предефинира оператора * и евентуално за извеждане и въвеждане - така ще можеш да работиш с нея съвсем като с обикновена променлива.

Редактирано 16 април 200719 г. от Styx (преглед на промените)

Първо размерът на масивите не може да се променя (освен ако не се използва някаква динамична структура), но и тогава проблемът си остава.

Заделяш нов, по-голям масив, копираш стария и го освобождаваш . Бих ти предложил същото - да използваш 100-тична бойна система. Преобразуването от и в десетична е елементарно и ще намалиш драстично броят на пресмятанията - при 4 цифрено число в десетична ще имаш 2-цифрено в стотична. Или можеш да го погледнеш така - работиш в десетична, но обработваш цифрите 2x2.

Това върху което исках да наблегна, е че се използва тип динамичен масив (символи или числа), а не тип число. Използването на 100-чна вместо 10-чна бройна система спестява памет, а може и да увеличи скоростта. А защо да не се използва по-голяма бройна състема. например 256 или 512?

Това върху което исках да наблегна, е че се използва тип динамичен масив (символи или числа), а не тип число.

То и не може да се използва число. Ако не се лъжа в C/C++ най-голямата целочислена променлива величина е 64 битова - очевидно недостатъчно за такива изчисления. Ако се използва floating point променлива стойностата може и да е в допустимият обхват, но ще се изгуби от точността.

С 100-тична е мързеливо решение - спестява се преобразуването. Вероятно не особено ефективно.

Предполагам, че най-ефективното от към скорост решение е да се работи на assembler и да се използва максималната широчина на регистрите на съответният процесор. Но пък ще бъде голяма играчка. И като че ли идеята на vennik е по-различна - намиране на абстрактно алгоритмично решение на задачата?

Редактирано 17 април 200719 г. от drahshta (преглед на промените)

То и не може да се използва число. Ако не се лъжа в C/C++ най-голямата целочислена променлива величина е 64 битова - очевидно недостатъчно за такива изчисления. Ако се използва floating point променлива стойностата може и да е в допустимият обхват, но ще се изгуби от точността.

С 100-тична е мързеливо решение - спестява се преобразуването. Вероятно не особено ефективно.

Предполагам, че най-ефективното от към скорост решение е да се работи на assembler и да се използва максималната широчина на регистрите на съответният процесор. Но пък ще бъде голяма играчка. И като че ли идеята на vennik е по-различна - намиране на абстрактно алгоритмично решение на задачата?

Какво имаш предвид с това за 100-чна бройна система? Например числото 95 как ще изглежда в нея?

Докато разглеждах темите от форума не открих тема с такова интересно заглавие. Има математически, логически задачи, конкретни проблеми за някакъв програмен език или проблеми за компилатори и интерпретатори. Надявам се да се намерят интересни идеи тук. Според мен най-подходящи за тук ще са езици като Pascal, C/C++, C#, Java или псевдокод.

И веднага към проблема който ме интересува в момента:

Факториел от голямо число. Някой може ли да ми предложи ефективен алгоритъм за намиране на факториел от голямо число (от порядъка на хиляди). Предполагам че се досещате какъв е проблема. Ще се радвам дори само на насочващи идеи.

Лично аз съм решавала тази задача като се вкарва всяка от цифрите в масив, прави се умножение и събиране на масивите като умножение и събиране на числата и оттам и факториел на големи числа За друго не съм се сещала

Лично аз съм решавала тази задача като се вкарва всяка от цифрите в масив, прави се умножение и събиране на масивите като умножение и събиране на числата и оттам и факториел на големи числа За друго не съм се сещала

Да, интересна идея. Обаче трябва да е известен предварително броят на цифрите на резултата, за да се декларира масива. Може да се използва динамична структура, но как най-ефективно и изобщо по какъв начин извършваш самото умножение в изчисленето на факториел с така представените числа?

Редактирано 15 октомври 200718 г. от vennik (преглед на промените)

Да, интересна идея. Обаче трябва да е известен предварително броят на цифрите на резултата, за да се декларира масива. Може да се използва динамична структура, но как най-ефективно и изобщо по какъв начин извършваш самото умножение в изчисленето на факториел с така представените числа?

Сложно ми е да го обяснявам тука, но общо взето прави се процедура за умножение на масивите, след което я извиквам N на брой пъти като всеки път резултата се пази в едномерен масив от 100 елемента. Така има резултат докато N! е с не-повече от 10 цифри. Като каза обаче динамична структура трябва да пробвам дали евентуално със стек или опашка не може да се реализира тази идея, така ще е по-ефективно

Има един известен начин за умножение по метода с младшите разряди напред по схемата с неподвижно множимо, който се реализира в някой логически схеми. Има и някой оптимизации при умножението които са малко по-сложни за реализиране. Обаче ми се струва, че може самата процедура по изчисляване на факториел да не се извършва по определение, а да се използва някакъв съкратен начин. Преди време бях попаднал на някакви математически теории за по-кратко изчисление на факториел, но нищо не си спомням. Като цяло изчислението на факториел е тежка операция и каквито и оптимизации по отношение на използваните структури от данни или операцията умножение да се правят, ако то се извършва по определение (т.е. да се изчислява по следния начин: n! = 1x2x3x ... xn) при числа n от порядъка на 10^3 -10^4 и нагоре ще се получава значително забавяне при сегашните изчислителни способности на компютрите. Пък и по-важно е алгоритъма да е максимално ефективен, отколкото да се използва много мощен компютър за решаването на даден проблем. Какво е бързодействието при твоята реализация?

Сложно ми е да го обяснявам тука, но общо взето прави се процедура за умножение на масивите, след което я извиквам N на брой пъти като всеки път резултата се пази в едномерен масив от 100 елемента. Така има резултат докато N! е с не-повече от 10 цифри. Като каза обаче динамична структура трябва да пробвам дали евентуално със стек или опашка не може да се реализира тази идея, така ще е по-ефективно

Има един известен начин за умножение по метода с младшите разряди напред по схемата с неподвижно множимо, който се реализира в някой логически схеми. Има и някой оптимизации при умножението които са малко по-сложни за реализиране. Обаче ми се струва, че може самата процедура по изчисляване на факториел да не се извършва по определение, а да се използва някакъв съкратен начин. Преди време бях попаднал на някакви математически теории за по-кратко изчисление на факториел, но нищо не си спомням. Като цяло изчислението на факториел е тежка операция и каквито и оптимизации по отношение на използваните структури от данни или операцията умножение да се правят, ако то се извършва по определение (т.е. да се изчислява по следния начин: n! = 1x2x3x ... xn) при числа n от порядъка на 10^3 -10^4 и нагоре ще се получава значително забавяне при сегашните изчислителни способности на компютрите. Пък и по-важно е алгоритъма да е максимално ефективен, отколкото да се използва много мощен компютър за решаването на даден проблем. Какво е бързодействието при твоята реализация?

Е не съм го смятала, но има и една формула за n!=n*(n-1)! но за друга не си спомням да има

Това се свежда към основния вариант.

Е не съм го смятала, но има и една формула за n!=n*(n-1)! но за друга не си спомням да има

Ако към масива ще се добавят неизвестен, предварително брой цифри, то по-добре да се ползва свързан списък.

Ако не ти е интересно сам да направиш реализацията, а се интересуваш по-скоро от резултата ползвай библиотека за числа с произволна точност. Например GMP. Доколкото знам система Mathematica ползва нея.

По темата, ето един сайт за Алгоритми и структури от данни и ако ще ползваш свързан списък виж упражнение 3 - свързан списък.