one more doubt , 1s complement of zero can either be 1,1111 or 0,1111, right? when you take the complement of a number, you gotta take the complement of the sign bit also, right?
No. 1s complement of zero is either 1,1111 or 0,0000.
The book does not have answers provided because I have found that when books have answers, too many readers look at the answers and think they've understood the problems.
So if you could not make your first strategy work, perhaps you should try harder. The main point to realize is that you should use copy rather than uninitialized_copy to copy the elements that are to fill the erasure; then destroy the elements at the end separately.
Your code has an interesting strategy, but it has a few problems.
First, the C++ standard defines erase to work by copying elements from the part of the vector after the erasure on top of the elements being erased, then destroying the elements at the end of the original vector. It does this for several reasons.
One reason is that this strategy makes it unnecessary to have enough memory to contain two copies of the entire vector, which would otherwise be necessary if you were erasing, say, a single element. It also makes it unnecessary to copy the elements before the point of the erasure, which might be important if you are erasing only a few elements near the end of the vector.
Still, your strategy is an interesting one, and it has the advantage that if you are erasing a large part of the vector, you wind up using less memory after the smoke has cleared. So let's look at the code and see if there are any problems.
My first observation is that the parameters begin and end should be type iterator or const iterator& , not iterator& . As your code is written, it insists on accepting lvalues as arguments, and implicitly states its intention to modify those arguments--which you have no reason to want to do.
The next problem is on line 12, where the second argument to uninitialized_copy , begin-1 , should be begin . It is easy to see …
I do not believe that you are showing us the actual code. My reason for this disbelief is that you define a variable named maclu but then you use a variable named maclu1 . In order for this code to work, therefore, you must have defined maclu1 somewhere, but you have not shown us where.
Using rand() % n for a random number between 0 and n-1 gives results that are generally not random, even if rand() itself is perfect.
To see why, assume that rand() returns a 32-bit signed value, i.e. a value between 0 and 2147483647, inclusive, and that you are computing rand() % 190.
There are 2147483648 possible values that rand() can take on, and 2147483648 % 190 is 98. In other words, 190 does not divide 2147483648 exactly. This fact means that the 190 possible values that this algorithm yields cannot possibly occur with equal probability.
Having pointed out the problem, I'm going to leave the solution as an exercise...or, if you like, you can look up the nrand function in Accelerated C++.
If the #1, #2, etc. strings are unique and recognizable without knowing whether they're needed, then just make a single preliminary pass through the file, finding all such strings, and putting them into a map that leads to their locations.
Then, each time you want to locate such a string, just look it up in the map.
When you apply sizeof to an object of type string , you get the amount of memory that needs to be allocated for an object of that type, exclusive of dynamic memory. This number has nothing to do with the number of characters in the string , so the results you get will have little if any connection to anything useful.
The gentlemen above me have done a great job & answered well. I'd just like to add that chars inside switches are in fact converted to their ASCII equivalent ints. :)
Not quite. A char is just an integer with (usually) severe constraints on its value. Operations that involve chars and other integral types have nothing to do with ASCII or any other encoding.
I have to say that I don't like either alternative, becuase there is a much simpler, cleaner one. There is a built-in function named getattr with the property that getattr(x, 'a') yields the value of x.a . Similarly, setattr(x, 'a', y) has the same effect as x.a = y .
The way to know that such a method does not exist is to show that the values of A{M] through A[N-1] might be such that you cannot find out what the the median of A[0] through A[N-1] is without using the value that you threw away.
In other words, suppose you have already read A{0] through A[M-1] and you have not read A[M] through A[N-1]. Suppose further that you intend to discard A{i], with 0 <= i < M. Then what you need to prove is that it is always possible to find a single value x, together with values for A[M] through A[N-1] with the property that
the median of A[0] through A[N-1]
is not equal to
the median of (A[0] through A[i-1]), x, (A[i+1] through A[N-1])
Notice that in the process of finding these values, you can also determine the value of N. In other words, you can put as many values in A[M] through A[N-1] as you like.
Once you have figured out how to do this, you have solved the problem, because if the median of A[0] through A[N-1] depends on a number that you have thrown away, there is no way to figure out what that median might have been without knowing the discarded number.
I will leave as an exercise the problem of determining appropriate values for x and A[M] through A[N-1].
I am not going to try to run the code; I'm just pointing out the source of the first error message you cited.
The compiler says that Xnode is not defined, which means that the compiler has not seen its definition at the point at which you first use it. To fix that problem, you must arrange for the compiler to see the definition.
The definition of the type Xnode is missing. Once you have found the .h file that defines it, you should put include statements for that file in appropriate places.
It seems to me that the question you are trying to answer is a completely different question from the original exercise.
I think you are trying to answer the following question: Suppose we have a set of numbers and we throw one of those numbers away. Prove that the median of the reduced set (i.e. the set of numbers after we discarded one of them) will not always be the same as the median of the original set.
This is a very easy claim to prove, because in order to prove it, all you have to do is find one example--as you have done.
But it has nothing to do with the original problem. The original problem asks you to prove that there is no way to find the median of the original set no matter what you do. So any answer you give that talks about taking the median of the set after you have discarded a value is wrong, because it does nothing to prove that you might not be able to find the median of the original set in some other way.
I hate to rain on people's parades, but the original post says that it requires a bidirectional iterator. In fact, the code does <= comparisons on iterators--which means that it really requires random-access iterators.
"This proves that on some occasions you can discard a number."
Indeed it does. But those occasions depend on the numbers you have not yet read.
So, for example, imagine that you have read 1,5,7,9. You cannot discard the 5 because the numbers you have not seen yet might be 2,3,4,6,8. If they are, and you have discarded 5, then you have no way of knowing what the median actually was.
So we have just shown that for this particular input (1,5,7,9), we cannot discard 5.
Your job is to find a similar argument that shows that we cannot discard 1, nor can we discard 7, nor 9.
Then you have to extend the argument to show that for *any* numbers you have read, you cannot *ever* afford to discard *any* of them because the numbers you have not read yet *might* make it necessary to know the value of the number you discarded in order to figure out the median.
This is a subtle kind of argument, but if you spend the effort needed to fill in the details, you will learn quite a bit about how to write a proof.
Here is a hint. You have no idea what N is, except that N >= M. In particular, N might be much larger than M. So supppose you discard a single number, say A where 0 <= i < M. Can you imagine a set of values A[M] through A[N-1] that might make the median of A[0] through A[N-1] depend on the value A that you discarded?
Right. M and N cannot be negative because they are counters -- they represent the number of elements in a set -- and a set cannot have a negative number of elements.
Again, I can't figure out what you are trying to say. You say that "M (the numbers which are read in)..."
M is not the numbers which are read in -- M is how many numbers have been read so far. The numbers themselves are A[0] through A[M-1].
You may think that I am being too picky when I say things like this, but if you are going to try to prove something, it is important to do so in a way that makes it unnecessary for anyone to guess what you are trying to say.
You haven't actually asked a question; you've made a claim. As it happens, that claim is false, and it is false for a good reason.
Consider:
class Foo { /* something */ };
class Bar: public Foo {
public:
void f(double);
};
// ...
void x()
{
Bar b;
b.f(0); // Which function is called?
}
If C++ were to behave as you claim it does, you would not be able to answer this question, because the answer would depend on whether class Foo defined a member f that accepted an int argument. So whenever you derived a function from a class that someone else had written, you would have to know the name and argument types of every function in that base class, just in case you happened to define a function with the same name yourself.
Even worse: Suppose a newer version of the base class came along and defined a function that did not exist in a previous version? All of a sudden, you would find the meaning of your code changed.
So what C++ actually does is to say that a derived class is a new scope. Except for virtual functions, very name defined in a derived class hides the corresponding name from any base classes. Although this rule sometimes behaves in ways that seem surprising, in most cases it is safer than the alternative.
It is true that if M=0, there are no values to discard, so you don't have to worry about what happens if you discard one. Nevertheless, when you are trying to think formally about a problem, it is important to be very careful with your use of terms.
No, you are completely incorrect. First, I said 0 <= M <= N. You said 0 < M < N. So when I asked you to check your understanding by trying to prove something, you tried to prove something else.
I don't like to sound unkind, but if you are going to be successful as a programmer, you really have to learn to read more carefully.
You want to find the median of N numbers, which I will call A[0] through A[N-1]. You do not know the value of N.
You have already read M numbers, which are A[0] through A[M-1]. Because you have already read them, you know the value of M. You also know that 0 <= M <= N. If you have understood everything up to this point, you should be able to explain how you know that 0 <= M <= N.
What you have to prove is that you need to retain the values of all the numbers A{0] through A[M-1]. Note that if you knew the value of N, you might not have to do this. For example, if M=N, then that means you have read all of the numbers already, so all you have to do is compute the median and you can throw them all away.
For that matter, if M+1=N, then the median of A[0] through A[N-1] has a value that depends on only a few elements of A (Problem: Figure out which ones), so you can discard all but those few elements.
But you do not know how much larger N is than M, and it is this fact that means you have to remember all of the elements of A that you have read so far.
The problem, then, is to prove it.
Please note that statements such as "the numbers read …
You are assuming that if you discard a value, you are also discarding the knowledge of how many values there were. Nowhere does the problem say that.
Moreover, the problem is to show that there is *no* number you can discard. If I have 3, 1, 4, 1, 5, I can discard 1, 4, or 5, and so long as I remember that there were five numbers originally, I can still compute the median as being 3.
I am sorry, but I do not understand the connection between what you just said and the problem that you are trying to solve.
Again, the problem is to prove that it is impossible to compute the median of a collection of numbers without storing the values of all of the numbers at the same time. This property is in contrast with the mean, which it is possible to compute by storing only the sum of the numbers seen so far and the count of how many numbers have been read.
I think that this article, although interesting, has nothing to do with the original exercise in the book. In order to answer the exercise, you have to understand something important about algorithms, namely what information an algorithm needs at what point in its execution in order to be able to deliver a result.
In effect, the exercise asks you to prove a particular property of a particular collection of algorithms (i.e. all algorithms that are capable of computing the median of a sequence of values). I think that the only way to be sure you understand this property is to construct a proof yourself.
When you say "If you discarded a value you can't know if the outcome will be the same as the answer when you don't discard a value." This statement is correct, but it does not solve the problem.
The reason is that perhaps there might be some other procedure you could use to figure out what the median would have been anyway. So you have to prove that no such procedure can exist.
Suppose you have read some numbers, and there are other numbers you haven't read yet so you don't know what they are.
Pick one of the numbers you've read so far. Your job is to prove that whatever that number might be, it is possible that the numbers you are about to read will make it necessary for you to keep that number. To do this, you do not have to know what the unread numbers are -- you just have to imagine what they might be.
Another part of the point of this exercise, by the way, is to get you familiar with how people think about proofs, because often the best way of convincing yourself that a program works correctly is to sketch a simple proof. It doesn't even have to have every detail filled in.
I think it is very unlikely that the best solution to this problem will involve a two-dimensional array. An array of structures, perhaps, or (better) a vector of structures; but not a two-dimensional array.
How about posting a code fragment that illustrates your problem?
The quartiles of a set of data have nothing to do with groups of four numbers. Rather, the notion of a quartile is a generalization of the notion of a median.
In other words: To find the median of a set of numbers, you sort the numbers and then divide the sorted set into two pieces that are as close to equal in size as you can manage. The median is the value that fits between those halves. In other words, the median is the value such that the same number of values are >= the median as are <= the median.
The quartiles of a set of numbers are the values that divide the set into four subsets of equal size.
Ok, thanks for the additional info :!: I think I could do this by putting an if statement in it, for example when the while loop is at N°3 it should enter 0 into the vector, this way the amount of vectors is correct, but the total amount isn't.
The point of the exercise is to be sure that the reader understands why it is necessary for an algorithm that computes the median of a collection of values to be able to have access to all of the values at the same time. This access is not necessary for an algorithm that computes the mean, as such an algorithm can store just a running total of the values it has read.
