问题描述:
在书架上放有编号为1 ,2 ,…,n的n(n<=100)本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。
例如:n = 3时:
原来位置为:1 2 3
放回去时只能为:3 1 2 或 2 3 1 这两种
问题:当取n本书时满足以上条件的放法共有多少种?
输入文件4.in,一行,一个整数n。
输出文件4.out,仅1行,一个整数,表示满足以上条件的放法总数。
样例:
输入
3
输出
2
此题用高精度解。。不知道我哪里错了。。
var
f:array[1..100,1..100] of integer;
a:array[1..100]of integer;
n,i,k:longint;
begin
assign(input,'4.in');
assign(output,'4.out');
reset(input);rewrite(output);
read(n);
f[2,100]:=1;
for i:= 3 to n do
begin
fillchar(a,sizeof(a),0);
for k:= 100 downto 1 do
begin
a[k]:=f[i-1,k]+f[i-2,k]+a[k];
if a[k]>9 then begin a[k-1]:=a[k-1]+a[k] div 10;a[k]:=a[k] mod 10;end;
end;
for k:=100 downto 1 do
begin
f[i,k]:=(i-1)*a[k];
if f[i,k]>9 then begin f[i,k-1]:=f[i,k-1]+f[i,k] div 10;f[i,k]:=f[i,k]mod 10;end;
end;
end;
k:=1;
while f[n,k]=0 do k:=k+1;
for i:= k to 100 do
write(f[n,i]);
close(input);close(output);
end.