ในปัญหานี้ เราได้รับหมายเลข N ซึ่งแสดงถึงจำนวนอิฐที่จัดเตรียมไว้เพื่อสร้างบันได งานของเราคือ f ระบุจำนวนขั้นบันได .
การใช้อิฐที่กำหนดเราต้องสร้างขั้นบันได แต่ละขั้นตอนใช้อิฐอีกหนึ่งก้อนที่ขั้นตอนสุดท้าย และขั้นแรกให้อิฐสูงสองก้อน เราต้องหาจำนวนขั้นที่ก่อจากอิฐได้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
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 เสมอ เนื่องจากเรามีผลรวมของอิฐทั้งหมดที่ต้องการ ในกรณีนี้ เรามีคำตอบจากค่าใดค่าหนึ่งจากสองค่าที่หาได้จากค่ากลางและค่ากลาง - 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
