ในปัญหานี้ เราได้รับตัวเลข N แสดงจำนวนอิฐที่ให้มาเพื่อสร้างบันได ภารกิจของเราคือ หาจำนวนขั้นบันได
โดยใช้อิฐที่ให้มา เราต้องสร้างขั้นบันได แต่ละขั้นใช้オิฐมากกว่าขั้นก่อนหน้าหนึ่งอิฐ และขั้นแรกสูง 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 แล้วคืนค่าจำนวนขั้นล่าสุด
วิธีนี้ดีแต่ความซับซ้อนของเวลาเป็น O(N) และวิธีที่ดีกว่าสามารถทำได้โดยใช้สูตรผลรวมและ binary search
เรามี X ซึ่งเป็นจำนวนอิฐทั้งหมดที่จะใช้ ซึ่งมักจะมากกว่า (n*(n+1)) /2 เนื่องจากเรามีผลรวมของอิฐที่ต้องการทั้งหมด ในกรณีนี้ เรามีคำตอบจากค่าทั้งสองที่หาได้จาก mid และ mid - 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
