C++を使用して階段のステップ数を見つける

この問題では、階段を作成するために提供されたレンガの数を示す番号Nが与えられます。私たちの仕事はf 階段の数を確認する 。

与えられたレンガを使用して、階段を作成する必要があります。各ステップは、最後のステップよりももう1つレンガを取ります。そして最初のステップは2つのレンガの高さです。レンガから作ることができるそのようなステップの数を見つける必要があります。

問題を理解するために例を見てみましょう

入力

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を超えてから、最後のステップのカウントを返すことです。

このソリューションは優れていますが、時間計算量はNのオーダーです。また、合計式と二分探索を使用してソリューションを見つけるためのより良いアプローチを作成できます。

使用するブリックの総数であるXがあり、必要なすべてのブリックの合計があるため、常に（n *（n + 1））/2よりも作成されます。この場合、midとmid-1から見つかった2つの値のいずれかからの解があります。

例

ソリューションの動作を説明するプログラム

#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