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

Question

Michael 2023-7-9

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1993518-finding-the-amount-of-times-101-appears-and-does-not-appear-in-a-series-of-strings

编辑： Mahesh Chilla 2023-7-10

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Matt J 2023-7-9

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 2023-7-10

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1993518-finding-the-amount-of-times-101-appears-and-does-not-appear-in-a-series-of-strings#answer_1270533

编辑：Mahesh Chilla 2023-7-10

在 MATLAB Online 中打开

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.

Hope this helps,

Thank you!!

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Image Analyst 2023-7-9

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1993518-finding-the-amount-of-times-101-appears-and-does-not-appear-in-a-series-of-strings#answer_1269898

在 MATLAB Online 中打开

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