資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用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中找到解決方案。
示例
程式說明了我們解決方案的工作原理
#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 次瀏覽
廣告