I'm learning to code (again)!

Miscellaneous and Personal Stuff I Must Share
1

Every now and then I get bored and pick up my C++ book, and relearn the basics, and teach myself new things. It seems I don’t have the attention span to learn the whole thing at once. I was surprised by how much actually has stuck, though.

Like for example, I was able to make a guess the number game where the computer picks a random integer, and the player has to guess what it is, while the computer tells you if it’s too high or two low. I did this on a whim the first day I decided to pick it back up, and it took about 20 minutes. I was so proud I showed it to all my friends :smiley: .

I just finished a program that would calculate how many quarters, dimes, nickels, and pennies are in a user-given monetary amount.

I’ve also made a program that makes sequentially bigger rows of asterisks, up to a given amount. And a variation on that, where the rows get bigger, then smaller.

So, coding-dopers, how about you give me some problems which can be solved with my limited knowledge.

So far I know how to use:
-if statements
-for, while, and do-while loops
-void, and return functions
-switch statements

I think that’s it for now, but I welcome all challenges, no matter the difficulty.

Alternatively, if you would like to see my programs (either the source code, the compiled version, or both), you can email me!

2

These should keep you busy.

3

Do you know how to write recursive programs?

Try writing one that takes in a number n and returns the nth Fibonacci number.

For reference, F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2);

Once you learn recursion, you can learn dynamic programming, which is a really awesome programming technique that can help you find an optimal solution to lots of tricky problems.

4

You mean like this?:


int main(){

	int limit;
	int a;
	int b;
	int c;
	int count;

	cout << "Please enter limit: ";
	cin >> limit;
	cout << endl;

	a = 0;
	b = 1;
	
	for (count = 1; count <= limit; count++){
		cout << b << " ";
		c = b;
		b = a + b;
		a = c;
		}
	
	return 0;
	}
5

Well, yes, that works. But it’s not recursion. My fault: I didn’t explain. A recursive program is one that calls itself. If you’ve ever written an inductive proof, it’s a similar sort of concept.

Can you write a function fib(int n) that returns the nth fibonacci number, and to do so, doesn’t run a for loop and add it up, but calls itself again?

6

Ah, now I see. So it’d be like this:


int fib(int limit){

	c = b;
	b = a + b;
	a = c;
	count++;
	cout << b << " ";
	
	if(count >= limit){
		return 0;
		}
	else{
		fib(limit);
		}
}
7

That’s partway there Electronic Chaos (and technically is everything I described). You’ve removed the for loop and replaced it with recursive calls. To make the function completely recursive, though, you should not rely on any external (global) variables. You can do that by removing the variables and using the arguments of the function itself to pass the information you need.

To illustrate my point, here’s an example recursive function that adds two numbers together


int sum(x, y) {
    if (y == 0)
        return x;
    else
        return sum(x+1, y-1);
}

Now, obviously, that’s a really stupid way to add numbers. And in this case only works if y > 0 to start. But the idea is that you let further function calls do the heavy lifting and don’t store extra information in external variables.

8

Gah, I don’t know why people insist on using fibonacci to demonstrate recursion. Nobody but a braindead monkey would EVER write fibonacci the pure recursive manner due to it being godawful slow (assuming your not programming in a pure functional language :D). There are so much better examples to demonstrate recursion to a beginner.

9

The problems I looked at in UncleRojelio’s link looked scary.

Add some knowledge of arrays (which is essential) this should be enough to write a Sudoku puzzle solver.

You’ll probably want learn how to read and write files, you don’t want to be entering all your Sudoku data at the console.

10

I’s kinda like the “Hello World” of recursion. Just roll with it.

The really scary part is when you sumbit them and the robot emails back that you are WRONG!!!.

Electronic Chaos, the other central part of recursion, besides the fact that the function calls itself, is that the problem gets smaller upon each recursion. Take for (cannonical) example; Factorial. You could simply define:


n! = 1 * 2 * ... * n

but a better and recursive why to think of it is:


0! = 1               // base case
n! = n * (n-1)!  // general case

Now, you can imagine a function that calls itself repeatedly as the value of n decreases. Upon reaching the base case, the function returns as begins unstacking the previous calls until the original call returns with the answer.

Recursion is one of those portals through which all programers must pass. It is very important to be able to wrap your head around this concept for it leads to the Holy Grail of computer science; Funtional Programming.

11

Yike, as fun as programming is, that last line should have read: Functional Programming.

I would like to recommend this book for your programming pleasure. Chock full of fun and interesting programming challenges.

12

I prefer to think of it as the “Bubble Sort” of recursion.

13

I had the same prof for three different CS courses. Programming, Algorithms, and Data Structures. He managed to shoehorn old Fibonacci into every class one way or another.

That and Haskell. One way or another.

14

Hmm…the toughest thing I ever done is a path-finding program, using recurison. You need an array for that. So the project spec is:

  1. Define a maze given a 2d array
  2. Define a start point
  3. Define an end point
  4. Trace a route from the start to end

Actually, given what you know, and some array basics, you can do all sort of nifty stuff…

  1. An ASCII calendar.
  2. A Trek game! You command a starship (think Enterprise) and have to elminate all the enemies from the galaxy. Galaxy is divided in 8x8 quadrants, and each quadrant has starbases, black holes, stars and etc.
15

Now that you know about recursion, Electronic Chaos, learn about binary trees and write a recursive function that will traverse a binary tree and output the data of each node.

16

I work with a guy that wrote part of a version at the University of Texas. Their version was written in Fortran, and the printed source resulted in a three inch thick stack of pin-feed computer paper. No telling how tall the stack of computer punch cards used to enter the source into the mainframe was. I used to play it in high school on a teletype machine hooked to an acoustic modem. Those were the days.

17

When you want to write a level-order search, let us know, we’ll let you in on the secret.

18

After that you might want to look into Binary Search Trees:
Obiligatory Wiki-Link: http://en.wikipedia.org/wiki/Binary_search_tree

19

Then you can compare and contrast that with the Hash table.

20

When I taught C++, one textbook I used had this exercise

“Enter a height, program draws a diamond that wide using asterisks.”
e.g. enter 5 you get:



  *
 ***
*****
 ***
  *

I almost dismissed this as too trivial, but there are soooo many ways to solve it, it became a great compare/contrast exercise when taken up as a group. And there are some gotchas.

I too consider Fibonacci to be the “Hello, world” of recursion not because recursion is the best way to do it but that the whole shebang is easy to grasp.

As a test for recursion I would assign the Towers of Hanoi
Write a program that outputs the steps to solve the Towers of Hanoi (make the number of rings an input if you wish, or fix it at 4)

The output should look something like this
“Move ring from tower 1 to tower 2”
“Move ring from tower 1 to tower 3”
“Move ring from tower 2 to tower 3”
etc…

As for C++ - are you ready for object oriented exercises? The classic is:
[ul]
[li]Define a class named Shape that has an abstract method GetArea(), and DisplayCharacteristics()[/li][li]Inherit from Shape to define Circle, Rectangle, Triangle, Square, each overloading GetArea() and DisplayCharacteristics() as appropriate. e.g. DisplayCharacteristics() for the Circle could be cout << “A circle with " << r << " radius.” << endl;[/li][li]Display a menu offering the user to pick one of these four shapes, then to supply the defining coordinates of the chosen shape (radius for circle, base & height for the triangle, etc)[/li][li]Using the input, construct the appropriate shape and add it to an array of shapes.[/li][li]When user is done entering shapes, iterate the array displaying the characteristics and area of each Shape.[/li][/ul]