Am I using correct programming principles?

[beefy]

Hello!

I'm currently working on the first few problems from projecteuler.net, so that I can learn Java 'by doing' as well as reading.

Problem 2 is:

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, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

My code:

public class ProblemSet {

	public static void main(String[] args) {
		
		int fibminus2 = 1;
		int fibminus1 = 2;
		int newno = 0;
		int total = 2;

		while(newno < 4000000){
			
			newno = fibminus1+fibminus2;
			
			if(newno % 2 == 0){
				total+=newno;
			}
			
			fibminus2 = fibminus1;
			fibminus1 = newno;
		}
		System.out.println(total);
	}
}

In case you didn't understand my variable naming, fibminus2 + fibminus1 will give you the next number in the sequence (newno).

I've been able to solve this problem, but the thing I would like to get feedback on is whether I wrote this in a 'correct' and 'efficient' way. I know this request is a little vague, and for that I'm sorry. I want to learn good programming principles from the very start. ;)

There is a thread on the Project Euler website where people can share their solutions. There are quite a few Java ones, but I can't really tell which ones use good principles and which one use bad/inefficient ones.

One question I have in particular is whether I should be using the while loop, like I did in my code, or whether I should be using the for loop (like this: for(int i = 0, i < 4000000, i++))

I'd very much appreciate help in any form!
Beefy

[JosAH]

One question I have in particular is whether I should be using the while loop, like I did in my code, or whether I should be using the for loop (like this: for(int i = 0, i < 4000000, i++))

You're doing fine; there are (almost) no principles when it comes to a simple, single algorithm; the code is efficient as it is and changing the while loop to a for loop is just a matter of preferences. Your suggestion doesn't work because you don't have to loop 4000000 times, i.e. you have to quit your loop when the last fibonacci number is larger than (or equal) to 4000000.

kind regards,

Jos

[beefy]

Thanks for your reply Jos!

I was wondering about whether I was going about it in the correct way, so that when I move on to larger and more complex problems, I'll be doing it the right way ;)

I guess I'll ask you guys again when I have a large problem that takes more processing time to complete ;)

Beefy

[JosAH]

Thanks for your reply Jos!

I was wondering about whether I was going about it in the correct way, so that when I move on to larger and more complex problems, I'll be doing it the right way ;)

I guess I'll ask you guys again when I have a large problem that takes more processing time to complete ;)

Beefy

A bit of a tip (more of an exercise really): can you implement the same using a separate method that can deliver the answer? Your main( ... ) method should look like this:

public static void main(String[] args) {
   System.out.println("The answer is: "+solveProblem());
}

The solveProblem() should do the hard work (which you already have done).

kind regards,

Jos

[beefy]

Can you implement the same using a separate method that can deliver the answer?

I think I got it:

public class ProblemSet {

	public static void main(String[] args) {
		System.out.println(solveProblem());
	}
	
	public static int solveProblem(){
		int fibminus2 = 1;
		int fibminus1 = 2;
		int newno = 0;
		int total = 2;

		while(newno < 4000001){
			
			newno = fibminus1+fibminus2;
			
			if(newno % 2 == 0){
				total+=newno;
			}
			
			fibminus2 = fibminus1;
			fibminus1 = newno;
		}
		
		return total;
	}
}

Anything wrong with this code?

At first I defined the method solveProblem() without making it "static", but I got a error in Eclipse which added the "static" for me. What does that change?

[JosAH]

Anything wrong with this code?

At first I defined the method solveProblem() without making it "static", but I got a error in Eclipse which added the "static" for me. What does that change?

Well done. If you don't make that method static it belongs to an object (of the class where the method is defined). You don't have an object (instantiation) of that class so you can't call that method.

Another (small) nitpick: why did you make that method 'public'? Do you want to be able to call that method from somewhere else? Think about it; if you just want to call it from within that class (e.g. from your main( ... ) method) make that solveProblem( ... ) method private.

