Once you understand the basics of C++ programming language, it is essential for you to develop your problem solving skills using C++ program. In other words, you should know how to develop your programming logic to solve a given problem.
In this tutorial, we’ll give a simple binary problem, which you should solve by writing a C++ program.
Problem Definition
The user will enter the number of digits (n) of a binary number. You need to write a C++ program that will generate all binary numbers with n ciphers, of which two are ones and the rest of ciphers are zeros.
For example:
User input: n=3
Program output: 011, 101, 110.
User input: n=4
Program output: 0011, 0101, 0110, 1001, 1010, 1100.
User input: n=5
Program output: 00011, 00101, 00110, 01001, 01010, 01100, 10001, 10010, 10100, 11000..
Problem Analysis
We can solve this problem using several ways. The following are three possible solutions among several potential solutions.
Algorithm 1: Generate all n cipher binary numbers and display only those that have two ones and rest zeros in their binary presentation.
Algorithm 2: Try to discern the pattern, and translate those numbers into their binary format.
Algorithm 3: First, let us write the output as shown below. We have two markers that represent position of two ones in binary number. For simplicity we could call them the left one and the right one. At the start position, the first row, the left one is located at the second position from right end and the right one is located at far right. Right one shifts to the left side, and when it reaches the left one, it resets its position and goes to the far right end, the left one moves one position toward left end. When left one reaches left end, and the right one is just next to the left one, we stop the program.
0011, 0101, 0110, 1001, 1010, 1100
The first algorithm shown above is very straight forward. It creates a correct solution, but the processor would have many cases of unnecessary checks. However, this approach would be acceptable if we wish to display n binary numbers with k ones.
The second algorithm shown above is good in terms of speed, but its implementation could be difficult to understand.
So, we’ll pick the third algorithm to solve our problem.
C++ Program Code to Solve the Problem
If you are totally new to C++ programming, you should first understand C++ class and object.
The following C++ program code was developed using the third algorithm explained above, which will solve our given problem.
#include <iostream>
using namespace std;
void Display( int , int, int);
int
main(void){
cout<<"How many digits in the binary number->";
int iN; cin>>iN;
//Start position for left and right marker
int i= iN-1,
j= iN;
while(!((i==1)&&(j==2)))
{
Display( i, j, iN);
if(i==j-1)
{
i--; j=iN; cout<<endl;
}
else
{
j--;
}
}
cout<<"11";
for(int i=2; i<iN; cout<<'0',i++);
cout<<endl;
int iEnd; cin>>iEnd;
return EXIT_SUCCESS;
}
void
Display( int i,int j,int n)
{
for(int k=1; k<= n; k++)
if( (k==i)||(k==j))
cout<<'1';
else
cout<<'0';
cout<<endl;
}
Additional Exercises
- Try to solve a similar problem, but n cipher binary number has only single one.
- Try to solve a similar problem, but n cipher binary number has three ones.
- Try to solve a similar problem, but n cipher binary number has k ones.
- Try to disassemble arbitrary positive integer n into the sum of two squares of positive integers. a^2 + b^2 = n where a,b <n.
- Try to disassemble arbitrary positive integer n into the sum of two cubes of positive integers. a^3 + b^3 = n where a,b <n.
- If we have a set of k different positive integers and one positive integer n.
- You need to find whether is it possible to find two numbers from the set, whose sum would equal the n. If possible determine all positive representation.
- Find the sum of an arbitrary two numbers from the set, whose sum is closest but not equal nor greater than n.
- Find the sum of an arbitrary two numbers from the set, whose sum is closest but not equal nor lesser than n.
- Find all combination of two numbers from the set which sum is in certain interval [x…y].
- We have the set of k positive integers, and one positive integer n. Investigate whether is it possible to get a number n as a: sum, difference or product of two arbitrary numbers ki and kj from the set.
My name is Ramesh Natarajan. I will be posting instruction guides, how-to, troubleshooting tips and tricks on Linux, database, hardware, security and web. My focus is to write articles that will either teach you or help you resolve a problem. Read more about
Comments on this entry are closed.
My C code to solve the problem:
#include <stdio.h> void display(int id1, int id2, int num) { int x; for (x = 0; x < num; x++) { if (x == id1 || x == id2) { printf("1"); } else { printf("0"); } } } int main(int argc, char **argv) { int n = 4; /* Binary number size */ int id1 = 0; int id2 = 1; /* This tells the program to not print ", " before the first number. */ int first = 1; for (id1 = n-2; id1 >= 0; id1--) { for (id2 = n-1; id2 >= 1; id2--) { if (id1 != id2) { if (!first) { printf(", "); } display(id1, id2, n); first = 0; } } }Unfortunately the example is not good to show what C++ is all about. The code would change just insignificantly if written in pure C. It is an example for writing an algorithm in C, not in C++
Well, I like to use C++ this way.
I know OOP, grafical user interface and so on. You have miss the point.
Onece apona time, I have had some text books, and the code was the most optimized and so on, but some how I did not learn a lot.
Then I got some other text book, it was full of mistakes, and so on, I tried to improve the code and then I started to learn.
For You the best thing would be, if the mayor concern is not having the classes, try to do it but with all OOP things.
Even on this site, there are samples of classes and objects and inheritacne, and so on, just go for it!
God luck, and thank you for beeing interested in the article!
If you like OOP things try to make the class with one function inside, and if you really like it try to solve the 1, 2, and 3 in same class, or you could create few different classes as well as abstract one and then you start bilding it…
God luck, and have fun.
Nice effort Diogo! Keep up good work.
This is my Go code to solve the problem
“`
package main
import “fmt”
var inputnum uint = 10
func main() {
var i, j, a, b uint
for i = 1; i <= inputnum-1; i++ {
a = 1 << i
for j = 0; j <= i-1; j++ {
b = 1 << j
fmt.Printf("%0*b\n", int(inputnum), a+b)
}
}
“`
Thank you for beeint iterested! I don’t use Go, so from that point of view I would bew useles for now. But it is nice to see people participate and have different ideas how to solve the problem. Good.
Try to write the comments when you develop your code.
This would be example where to use them, that way I would see what the algorithm is.
And for those who would like to use OOP, there is a UML for class-es and so on.
A lot of students studying computer science are looking for this type of article. C++.
That’s the whole deal. I hope they will come here very often.
Thank you Davison for nice comment, but my intention was not only to reach the students but those people that start the programming and also those ones that would like to learn C++ after they have learnd some other programming language. And int next articles I will try to show some more interesting things that have not been on the ear on TSG. I will hope to attract more people to see some of the things that I will be sharing in future.
Below is a pure c++ compact code that presents a most general version of the above with a much more neat algorithm. You give it the number of 1-bits and the max. number of bits (order) allowed and it filters out all patterns with the same number in the max. interval {0, 1, …, 2^order}.
The trick is that you do not need to look inside binary patterns at all! It suffices to know the sequence of 1-bit summands as shown in Wolfram’s site here.
Unfortunately, neither Wolfram nor Wikipedia mention that these are recursively constructible functions. The program performs that particular recursion and then extracts the binary representation of the corresponding array index. For more on such techniques check the report at the link here.
#include #include using namespace std; void dec2bin(int); int main() { int bits, size, last; int order; int *index; cout <> bits; cout <> size; order = pow(2, size); index = new int [order]; // allocate memory to index dynamically cout << "Combinatory Set Order : " << order << endl; last = 1; index[0] = 0; for (i=1; i<=size; i++){ for (j=1; j<=last; j++){ k = last + j - 1; index[k] = index[j-1] + 1; if (index[k]==bits) { cout << k << ' '; dec2bin( k ); cout << endl; } } last = 2*last; } delete index; return 0; } void dec2bin(int number) { int remainder; if(number <= 1) { cout <> 1); cout << remainder; return; }That’s a nice programming problem, but I got a few (somewhat caustic — please excuse) comments:
a) What is the reference to “C++ class and object” good for? I mean, there are really no (useer-defined) classes or objects around… (this is somewhat the same as engeland’s comment)
b) C++ is a tool (particularly in this case and for this task), and this problem is probably an equally good task for Python, C, BASIC, … (or meow’s “Go”, for that matter).
That’s not to say, it were not a good problem for learning C++.
c) The solution meow offers is very understandable, regardless of the different language. And it’s a good one, because it hints at an important aspect: Try to see if someone else came up with a solution already or if you can translate the problem to something you already know an efficient solution for.
meow’s program is essentially what you often see in the scientific context (e.g. sum over i and a nested sum over j, where j < i, and maybe a third one over k, where k < j).
To go a step further, one would probably like the code to be recursive, such that an arbitrary depth can be achieved.
The points to stress from c):
– Try to see what others have done (and learn from it), instead of reinventing the wheel (ok, for an exercise, you sometimes have to reinvent the wheel and the spokes and…)
– Understand the problem by abstraction to something you know (Algo 1 is the "get something done" approach of intellectual blindness — sometimes ok, but generally bad. Algo 2 makes an attempt, but that's not followed (for legitimate reasons). Algo 3 is obviously born out of a better understanding of the problem)
Just my $0.02 worth. 😉
@rtheo: I’m afraid the form “swallowed” some of your code. There are obviously some parts missing (e.g. the “remainder” assignment at some point). It would also help to have a little more explanation of the code (what does the digit sum have to do with it? etc.). And without knowing your real code, I dare say the “if” statement lets one assume that this is not a very efficient solution.
to RTheo, well I have provided my solution, tried to make people interested in it, I am very happy that there has been some response, but I don’t understand why do you have the need to put may solution down, it could be usefull in some other situations. I have solve the problem the way I did. OK if you think that is for critics you are free to so so. I will not test your solution it is like something I did all my life. Well code mistakes will not be discused.
to Hendrik Vennekte > Well well objects, try for example to read what I have written to already mentioned ser, if you don’t like it like that try to writte the stand allone function or perhaps would you prefer a frined function, well it is a exericeze for the people who like to program. I am very aware of tha proverb Give a man a fish he will eat today, tech him how to fish he will eat forever. Well for language, I don’t code in Go, so this would be examplle where to use comments in code, but sharp criticizm that is good, it is bit provocativ, so whay you don’t try the other ones, the ones that are not solved, well that would be more fun. For recursion it is funny because it would be like the that thing that people call rim. Hope the next tree articles will be more fun for you> it will be tha templates, some vectors and Fibonachi. The one who adores recursion could try it him self and post it. It is a show of of ideas, all the time welcome for that one. Not try to put of or what so ever, just don’t see ….
Shor story long it could be done like> for(int i=0; i<n-1; ++i) for(int j= i+1; j <n; ++j) Display(i,j); but look at the Bigger picture, that is the way one day I will walk.
As far as the form is concerned, a simple copy+paste suffices to reproduce the text. I am not responsible for what happens after moderation. Missing lines are just
#include , #include
The decimal-to-binary routine is not essential and can be replaced with bitset.
The “if” statement has nothing to do with efficiency whatsoever. The whole point was to show that there is no need to have the actual bit patterns in order to locate certain properties of them. For example, in the case you want to know all integers containing just 2 bits, the sum of digits tells you that immediately. One then just needs to observe that this function is recursive in the following manner
Starting with the Set {0} you add 1 to get the Set {0, 1} and you repeat as
S(n+1) <– { {S(n)}, {S(n) + 1} }
You then just pick up the subset of the above sequence containing only 2s.
If the moderator wishes so, it is possible to show other such interesting techniques like locating cyclic permutations or constructing integer partitions.
Look at the link and think waht would be the meaning!
Well the MT would go like this, thanks for that link i will study that thing later.
Step 1.
Create arrays like 000011, 000101, 001001, 010001, 1000001,
Step 2.
Look at them like big bag of jobs, each trad would take one and apply tha thirs algorithm .
For thos who mentioned payments well listen to ZaZ(Je Veux). This algrithm is my becaUSE I have never read that in litereature, internet, or in any books. I can not say that somebody else have never thougt about it…
Great fun for TSG comunity….
@rtheo Thanks for the clarification, the formula is somewhat easier to read. (you might want to add the “cout ” statements to the list of things that didn’t quite copy correctly, though 😉 ).
> The “if” statement has nothing to do with efficiency whatsoever.
Sorry, but I’ll have to profoundly disagree with that. I’ve seen code where “if”s in the innermost loop were detrimental to performance and I’ve seen code, where “if”s saved from more expensive computations (sqrt), but their effect (positive or negative) somewhat depends on the problem at hand. But my real point about the “if” in this algo will follow below.
> The whole point was to show…
That’s certainly an interesting and legitimate point
> the sum of digits tells you that immediately
So that essentially means you followed the route of “Algo 2” from the original. Nice work!
> function is recursive
Ok, here we have a slight difference in nomenclature. What you are referring to is more “mathematical recursion”, but your algorithm is not recursive but sequential (which is good, because recursion often trades performance for universality). What I was referring to is recursion for an arbitrary number of 1s in the bit pattern (something like
void generatePattern(vector patternSoFar, int digitsLeft, int OnesLeft)
which would print the pattern, once digitsLeft == 0)
That’s more “algorithmic recursion”. (these terms might not be accurate, I’m just trying to illustrate)
Some style critique as I am tracing your algo on paper: C++ coders usually prefer the (int i = 0 ; i You then just pick up the subset
… and here is where the problem lies (and why “if” HINTS at an inefficiency — note that “if” is not inefficient per se): That’s just highly inefficient. Because it is essentially Algo 1 (Generate everything (ok, you are not doing that explicitly, of course) and then “display only those that have two ones and rest zeros in their binary presentation”). The problem is that you have many, many “unsuccessful” attempts and that’s why the “if” hints at an inefficiency: It just turns out that the condition of the “if” is not fulfilled very often.
Don’t get me wrong, please: I think you have an interesting approach an sure taught us (that is me in particular) something interesting about number theory. But for the problem at hand, the solution is a) too complex (ok, one might disagree here) and b) too inefficent.
To make it more specific: Your algo runs with O(2^n) where n is the length of the bit pattern, while meow’s code runs with O(n^2), which is much, much better.
Your algo scales independently of how many 1s should be in the pattern, but the analogon of meow’s would be O(n^k) (where k = number of 1s), which is polynomial.
(if you look at the actual performance, the worst case for meow is obviously k = n/2 because from then on you could just interchange 1s and 0s).
> If the moderator wishes so…
Ok, I’m not the moderator, but please do. But I guess this would be enough for an article in its own right.
… by the way O(2^n) is the worst possible scaling (equivalent to checking all numbers in sequence).
and meow’s scaling is (more precisely) rather O((n over k)) (binomial coefficient) (which is < O(n^k)) and thus really the best possible as that is the actual number of combinations we are looking for.
Well for Meow’s case I am not sure. It would be better if he had made some comments, so that people who don’t use Go would know, what did he ment. And if row a=1<<i is like overloading operator << then if that thind is called i timer, well sir you know already recalculate the speed for the starters, becaus if is implemented with overloading the operator, that will make the think more slow and it could have some repeats inside that I don't know of, and will not be able to accept your estimation.
@duskoKoscica Meow’s code does pretty much the same as the article’s code does in terms of the “for” (original: “while”) loops. It visits every binary number that matches the criterion exactly once, therefore the scaling is proportional to how many numbers there are of that kind (for k =2, that would be n*(n-1)/2 = (n over k)). For my personal taste, I’d claim that his formulation (regarding the loops) is easier (as it looks more similar to the sum_{i=1}^n sum_{j < i} situation, I alluded to earlier).
My suspicion is that
a = 1 << i
is the same as in C++ (aka the "bit shift operator"), not to be confused with "<<" in the case where the left operand is a stream (as in "cout << …")! If that's implemented extremely poorly, you'd be right and it would add another n to the scaling (would still be polynomial, though). But it should be possible to implement that in constant time in hardware. On the other hand, that does not refute this being the most efficient, as the number has to be generated eventually at some point (see the "void Display()" function in the article, has the same problem).
I'm not an expert on this, but I dare say overloading (remember that "<<" is really the bit shift operator, built in) should be something resolvable at compile time and any reasonable compiler should not introduce too much overhead here.
Ok, here’s some code with a recursive call for an arbitrary number of ones and zeros (I’d contend it looks much nicer without the comments, but I’ll concede that commenting in general is a good thing):
#include #include using namespace std ; void printBinNumbers( int zeros, // number of zeros remaining int ones, // number of ones remaining vector numberSoFar = vector() // binary number accumulated so far, with default // argument (empty number) ) { if (!zeros && !ones) // no digits left -> print it { for (int i = 0 ; i < numberSoFar.size() ; ++i) cout << numberSoFar[i] ; cout << endl ; return ; // not strictly necessary, // but for efficiency's sake } numberSoFar.push_back(0) ; // add a digit (zero) if (zeros) printBinNumbers(zeros-1, ones, numberSoFar) ; // recursive call, already added a zero to the // number above. if (ones) { numberSoFar.back() = 1 ; // change the last // digit to one. printBinNumbers(zeros, ones-1, numberSoFar) ; // and another recursive call. } } int main() { printBinNumbers(5,2) ; // sample call for five zeros and // two ones. }… and sorry for not formatting correctly (looks like a mess).
An one more thing I did not know that you could calculate the speed up of the parallel proces versus the single thread like that. I mean the way you have calculate it, it would be of great help for me to see it on Internet, like some site or something like that.
One more, is there iomanip library, could you check that for me please, it has sometnihg like setfill( something), it would be great comtribution to the article.
Well when they create nice environment to hava like 1000 treads I would like to comapare multy treading solution with high number of treads on the high number of cores with recusive one.
@duskokoscica: Who calculated the speed up of parallel processes here? And what does “setfill” have to do with that? That’s a stream manipulator…
One thing the code meow had shown still don’t have comments, if you could writte it in C++ so that I could understand it more better, but if I could gess… Well, you better writte the code in C++, because you know the Go, and it would be possible to see what when why and so on. The MT algoritm is for multy threading purpose only. So if we had some misscomunication it would be better to writte to who are you commenting and which of the comments. I have for example nice comment from that guy that refered me to Wolfram link.
Oh sorry, sorry, My bad, I did not get what that code in Go ment. Now I have C++ code to go with small n, tha ones that could be fitted in unsigned long long int, and if somebody uses bigger n, that will not fit in unsigned long long int, then I could apply the third algoritme. But the problem with it is that the number n would be different in different evnironments, like int could depend on the ….. Well, cool that is indid fast but it should be applied with care! Thanks people nice stuff! So what data type Linux pros use for int?
@duskoKoscica: Ok, but I still don’t get what the multi-thread comment was about? Is that somewhere in the wolfram articles? I’m confused…
Regarding the int types (I wouldn’t consider myself a “pro”, though): There are generally two aspects to consider: performance and size. If you have huge arrays, size might be the constraining factor and you’d want your integer (or float for that matter) to be small (short (or float for floats)). However, (to the best of my knowledge) the CPU is usually built for handling larger ones efficiently (64bit), so for the CPU it doesn’t matter much, whether it has to process n times a 16 bit or a 64 bit integer (if we disregard transfer in memory for a moment — which makes a difference provided that the architecture can address smaller ints).
The vector I used is a particular example of how this gets difficult. A bool is normally 1 byte (because that’s the smallest allowed value), but the vector MAY be optimized such that one element consumes only the one bit it actually needs (but this makes operator[], e.g., a little different from normal).
Another remark: Be careful when porting code from one platform to another (I had that once, when Windows ints were 16 bit and Linux ints were 32)…
(not sure if all of this somehow answers your question, but I hope it helps)
As now thing look it was a micomunication. Like spagetti communication.
Don’t worry about now, I will find site where they have source code from Linux pross and that is what it make it so great. You don’t need to wait from some leaks like from … so that you figure out some technologies… Have nice day people!