link3408 link3409 link3410 link3411 link3412 link3413 link3414 link3415 link3416 link3417 link3418 link3419 link3420 link3421 link3422 link3423 link3424 link3425 link3426 link3427 link3428 link3429 link3430 link3431 link3432 link3433 link3434 link3435 link3436 link3437 link3438 link3439 link3440 link3441 link3442 link3443 link3444 link3445 link3446 link3447 link3448 link3449 link3450 link3451 link3452 link3453 link3454 link3455 link3456 link3457 link3458 link3459 link3460 link3461 link3462 link3463 link3464 link3465 link3466 link3467 link3468 link3469 link3470 link3471 link3472 link3473 link3474 link3475 link3476 link3477 link3478 link3479 link3480 link3481 link3482 link3483 link3484 link3485 link3486 link3487 link3488 link3489 link3490 link3491 link3492 link3493 link3494 link3495 link3496 link3497 link3498 link3499 link3500 link3501 link3502 link3503 link3504 link3505 link3506 link3507 link3508 link3509 link3510 link3511 link3512 link3513 link3514 link3515 link3516 link3517 link3518 link3519 link3520 link3521 link3522 link3523 link3524 link3525 link3526 link3527 link3528 link3529 link3530 link3531 link3532 link3533 link3534 link3535 link3536 link3537 link3538 link3539 link3540 link3541 link3542 link3543 link3544 link3545 link3546 link3547 link3548 link3549
C++ Builder
| Главная | Уроки | Статьи | FAQ | Форум | Downloads | Литература | Ссылки | RXLib | Диски |

 
С++ и факториал, Факториал
** Vital_K
Отправлено: 15.03.2005, 20:25


Не зарегистрирован







Приветствую вас, неутомимые странники по просторам необъятного с++. Подскажите пож, почему в с++ (простом — turboс++) я не могу вычеслить факториал 10. Почему неправильное число получается.
Спасибо заранее.
klen
Отправлено: 16.03.2005, 07:31


Машинист паровоза

Группа: Участник
Сообщений: 239



А почему мне зарплату 3 месяца не платят??? Не знаешь?

Ты хоть выложи свой кривокод, тады и будем вместе разбиратся. Или предлогаешь мне угадать?



CODE

__int64 Fack = 1;
 int Pow = 3;
 if ( Pow )
   for (int i = 1; i <= Pow; i++)
    {
     Fack *= i;
    }
Guest
Отправлено: 17.03.2005, 09:02


Не зарегистрирован







Упссс, да, вот он код
CODE

#include<stdio.h>
#include<conio.h>
faktorial(int n)
{
int i;
int p=1;
for(i=1;i<=n;i++)
p*=i;
return p;
}


main()
{

int k;
int i;
clrscr();
printf("Vvedite chislo:");
scanf("%i",&k);
for(i=1;i<=k;i++)
printf("%i\t",faktorial(i));
getch();


}


Отредактировано Георгий — 17/03/2005, 10:23
AVC
Отправлено: 17.03.2005, 09:28


Ветеран

Группа: Модератор
Сообщений: 1583



QUOTE

я не могу вычеслить факториал 10. Почему неправильное число получается.


CODE

void __fastcall TF_Main::BitBtn1Click(TObject *Sender)
{
int i;
int p=1;
for(i=1;i<=10;i++) p*=i;

ShowMessage(AnsiString(1*2*3*4*5*6*7*8*9*10) + "\n" + AnsiString(p));
// видим
// 3628800
// 3628800
}


И что вам не нравиться?
Для больших чисел лучше вместо int использовать int64 или double
А если ваш код для DOS то там int == int16 — птшите хотя бы long
AVC
Отправлено: 17.03.2005, 09:35


Ветеран

Группа: Модератор
Сообщений: 1583



Для DOS так работает
CODE

#include <stdio.h>

long faktorial(int n) // ------------------------
{
int i;
long p=1; // -------------------------------
for(i=1;i<=n;i++)
p*=i;
return p;
}

main()
{
int k;
int i;
clrscr();
printf("Vvedite chislo:");
scanf("%i",&k);
for(i=1;i<=k;i++)
printf("%ld\n", faktorial(i)); // ---------------------------
getch();
return 0;
}
Георгий
Отправлено: 17.03.2005, 10:29


Почетный железнодорожник

Группа: Модератор
Сообщений: 874



