กำหนดจำนวนเต็ม n เป็นอินพุต เป้าหมายคือการหาจำนวนวิธีที่เราสามารถแทน 'n' เป็นผลรวมของจำนวนเต็มคี่ ตัวอย่างเช่น ถ้า n เป็น 3 สามารถแสดงเป็นผลรวม ( 1+1+1 ) และ (3) รวมเป็น 2 วิธี
ตัวอย่าง
อินพุต
n=6
ผลลัพธ์
Count of ways to express ‘n’ as sum of odd integers are: 8
คำอธิบาย
The ways in which we can express ‘n’ as sum of odd integers − 1. 1+1+1+1+1+1 2. 3+1+1+1 3. 1+3+1+1 4. 1+1+3+1 5. 1+1+1+3 6. 3+3 7. 1+5 8. 5+1
อินพุต
n=9
ผลลัพธ์
Count of ways to express ‘n’ as sum of odd integers are: 34
คำอธิบาย
The some of the ways in which we can express ‘n’ as sum of odd integers: 1. 1+1+1+1+1+1+1+1+1 2. 3+3+3 3. 5+3+1 4. 7+1+1 5. ….and other such combinations
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะตรวจสอบวิธีการแสดงตัวเลขเป็นผลรวมของจำนวนเต็มคี่จากตัวเลขก่อนหน้าที่เป็นตัวเลขที่ n-1 และ n-2 ทางจะเป็นวิธี(n-1) + วิธี(n−2).
-
ใช้จำนวนเต็ม n เป็นอินพุต
-
ฟังก์ชัน odd_ways(int n) ใช้ตัวเลขและส่งกลับจำนวนวิธีที่จะแสดง 'n' เป็นผลรวมของจำนวนเต็มคี่
-
ใช้อาร์เรย์ arr ที่มีความยาว n+1 เพื่อเก็บวิธีการนับสำหรับการแสดงตัวเลขเป็นผลรวมของจำนวนเต็มคี่
-
สำหรับหมายเลข 0 ไม่มีวิธีดังกล่าว ดังนั้นให้ตั้งค่า arr[0] เป็น 0
-
สำหรับหมายเลข 1 มีทางเดียวเท่านั้น ให้ตั้งค่า arr[1] ด้วย 1.
-
สำหรับตัวเลขที่เหลือ เราสามารถตั้งค่า arr[i] ด้วย arr[i−1]+arr[i−2] สำหรับ i ระหว่าง 2 ถึง n
-
ในตอนท้ายเรามี arr[n] สำหรับจำนวนวิธีที่ n ถูกแทนเป็นผลรวมของจำนวนเต็มคี่
-
คืนค่า arr[n] เป็นผลลัพธ์
ตัวอย่าง
#include<iostream>
using namespace std;
int odd_ways(int n){
int arr[n+1];
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i <= n; i++){
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
}
int main(){
int n = 6;
cout<<"Count of ways to express ‘n’ as sum of odd integers are: "<<odd_ways(n);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of ways to express ‘n’ as sum of odd integers are: 8