kind regards,

Jos

[beefy]

Well done. If you don't make that method static it belongs to an object (of the class where the method is defined). You don't have an object (instantiation) of that class so you can't call that method.

Another (small) nitpick: why did you make that method 'public'? Do you want to be able to call that method from somewhere else? Think about it; if you just want to call it from within that class (e.g. from your main( ... ) method) make that solveProblem( ... ) method private.

Thanks Jos,

Yes, the method should be private. I learnt that yesterday, so I should know that :p

About the "static" method, I still don't really understand it yet, but I think I have to learn more about concepts like 'Objects', 'Classes', 'Methods' etc before I do. I'm heading back to the first few Stanford Opencourseware Java lectures so that I can force all of the concepts into my brain ;)

[JosAH]

About the "static" method, I still don't really understand it yet, but I think I have to learn more about concepts like 'Objects', 'Classes', 'Methods' etc before I do. I'm heading back to the first few Stanford Opencourseware Java lectures so that I can force all of the concepts into my brain ;)

A class is a blueprint for an object (an instantiation) of that class; it tells what you (or anything else) can 'say' to that object; that 'saying things' are the methods that belong to the object. If I want to say giveMeYourWallet( ... ) I need something from the class Human to say it to. Object Oriented Programming (OOP) is all about objects that 'say' things to each other in order to get the job done; that's basically it and it nicely divides the notion of 'who does what' and 'why'. It doesn't just organize the data that is needed to get something done but it also organizes that 'whats' that have to get the job done.

kind regards,

Jos

[Tolls]

Following on from that, this is why you might encounter the concept of coding to interfaces. That is, you essentially define what something does by initially defining the interface. Only then do you write the actual class (ie the how it does something).

Though this might be little early on to actually be doing this (it's not so effective on small exercises)...worth bearing in mind, though.

[gcalvin]

Thanks Jos,

Yes, the method should be private. I learnt that yesterday, so I should know that :p

About the "static" method, I still don't really understand it yet, but I think I have to learn more about concepts like 'Objects', 'Classes', 'Methods' etc before I do. I'm heading back to the first few Stanford Opencourseware Java lectures so that I can force all of the concepts into my brain ;)

The Stanford courses are great, but here's another video tutorial that does a great job of giving you a running start.

Eclipse and Java for Total Beginners

It's geared around Eclipse, but the Java coverage is great too, and it also covers test-driven development. It moves quickly and covers quite a bit in about three hours of total video time, in bite-sized chunks.

-Gary-

[gcalvin]

By the way, to help get static methods clear in your head, play around with Math.random() and the Random class. Math.random() is a good example of a static method, while the Random class does the same job the more object-oriented way.

-Gary-

[beefy]

Thanks guys for your help! :)

[m00nchile]

By the way, we were just toying around with a recursive method for fibbonnaci sequence at my class in uni. Since the definition of a number in the sequence is based on other numbers makes this problem inherently recursive:

int fib(int n) {
  if(n <= 1) return n;
  return fib(n-1)+fib(n-2);
}

Now, this is a pretty simple method, easy to understand, but it's slow as heck. The main problem is this: if you want to calculate the 5th element, first you have to calculate the 4th and 3rd element. Then you calculate the 4th again, the 3rd again and then the 2nd. A lot of calculations that were already done. A solution is, the try and memorize the results of calculations that you have already done. Try this on for size, and try to measure the running time for the normal method and the improved one for a large n value.

int fibMemo(int n) {
  Integer[] memo = new Integer[n+1];
  return fibMemo(n, memo);
}

int fibMemo(int n, Integer[] memo) {
  if(memo[n] == null) {//we haven't calculated this yet
    if(n <= 1) memo[n] = n; //base condition
    else memo[n] = fibMemo(n-1, memo)+fibMemo(n-2, memo);
  }
  return memo[n]; //if the first if returns false, no calculations are made, because we
  //already calculated this number
}