使用 C++ 获取到达目标页码所需的最小翻页次数。

问题陈述

给定一本 N 页的书，任务是计算到达给定目标页码 K 所需的最小翻页次数。

  • 我们可以从书的正面（即第 1 页）或书的反面（即第 N 页）开始翻页。

  • 每页都有两面，正面和反面，除了第一页，它只有反面，最后一页可能只有反面，具体取决于书的页数。

如果 N = 5 且 K = 4，则我们必须翻转至少 1 页 -

  • 如果我们从正面开始翻页，则需要翻 2 次 (1) -> (2, 3) -> (4,5)

  • 如果我们从背面开始翻页，(4, 5) 需要翻 1 次，翻页次数 = 1

因此，最小翻页次数 = 1。

算法

使用以下公式计算最终结果 -

1. If K is even, front distance = (K – 0)/2 and back distance = (N – 1 – K)/2
2. If K is odd, front distance = (K – 1)/2 and back distance = (N – K)/2

示例

#include <iostream>
#include <algorithm>
using namespace std;
int getMinPageTurns(int n, int k){
   if (n % 2 == 0) {
      ++n;
   }
   return min((k + 1) / 2, (n -k + 1) / 2);
}
int main(){
   int n = 5, k = 4;
   cout << "Required page turns = " << getMinPageTurns(n, k) << endl;
   return 0;
}

输出

编译并执行上述程序时，会生成以下输出 -

Required page turns = 1

更新于: 2019年10月31日

479 次查看

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告