跳石板
题目
https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?tpId=122&tqId=33674&ru=/exam/oj
思路分析
以从石板4调到石板24为例:
i=4: 4(0)——>6(1)
i=5:(无)
i=6: 4(0)——>6(1)——>8(2) or 4(0)——>6(1)——>9(3)
i=7:(无)
i=8: 4(0)——>6(1)——>8(2)——>10(3) or 4(0)——>6(1)——>8(2)——>12(3)
i=9:4(0)——>6(1)——>9(3)——>12(4)【由于与i=8时的第二分支比步数大1,故选取i=8时的第二分支】
i=10:4(0)——>6(1)——>8(2)——>10(3)——>12(4)【舍弃,理由同上】 or 4(0)——>6(1)——>8(2)——>10(3)——>15(4)
.......
所以我们可以通过i的遍历寻找到跳到合适石板上的步数。
代码
这个代码放到题目验证无法通过,因为当m过大时,运算超时,这道题最好的解答还是使用动态规划,但是求较小的m时,如果没有学过动态规划,这个代码也可以用。
#include<stdio.h> int main() { int n,m; int i,j; int s[100000]; scanf("%d%d",&n,&m); s[n]=0;//步数 for(i=n;i<=m;i++) { for(j=2;j<i;j++)//寻找约数 { if(i%j==0) { if(s[i+j]==0) { s[i+j]=s[i]+1; if(i+j==m) { printf("%d",s[m]); } } } } } if(s[m]==0)//无法跳到目标石板 { printf("-1"); } return 0; }
运行结果
标签:10,12,石板,int,C语言,例题,步数 From: https://www.cnblogs.com/hcrzhi/p/17340704.html