PTA基础编程题目集—

PTA基础编程题目集——爬动的蠕虫

原题链接https://pintia.cn/problem-sets/14/problems/797

这题一开始考虑时犯了一些错误，一开始是这样考虑的，按题目的意思，每2分钟蠕虫爬行的距离是(U-D)寸。那么平均每分钟爬行的距离是(U-D+1)/2寸。然后对照样例数据N=12,U=3,D=1算出需要8分钟爬完，当然这个结果是错的。调整一下思路，假设时间为t，爬行距离为s。当t=0时，s=0；当t=1时，s=U；当t=2时，s=U-D；当t=3时，s=U-D+U；当t=4时，S=U-D+U-D；.......所以，可以根据s和t的关系得出以t为自变量关于s的函数关系f(t)，这是个分段函数，当t%2==0时，f(t)=(t/2)(U-D)；当t%2==1时，f(t)=f(t-1)+U。这里有个递归的形式，因为当t%2==1时，t-1肯定是偶数，所以可以进一步将t-1代入f(t)=(t/2)(U-D)得出当t为奇数时f(t)=((t-1)/2)(U-D)+U。

有了函数关系，就可以写代码了，代码如下：

 1 #include <stdio.h>
 2 int main(void){
 3     int t = 0, s, n, u, d;      //t表示时间，s表示爬行距离
 4     scanf("%d %d %d", &n, &u, &d);
 5     while(1){
 6         if(t % 2 == 0){
 7             s = (t / 2)*(u - d);
 8         }else{
 9             s = ((t - 1) / 2) * (u - d) + u;
10         }
11         if(s >= n){          //当爬行距离大于指定距离，跳出循环
12             break;
13         }
14         t++;
15     }
16     printf("%d
", t);       //打印所花费的时间
17     return 0;
18 }

如果直接采用递归形式，代码如下：

 1 #include <stdio.h>
 2 int distance(const int t, const int u, const int d);
 3 int main(void){
 4     int t, s, n, u, d;
 5     scanf("%d %d %d", &n, &u, &d);
 6     for(t = 0; ; t++){
 7         s = distance(t, u, d);
 8         if(s >= n){
 9             break;
10         }
11     }
12     printf("%d
", t);
13     return 0;
14 }
15 
16 //计算指定时间点爬行的距离
17 int distance(const int t, const int u, const int d){
18     if(t % 2 == 0){
19         return (t / 2)*(u - d);
20     }else{
21         return distance(t - 1, u, d) + u;
22     }
23 }