กำหนดขนาดตัวแปรสามตัว max_val, last_element เป็นอินพุต เป้าหมายคือการหาจำนวนอาร์เรย์ต่างๆ ที่สามารถสร้างขึ้นในลักษณะที่มีองค์ประกอบขนาด มีองค์ประกอบระหว่าง 1 ถึง max_val และองค์ประกอบแรกจะเป็น 1 เสมอ และองค์ประกอบสุดท้ายจะเป็น max_val เสมอ ตรวจสอบให้แน่ใจด้วยว่าไม่มีองค์ประกอบที่ต่อเนื่องกันสององค์ประกอบที่เหมือนกัน
ให้เราเข้าใจด้วยตัวอย่าง
ตัวอย่าง
ป้อนข้อมูล - ขนาด =5, max_val =3, last_element =3
ผลลัพธ์ - จำนวนอาร์เรย์ที่มีองค์ประกอบต่อเนื่องกันที่มีค่าต่างกันคือ 5
คำอธิบาย - อาร์เรย์จะเป็น:-
[1, 2, 3, 1, 3 ], [1, 2, 3, 2, 3 ], [1, 2, 1, 2, 3 ], [1, 3, 1, 2, 3 ], [1 , 3, 2, 1, 3 ].
ป้อนข้อมูล - ขนาด =3 max_val =2 สุดท้าย_องค์ประกอบ =2
ผลลัพธ์ - จำนวนอาร์เรย์ที่มีองค์ประกอบต่อเนื่องกันที่มีค่าต่างกันคือ 0
คำอธิบาย - ไม่มีอาร์เรย์ที่เป็นไปได้ที่มี 3 องค์ประกอบและมี [ 1, _, 2 ] เป็นองค์ประกอบที่ต่อเนื่องกัน เนื่องจากเราไม่สามารถเติมอะไรก็ได้ยกเว้น 1 หรือ 2 สำหรับองค์ประกอบตรงกลาง และจะละเมิดเงื่อนไขขององค์ประกอบที่แตกต่างกันที่ต่อเนื่องกัน
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
- ในแนวทางนี้ เราจะใช้ไดนามิกการเขียนโปรแกรมและ combinatorics ในการค้นหาจำนวนอาร์เรย์ดังกล่าว
- องค์ประกอบแรกและองค์ประกอบสุดท้ายจะได้รับการแก้ไขเป็น 1 และองค์ประกอบสุดท้าย_ สำหรับอาร์เรย์ทุกขนาด วิธีการเติมจะใช้ได้สำหรับองค์ประกอบขนาด-2 เท่านั้น
- สำหรับการเติม [1 ถึง max_val] องค์ประกอบที่จะเติมในขนาด-2 ตำแหน่ง Ways จะเป็น way(max_val)=ways(size) / (max_val - 1)
- สำหรับแต่ละช่วง 1 ถึง i วิธีจะเป็น ways(i)=ways(size) / (max_val - 1) [ ways(size) =จำนวนวิธีเติมองค์ประกอบสุดท้ายด้วยตัวเลข 2 ถึง max_val )
- หากlast_element เป็น 1 ทางจะเป็น way(size-1) เนื่องจากองค์ประกอบสุดท้ายสามารถเป็น 1 ได้เท่านั้น
- องค์ประกอบสุดท้ายที่สองสามารถอยู่ระหว่าง 1 ถึง max_val เสมอ
- หากองค์ประกอบสุดท้ายที่สองไม่ใช่ 1 วิธีจะเป็น (max_val-2)*ways(i-1) เนื่องจาก arri ไม่สามารถเป็น 1 หรือ arri-1
- หากองค์ประกอบสุดท้ายที่สองคือ 1 วิธีจะเป็น (max_val-1)*ways(i-1) เป็น arri-1 คือ 1 และ arri-2 ไม่ใช่ 1.
- วิธี(i) จะเป็น :- (max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)
- นำขนาดตัวแปร max_val และ last_element เป็นอินพุต
- ฟังก์ชัน diff_val(ขนาด int, int max_val, int last_element) รับอินพุตทั้งหมดและส่งกลับจำนวนอาร์เรย์ที่มีองค์ประกอบต่อเนื่องกันที่มีค่าต่างกัน
- นับเริ่มต้นเป็น 0
- ใช้อาร์เรย์ arr[Max_N] ={ 0 } การจัดเก็บจำนวนวิธีในการเติมอาร์เรย์ เริ่มต้น arr[0] ด้วย 0 และ arr[1] ด้วย 1.
- เปลี่ยนเส้นทางจาก i=2 ไปยัง i<ขนาด
- ใช้ temp_1 =(max_val - 2) * arr[i - 1] และ temp_2 =(max_val - 1) * arr[i - 2]
- ตั้งค่า arr[i] =temp_1 + temp_2.
- ในกรณีที่ last_element ==1 ให้ตั้งค่า count =(max_val - 1) * arr[size - 2]
- มิฉะนั้น return arr[size - 1].
- เมื่อสิ้นสุดการส่งคืน นับเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define Max_N 109
int diff_val(int size, int max_val, int last_element) {
int count = 0;
int arr[Max_N] = {
0
};
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < size; i++) {
int temp_1 = (max_val - 2) * arr[i - 1];
int temp_2 = (max_val - 1) * arr[i - 2];
arr[i] = temp_1 + temp_2;
}
if (last_element == 1) {
count = (max_val - 1) * arr[size - 2];
} else {
return arr[size - 1];
}
return count;
}
int main() {
int size = 5;
int max_val = 3;
int last_element = 3;
cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
return 0;
} หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Count of arrays having consecutive element with different values are: 5
