|
Took roughly ~4mins, the next_combination function (similar to next_permutation) may someday end-up in the STL, if so probably 2mins or so....
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first,
BidirectionalIterator k,
BidirectionalIterator last);
int main()
{
std::vector<int> v;
v.push_back(7);
v.push_back(8);
v.push_back(12);
v.push_back(3);
v.push_back(4);
int target = 15;
int combination_count = 0;
std::sort(v.begin(),v.end());
for(unsigned int i = 1; i <= v.size(); ++i)
{
std::vector<int> tmp;
std::copy(v.begin(),v.end(),std::back_inserter(tmp));
do
{
if (std::accumulate(tmp.begin(),tmp.begin() + i, 0) == target)
{
std::cout << ++combination_count << "] ";
for(unsigned int j = 0; j < i; ++j)
{
std::cout << tmp[j] << (j < (i-1) ? "+" : "\n");
}
}
}
while(next_combination(tmp.begin(),tmp.begin() + i,tmp.end()));
}
if (0 == combination_count)
{
std::cout << "No combinations found." < std::endl;
}
return 0;
}
template <class BidirectionalIterator>
bool next_combination(BidirectionalIterator first,
BidirectionalIterator k,
BidirectionalIterator last)
{
if ((first == last) || (k == first) || (k == last)) return false;
BidirectionalIterator i = first;
BidirectionalIterator ii = last;
++i;
if (i == last) return false;
i = last;
--i;
i = k;
--ii;
while (i != first)
{
if (*--i < *ii)
{
BidirectionalIterator j = k;
while(!(*i < *j)) j++;
iter_swap(i,j);
i++;j++;ii=k;
rotate(i,j,last);
while(j!=last){ ++j; ++ii;}
rotate(k,ii,last);
return true;
}
}
rotate (first,k,last);
return false;
}
|
|
|
|
|
My 10 mins. I really wanted to do something cool with yield, but the difficulty of nesting these really stuffed me. I wanted to recursively traverse the mask like a b-tree and yield out results along the way.
class SubsetSummer<br />
{<br />
static IEnumerable< long> SubsetSumCore(IList< int> values, int target)<br />
{<br />
long mask = (1 << values.Count);<br />
<br />
while(mask-- > 0)<br />
{<br />
int total = 0;<br />
for(int bit = 0; bit< values.Count; bit++)<br />
{<br />
if ((mask & 1 << bit) > 0) total += values[bit];<br />
}<br />
<br />
if (total == target) yield return mask;<br />
}<br />
}<br />
<br />
static IEnumerable< List< int>> SubsetSum(IList< int> values, int target)<br />
{<br />
foreach (var resultMask in SubsetSumCore(values,target))<br />
{<br />
var results = new List< int>();<br />
for (int bit = 0; bit < values.Count; bit++)<br />
{<br />
if ((resultMask & 1 << bit) > 0) results.Add(values[bit]);<br />
}<br />
yield return results;<br />
}<br />
}<br />
<br />
static void Main(string[] args)<br />
{<br />
var values = new []{7, 8, 12, 3, 4};<br />
<br />
foreach (var result in SubsetSum(values, 15))<br />
{<br />
Console.WriteLine(string.Join(" + ", result.ConvertAll(i => i.ToString()).ToArray()));<br />
}<br />
}<br />
}
(wow that really shagged my generics)
|
|
|
|
|
Sorry you have failed. The program does not meet the requirements. Where is the user input and validation?
If it does not need to meet them then this program will do the job and take a lot less time and thought.
class SubsetSummer
{
static void Main(string[] args)
{
Console.WriteLine("3 + 4 + 8");
Console.WriteLine("3 + 12");
Console.WriteLine("7 + 8");
}
}
|
|
|
|
|
You forgot to place this in the punintended namespace.
ASP - AJAX is SEXY. PERIOD.
|
|
|
|
|
I guess if you find user input and validation challenging then you can focus on those parts. This is maths & algs, not "C# 101".
|
|
|
|
|
Hi all,
I read about several methods for constructing an ellipse with straightedge and compass, and one seemed very peculiar to me. It was called the trammel method...and it's the only one that I can't prove. It seemed so simple, but I just can't prove it.
If anyone could find a proof for me or point me in the right direction?
And also if this is in the wrong section please kindly inform me which section it should be in.
Thanks.
|
|
|
|
|
What do you mean by 'proof'? Are you implying you want an algebraic proof of the trammel method?
There is a web page here[^] that explains how to do it using a trammel and a nice animated one here[^].
|
|
|
|
|
Hi,
the proof is rather simple:
let the coordinates of A,B and O be called (x,y), (xB,0) and (0,yO) respectively. Then (based on AB=b and BO=AO-AB=a-b):
xB= x*(a-b)/a
yO= -y*(a-b)/b
(congruent triangles, or rule of three)
Now triangle "B,O,origin" is rectangular, hence xB*xB + yO*yO = (a-b)*(a-b)
(Pythagoras)
substituting the earlier formulae for xB and yO, and simplifying yields
(x/a)^2 + (y/b)^2 = 1
which is exactly the equation of an ellipse with radii a and b. QED.
modified on Sunday, October 26, 2008 3:08 PM
|
|
|
|
|
Now I just feel stupid.
Thanks.
|
|
|
|
|
hi Dear,
I have one item and its Avg Selling Price is 10 and Qty is 10 which makes its value to 10 * 10 =100
so now if i do some purchase and get one more item on the Price of 4 then it makes Qty 10+1 =11
and Avg Selling Price 100 + 4 =104
while if if divide 104 / 11 = 9.45 so its Avg Price becomes 9.45 and if i multiply
9.45 *11 =103.95
while my stock value is 104 means loss of 0.05
any Suggestion
Thanks in Adv
regards,
Mirza Rahman
|
|
|
|
|
softdev_sup wrote: any Suggestion
Yes, use a better calculator or rational numbers.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
Dividing 104 by 11 is 9.4545454545454545....
Because you are truncating after two decimal places you lose numerical precision. If you do the calculation keeping everything explicitly in fraction notation, you will see it comes out to 104.
|
|
|
|
|
Thanks for replying but i have to store this value in database which is user defined and max up to 8 , any other solution
because when we round up to 8 same problem comes
|
|
|
|
|
I'd suggest storing the intermediate values and compute the value when you need it.
|
|
|
|
|
I suggest the same solution as Andrew.
|
|
|
|
|
Go with Andrew's suggestion. It is better to just do the calculations when you actually need to use them, rather than trying to store in the database and having the issue you are running into.
"The clue train passed his station without stopping." - John Simmons / outlaw programmer
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
"Not only do you continue to babble nonsense, you can't even correctly remember the nonsense you babbled just minutes ago." - Rob Graham
|
|
|
|
|
I hope you don't mean you're storing these values as varchar/text/string etc.
|
|
|
|
|
When performing calculations on real numbers it's usually best to utilize the full precision of the machine or database environment, then do any rounding only at the final step. If that means you have to carry internal data to 6 decimals, so be it. It doesn't cost you anything in performance and will save a lot of grief when users start looking at your results.
"A Journey of a Thousand Rest Stops Begins with a Single Movement"
|
|
|
|
|
Hi,
in order to preserve accuracy, you should keep track of the total amount
(104 in your example) and the total quantity (11). The Avg Selling Price
is of secondary importance. You should not perform a division (which
looses accuracy, especially if you apply rounding to the quotient) and
later try to undo it by multiplying again, just keep track of amount and count.
Amount has no precision problem, since it has a fixed resolution (e.g. 1 cent),
and count is an integer.
|
|
|
|
|
Excellent read[^]. It might solve a problem of mine if I can implement it a certain way.
|
|
|
|
|
I have a large number of articles. I have a large number of possible keywords. Each article has at least one keyword associated with it, but may have many keywords. There is a database containing a list of all articles and a boolean variable set to true for each keyword if that keyword applies.
A user has a list of all keywords and selects those which interest them.
I am trying to find a more elegant way to extract the list of relevant articles than a brute force SQL SELECT.
Any suggestions would be appreciated!
|
|
|
|
|
I guess you will not be able to escape from a select statement...maybe you could try to use a stored procedure for that, or try to optimize the select, but not without a select I think
Intelligence is almost useless for those who have nothing else!
Email: caiokf@gmail.com
|
|
|
|
|
I think your database design is not ideal.. You should have a table for all the articles and a table for all possible keywords. In a third table you save all keyword-article associations (using the primary key of the article and keyword).
|
|
|
|
|
There is ABC triangle randomly rotated on XY plane. A,B coords are known, ACB angle is 90'. AC length is known. How to find C coords????
chesnokov
|
|
|
|
|
Someone already showed you the way to go.
[^].
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|