You are not logged in.
Pages: 1
We need all the permutations: both "i" and "j" need to be of range { 1 <= "i/j" <= n }
but in my first post the lowest index was 0 and the highest index of the element was n-1 instead of "n". This is C++ specific because the index of the first element starts at 0. So the last one is n-1.
If the vector is: {2,3,5}
then we have these pairs:
2*2 = 4
2*3 = 6
2*5 = 10
3*2 = 6
3*3 = 9
3*5 = 15
5*2 = 10
5*3 = 15
5*5 = 25
However, you gave me the right hint. I've solved it.
The big hint is n^2. That's it.
Thanks for your "quick thought" . I was way too angry for a moment to think on my own you see :).
I need help on the following puzzle. I'll tell you the requirements then the story behind it.
Requirement:
find the amount of even and odd products from a vector with n elements in it. Or more specific:
ep = | {(i,j) :: 0 <= i < n AND 0 <= j < n AND even(Numbers[ i ] * Numbers[ j ]) |
op = | {(i,j) :: 0 <= i < n AND 0 <= j < n AND odd(Numbers[ i ] * Numbers[ j ]) |
Make an algorithm in some pseudo/imper coding language.
The Story
A collegue of mine sent me two algorithms, one algorithm takes too long (O(n^n) ) and one with complexity O(n). He claimed that the algorithm met the requirements as posted above. He was wrong and a student of found out (I never checked it).
I"ll give you the code:
#include <iostream>
#include <cstdlib>
void odd_even_pairs(const int* vec, std::size_t size, unsigned& ep, unsigned& op);
void odd_even_pairs_fast(const int* vec, std::size_t size, unsigned& ep, unsigned& op);
bool even(int num);
static const int Numbers[] = {12, 4, 6, 3, 7, 9, 10 , 44, 63, 63, 23, 34, 36,
346, 43, 61, 56, 264, 2463, 25, 2544, 14, 14, 11, 99, 345, -5, -34, -24};
int main()
{
unsigned ep(0), op(0);
std::size_t size(0);
size = sizeof Numbers / sizeof *Numbers;
odd_even_pairs(Numbers, size, ep, op);
std::cout<<"Even pairs: " << ep << std::endl;
std::cout<<"Odd pairs: " << op <<std::endl;
return 0;
}
//------------------------------------
bool even(int num)
{
return ((num % 2) == 0);
}
//-------------------------------------
void odd_even_pairs(const int* vec, std::size_t size, unsigned& ep, unsigned& op)
{
for(std::size_t i = 0; i < size; ++i)
{
for(std::size_t j = 0; j < size; ++j)
{
if( even(vec[i]) == even(vec[j]) )
{
++ep;
}
else
{
++op;
}
}
}
}
//-------------------------------------
void odd_even_pairs_fast(const int* vec, std::size_t size, unsigned& ep, unsigned& op)
{
// TO DO BY STUDENT
}Obviously there is a flaw in his code because multiplication by an ODD number gives you an EVEN product if the other half of the pair is EVEN.
When I asked him what made him think this algorithm was correct, he answered he didn't check either: he got it from a (Dutch) book: MatheMagie by Maarten Pennings.
So there you have it. One big mess.
My question:
Does anyone have an efficient forumula to calculate where the postcondition as posted in blue is met?
Pages: 1