Sign in to follow this  
nullsquared

Template recursion.

Recommended Posts

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!

BIG EDIT

I have a template problem.... Scroll down a little. [Edited by - agi_shi on March 6, 2006 3:52:09 PM]

Share this post


Link to post
Share on other sites
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].

Share this post


Link to post
Share on other sites
Write a spelling checker. You can learn all those things, plus some interesting algorithms, plus it might help your spelling. [smile]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
37 38 39 40 41 42
43 44 45 46 47 48
49 50 51 52 53 54

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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].

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this