2154 杭电 数学规律 ACM

时间:2023-03-09 05:42:12
2154 杭电 数学规律 ACM

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2154
很简单的找规律的数学题目;
思路:因为挑完N次后都要跳回A,所以相当于挑N-1次后必须留在B C区域,又由于B与C可以看作是对称的,所以每次算的时候可以假定全部先从B跳,最后结果乘以2就好。还可以用深度遍历的思想。每次尽量跳的路线远一点。
2 2
3 2
4 6
5 10
6 22
可以发现规律:
if(i%2==0)

a[i]=2*a[i-1]+2;

else a[i]=2*a[i-1]-2;
自己再验证哈,没问题。

#include<stdio.h>
int main()
{
int arr[1002]={0,0,2,2},n;
for(int i=4;i<1001;i++)
{
if(i%2==0)
arr[i]=arr[i-1]*2+2;
else
arr[i]=arr[i-1]*2-2;
arr[i]=arr[i]%10000;
}
while(scanf("%d",&n)!=EOF&&n!=0)
printf("%d\n",arr[n]%10000);
}