Trong bài toán này, chúng ta được cho một số N biểu thị số viên gạch được cung cấp để tạo ra cầu thang. Nhiệm vụ của chúng tôi là f ind số bậc cầu thang .
Sử dụng những viên gạch đã cho, chúng ta cần tạo một bậc cầu thang. Mỗi bước lấy thêm một viên gạch đó là bước cuối cùng. Và bậc đầu tiên là hai viên gạch cao. Chúng tôi cần tìm số lượng các bước như vậy có thể được tạo ra từ gạch.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 40
Đầu ra
3
Giải thích
Bước =1; gạch yêu cầu =2; tổng số gạch sử dụng =2; gạch còn lại =38
Bước =2; gạch yêu cầu =3; tổng số gạch sử dụng =5; gạch còn lại =35
Bước =3; gạch yêu cầu =4; tổng số gạch sử dụng =9; gạch còn lại =31
Bước =4; gạch yêu cầu =5; tổng số gạch sử dụng =14; gạch còn lại =26
Bước =5; gạch yêu cầu =6; tổng số gạch sử dụng =20; gạch còn lại =20
Bước =6; gạch yêu cầu =7; tổng số gạch sử dụng =27; gạch còn lại =13
Bước =7; gạch yêu cầu =8; tổng số gạch sử dụng =35; gạch còn lại =5
Không thể tạo thêm bước nào vì bước thứ 8 yêu cầu 9 viên gạch và chỉ có 5 viên gạch hiện tại.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng một vòng lặp, bắt đầu từ 2 cho đến khi số viên gạch được sử dụng vượt quá N và sau đó trả về số bước cuối cùng.
Giải pháp này là tốt nhưng độ phức tạp về thời gian là N. Và có thể thực hiện một cách tiếp cận tốt hơn để tìm ra giải pháp bằng cách sử dụng công thức tổng và tìm kiếm nhị phân.
Chúng tôi có X là tổng số viên gạch sẽ được sử dụng luôn được tạo ra lớn hơn (n * (n + 1)) / 2 vì chúng tôi có tổng tất cả các viên gạch được yêu cầu. Trong trường hợp này, chúng tôi có một giải pháp từ một trong hai giá trị được tìm thấy từ giữa và giữa - 1.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The number of stair steps that can be made is 9