3道看程序写答案题求解 [复制链接]

1.下面这个程序怎样做出来?用笔算
var
　　n:longint
　　function g(k:longint):longint;
　　begin
　　if k <=1 then g:=k
  else g:=(2002*g(k-1)+2003*g(k-2))mod 2005;
　　end;
　　begin 　　
read(n);　　
writeln(g(n));
　end.　　
输入：2005 　
答案输出：31

2、下面这个程序怎样做出来?用笔算
program program4;
const
u: array[0..2] of integer = (1, -3, 2);
v: array[0..1] of integer = (-2, 3);
var
i, n, sum: integer;
function g(n: integer): integer;
var i, sum: integer;
begin
sum := 0;
for i := 1 to n do inc(sum, u[i mod 3] * i);
g := sum;
end;
begin
sum := 0;
read(n);
for i := 1 to n do inc(sum, v[i mod 2] * g(i));
writeln(sum);
end.
输入：103
答案输出：-400    

3.下面这个程序怎样做出来?用笔算
var
　a : array[1..50] of integer;
　n,i,sum:integer;
　procedure work(p,r:integer);
　　var
　　i,j,temp:integer;
begin
　　if p<r then
  begin
i:=p-1;
　　   for j:=p to r-1 do
if a[j]>=a[r] then
    begin
inc(i);
temp:=a; a:=a[j]; a[j]:=temp;
end;
temp:=a[i+1]; a[i+1]:= a[r]; a[r]:=temp;
work(p,i);
work(i+2,r);
end;
end;
begin
read(n);
for i:=1 to n do read(a);
　work(1,n);
for i:=1 to n-1 do sum:=sum+abs(a[i+1]-a);
　writeln(sum);　
end.
　输入：10 23 435 12 345 3123 43 456 12 32 -100
　答案输出：3223

第一题转化为一个一次递推数列求第n项的问题。
a[n]:=a[n-1]*2002+a[n-2]*2003
也就是a[n]:=a[n-1]*-3+a[n-2]*-2
然后要通过一系列代数变化来得到通向公式。线性递推数列的解法一般用特征方程法

第一题转化为一个一次递推数列求第n项的问题。
a[n]:=a[n-1]*2002+a[n-2]*2003
也就是a[n]:=a[n-1]*-3+a[n-2]*-2
然后要通过一系列代数变化来得到通向公式。线性递推数列的解法一般用特征方程法

a(0)=0
a(1)=1
a(n)=a(n-1)*(-3)+a(n-2)*(-2)
通项公式求出来是什么？

a(0)=0
a(1)=1
a(n)=a(n-1)*(-3)+a(n-2)*(-2)
通项公式求出来是什么？

var
　　n:longint
　　function g(k:longint):longint;
　　begin
　　if k <=1 then g:=k
  else g:=(2002*g(k-1)+2003*g(k-2))mod 2005;
　　end;
　　begin 　　
read(n);　　
writeln(g(n));
　end.　　
输入：2005 　
答案输出：31

把2005带入K 然后就按if k <=1 then g:=k
  else g:=(2002*g(k-1)+2003*g(k-2))mod 2005;
判断被

an=((-1)^n-(-2)^n)  mod 2005
a2005=(-1+2^2005) mod  2005=-1+2^2005 mod 2005=31

2^400≡1 ( mod 2005)
2^2000=1( mod 2005)
所以:2^2005 mod 2005=32 mod 2005=32

n=            1  2  3  4  5  6    7  8  9  10  11  12  13  ……
u[n mod 3]=  -3  2  1  -3  2  1  -3  2  1  -3  2    1    -3  ……
g[n]=        -3  1  4  -8  2  8  -13  3  12  -18  4    16  -23 ……
v[n mod 2]=  3  -2  3  -2  3  -2    3  -2  3    -2  3  -2    3  ……
v*g=        -9  -2  12 16  6  -16  -39  -6  36  36  12  -32  -69 ……

从上表可以看出n从1到6，v*g的和为7；n从7到12，v*g的和也为7；这样我大胆的猜想：n从13到18，v*g的和也为7，……n从97到102，v*g的和也为7，从而n从1到102，v*g的和为7*（102/6）=7*17=119。
现在我们只要计算v[103 mod 2]*g[103]的结果就可以了。
再观察v*g的规律，v*g[1]=-9,v*g[7]=-39,v*g[13]=-69，感觉这是一个等差数列，
通项公式为-30*m-9(0=<m<=17,m= n div 6)
当n=103时，m=103 div 6=17，所以v[103 mod 2]*g[103]=-30*17-9=-519
所以最后结果为119+（-519）=-400

结果 是 31                 

an=((-1)^n-(-2)^n)  mod 2005
a2005=(-1+2^2005) mod  2005=-1+2^2005 mod 2005=31

2^400≡1 ( mod 2005)
2^2000=1( mod 2005)
所以:2^2005 mod 2005=32 mod 2005=32
因此:a2005=(-1+2^2005) mod  2005=-1+2^2005 mod 2005=31