размер int — системнозависимый. под 16 битными ОС и средствами разработки под них int = 16 бит. в 32х битных (например cbuilder под MS windows)

соответственно 10!> 32 000 что приводит к банальному переполнению.

если всё это необходимо для выполнения чего-нибудь в роде лабораторной работы, то используйте double или long double
Vital_K
Отправлено: 18.03.2005, 07:12


Ученик-кочегар

Группа: Участник
Сообщений: 27



Большое спасибо....
erzzz
Отправлено: 17.10.2006, 17:06


Ученик-кочегар

Группа: Участник
Сообщений: 2



Доброго времени суток товарищи. Тут в общем такой вот вопросик. Факториал 10 — это нормально. Но мне потребовалось для работы высчитать факториал чисел, больших или равных 100000. Переполнение здесь налицо. Каким методом можно все это дело описать чтобы работало. int, double, long int и т.д. отдыхают. Может кто знает. Заранее благодарю.
Grigoriy
Отправлено: 17.10.2006, 17:49


Мастер участка

Группа: Участник
Сообщений: 381



QUOTE (erzzz @ 17.10.2006, 18:06)
Но мне потребовалось для работы высчитать факториал чисел, больших или равных 100000. Переполнение здесь налицо.

Здравствуйте, erzzz.

Вам бы лучше было бы не оперировать с большими числами, а оперировать с дробями, делимое и делитель которых — это большие числа.

Я правильно подсказываю ?

К примеру, функция ЭКСПОНЕНТА (e в степени x) вычисляется так

EXP = 1+x/1!+x^2/2!+x^3/3!+x^4/4! ......

но это не означает, что необходимо вычислять значения фактериалов wink.gif smile.gif

просто нужно вычислять значения дробей такого ряда

x/1, x/2, x/3, x/4 ....

а потом каждую из этих дробей необходимо умножать на полученный промежуточный результат предыдущего умножения и мы будем получать значения что-то вроде

x^100/100!

без вычисления 100!
таким образом
CODE

double sgi_exp(double a)
{
double pr1=1;//значение члена ряда
double S=1;//сумма ряда
int c=0;//счетчик
while (pr1>10E-18) S+=(pr1*=a/(++c));
return S;
};


А какая у вас задача ?

Отредактировано Grigoriy — 17.10.2006, 20:28
erzzz
  Отправлено: 17.10.2006, 22:16


Ученик-кочегар

Группа: Участник
Сообщений: 2



Добрый день, или вечер, а может и ночь Grigoriy.
Брат работает на одном столичном предприятии. Так вот периодически они там такой х***** страдают. Им и потребовался ряд чисел, которые равны 10! 100! 1.000! 10.000! 100.000! 1.000.000! ... 100.000.000.000! Для чего — сам не знаю. Просто стало самому интересно. Вот и полез даже за советом.

А если это все дело организовать через строки, а потом их просто умножать как в школе столбиком по коду символа??? Как вариант это можно рассмотреть???
Grigoriy
Отправлено: 18.10.2006, 03:51


Мастер участка

Группа: Участник
Сообщений: 381



Ну так вот я и утверждаю, что нет в любом случае никакой необходимости оперировать с числами большими чем (20!), а вообще всегда можно обойти машинное переполнение значения числа.

Для любой задачи существует бесконечное множество методов решений и максимальной сложностью эти методы не ограничиваются.

Если вам известно, дорогой друг, что один ученый потратил 40 лет жизни для того, чтобы посчитать число PI с точностью до 12 знака, и известен ряд
ArcTangens и формулы кратных углов, то я могу с 100% уверенностью вам утверждать, что с помощью ряда Тейлора для Арктангенса и формулы тангенса половинного угла можно было бы посчитать ЭТО ЧИСЛО с той же точностью за 1 ДЕНЬ. И знаете почему такая разница в количестве операций ? Потому что жизнь так хороша и прекрасна !
Ну, еще есть вот такой ряд для PI

1 — 1/3 + 1/5 — 1/7 + 1/9 — ... = PI/4

Теперь посудите сами, сколько операций нужно выполнить для точности до 18 десятичного знака, а ведь ряд то правильный...

QUOTE

А если это все дело организовать через строки, а потом их просто умножать как в школе столбиком по коду символа???

