Finding the amount of times '101' appears and does not appear in a series of strings

Hello!

I am trying to answer two connected questions for my Computer Engineering class. The code runs, however, I do not think it is correct. I feel as if I have multiple errors or am overlooking some aspects. Please help! Thank you so much

My code:

%% possible different binary strings
A = 2;
B = 31;
C = A.^B;

fprintf('The number of different binary strings of length %d is: %d\n', B, C);


%% question "How many binary strings of length 31 DO contain the string 101?"

% Define the length of the binary strings
n = 31;

% Initialize the dynamic programming table
dp = zeros(n + 1, 2);
dp(1, :) = [1, 0]; % Base case

% Populate the dynamic programming table
for i = 2 : n + 1
    dp(i, 1) = dp(i - 1, 1) + dp(i - 1, 2); % Ending with '0'
    dp(i, 2) = dp(i - 1, 1); % Ending with '1'
    
    % Check if "101" is formed at the current position
    if i >= 4
        dp(i, 2) = dp(i, 2) - dp(i - 3, 1); % Subtract the count without "101"
    
    elseif i >= 3
        dp(i, 2) = dp(i, 2) - dp(i - 2, 1); % Subtract the count of strings ending with "101"
    end
end

% Compute the total count of binary strings containing '101'
count = dp(n + 1, 1) + dp(n + 1, 2);

% Display the result
fprintf('The number of binary strings of length %d that contain the string "101" is: %d\n', n, count);


%% question "How many binary strings of length 31 do NOT contain the string 101?"

% Define the length of the binary strings
n = 31;

% Initialize the dynamic programming table
dp = zeros(n + 1, 2);
dp(1, :) = [1, 1]; % Base case

% Populate the dynamic programming table
for i = 2 : n + 1
    dp(i, 1) = dp(i - 1, 1) + dp(i - 1, 2); % Ending with '0'
    dp(i, 2) = dp(i - 1, 1); % Ending with '1'
end

% Compute the total count of binary strings without '101'
count = dp(n + 1, 1) + dp(n + 1, 2);

% Display the result
fprintf('The number of binary strings of length %d that do not contain the string "101" is: %d\n', n, count);

Output:

The number of different binary strings of length 31 is: 2147483648

The number of binary strings of length 31 that contain the string "101" is: 7739

The number of binary strings of length 31 that do not contain the string "101" is: 5702887

[Matt J]

I feel as if I have multiple errors or am overlooking some aspects. Please help!

Help with what? You haven't told us what you think is wrong.

Answer 1

[Mahesh Chilla]

Hi Michael!

To generate all possible binary arrays of size 'n' and counts how many times the pattern [1 0 1] appears in those arrays. Initially, the code creates binary arrays by converting decimal numbers from 0 to 2^n-1 into their binary representations. A counter variable called 'ans' is initialized to 0 to keep track of the pattern occurrences. The code then examines each binary array, searching for the pattern [1 0 1] using the 'strfind' function. The function returns the starting indices of the pattern within each array. Occurrences of the pattern are counted by calculating the number of elements in the 'ind' array using numel. The count is added to the ans counter. Finally, the total count of [1 0 1] pattern occurrences is displayed by printing the value of ans. To find the the number of no occurences of [1 0 1], you can add another statement in the 'for' loop i.e "ans1=ans1+n-2-numel(ind)", since max occurences in an array is n-2 (where n is the size of the array)Assuming the value of 'n' to be 4, since 'n' as 31 gives maximum array size error.

The following code will find the occurences of [1 0 1] in all possible binary arrays of size 'n'.

n = 4;  % Size of the binary array

arr = dec2bin(0:2^n-1) - '0'; % Generate all binary arrays

ans = 0;  % Counter for occurrences of [1 0 1] pattern

sz = size(arr);  % Get the size of the binary array

for i = 1:sz(1)
    ind = strfind(arr(i,:), [1 0 1]); % Returns starting indexes of each occurrence of [1 0 1] in arr(i,:)
    ans = ans + numel(ind); % Count the number of occurrences and add to the counter
end

ans  % Display the total count of [1 0 1] pattern occurrences

ans = 4

To learn more about the functions used in the code, refer the MATLAB's documentation.

• https://www.mathworks.com/help/matlab/ref/dec2bin.html
• https://www.mathworks.com/help/matlab/ref/strfind.html

Hope this helps,

Thank you!!

Answer 2

[Image Analyst]

Use strfind. For example:

dp = [0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1]

dp = 1×19

0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1

indexes = strfind(dp, [1 0 1])

indexes = 1×5

2 4 8 10 16

numOccurrences = numel(indexes)

numOccurrences = 5