Algorithm 版 (精华区)

发信人: Lerry (戒网·学习), 信区: Algorithm
标  题: [合集]My Answer for P48
发信站: 哈工大紫丁香 (2001年12月22日23:23:56 星期六), 站内信件


────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日20:50:12 星期二 说道:

20000以内有效，请大家帮忙看看
var
    s:array[1..20000] of integer;
    n,i,j,k,l:integer;
begin
    readln(n);
    fillchar(s,sizeof(s),0);
    s[1]:=1; j:=1;
    for i:=2 to n do begin
        k:=0;
        for l:=1 to j+2 do begin
            k:=s[l]*i+k;
            s[l]:=k mod 100000;
            k:=k div 100000;
        end;
        if s[j+1]<>0 then begin
            inc(j);
            if s[j+1]<>0 then inc(j);
        end;
    end;
    write(n,'!=',s[j]);
    for i:=j-1 downto 1 do begin
        if s[i]<1000 then write('0');
        if s[i]<100 then write('0');
        if s[i]<10 then write('0');
        write(s[i]);
    end;
    writeln;
    writeln;
    writeln(j);
    readln;
end.

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日20:53:14 星期二 说道:

faint
这个题好像很简单的说

────────────────────────────────────────
 Lerry (戒网·学习)                   于 2001年12月04日20:55:40 星期二 说道:

这么快

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日20:56:18 星期二 说道:

哈哈，拣软柿子捏拉！ :)

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日20:58:45 星期二 说道:

有几个问题要请教。
var
    s:array[1..20000] of integer;
    n,i,j,k,l:integer;
begin
    readln(n);
    fillchar(s,sizeof(s),0);
    s[1]:=1; j:=1;
    for i:=2 to n do begin
        k:=0;
        for l:=1 to j+2 do begin
            k:=s[l]*i+k;
            s[l]:=k mod 100000;
                        ~~~~~~~这个数是怎样算出来的？
            k:=k div 100000;
        end;
        if s[j+1]<>0 then begin
            inc(j);
            if s[j+1]<>0 then inc(j);
        end;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~如果500*9怎么办？
    end;
    write(n,'!=',s[j]);
    for i:=j-1 downto 1 do begin
        if s[i]<1000 then write('0');
        if s[i]<100 then write('0');
        if s[i]<10 then write('0');
        write(s[i]);
    end;
    writeln;
    writeln;
    writeln(j);
    readln;
end.

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日21:00:58 星期二 说道:

复杂度是多少??

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日21:02:18 星期二 说道:

就是高精度运算吧

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日21:03:33 星期二 说道:

faint
我说的不是这个.是算法的复杂度

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日21:05:44 星期二 说道:

感觉是O(n*f(n))
f(n)<n
呵呵。

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日21:06:10 星期二 说道:

f(n)是什么??

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日21:08:31 星期二 说道:

一个n的函数

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日21:25:18 星期二 说道:

20000*100000<2^31, 所以用了100000

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日21:27:05 星期二 说道:

我认为n=几万时近似于n^2

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日21:28:06 星期二 说道:

空间复杂度呢??
o(n)么??

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日21:29:22 星期二 说道:

我想n在万这个级别的时候是这样

────────────────────────────────────────
 Lerry (戒网·学习)                   于 2001年12月04日21:29:53 星期二 说道:

这个方法不错的说

────────────────────────────────────────
 sino (一层秋雨一层凉)                于 2001年12月04日21:34:44 星期二 说道:

不过n很大的时候，比如几百万，不知道应该怎么做了

────────────────────────────────────────
 ssos (存在与虚无·戒酒戒网)          于 2001年12月04日21:35:22 星期二 说道:

这是哪道题,没看明白程序的说

────────────────────────────────────────
 lizhenguo (夸父·追日)               于 2001年12月04日22:17:19 星期二 说道:

实际上就是求n的阶乘。

────────────────────────────────────────