首页 > 代码库 > 九连环-递归解法

九连环-递归解法

//求取下n环和放上n环的步数

int
ans;//规则一:第一环可以在任何时候放上或取下环柄。//规则二:只有紧跟在领头环后的环可以放上或取下环柄。(领头环是套在柄上的最前面的环int DownRing(int);int UpRing(int);int DownRing(int n){ int res = 0; if(n == 1) return 1; if(n>2) res = (res + DownRing(n-2))%SMod; //移下n-2个,第n-1个变为领头环 res += 1; //移下第n个 if(n>2) res = (res + UpRing(n-2))%SMod; //将n-2个移上去,以便移下第n-1个 if(n>1) res = (res + DownRing(n-1))%SMod; //此时就变成了将n-1个移下去了 return res;}int UpRing(int n){ int res = 0; if(n == 1) return 1; if(n>1) res = (res + UpRing(n-1))%SMod; //移上n-1个 if(n>2) res = (res + DownRing(n-2))%SMod; //将n-2个移下,此时第n-1个变成领头环 res += 1; //移上第n个 if(n>2) res = (res + UpRing(n-2))%SMod; //将n-2个环移上去 return res;}int main(){ int n; while(scanf("%d",&n)!=EOF) printf("%d\n",DownRing(n)); return 0;}