Question

In: Computer Science

Answer the following Discrete Structures Suppose string s = (s1 s2 ..sn). Give a recursive definition...

Answer the following Discrete Structures

Suppose string s = (s₁ s₂ ..s_n). Give a recursive definition of the function numOnes(n), which counts the number of 1s in bit-string of length n, Make sure to define the function for the base case, numOnes(0).

Solutions

Expert Solution

Explanation :

String :

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation).
A string is generally considered as a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding.
String may also denote more general arrays or other sequence (or list) data types and structures.
Depending on the programming language and precise data type used, a variable declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ dynamic allocation to allow it to hold a variable number of elements.
When a string appears literally in source code, it is known as a string literal or an anonymous string.
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set called an alphabet.

In the light of the above discussions, the solution to the given set of question is as follows:

The Solution :

INPUT :The given bit string s = ( s1 s2 ... sn )

OUTPUT : The number of 1s in the string s counted by the recursive function numOnes(n).

Note : The function should define the base case numOnes( 0 ) .

Definition of the recursive function numOnes(n) :

numOnes ( n )

{

int number = 0; // define variable to store the number of 1s, initialised to 0

int i = 0 ; // define loop variable

int length = n; // define variable length to denote the length of the string passed as argument in the function call

string s = ( s1 s2 ... sn ) ; // the given string of bits consisting a series of 0 or 1, may be blank string as well

for ( i = 0, i < length, i++ )

{

if s [ i ] = =1,

{

number = number + 1;

} // end if

return number;

} // end for loop

} // end function

Note : For the base case numOnes ( 0 ), the function returns number = 0 as it was initialised to 0.

This concludes the answer to all parts of the question along with the necessary explanations.

Please do not forget to like the answer if it helps you. Thank you.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Let S = (s1, s2, . . . , sn) be a given sequence of integer...

Let S = (s1, s2, . . . , sn) be a given sequence of integer numbers. The numbers can be positive or negative. We define a slice of S as a sub- sequence (si,si+1,...,sj) where 1 ≤ i < j ≤ n. The weight of a slice is defined as the sum of its elements. Provide efficient algorithms to answer each of the following questions: a)Is there any slice with zero weight ? b)Find the maximum weight slice in...

Java RECURSIVE methods: => intersection(String s1, String s2): takes two strings and returns the string consisting...

Java RECURSIVE methods: => intersection(String s1, String s2): takes two strings and returns the string consisting of all letters that appear in both s1 and s2. => union(String s1, String s2): takes two strings and returns the string consisting of all letters that appear in either s1 or s2. =>difference(String s1, String s2): takes two strings and returns the string consisting of all letters that appear only in s1.

Code in c# Write a recursive method called isReverse(String s1, String s2) that accepts two strings...

Code in c# Write a recursive method called isReverse(String s1, String s2) that accepts two strings as parameters and returns true if the two strings contain the same sequence of characters as each other but in the opposite order and false otherwise. • The recursive function should ignore capitalization. (For example, the call of isReverse("hello", "eLLoH") would return true.) • The empty string, as well as any one letter string, should be its own reverse. Write a driver program that...

1. What is the output of the following code: string s1 = “X”; string s2 =...

1. What is the output of the following code: string s1 = “X”; string s2 = “A” + s1 + “BC” + s1 + “DEF” + s1 + “G”; cout << s2; 2. What is the output of the following code: string s1 = “X”; string s2 = “A” + s1 + “BC” + s1 + “DEF” + s1 + “G”; cout << s[0] + s[3]; 3. What is the output of the following code: string s1 = “X”; string...

True or False) The following code will output "I was true". bool isGreater(string s1, string s2)...

True or False) The following code will output "I was true". bool isGreater(string s1, string s2) { if(s1 > s2) { return true; } return false; } int main() { if(isGreater("before","back")) { cout << "I was true"; } else { cout << "I was false"; } return 0; }

(10 marks) Write a function to check whether string s1 is a substring of string s2....

Write a function to check whether string s1 is a substring of string s2. The function returns the first index in s2 if there is a match. Otherwise, return -1. For example, the function should return 2 if s1 is "to" and s2 is "October". If s1 is "andy" and s2 is "candy", then the function should return 1. The function prototype is as follows: int indexOf(const char *s1, const char *s2).

Suppose you have a set of real-valued waveforms {s1(t), s2(t),..., sN(t)}, and you want to find...

Suppose you have a set of real-valued waveforms {s1(t), s2(t),..., sN(t)}, and you want to find a basis for the span of their complex envelopes. The obvious approach would be to first downconvert each of the waveforms, and then apply the Gram-Schmidt procedure to the set of complex envelopes. Will we get the same answer if we first apply Gram-Schmidt, and then downconvert? Justify your answer.

Determine if each of the following recursive definition is a valid recursive definition of a function...

Determine if each of the following recursive definition is a valid recursive definition of a function f from a set of non-negative integers. If f is well defined, find a formula for f(n) where n is non-negative and prove that your formula is valid. f(0) = 1, f(n) = -f(n-1) + 1 for n ≥ 1 f(0) = 0, f(1) = 1, f(n) = 2f(n-1) +1 for n ≥ 1 f(0) =0, f(n) = 2f(n-1) + 2 for n ≥...

Suppose you have two strains of mice, S1 and S2. Strain S2 is genetically modified to...

Suppose you have two strains of mice, S1 and S2. Strain S2 is genetically modified to metabolize a pharmacon P supposedly faster than S1. You conducted an experiment in a sample set of each strain, in which the pharmacon was injected and its concentration in blood was measured every 15min for 2h. Of course, age, gender, and weight was recorded for each animal. You want to statistically demonstrate that the metabolic rate of N is higher in S2 than S1....

Write each vector as a linear combination of the vectors in S. (Use s1 and s2,...

Write each vector as a linear combination of the vectors in S. (Use s1 and s2, respectively, for the vectors in the set. If not possible, enter IMPOSSIBLE.) S = {(1, 2, −2), (2, −1, 1)} (a) z = (−8, −1, 1) z = (b) v = (−2, −5, 5) v = (c) w = (1, −23, 23) w = (d) u = (2, −6, −6) u =

Subjects