建设房产网站,沭阳网站建设招聘,公司网站怎样维护运营,东莞网站建设的收费题目链接#xff1a; https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?tpId85tqId29852rp1ru 题目分析#xff1a; 这道题就是计算从N开始加#xff0c;最少加几次等于M#xff0c;前提条件是每次相加的数必须是当前数的约数 思…题目链接 https://www.nowcoder.com/practice/4284c8f466814870bae7799a07d49ec8?tpId85tqId29852rp1ru 题目分析 这道题就是计算从N开始加最少加几次等于M前提条件是每次相加的数必须是当前数的约数 思路分析 将M个石板看做一个保存结果的数组jumpNum每个jumpNum[i]中都储存着从N到当前位置最小的步数如果是0则说明不能走到这个位置。从起点开始对jumpNum进行遍历先求当前位置的所有约数也就是当前位置可以向前走的步数然后更新到能到达的位置的最小步数。之前没有来过这个位置就将该位置更新为当前步数1否则更新为之前的步数和当前步数1两者最小的经过遍历一一次后得到结果jumpNum[M]就是从N开始加加到M的最少次数如果是0说明不可能加到M。 图解思路 上代码
#includeiostream
#includevector
#includealgorithmusing namespace std;//计算约数求除了1和本身的约数
void divisorNum(int n, vectorint divNum)
{for (int i 2; i sqrt(n); i){if (n%i 0){divNum.push_back(i);//非平方数时还有另一个数也要加入if (n / i ! i)divNum.push_back(n / i);}}
}
int Jump(int N, int M)
{//储存到达此stepNum点的步数vectorintstepNum(M 1, 0);//初始N为1步从N到N为1步stepNum[N] 1;for (int i N; i M; i){//用来保存N的所有约数即为从本身这个点开始能走的数量vectorintdivNum;//如果当前的位置是0代表这个点不能到因为0没有约数if (stepNum[i] 0)continue;//将当前位置可以走的步数存放在divisorNUm中divisorNum(i, divNum);//开始挨个试这些步数for (int j 0; jdivNum.size(); j){//之前走到该点的步数为stepNum[divNum[j] i]//走到当前位置的步数为stepNum[i] 1//如果当前位置不是M并且走的步数不为零//那么当前能走到该点的步数要和之前该点的步数进行对比取最小的if ((divNum[j] i) M stepNum[divNum[j] i] ! 0)stepNum[divNum[j] i] min(stepNum[divNum[j] i], stepNum[i] 1);//否则如果当前位置不是M//那么就说明走到这个位置的步数为0就要将这个位置的步数更新else if((divNum[j] i) M)stepNum[divNum[j] i] stepNum[i] 1;}}for (int i 0; i stepNum.size(); i){cout stepNum[i] -;}cout endl;if (stepNum[M] 0)return-1;else//初始化时多给了一步故需要减1return stepNum[M] - 1;
}
int main()
{int n, m;cin n m;cout Jump(n, m) endl;return 0;
}
