使用C++查找台阶数

在这个问题中，我们给定一个数字N，表示用于创建楼梯的砖块数量。我们的任务是查找台阶数。

使用给定的砖块，我们需要创建一个阶梯。每一步都比上一步多一块砖。第一步高两块砖。我们需要找到可以用这些砖块建造的台阶数。

让我们来看一个例子来理解这个问题：

输入

N = 40

输出

3

解释

步骤 = 1；所需砖块 = 2；已用砖块总数 = 2；剩余砖块 = 38

步骤 = 2；所需砖块 = 3；已用砖块总数 = 5；剩余砖块 = 35

步骤 = 3；所需砖块 = 4；已用砖块总数 = 9；剩余砖块 = 31

步骤 = 4；所需砖块 = 5；已用砖块总数 = 14；剩余砖块 = 26

步骤 = 5；所需砖块 = 6；已用砖块总数 = 20；剩余砖块 = 20

步骤 = 6；所需砖块 = 7；已用砖块总数 = 27；剩余砖块 = 13

步骤 = 7；所需砖块 = 8；已用砖块总数 = 35；剩余砖块 = 5

由于第8步需要9块砖，而只有5块，因此无法再创建更多步骤。

解决方案方法

解决这个问题的一个简单方法是使用循环，从2开始，直到使用的砖块数量超过N，然后返回最后一步的计数。

这个解决方案很好，但是时间复杂度是O(N)。可以使用求和公式和二分查找来找到更好的方法。

我们有X，它是总共使用的砖块数量，它总是大于(n*(n+1))/2，因为我们有所有所需砖块的总和。在这种情况下，我们可以从中间值或中间值-1中找到解决方案。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

程序说明了我们解决方案的工作原理

Open Compiler
#include <iostream>
using namespace std;
int findStairCount(int T){
   int low = 1;
   int high = T/2;
   while (low <= high) {
      int mid = (low + high) / 2;
      if ((mid * (mid + 1)) == T)
         return mid;
      if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T)
         return mid - 1;
      if ((mid * (mid + 1)) > T)
         high = mid - 1;
      else
         low = mid + 1;
      }
   return -1;
}
int main(){
   int N = 60;
   int stepCount = findStairCount(2*N);
   if (stepCount != -1)
      stepCount--;
   cout<<"The number of stair steps that can be made is "<<stepCount;
   return 0;
}

输出

The number of stair steps that can be made is 9

更新于：2022年2月11日

227 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告