Thursday, September 29, 2011

Project Euler - Problem Seven

This one took a little extra input from good ole Michael. Apparently, me and prime numbers just don't get along very well. It's like we hate each other without even knowing it. Here's the problem:
With Michael's help, I managed to get it done though. It's really fairly simple, so I'm going to just do like regular and put a few screenshots up.

After discussion with Michael, we decided that it would be best to have a list of the primes we've found so far. It'll start off primed with two and three. Everything after that will be found via the program. It'll do a number mod everything currently in the list of primes. If it isn't divisible by any of the primes, then that number is added to the list and it moves on to the next number.

This seems to work pretty well, considering that it doesn't take very long at all to run. It's pretty cool to put a little cout statement to print out primes as they're found. I've got on in my code here. It lets me know if it's working too!

So here are my functions:
primelist_zero simply zeros out the list of primes. I did this so that I can have loops that run while elements in the list are or aren't zero. There's probably a better way to do it, but this one works.
Next there's the is_prime function. The name on this one is pretty telling about its function. It just checks whether or not a number is prime.
You're starting with an increment of zero each time the function is called. This increment variable is used to know which element of primeList to mod by. If the number mod by any number in the primeList equals zero, then it exits the function call. Otherwise, it adds one to the increment variable and checks again.  It does that until it gets to an empty spot in the primeList, at which point the number has to be prime.

These functions are wrapped up in a nice little main:
If you've got any problems, feel free to ask!

Wednesday, September 28, 2011

Project Euler - Problem Six

These exercises are really helping my programming. This one took about fifty-five seconds of planning a a few minutes to write up. It's a bit spaced out to do in one screenshot, so I'll space it out a bit.

The code is fairly simple for this one. Here's the problem:
Now, I see two different functions there, but I don't know about you. I'm going to go ahead and declare them like this:
The functions themselves are very straightforward and didn't take much thinking through.
Add_squares adds the squares of all the numbers:
Square_sum adds all the numbers and then squares it:
Finally, I wrapped them all up in a nice main function:
Also....you'll notice that I got excited and forgot to change my cout statement....soooo...

So, that's it. Easier than pi!

Project Euler - Problem Five

Problem five was one of the quickest and easiest so far.  I'm pretty sure that the biggest thing that problem five did for me was  that it helped me find a really nice answer repository! So now I can easily check to make sure that I've got the right answer. Here's the link: projecteuler-solutions

Since problem five was so easy, I'm not going to even attempt to do a step by step breakdown. If anyone has any questions, just ask and I'd be more than happy to help.

Project Euler - Problem Four

OH GOD THEY JUST NEVER STOP.

So I'm on problem four.  This one is fairly simple, and is honestly a bunch easier for me than the prime numbers one was. Maybe that's just because I had an entire chemistry lecture to think about this one. Either way though, it's a fairly straightforward one.

In fact....I think I'll actually include a little lesson with this one. First, let's state the problem:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

The first real question is how we're going to check for whether a number is a palindrome or not. Everything else just falls into place after that.
Here's how to do it!

Modulus.

Whaaaa?

Really though. Modulus is just a division's remainder. So, mod ten should remove the last digit of a number. Check it out with some sort of math machine. 987654321 % 10 yields a result of 1. This means that you're able to get the last digit of the number if you mod ten. (HINT HINT)
So if you do n%10 to get the last digit, what do you do next?
Well...you get the idea. You do this:

rev = rev * 10 + dig;               // This will add the result to a number. (HINT: This is
                                                                 // going to be the opposite of the number you put in.
        num = num / 10;         //  This part will remove the number you just put into rev
                                                           

Now, you can apply this fairly easily into a function. I personally did mine as a Boolean function. I'll post a screenshot of my code below.

This one is the function:
This one is going to be the main loops that do the multiplication:
This one is the whole program:


Anyway, that's the solution to the fourth Project Euler problem. More to come? Maybe.



Project Euler - Problem Three

