เราได้รับจำนวนบวก N เป้าหมายคือการนับจำนวนวิธีที่ตัวเลข N สามารถแบ่งออกเป็น 3 ส่วน ชิ้นส่วนอาจจะเท่ากันหรือไม่เท่ากันก็ได้ N อยู่ในช่วง [1,5000].
เราจะทำสิ่งนี้โดยใช้สามสำหรับลูปสำหรับ 3 ส่วนของตัวเลข ตรวจสอบวงในสุดว่าผลรวมของทั้งสามมีค่าเท่ากับ N หากเป็นจริง ให้เพิ่มจำนวนวิธี
มาทำความเข้าใจกับตัวอย่างกัน
ป้อนข้อมูล − N=5
ผลผลิต − จำนวนวิธีในการหาร N ออกเป็น 3 ส่วน:2
คำอธิบาย − 5 สามารถแสดงเป็นผลรวมของ (1,1,3) และ (1,2,2)
ป้อนข้อมูล − N=9
ผลผลิต − จำนวนวิธีในการหาร N ออกเป็น 3 ส่วน:7
คำอธิบาย − 9 สามารถแสดงเป็นผลรวมของ :(1, 1, 7), (1, 2, 6), (1, 3, 5), (1, 4, 4), (2, 2, 5), ( 2, 3,4) และ (3, 3, 3).
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้จำนวนเต็ม N ที่เริ่มต้นด้วยค่าระหว่าง 1 ถึง 5000
-
ฟังก์ชัน divideN(int n) รับ n และส่งกลับจำนวนวิธีที่ n สามารถแบ่งออกเป็น 3 ส่วนได้
-
นับตัวแปรเริ่มต้นเป็น 0 สำหรับจำนวนวิธี
-
ข้ามโดยใช้สามลูปสำหรับแต่ละส่วนของตัวเลข
-
วงนอกสุดจาก 1<=i
-
ตรวจสอบว่าผลรวมของ i, j และ k เท่ากับ n หรือไม่ ถ้าเป็นจริงจะนับการเพิ่มขึ้น
-
เมื่อสิ้นสุดลูปทั้งหมด การนับจะมีจำนวนวิธีในการหาร n ออกเป็น 3 ส่วน
-
คืนค่าการนับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int divideN(int n){
int count = 0;
for (int i = 1; i < n; i++){
for (int j = i ; j < n; j++){
for (int k = j; k < n; k++){
int sum=i+j+k;
if(sum==n)
{ count++; }
}
}
}
return count;
}
int main(){
int N=500;
cout <<endl<< "Number of ways to divide N in 3 parts : "<<divideN(N);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Number of ways to divide N in 3 parts: 20833
