Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20050828 17:05:39
[algorithm] products of even/odd pair combinations helpI need help on the following puzzle. I'll tell you the requirements then the story behind it. 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. #2 20050828 17:48:32
Re: [algorithm] products of even/odd pair combinations helpIn other words, if presented with a list of numbers (say: 3,4,7,10), find out how many even pairs there are and how many odd. "The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman #3 20050828 19:14:10
Re: [algorithm] products of even/odd pair combinations helpWe need all the permutations: both "i" and "j" need to be of range { 1 <= "i/j" <= n } Last edited by Valmont (20050828 19:38:58) #4 20070113 10:28:40
Re: [algorithm] products of even/odd pair combinations helpWe have a vector of numbers and we want to know how many pairs have an Code: ?x2 ?x3 ?x4 ?x7 ?x10 + 2x?  2x2= 4 2x3= 6 2x4= 8 2x7=14 2x10= 20 3x?  3x2= 6 3x3= 9 3x4=12 3x7=21 3x10= 30 4x?  4x2= 8 4x3=12 4x4=16 4x7=28 4x10= 40 7x?  7x2=14 7x3=21 7x4=28 7x7=49 7x10= 70 10x?  10x2=20 10x3=30 10x4=40 10x7=70 10x10=100 We see that there are only 4 odd products: Code:9 (=3x3), 21 (=3x7), 21 (7x3), 49 (7x7). Do we have to check all 25 (5^2) pairs to find this result? Code: ?x2 ?x3 ?x4 ?x7 ?x10  EVEN ODD EVEN ODD EVEN + 2x? EVEN  2x2= 4 2x3= 6 2x4= 8 2x7=14 2x10= 20 3x? ODD  3x2= 6 3x3= 9(*) 3x4=12 3x7=21(*) 3x10= 30 4x? EVEN  4x2= 8 4x3=12 4x4=16 4x7=28 4x10= 40 7x? ODD  7x2=14 7x3=21(*) 7x4=28 7x7=49(*) 7x10= 70 10x? EVEN  10x2=20 10x3=30 10x4=40 10x7=70 10x10=100 and this confirms that only the 4 products formed by multipling two Code:e= 0; o= 0; for(i=0; i<size; ++i) { if( even(vec[i]) ) { e++; } else { o++; } } ep= e*e + e*o + o*e op= o*o gives the correct result, in O(n) as opposed to the O(n^2) of the original 