Let this be a lesson in why reinventing the wheel isn't always best.

I'll start with the problem:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Now, that isn't too hard.  In fact, I had code that would do it fairly quickly. My downfall, however, was that I wasn't looking for any sort of help. I'd decided that I wanted to do it completely and all by myself. That's an honorable pursuit, and one that everyone should do at some point. Always relying on other people for help gets old.

There comes a time when you've got to realize that asking for help, or at least advice, isn't always bad though. My program ran so slow. It was rather clumsy and dumb, to be quite honest. I really didn't like it at all. So I started googling. I ended up finding a website that had complete and working C++ (and Java) code for running the Sieve of Eratosthenes. I picked the code up off of here, and it runs at least a bajillion times better than mine.

Now, is it mine?  Not even a little bit. The most I put into my problem three solution was really a few lines to print out a menu, and that isn't even necessary. Was it something worth doing though?  Yeah, it definitely was. Now, I know a whole new way to do prime numbers.

And trust me. It's cool. Read the link and give it a shot.

Friday, September 23, 2011

Project Euler - Problem Two

Recursion is so much fun. It's not the easiest thing I've ever tried to wrap my mind around, but it's fun.

Okay, so here is the solution to Project Euler's second problem.

The problem is this:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

So, you're going to need to figure out what this means.
int fib(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    else
        return fib(n - 1) + fib(n - 2);


This is the code to find the fib of a number. If you put ten in, you'll get 89. Now, simply putting fib() of four million won't work. We want the sum of the even-valued terms.  In other words, we need something else to make it happen.

Personally, I used a do/while loop with an if statement inside of it.

You can see what I did here. The actual solution is 4613732.


Project Euler - Problem One Redux

So it's been a while. School is...well...school is hell this semester. But hey! It's all good, right? Today I decided that I'm going to sit down and relax my mind by doing some easy stuff. I couldn't let myself be unproductive though, so I decided to try and do some computer science studying. Sooooooo, I redid project Euler's problem one.  Except this time I also used recursion. It's pretty cool looking, and I'll walk you through how it works.

Okay, so instead of putting a big ole block of code, I just took a screenshot. Project One is simple enough, and if you actually want a big block explaining exactly what's going on, check out my first post.  Instead of the code itself, I took a screenshot.

You can see pretty much everything there. I tried to be all studious and comment it nicely.

Now, that works pretty darn well. Recursion makes it even cooler looking though.

Recursion is used whenever you can see that the answer to a problem is really just a smaller version of the problem.  Now, my computer science professor did say that it's not always best to use recursion.  It takes a lot of stuff to make a recursive call, so it probably shouldn't be used for just everything you've got.  As it is though, this function is so small that it really doesn't matter. PLUS IT IS SO COOL.

So, how does it work?

It's as simple as a function that calls itself.  To get to that point though, we need to figure out what the simplest case is. In the implementation that I'm using, the reasoning goes like this:
  1. We'll pass in the current position (a default of one) and the upper limit (which is 1000 for Project Euler).
  2. The simplest case, the base case, is if these two numbers are equal to each other.  That would mean that the number we are currently working with is the upper limit.
  3. Otherwise, we want to find out whether the number we're currently working with is a multiple of three or five. 
    • We can do this using the modulus  (%)  operator. It is the remainder of division between two numbers. If number A is a multiple of number B, then A%B should be zero (since it should divide evenly, thus without a remainder).
  4. Once we've establised that a number IS a multiple of three or five, we want to add it to the total. 
  5. Now we want to do the same thing again, except on a number that is one higher than our current number.
So, in pseudo-code:
If the current number is equal to the upper limit, return from the function. Else, we want to check whether the current number modulus three or five is equal to zero. If so, then we know it is a multiple of either three or five and should therefore be added to the total, so we return it AND we call the function again.

Now, think over that and see what you get. Here's mine!



If you've got any questions, please ask! This isn't exactly a tutorial on how to program, but it should guide you into how to do at least this problem recursively.