กำหนดตัวแปรสามตัวคือ size, max_val, last_element เป็นอินพุต เป้าหมายคือหาจำนวนอาร์เรย์ที่แตกต่างกันที่สามารถสร้างได้ โดยที่อาร์เรย์มีจำนวนสมาชิกเท่ากับ size มีสมาชิกอยู่ระหว่าง 1 และ max_val สมาชิกแรกจะเป็น 1 เสมอ และสมาชิกสุดท้ายจะเป็น max_val เสมอ นอกจากนี้ ต้องให้แน่ใจว่าไม่มีสมาชิกติดกันสองตัวที่เหมือนกัน
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - size = 5, max_val = 3, last_element = 3
Output - จำนวนอาร์เรย์ที่มีสมาชิกติดกันต่างกันคือ: 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]
Input - size = 3, max_val = 2, last_element = 2
Output - จำนวนอาร์เรย์ที่มีสมาชิกติดกันต่างกันคือ: 0
คำอธิบาย - ไม่มีอาร์เรย์ที่เป็นไปได้ด้วย 3 สมาชิกและมี [1, _, 2] เป็นสมาชิกติดกัน เนื่องจากเราไม่สามารถเติมค่าอะไรได้นอกจาก 1 หรือ 2 สำหรับสมาชิกกลาง และสิ่งนี้จะละเมิดเงื่อนไขสมาชิกติดกันต่างกัน
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- ในแนวทางนี้เราจะใช้ dynamic programming และ combinatorics เพื่อหาจำนวนอาร์เรย์ดังกล่าว
- สมาชิกแรกและสุดท้ายจะถูกกำหนดเป็น 1 และ last_element สำหรับอาร์เรย์ขนาดใดก็ตาม วิธีการเติมจะเป็นสำหรับ size-2 สมาชิกเท่านั้น
- สำหรับการเติมสมาชิก [1 ถึง max_val] ในช่อง size-2 วิธีการจะเป็น ways(max_val) = ways(size) / (max_val - 1)
- สำหรับแต่ละช่วง 1 ถึง i วิธีการจะเป็น ways(i) = ways(size) / (max_val - 1) [ ways(size) = จำนวนวิธีที่สมาชิกสุดท้ายสามารถเติมด้วยตัวเลข 2 ถึง max_val )
- ถ้า last_element เป็น 1 แล้ว ways จะเป็น ways(size-1) เนื่องจากสมาชิกสุดท้ายสามารถเป็นได้แค่ 1
- สมาชิกลำดับสองจากท้ายสามารถอยู่ระหว่าง 1 ถึง max_val ได้เสมอ
- ถ้าสมาชิกลำดับสองจากท้ายไม่ใช่ 1 แล้ว ways จะเป็น (max_val-2)*ways(i-1) เนื่องจาก arri ไม่สามารถเป็น 1 หรือ arri-1 ได้
- ถ้าสมาชิกลำดับสองจากท้ายเป็น 1 แล้ว ways จะเป็น (max_val-1)*ways(i-1) เนื่องจาก arri-1 เป็น 1 และ arri-2 ไม่ใช่ 1
- Ways(i) จะเป็น: (max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)
- รับตัวแปร size, max_val และ last_element เป็นอินพุต
- ฟังก์ชัน diff_val(int size, int max_val, int last_element) รับอินพุตทั้งหมดและคืนค่าจำนวนอาร์เรย์ที่มีสมาชิกติดกันต่างกัน
- กำหนดค่า count เริ่มต้นเป็น 0
- รับอาร์เรย์ arr[Max_N] = { 0 } เก็บจำนวนวิธีการเติมอาร์เรย์ เริ่มต้น arr[0] = 0 และ arr[1] = 1
- วนลูปจาก i=2 ถึง i < size
- กำหนด 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]
- มิฉะนั้นคืนค่า arr[size - 1]
- ในที่สุดคืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#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
