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