Посчитать факториал до 1000

#cpp #c

Задача № 18 Посчитать факториал до 1000 (ACMP.RU).
Задание не проходит по 10 тесту, хотя 1000! считает правильно (проверил первые 20
знаков, сравнивая с Вольфрам Альфа). Второй день ищу ошибку и не могу найти
#include 

int main(int argc, char *argv[])
{
    unsigned long int a[6000] = { }, n, b[6000] = {
    }, t;
    freopen("INPUT.TXT", "r", stdin);
    freopen("OUTPUT.TXT", "w", stdout);
    scanf("%d", &n);
    if (n < 0) {
        printf("0");
        return 0;
    }
    a[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 6000; j++) {
            t = a[j] * i;
            b[j] = b[j] + t % 100000;
            b[j + 1] = b[j + 1] + t / 100000;
        }
        for (int j = 5999; j >= 0; j--) {
            a[j] = b[j];
            b[j] = 0;
        }
    }
    int i = 5999;
    while (a[i] == 0) {
        i--;
        if (a[i] != 0)
            printf("%d", a[i]);
    }
    i--;

    for (int j = i; j >= 0; j--) {
        if (a[j] / 10000 == 0)
            printf("0");
        if (a[j] / 1000 == 0)
            printf("0");
        if (a[j] / 100 == 0)
            printf("0");
        if (a[j] / 10 == 0)
            printf("0");
        printf("%d", a[j]);
    }
}

Заранее спасибо всем, кто откликнется.
Задачу решил с помощью Java из-за того, что в яве не нужно парится с длинной арифметикой.
Вот код:
import java.math.BigInteger;
import java.io.*;
import java.util.Scanner;

/**
 *
 * @author StalinZ
 */
public class Main  {
   public static void main(String[] args) throws FileNotFoundException {
       new Main().run();

}
   PrintWriter pw;
   Scanner sc;

    private void run() throws FileNotFoundException {
   sc = new Scanner(new File("input.txt"));
   int a=sc.nextInt();
   pw = new PrintWriter(new File("output.txt"));
   BigInteger ret =BigInteger.ONE ;
   for (int i=1;i<=a;i++) ret =  ret.multiply(ret.valueOf(i));
   pw.print(ret.toString());
   pw.close();
    }
}

Правда я заметил, что ява жрёт больше памяти    

Ответы

Ответ 1

Только что решил задачку сам, проверил, получил accepted. 


Конкретно ваша программа, например, фейлится на тесте n = 999 и выводит один лишний
ноль. Почему это происходит, подсказывать не буду, думаю вам самому интересно будет
разобраться.



Если что, то мое решение можно посмотреть на pastie.org


Ответ 2

Вообще есть неплохой метод нахождения факториалов и сумм ряда. Заключается он в перемножении
произведений крайних членов друг на друга( для факториала ) и в сложении крайних членов
и последующим умножением на длину ряда(N) деленную на 2. Вот примеры сказанного:

Для факторила:

N(5) = (1*5) * (2*4) * (3)  // как видно, каждый раз перемножаем крайние члены.
N(7) = (1*7) * (2*6) * (3*5) * (4)




Для суммы ряда:

Sum(6) = 7*3 => (1+6=7), (2+5=7), (3+4=7) = 21
Sum(5) = 5*3 => (5+0=5), (4+1=5), (3+2=5) = 15




P.S
Прошу прощение за корявые картинки, но суть должна быть ясна =)


Ответ 3

Сделайте попроще вывод ответа
for (int j = i; j >= 0; j--)  
    printf("%05ld", a[j]);


Ответ 4

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


Ответ 5

Алгоритм у меня правильный, 1000! вычисляет правильно, но блин на десятом тесте time
limit exceeded 1,37 секунд, что делать не знаю:
#include
#include
using namespace std;
string mult(string n, int x){
       int add=0,num;
       string str="";
       for (int i=n.size()-1; i>=0; i--){
           num=((int)n[i]-48)*x+add;
           str=char(num%10+48)+str;
           add=num/10;
       }
       string tostr="";
       int d=1;
       while (add>=d){
             tostr=char((add%(d*10))/d+48)+tostr;
             d*=10;
       }
       return tostr+str;
}
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    string str="1";
    for (int i=1; i<=n; i++)
        str=mult(str,i);
    cout<
Ответ 6

Нашёл эту задач у Хорстмана. Так как занимаюсь только второй день, смог решить только так:
    import java.math.BigInteger;
    import java.util.Scanner;

public class asf
{
    public static void main(String[] args) {
        Scanner z = new Scanner(System.in);
        System.out.println("Введите число");
        int y =z.nextInt();
        BigInteger a = new BigInteger("1");
        BigInteger b = new BigInteger("1");
        BigInteger c = new BigInteger("1");
        BigInteger d = new BigInteger("1");
        d=BigInteger.valueOf(y);
        d=d.subtract(c);
        for (int i=-1; i<=0;b=b.add(c)) {
            i = b.compareTo(d);
            a = a.multiply(b);
        }
        System.out.println("Факториал числа "+y+" равен "+a);

    }
}


Программа делает на цикл больше, т.ч. решил костылём. Если кто даст совет как улучшить,
с радостью послушаю.


Ответ 7

По условию -х! = 0? Или что-то другое должно выводить?
И что за 10-й тест?
Да, (если верить этому) 1000! = 

402387260077093773543702433923003985719374864210714632543799
910429938512398629020592044208486969404800479988610197196058
631666872994808558901323829669944590997424504087073759918823
627727188732519779505950995276120874975462497043601418278094
646496291056393887437886487337119181045825783647849977012476
632889835955735432513185323958463075557409114262417474349347
553428646576611667797396668820291207379143853719588249808126
867838374559731746136085379534524221586593201928090878297308
431392844403281231558611036976801357304216168747609675871348
312025478589320767169132448426236131412508780208000261683151
027341827977704784635868170164365024153691398281264810213092
761244896359928705114964975419909342221566832572080821333186
116811553615836546984046708975602900950537616475847728421889
679646244945160765353408198901385442487984959953319101723355
556602139450399736280750137837615307127761926849034352625200
015888535147331611702103968175921510907788019393178114194545
257223865541461062892187960223838971476088506276862967146674
697562911234082439208160153780889893964518263243671616762179
168909779911903754031274622289988005195444414282012187361745
992642956581746628302955570299024324153181617210465832036786
906117260158783520751516284225540265170483304226143974286933
061690897968482590125458327168226458066526769958652682272807
075781391858178889652208164348344825993266043367660176999612
831860788386150279465955131156552036093988180612138558600301
435694527224206344631797460594682573103790084024432438465657
245014402821885252470935190620929023136493273497565513958720
559654228749774011413346962715422845862377387538230483865688
976461927383814900140767310446640259899490222221765904339901
886018566526485061799702356193897017860040811889729918311021
171229845901641921068884387121855646124960798722908519296819
372388642614839657382291123125024186649353143970137428531926
649875337218940694281434118520158014123344828015051399694290
153483077644569099073152433278288269864602789864321139083506
217095002597389863554277196742822248757586765752344220207573
630569498825087968928162753848863396909959826280956121450994
871701244516461260379029309120889086942028510640182154399457
156805941872748998094254742173582401063677404595741785160829
230135358081840096996372524230560855903700624271243416909004
153690105933983835777939410970027753472000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000