ХЕ-ХЕ-ХЕ !
Ну и что потом нужно делать с этими большущими числами ?
Что это они будут означать ?
Количество денег ? Или количество товаров ? А может это объем топлива ?
Ну теперь подумайте сами и убедитесь, ну это бред дохлого зайца... с такими числами работать.
100.000.000.000! — ну да мне вообще смешно ! biggrin.gif biggrin.gif biggrin.gif biggrin.gif

А может нужно выполнить вот это
100.000.000.001! / 100.000.000.000!
Ну тогда оно будет равно вот этому
100000000001
Так что, обязательно вычислять оба факториала ?
Не чудите.
AVC
Отправлено: 18.10.2006, 08:37


Ветеран

Группа: Модератор
Сообщений: 1583



QUOTE (erzzz @ 17.10.2006, 17:06)
Доброго времени суток товарищи. Тут в общем такой вот вопросик. Факториал 10 — это нормально. Но мне потребовалось для работы высчитать факториал чисел, больших или равных 100000. Переполнение здесь налицо. Каким методом можно все это дело описать чтобы работало. int, double, long int и т.д. отдыхают. Может кто знает. Заранее благодарю.

Разработать собственный класс. Частный случай — хранить число как строку, но лучше просто в последовательности байтов заранее известного размера. Так как предпологается только целочисленная арифметика то перекрыть операции будет не сложно. "Умножение в столбик" вспомнить придется.

PS. Помнится Константин поднимал подобную тему. Но могу и ошибаться.
Konstantine
Отправлено: 18.10.2006, 11:31


Мастер участка

Группа: Модератор
Сообщений: 545



AVC, да, делал я когда-то такое. приятно когда помнют victory.gif rolleyes.gif
но 100000! вы будете долго вычислять. всё-таки проц не резиновый

если грубо прикинуть, то 1000! будет состоять где-то из миллиона знаков. и соответственно вычисления — даже с ММХ технологией на сложение 2-х таких чисел уйдёт 62.500 тактов, т.е. ~0.02 мсек !!! а чтоб помножить в столбик — нужна 1000 таких сложений — т.е. 2 секунд wizard.gif . одно умножение! а факториал 1000 — это 1000 умножений.
да, 1000! реально сделать, но дальше ж — больше...
1001! = это на 3 знака больше, и т.д...
вот и думайте, господа cool.gif

а, да, и писАть-то придётся не на С а в ассемблерной вставке — а то проиграете время раз в 10 (точно говорю — недавно писал и сравнивал)

P.S.: возможно есть ошибки в расчётах — я их писАл быстро по первой мысли, просто чтоб доказать что время не резиновое.
Konstantine
Отправлено: 18.10.2006, 11:52


Мастер участка

Группа: Модератор
Сообщений: 545



если нужно не очень точно — то используйте long double
его числа могут быть:
3.37 10^-4932 < |X| < 1.18 10^4932
т.е. 4932 знака. можно ухитряться и хранить намного большие числа, но точность будет падать (ну храняться первые N цифр числа)
Konstantine
Отправлено: 18.10.2006, 11:57


Мастер участка

Группа: Модератор
Сообщений: 545



статейка в тему:
http://algolist.manual.ru/maths/longnum.php
там же приведен график времени от разрядности (на 2002 год)
Zor
Отправлено: 21.11.2006, 15:00


Ученик-кочегар

Группа: Участник
Сообщений: 4



2 Konstantine
Двоечник! long double 19-20 знаков максимум
olegenty
Отправлено: 21.11.2006, 15:07


Ветеран

Группа: Модератор
Сообщений: 2412



2 Zor — тебя кто-то обманул насчёт 19-20 знаков.
Zor
Отправлено: 23.11.2006, 15:21


Ученик-кочегар

Группа: Участник
Сообщений: 4



Нуууу... если даже Модератор думает, что в 80бит можно впихнуть больше 20 знаков... Я пас.
Куда катится наше образование...
AVC
Отправлено: 23.11.2006, 16:18


Ветеран

Группа: Модератор
Сообщений: 1583



А нечего путать "знаков" и "значащих разрядов".
Konstantine
Отправлено: 23.11.2006, 17:55


Мастер участка

Группа: Модератор
Сообщений: 545



тема перевалила в другое русло.
я точно не помню, но лонг дабл — больше 2^4000
а чтоб не писать неточно — у яндекса спросил...

Вернуться в Вопросы программирования в C++Builder