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

1 次查看（过去 30 天）
Michael
Michael 2023-7-9
编辑： 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 个评论
Matt J
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Mahesh Chilla
Mahesh Chilla 2023-7-10
编辑：Mahesh Chilla 2023-7-10
Ran in:
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!!

更多回答（1 个）

Image Analyst
Image Analyst 2023-7-9
Ran in:
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

类别

在 Help Center 和 File Exchange 中查找有关 Variables 的更多信息

标签

产品


版本

R2023a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by