Please answer in C++ Language. Assignment : For this assignment you’ll be creati
ID: 3812467 • Letter: P
Question
Please answer in C++ Language.
Assignment: For this assignment you’ll be creating three different programs that deal with strings. You can make one multi-purpose program, or three individual programs, but they’ll need to perform the following tasks:
1.) Given a binary string, your program will have to ‘add one’ to it, giving the next binary string in sequence. i.e. Given 101011, program returns 101100.
2.) Given an input string, print out all PERMUTATIONS of the string. i.e., “cat” would yield “cat, cta, act, atc, tac, tca” NOTE: In a string like “madam”, each a and m is considered unique, so there are several different permutations of that string which would output “madam” as well.
3.) Given a number between 1 and 6, print out every NON-REPEATING possible COMBINATION of the set {A,B,C,D,E,F}. i.e., Given 2, the program would return AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF, EF.
Use your program(s) to handle the following six pieces of input:
1.) 10111011
2.) 1111
3.) Trick
4.) Copycat
5.) 3
6.) 5
Explanation / Answer
The idea for the first part is as follows:
Initialize a carry variable, which will keep track of the value of the carry throughout.
First make change to the last element of the string, and get the carry value. Then parse the rest of the string backwards, and based on the value whether 1 or 0 and if carry is 1 or 0, make changes to string. We also need to handle the case where there are all 1's. In that case we will have parsed the string, but we will still have our carry as 1. In that case append the 1 to our modified string. Code is as follows:
#include <iostream>
#include <string>
using namespace std;
int main(){
string s;
cin >> s;
int i,carry = 0;
int len = s.length();
if(s[len-1] == '1'){
s[len-1] = '0';
carry = 1;
}
else{
s[len-1] = '1';
carry = 0;
}
for(i = len-2;i>=0;i--){
if(s[i] == '0' && carry == 0){
break;
}
else if((s[i] == '0' && carry == 1) || (s[i] == '1' && carry == 0) ){
s[i] = '1';
carry = 0;
}
else if(s[i] == '1' && carry == 1){
s[i] = '0';
carry = 1;
}
}
if(carry == 1){
s = '1'+s;
}
cout << s;
return 0;
}
For the second part, you can use the concept of backtracking to solve it.
Code is as follows:
#include <iostream>
#include <string>
using namespace std;
void permute(string a, int l, int r)
{
int i;
char temp;
if (l == r)
cout <<a << " ";
else
{
for (i = l; i <= r; i++)
{
temp = a[l];
a[l] = a[i];
a[i] = temp;
permute(a, l+1, r);
temp = a[l];
a[l] = a[i];
a[i] = temp;
}
}
}
int main()
{
string s;
cin >> s;
int n = s.length();
permute(s, 0, n-1);
return 0;
}