|
Concerning the situation that might arise if you have hundreds of entities I figured that I could just do some approximations. The most important parts would be those entities that's closest to the current largest number in the bank so to speak.
If you have one entity that adds say 10^70 you it I could just go over everything below say 10^60 to calculate what to add per second for all those entities instead of doing 60 different calculations.
So far I'm not working on creating a game but this kinda grew from curiosity but I did some testing and 100 different entities, one for each level up to 10^100 was just a few ms. No graphics or anything else but even if I kept increasing it would be a while before there would be a performance hit. For a mobile app it might me more important but my home computer doesn't have a high end cpu so I was quite happy with the current performance.
There is a game called clicker heroes and the highest I ever came in that game was in the span of 10^130.
There are so many of these games out there and they mainly target mobile with in game purchases which costs exorbitant amounts of money. While I see the allure of these games where the amount of in game points you accumulate while you are idle and can just pop in every once in a while to spend and increase the gathering rate I find it hard to comprehend how people can justify dropping 100$ > for in game credits.
I'll see if I make an implementation of your suggestion of vectors if I got the time but it's always interesting to compare different solutions. If I do I'll make a comparison with one of the string based methods too.
|
|
|
|
|
It sounds like you need arbitrary-precision numbers.
With C-1999 or C++2011, you are guaranteed to have a 64-bit built-in type. If you limit yourself to "digits" containing 9 decimal digits (they fit into 32 bits), you can perform the four basic arithmetic operations with "digits" that are easily converted to decimal notation.
The following article (printed in Dr. Dobb's Journal in August 1992; includes source code) should get you started: Multiple-Precision Arithmetic in C | Dr Dobb's[^]
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
i've got this homework problem which i tried to solve and didnt succeed so far. it goes like this:
Given k sets of integers A1,A2,..,Ak of total size O(n), you should determine whether exist a1A1, a2A2,...,akAk, such that a1+a2+..+ak-1 =ak. Your algorithm should run in Tk(n) time, where Tk(n) = O(n^(k/2)*log n) for even k, and O(n^((k+1)/2)) for odd values of k.
|
|
|
|
|
If you want help then you need to make some effort. No one here is going to do all your work for you.
|
|
|
|
|
I have to implement 3 data compression algorithms. I was thinking about LZW, Deflate and Bzip2. I can't find any good documentation for these algorithms. Do you know any data compression algorithms with good documentation, samples etc.?
|
|
|
|
|
I find that extremely hard to believe. A TON of documentation and discussion comes up with a simple Google for "LZW compression algorithm" "Deflate compression algorithm" and "bzip2 compression algorithm".
If you were looking for copy'n'paste code, yeah, that's going to get you a failing grade in class.
|
|
|
|
|
Agreed
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Member 12146827 wrote: I can't find any good documentation for these algorithms. Learn to use Google ! really !
Member 12146827 wrote: Do you know any data compression algorithms with good documentation, samples etc.? Yes, but your claims are just impossible, so you will have to search again. Don't fool us, April fools was 1 week ago.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Run-length encoding is a very simple one. It will save you some work by substituting it for one of the complex ones you mentioned.
|
|
|
|
|
|
Can anyone say which subjects and chapters in mathematics I need to know (thorough or basic) for learning algorithms? Also help me find a book on this mathematical subjects and a good book on algorithms for beginner?
|
|
|
|
|
If you type "algorithms" into Google you will find a wealth of information.
|
|
|
|
|
The information on google is all about how to make them, But I want the mathematics needed for it and there's no clear answer i got on google for that reason.
|
|
|
|
|
If you go and do some reading on the subject you will discover where the gaps in your knowledge are.
|
|
|
|
|
The general definition of "algorithm", in simple terms, is: A sequence of instructions to solve a problem. I can write an algorithm for how to clean my house. Or for picking apples from a tree. Or for flying a plane. There are as many potential algorithms as there are ideas what to do in this world and the variety of required skills to handle all of them is vast. The same holds true when entering the domain of computer science: There are algorithms for all sorts of stuff. Obviously, logical thinking and some sense for numbers won't hurt. In fact, most algorithms I've come across should be understandable by non-computer scientists if only written down in normal language instead of a programming language. Of course there are algorithms for which you will need very specific mathematical knowledge but the intersection of required skills for understanding arbitrary algorithms remains as simple as: Logical thinking and some sense for numbers.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
|
|
|
|
|
The guy behind C++ wrote two books,
The C++ Programming Language is something I believe any serious C++ connoisseur should have chewed on for longer periods of time.
Algorithms in a Nutshell by George T. Heineman, and others is something I just started to read, and so far its good.
|
|
|
|
|
Algebra is the most important, since everything is based on it. Graph theory helps develop the kind of reasoning you need for algorithms. I've found linear algebra useful for real-world algorithms I've had to implement, but it depends on the domain you're working in.
|
|
|
|
|
I'm looking for an algorithm to find all the possible combinations of meetings (details in attached photo). I would like to introduce the teams algorithm calculates all threrefore combinations of matches, or better yet, I could enter the value to the team as the level of play by all the teams and I got all the options from the most probably
Tournament tree: http://prntscr.com/aoukzm[^]
Sorry for my english
|
|
|
|
|
Eric Lippert did a series of blog posts on generating permutations and combinations in C#:
permutations | Fabulous adventures in coding[^]
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Check out my "Alternative Tip": Subset - Sum Problem with Numeric Collections [^]
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
It's not clear what you want. You mention "all the possible combinations", but your link is to an elimination tournament, which is different.
|
|
|
|
|
I've just received an email from codeproject telling me my post (above) has been marked as potentially being spam. WTF??
|
|
|
|
|
Hi,
The problem at first seems to be simple but it is not, al least form me...
Have array/set/group of numbers,
for example:
(3,2,7,1,9,5,5,2,8,6,3,1)
I need to make groups of these numbers, so that each group has element(s) that sum is euqal or max close to certain value, for example 10. Of course I understand that there are lots of solutions, but I need only one.
So, for this set I should get:
A - 2,7,1 -> 10
B - 9,1 -> 10
C - 2,8 -> 10
D - 5,5 -> 10
E - 6,3 -> 9
F - 3 -> 3
of course this is one of possible solution, but I don't need super optimalization for this algorithm.
If anyone has some idea how to approach to this problem I would be very grateful for help.
|
|
|
|
|
Sounds like a backtracking[^] candidate problem to me.
You would have to extend that classical approach to allow sub-optimal group-solutions (where sum < 10 or maybe also where sum > 10 up to a certain maximum)* , temporarily store all potential overall-solutions and when the backtracking is done, pick the best based on some criteria that you have to define. E.g. where the sum of differences from 10 is smallest (would be 8 in your example). Or, as you don't need the best possible solution, you could cancel the process once a satisfactory overall-solution has been found.
* : Which means that the evaluation should continue even after finding a potential group-solution until exceeding the tolerable limit.
If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson
|
|
|
|
|
I'd go for a rather simple implementation; sort the values, highest value first. In a loop, fetch a number from the array. Move right and keep adding numbers until you hit maximum. At maximum, fetch new number.
That's a rather blunt way of doing it though - backtracking would give a better result.
Bastard Programmer from Hell
If you can't read my code, try converting it here[^]
|
|
|
|