Template recursion.
Author
Ok, do you guys know of any good practice programs I should do?
Not only games and graphics, but mostly anything that would give me excerize. Like problem solving (find the mean median and mode of a set of numbers, for example), and anything else...
Please, if you know of some, list them... I would like to be able to practice them using the console, as I don't want the overhead of using graphics right now... Oh and also, don't suggest anything along the lines of a text RPG or something, please! I would like to have many little problems with many little programs that demonstrate how to solve the problem using C++, rather than a big project.
Thanks!
I'm talking about C++, and my experience is:
(up to, in order)
polymorphism
classes
templates
pointers
{other stuff at this point in C++}
Thanks!
Write a file encryptor which allows the creation of seft-executables and multiple-file packages ?.
It is not the actual algorithm is important, you'll learn how to deal with resources, adding/extracting data from an executable and other little stuff.
For C++ features, I couldn't think of one that doesn't implement GUI but also not a text game [rolleyes].
It is not the actual algorithm is important, you'll learn how to deal with resources, adding/extracting data from an executable and other little stuff.
For C++ features, I couldn't think of one that doesn't implement GUI but also not a text game [rolleyes].
Write a spelling checker. You can learn all those things, plus some interesting algorithms, plus it might help your spelling. [smile]
Write a program that displays all the prime numbers in a really huge number.
Like, find all the primes of 45349 and list them from least to greatest. I was planning on during it myself in a few days(after finishing my text rpg) and timing myself with a timer I was going to write.
Like, find all the primes of 45349 and list them from least to greatest. I was planning on during it myself in a few days(after finishing my text rpg) and timing myself with a timer I was going to write.
If you like getting your head around problems, then something I found useful is working out algorithms for certain types of statistical analysis. I recently worked out a routine to count number clusters from a set of chosen numbers from a grid. Say you have a 6x9 grid and each cell is numbered sequentially from 1 to 54, and the user choses 7 numbers of their choice from that 100. A cluster occurs where the chosen numbers lie horizontally, vertically, diagonally from each other in groups. eg.
chosen numbers
3, 10, 17, 22, 33, 39, 51
grid
this selection consists of 3 clusters.
Cluster counting is used in picking [better] numbers for lotteries. One of many things to check for. Statistical analysis has lots of good algoritms that require plenty of thought. Read up on gaming/gambling systems to find some good ones to implement.
Another good one is ways to generate better pseudo random numbers.
Or analysis like this. My father asked me about analysing the last 8 weeks of results from the local town lottery to see which numbers statistically had a higher chance of coming up because they had not appeared significantly over the last 8 weeks. Or something like that. He thinks he's onto a winning strategy with this, and wants me to implement it :-)
F451
chosen numbers
3, 10, 17, 22, 33, 39, 51
grid
1 2 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 1819 20 21 22 23 2425 26 27 28 29 3031 32 33 34 35 3637 38 39 40 41 4243 44 45 46 47 4849 50 51 52 53 54this selection consists of 3 clusters.
Cluster counting is used in picking [better] numbers for lotteries. One of many things to check for. Statistical analysis has lots of good algoritms that require plenty of thought. Read up on gaming/gambling systems to find some good ones to implement.
Another good one is ways to generate better pseudo random numbers.
Or analysis like this. My father asked me about analysing the last 8 weeks of results from the local town lottery to see which numbers statistically had a higher chance of coming up because they had not appeared significantly over the last 8 weeks. Or something like that. He thinks he's onto a winning strategy with this, and wants me to implement it :-)
F451
Here are a few which I think you might find fun (listed in order of increasing difficulty as judged by me). Some won't require use of those things you listed, but they should challenge your critical thinking skills and help you learn how to devise algorithms for tricky situations.
1) Write a program which computes the nth Fibonacci number at compile-time, and prints it to the console at runtime. (Hint: use templates, template recursion, and template specialization).
2) Write code for an n-dimensional array. The techniques used to solve this will probably be similar to those used in problem 1. Bonus points if you make it store its elements in STL containers of arbitrary type.
3) Given a positive integer n, find all primes p < n without performing any explicit primality tests (i.e., don't for each number k < n check if k has any factors f such that 1<f<k).
4) Write an algorithm which is as efficient as you can make it (preferably O(n*lg(n)), if you know about asymptotic notation; if not, don't worry about it [smile]) for solving this problem: given a set S of n integers and another integer x, determine whether or not there exist two elements in S whose sum is exactly x.
5) Solve the Blocks Problem.
6) Some other more challenging problems can be found here and three more here. For especially challenging problems, look here.
1) Write a program which computes the nth Fibonacci number at compile-time, and prints it to the console at runtime. (Hint: use templates, template recursion, and template specialization).
2) Write code for an n-dimensional array. The techniques used to solve this will probably be similar to those used in problem 1. Bonus points if you make it store its elements in STL containers of arbitrary type.
3) Given a positive integer n, find all primes p < n without performing any explicit primality tests (i.e., don't for each number k < n check if k has any factors f such that 1<f<k).
4) Write an algorithm which is as efficient as you can make it (preferably O(n*lg(n)), if you know about asymptotic notation; if not, don't worry about it [smile]) for solving this problem: given a set S of n integers and another integer x, determine whether or not there exist two elements in S whose sum is exactly x.
5) Solve the Blocks Problem.
6) Some other more challenging problems can be found here and three more here. For especially challenging problems, look here.
Author
Quote:Original post by nilkn
Here are a few which I think you might find fun (listed in order of increasing difficulty as judged by me). Some won't require use of those things you listed, but they should challenge your critical thinking skills and help you learn how to devise algorithms for tricky situations.
1) Write a program which computes the nth Fibonacci number at compile-time, and prints it to the console at runtime. (Hint: use templates, template recursion, and template specialization).
2) Write code for an n-dimensional array. The techniques used to solve this will probably be similar to those used in problem 1. Bonus points if you make it store its elements in STL containers of arbitrary type.
3) Given a positive integer n, find all primes p < n without performing any explicit primality tests (i.e., don't for each number k < n check if k has any factors f such that 1<f<k).
4) Write an algorithm which is as efficient as you can make it (preferably O(n*lg(n)), if you know about asymptotic notation; if not, don't worry about it [smile]) for solving this problem: given a set S of n integers and another integer x, determine whether or not there exist two elements in S whose sum is exactly x.
5) Solve the Blocks Problem.
6) Some other more challenging problems can be found here and three more here. For especially challenging problems, look here.
Wow, thanks!
So I took step one and viola, runtime-stuff is done (wow, they basicly give you the function on wikipedia... I didn't really know what it means cuz I'm only 13)... And it works! On to compile-time stuff, I almost got it done:
template<int n>int f() { if (n < 2) return (n >= 0) ? n : 0; return f<n - 1>() + f<n - 2>();}... (*Thinking.*)
Errors:
main.cpp: In function `int f() [with int n = -0x0000003de]':main.cpp:14: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating `int f() [with int n = -0x0000003e0]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003de]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003dc]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003da]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003d8]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003d6]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003d4]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003d2]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003d0]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003ce]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003cc]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003ca]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003c8]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003c6]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003c4]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003c2]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003c0]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003be]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003bc]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003ba]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003b8]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003b6]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003b4]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003b2]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003b0]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003ae]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003ac]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003aa]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003a8]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003a6]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003a4]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003a2]'main.cpp:14: instantiated from `int f() [with int n = -0x0000003a0]'main.cpp:14: instantiated from `int f() [with int n = -0x00000039e]'main.cpp:14: instantiated from `int f() [with int n = -0x00000039c]'main.cpp:14: instantiated from `int f() [with int n = -0x00000039a]'main.cpp:14: instantiated from `int f() [with int n = -0x000000398]'main.cpp:14: instantiated from `int f() [with int n = -0x000000396]'main.cpp:14: instantiated from `int f() [with int n = -0x000000394]'main.cpp:14: instantiated from `int f() [with int n = -0x000000392]'main.cpp:14: instantiated from `int f() [with int n = -0x000000390]'main.cpp:14: instantiated from `int f() [with int n = -0x00000038e]'main.cpp:14: instantiated from `int f() [with int n = -0x00000038c]'main.cpp:14: instantiated from `int f() [with int n = -0x00000038a]'main.cpp:14: instantiated from `int f() [with int n = -0x000000388]'main.cpp:14: instantiated from `int f() [with int n = -0x000000386]'main.cpp:14: instantiated from `int f() [with int n = -0x000000384]'main.cpp:14: instantiated from `int f() [with int n = -0x000000382]'main.cpp:14: instantiated from `int f() [with int n = -0x000000380]'main.cpp:14: instantiated from `int f() [with int n = -0x00000037e]'(Whew.)
I'm just calling f<9 - 1>()....
Any ideas?
Anyways, thanks for the listed things... I'll try them.
The compiler doesn't get to do the check in the code on n's value at compile-time because it's a run-time check. So it therefore still tries to instantiate versions of the function for negative n even though they wouldn't be called at runtime, and thus there's no lower limit to things.
What you need to do is override or specialize the template for the "base case" values instead:
That will still fail to compile for negative n - as it should. They call it 'n' when describing the problem because it's supposed to be a natural (i.e. 'counting', positive) number. Of course, you should probably specify unsigned int for the template type :)
What you need to do is override or specialize the template for the "base case" values instead:
template<>int f<0> { return 0;}template<>int f<1> { return 1;}// and then the 'normal' version, which no longer requires a runtime check.That will still fail to compile for negative n - as it should. They call it 'n' when describing the problem because it's supposed to be a natural (i.e. 'counting', positive) number. Of course, you should probably specify unsigned int for the template type :)
Author
Quote:Original post by Zahlman
The compiler doesn't get to do the check in the code on n's value at compile-time because it's a run-time check. So it therefore still tries to instantiate versions of the function for negative n even though they wouldn't be called at runtime, and thus there's no lower limit to things.
What you need to do is override or specialize the template for the "base case" values instead:template<>int f<0> { return 0;}template<>int f<1> { return 1;}// and then the 'normal' version, which no longer requires a runtime check.
That will still fail to compile for negative n - as it should. They call it 'n' when describing the problem because it's supposed to be a natural (i.e. 'counting', positive) number. Of course, you should probably specify unsigned int for the template type :)
OHH!!! So that's what the tutorial meant... It was like, "Template specialization can be used to make templates for specific objects." and I was like, "Wow, that's useful (not)."...
THANK YOU for explaining that... If I haven't rated you up already, I will now :).
EDIT: The heighest I could do is change your rating from a perfect 18-18 to a non-perfect 18-19 [smile].
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
