เราได้รับด้วยจำนวนเต็ม N และ K เรามีสตริงไบนารีที่มีความยาว N ซึ่งประกอบด้วย 0 และ 1 เท่านั้น เป้าหมายคือการหาจำนวนของสตริงดังกล่าวที่มีความยาว N ที่มี K ติดต่อกันเป็น 1 กล่าวคือ ถ้า N=3 และ K=2 ให้นับเลขฐานสอง 3 หลักทั้งหมดที่เป็นไปได้ซึ่งมี 2 ตัวติดกัน 1 ตัว
ตัวอย่าง − 111, 1 ที่อยู่ติดกันตรงนี้ปรากฏสองครั้ง ( K ครั้ง )
ใน 011 และ 110 ติดกัน 1 ปรากฏเพียงครั้งเดียว
เราจะแก้ปัญหานี้โดยเก็บผลลัพธ์ของค่าก่อนหน้า
กำลังนับอาร์เรย์ 3 มิติ[x][y][z] โดยที่ x คือ N, y คือ K และ z คือหลักสุดท้ายของสตริง ( 0 หรือ 1 )
- สำหรับ N=1 สตริงจะเป็น “0” และ “1” นับ 1’s=0 ประชิด
ดังนั้นสำหรับ K ใดๆ ถ้า N=1 ให้นับ=0
นับ[1][K][0] =นับ[1][K][1] =0.
- เมื่อหลักสุดท้ายเป็น 0 ให้เลข 1 ติดกันนับเป็น K
ตัวเลขทั้งหมดของความยาว N-1 พร้อมตัว K + 0 สุดท้าย → ความยาวใหม่ =N
หากการนับของ K ประชิด 1 คือ C การบวก 0 ต่อท้ายจะไม่เปลี่ยนการนับนั้น
นับ[N][K][0] =นับ[N-1][K][0] + นับ[N-1][K][1]
- เมื่อหลักสุดท้ายเป็น 1 ให้นำ 1 มาประชิดนับเป็น K
ตัวเลขทั้งหมดของความยาว N-1 ที่ลงท้ายด้วย 0 โดยตัว K + 1 ตัวสุดท้าย → ความยาวใหม่ =N
นับ[N-1][K][0]
ตัวเลขทั้งหมดของความยาว N-1 ที่ลงท้ายด้วย 1 โดยมีตัว K-1 + 1 ตัวสุดท้าย → ความยาวใหม่ =N
นับ[N-1][K-1][1]
นับ[N][K][1] =นับ[N-1][K][0] + นับ[N-1][K-1][1]
จำนวนสตริงดังกล่าวทั้งหมด=count[N][K][0] + count[N][K][1]
อินพุต
N=4, K=2
ผลลัพธ์
Count of strings: 2
คำอธิบาย − 1110, 0111 เป็นสตริงเดียวที่มีความยาว 4 โดยที่ 1 ที่อยู่ติดกันปรากฏขึ้นสองครั้งเท่านั้น
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
อินพุต
N=3, K=1
ผลลัพธ์
Count of strings: 2
คำอธิบาย − 110, 011 เป็นสตริงเดียวที่มีความยาว 3 โดยที่ 1 ที่อยู่ติดกันปรากฏขึ้น 1 ครั้ง
ใน 111 ตัวที่อยู่ติดกัน 1 ตัวจะปรากฏสองครั้ง
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
จำนวนเต็ม N และ K เก็บความยาวของสตริงและหมายเลข ของจำนวนครั้งที่อยู่ติดกัน 1 ปรากฏในแต่ละรายการ
-
ฟังก์ชัน stringcount(int n, int k) รับ n และ k เป็นพารามิเตอร์และส่งคืนค่าจำนวนสตริงที่มี K คูณด้วย 1 ที่ติดกัน
-
Array count[i][j][0/1] ใช้เพื่อนับจำนวนสตริงที่มีความยาว i โดยที่ j อยู่ติดกัน 1 ส่งด้วย 0 หรือ 1
-
เงื่อนไขเริ่มต้นคือ count[1][0][0] =1; นับ[1][0][1] =1;
-
ตอนนี้เริ่มจาก 2 สตริงความยาว ( i=2) ถึง n ความยาว สำหรับแต่ละสตริงการตรวจสอบจำนวน Ktimes ติดกัน 1 j=0;j<=k จากการนับครั้งก่อน อัปเดตจำนวนปัจจุบัน[i][j][0] andcount[i][j][1].
-
ถ้า j-1>=0 จำนวน 1 ตัวที่อยู่ติดกันมากกว่า 1 จากนั้นให้อัปเดตจำนวนสตริงที่ลงท้ายด้วย 1 เป็น count[i][j][1] + count[i - 1][j - 1][1 ];
-
ในตอนท้ายให้เพิ่ม count[n][k][0] และ count[n][k][1] เก็บไว้เป็นผลลัพธ์
- คืนผลลัพธ์ตามจำนวนที่ต้องการ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed i-1
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];
}
}
int result=count[n][k][0]+count[n][k][1];
return result;
}
int main(){
int N = 6, K = 3;
cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
} ผลลัพธ์
Strings of length 6 and 3 adjacent 1's in each :7
