Project1

标题: 迭代问题 [打印本页]

作者: dbshy 时间: 2008-6-15 20:35
标题: 迭代问题
一位搞OI的学弟问我一道迭代题,很久做不出,现请教大家

g(n) = n n<=1
g(n) = (2002*g(n-1)+2003*g(n-2)) mod 2005 n>1

求g(2005)
一道读程题,要详细解答过程,不要答案 [LINE]1,#dddddd[/LINE]版务信息：本贴由楼主自主结贴～

作者: 美兽 时间: 2008-6-15 20:56
怎么感觉答案已经自己写出来了……

作者: dbshy 时间: 2008-6-15 21:07

以下引用美兽于2008-6-15 12:56:57的发言：

怎么感觉答案已经自己写出来了……

????

作者: link006007 时间: 2008-6-15 21:08
这个递归感觉想在遍历树... ...{/fd}
2002*(2002*(2002*2002+2003)+2002*2003)+2003*2002 + 2003*(2002+2003)

作者: 美兽 时间: 2008-6-15 21:09
出口与循环体都有了，应不缺条件了？？

作者: dbshy 时间: 2008-6-15 21:12

以下引用美兽于2008-6-15 13:09:16的发言：

出口与循环体都有了，应不缺条件了？？

原题就是这样的,你做一下,连规律都找不道

作者: IamI 时间: 2008-6-15 21:12

以下引用美兽于2008-6-15 13:09:16的发言：

出口与循环体都有了，应不缺条件了？？

读程题，即不能编写程序，全靠手算计算出结果。

作者: link006007 时间: 2008-6-15 21:17
                     g(n)
         2002             2003
      2002    2003    2002  2003
2002 2003  2002    2002
2002

深度为n-1
左支2002 右支2003
父子想乘, 兄弟相加, 右支比左支少1层

草稿太乱  不知看错没

作者: dbshy 时间: 2008-6-15 21:22

以下引用link006007于2008-6-15 13:17:09的发言：

                  g(n)
         2002             2003
   2002    2003    2002  2003
2002 2003  2002    2002
2002

深度为n-1
左支2002 右支2003
父子想乘, 兄弟相加, 右支比左支少1层

草稿太乱  不知看错没

[本贴由作者于 2008-6-15 13:20:10 最后编辑]

然后呢???

作者: dbshy 时间: 2008-6-15 21:23

以下引用IamI于2008-6-15 13:12:26的发言：

以下引用美兽于2008-6-15 13:09:16的发言：

出口与循环体都有了，应不缺条件了？？

读程题，即不能编写程序，全靠手算计算出结果。

编程,MS也出不来,电脑卡死.....

作者: link006007 时间: 2008-6-15 21:24
你把n取小一点不久可以了我那个n才5... 就要这么多计算了

我觉得那个就是过程,然后就是结果不然还有什么{/gg}

对了你那个式子是这样么
def g(n)
if (n  <= 1)
   return n
else
   return 2002*g(n-1)+2003*g(n-2)
end
end

作者: dbshy 时间: 2008-6-15 21:27

以下引用link006007于2008-6-15 13:24:06的发言：

你把n取小一点不久可以了我那个n才5... 就要这么多计算了

我觉得那个就是过程,然后就是结果不然还有什么

[本贴由作者于 2008-6-15 13:25:49 最后编辑]

希望详细解答和答案

另外每次看到LS同学的名字,就让我想到了指针,然后就想到了链表,然后BFS,然后青蛙过河,然后

DP,然后就是FORD算法,然后就是马式加成

作者: dbshy 时间: 2008-6-15 21:31

以下引用link006007于2008-6-15 13:24:06的发言：

你把n取小一点不久可以了我那个n才5... 就要这么多计算了

我觉得那个就是过程,然后就是结果不然还有什么

对了你那个式子是这样么
def g(n)
  if (n  <= 1)
return n
  else
return 2002*g(n-1)+2003*g(n-2)
  end
end

[本贴由作者于 2008-6-15 13:27:18 最后编辑]

我觉得那个就是过程,然后就是结果?????
理解不能,结果是?????

作者: 美兽 时间: 2008-6-15 21:38
g(0)=1，g(1)=1

g(n)=(2002g(n-1)+2003g(n-2)) mod 2005
=(-3g(n-1)-2g(n-2)) mod 2005

自己展开代入合并

g(n-1)=((-1)n-1-(-2)n-1) mod 2005

g(2005)=(2^2005-1) mod 2005

   =(32^401-1) mod 2005

   =(31 mod 401) mod 2005

   =(31 mod 32) mod 2005

因为 32 < 2005

g(2005)= 32 [LINE]1,#dddddd[/LINE]系统信息：本贴由楼主认可为正确答案，66RPG感谢您的热情解答～

作者: 美兽 时间: 2008-6-15 21:39
菲波那契数列变形？？？

需要用递归展开与费尔马小定理变形。

作者: dbshy 时间: 2008-6-15 21:41

以下引用美兽于2008-6-15 13:38:01的发言：

g(0)=1，g(1)=1

g(n)=(2002g(n-1)+2003g(n-2)) mod 2005
=(-3g(n-1)-2g(n-2)) mod 2005

自己展开代入合并

g(n-1)=((-1)n-1-(-2)n-1) mod 2005

g(2005)=(2^2005-1) mod 2005

g(2005)=(32^401-1) mod 2005

g(2005)=(31 mod 401) mod 2005

g(2005)=(31 mod 32) mod 2005

因为 32 < 2005

g(2005)= 32

我的数学有待提高......

g(2005)=(31 mod 32) mod 2005 = 31

作者: 不陌生 时间: 2008-6-15 22:02
初学，不清楚

作者: link006007 时间: 2008-6-15 22:11

以下引用美兽于2008-6-15 13:38:01的发言：

果然还是数学最高{/hx}

欢迎光临 Project1 (https://rpg.blue/)