ภารกิจคือการหาจำนวนสูงสุดของสี่เหลี่ยมจัตุรัสที่มีด้าน 'a' ที่สามารถใส่เข้าไปในสามเหลี่ยมหน้าจั่วมุมฉากที่มีฐานเป็น 's' (สามเหลี่ยมหน้าจั่วมีด้านเท่ากันอย่างน้อย 2 ด้าน)
ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง:
อินพุต
s=5, a=1
ผลลัพธ์
10
คำอธิบาย − จำนวนของสี่เหลี่ยมจัตุรัสในฐานสามารถคำนวณได้โดยการหาร s ด้วย a แล้วลบ 1 ดังนั้นจำนวนกำลังสองในฐาน =5/1 – 1 =4
ในทำนองเดียวกันเมื่อวางสี่เหลี่ยมจัตุรัส 4 อันล่างแล้ว เราจะได้สามเหลี่ยมหน้าจั่วใหม่พร้อมฐาน (s-a) จากนั้นเราทำซ้ำขั้นตอนเดียวกันและรับ 3 สี่เหลี่ยมไปเรื่อยๆ จนกว่าจะวางสี่เหลี่ยมเดียวที่ด้านบน
อินพุต
s=7, a=2
ผลลัพธ์
3
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
ในการหาจำนวนสี่เหลี่ยมจัตุรัสสูงสุด เราจะต้องเริ่มจากฐานของสามเหลี่ยมแล้วหาจำนวนสี่เหลี่ยมจัตุรัส
-
ในการหาจำนวนกำลังสอง เราจะหารฐาน s ที่ด้านข้างของกำลังสองแล้วลบ 1 ออกจากมัน =s/a – 1
-
จากนั้นมันจะปล่อยให้เรามีสามเหลี่ยมหน้าจั่วอีกอันที่มีฐาน (s - a) ซึ่งจะรองรับสี่เหลี่ยมจัตุรัสน้อยกว่าแถวก่อนหน้าด้านล่างซึ่งเราสามารถคำนวณได้ดังนี้ -
สี่เหลี่ยมในแถวถัดไป =(s - a)/a – 1 =(s/a – a/a) – 1=s/a - 1 - 1 =s/a – 2 =หนึ่งสี่เหลี่ยมน้อยกว่าแถวก่อนหน้า
-
จำนวนกำลังสองลดลงเรื่อย ๆ จนถึง 1 ดังนั้นเราต้องหาเฉพาะจำนวนสี่เหลี่ยมในแถวฐานและใช้สูตรการบวกจำนวนธรรมชาติเพื่อหาผลรวมสุดท้ายซึ่งก็คือ -
(n) * (n + 1) / 2
ในกรณีนี้ สูตรจะกลายเป็น − ((s / a) – 1) * (s / a) / 2
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int Max(int s, int a){
//formula for calculating maximum squares
return ((s / a) - 1) * (s / a) / 2;
}
//Main function
int main(){
int s = 5, a = 1;
cout <<"Maximum squares possible are: "<<Max(s,a);
return 0;
} ผลลัพธ์
10
