Problem 3 (20 points) The function ones(x) takes as input a bit string (of O\'s
ID: 3914400 • Letter: P
Question
Problem 3 (20 points) The function ones(x) takes as input a bit string (of O's and 1's) and returns a count of how many digits in X are 1. All bit strings as input will have length of 1 or more so the smallest valid inputs are "1" and "O". Further, one can "subdivide" the a string into parts like X-YZ a) Give a recursive definition for the function ones(X). This can be mathematical notation or some sort of pseudocode. Use strong/structural induction to prove that the following identity hold. ones(x Y)onesones(Y) That is, the value of ones(0 applied to the concatenation of two bitstrings is equal to applying b) the function to each bitstring separatelyExplanation / Answer
#include <bits/stdc++.h>
using namespace std;
int ones(string str)
{
if(str.length()==1 && str[0]=='1')
{
return 1;
}
else
{
if(str[0]=='1')
{
return 1+ones(str.substr(1));
}
else
{
return ones(substr(1));
}
}
int main()
{
string str;
cout<<"Enter string input"<<endl;
cin>>str;
cout<<"No of ones in the given input string is"<<ones(str)<<endl;
return 0;
}
A structural induction proof says that if P(I) is true for some instance I and P(M) is also true if M is obtained by some recursion of I.
Here is also same main string is XY and the substrings X and Y are obtained in the recursion.
For example
length(L ++ M)=length L +length M
++ is concatination here.
length []=0
length(h:t)=1+length t
[] ++ list=list
(h:t)++ list=h:(t++list)
length(L++M)=length([] ++ M)
=length M
=0+length M
=length []+length M
=length L+length M
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.