Project Euler Solutions
This thread is dedicated for interesting project Euler solutions. Some initial attempt on project Euler solutions are available on our Wiki: http://smallbasic.com/wiki/ProjectEuler.ashx.
Problems are available at: http://projecteuler.net/index.php?section=problems
全部回复
- To kick off, the First Problem is:
"If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000."
Solution
Id: JLK064
Listing: http://smallbasic.com/program/?JLK064 I originally posted this as part of a response for the thread on arrays.
Euler Projects 18 and 67 require the use of arrays or other similar data structures. You are given a triangle of numbers, and your job to find the maximum sum traveling from the tip to the base of the triangle. Project 18 has a height of 15, problem 67 has a height of 100.
The small basic solution can be imported from the ID: XBN618- Euler Problem #28
http://projecteuler.net/index.php?section=problems&id=28
The goal of this problem is to build a 1000x1000 grid, populate the grid with increasing numbers spiraling out from the center, and find the sum of the diagonals of the resulting grid.
The first solution builds a 1000x1000 grid using the array object, with the needed spiraling values. Once built the code zips through the diagonals to find the sum.
SmallBasic Publish ID: NMQ902
Once I completed the above solution, it occurred to me that I could accomplish the same task by tracking the values of the diagonals as I was building the spiral. The array isn't needed. The second solution solves the problem without the array, and does so in half the time.
Small Basic Publish ID: RBH700 - Euler Problem #30
http://projecteuler.net/index.php?section=problems&id=30
The goal of this problem is to find the sum of all numbers where:
the sum of the fifth power of the numbers digits, equals that number
Example: 4150 = 4^5 + 1^5 + 5^5 + 0^5
This solution is a good example of why I have always been a fan of BASIC. Working with strings can be unpleasant in most languages. Basic makes it easy. I managed to cough up this solution in about five minutes, where it would have taken closer to an hour with Java simply because of the need to struggle with string manipulation (yes, I know you could also do some math to separate the digits).
Small Basic Publish ID: RLB652 - Very nice! Love the elegance of RLB652.
Another way to solve the Euler problem #28
This program is much faster than the previously posted one. It solves the problem by viewing the diagonals as the result of four different equations, each starting in the middle. It then adds every value for each of the results in the equations to a variable and when it's done it shows the result.
This is the solution i came up with, the program is very simple and should be easy to understand.
ID: QXH159- Nice. You are right gunnar, your solution is fifteen times faster and it is a more elegant solution than mine.
- Hi,
on the followed link you can find my humble attempt of solution for problem no 69.
The 'graphical' part makes sense only for small part of the triangle (up to 15-20 rows) but generally works for any (reasonable) size.
As this is one of my first excercises, please forgive me some basic mistakes.
http://smallbasic.com/program/?NXP803
ID: NXP803 - I've posted a solution with no looping... :)
Here's the way the young Gauss would have attacked the problem...
Use the Math.Floor function to find the number of multiples of 3 (n3) and 5 (n5) below the given number respectively.
Add up all the natural numbers from 1 to n3 (simple formula is n3x(n3 + 1) /2) and multiply by 3. (sum3)
Do likewise for n5, only multiply by 5 of course! (sum5)
Then, because the multiples coincide at multiples of 15, use similar programming to find the sum of all the multiples of 15.
The answer is then simply sum3 + sum5, minus the sum of the multiples of 15.
Take a look...
http://smallbasic.com/program/?LWS487 - I like your approach. Modern computers make number crunching easier than thinking.
However, doing it by brute force, noting the 'below input number' ...
total = 0
For i = 1 To input-1
If (math.Remainder(i,3) = 0 or math.Remainder(i,5) = 0) Then
total = total+i
EndIf
EndFor
TextWindow.WriteLine("The long answer is :" + total)
So for input = 15 we have:
3,6,9,12 & 5,10, sum= 45, you have 30
BTW we agree on the answer for 1000 - 233168
Perhaps I am missing something in the original problem. - No you didn't miss anything - I did! - a coding error on my part that only showed up when the target was an exact multiple of 15 - just forgot to do "Input - 1" when calculating the multiples of 15 to be subtracted...
Embarrassing!
Thanks for pointing it out...
Revised code at http://smallbasic.com/program/?KNR835
I love the way smallbasic handles really big numbers - input 1000000000000 into the program above...
Anyone know just how big a number it can cope with? - The following gives up at 2^95 on my PC.
i = 1
x = 2
While("True")
i = i+1
x =2*x
TextWindow.WriteLine(i+" : "+x)
EndWhile
- My first post in small basic forum
Problem #6
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
http://smallbasic.com/program/?NXP803-0 - This is what it got to on mine (btw it was done before you could snap your fingers):95 : 39614081257132168796771975168Then it said this in an error window:Value was either too large or too small for a Decimal.at System.Decimal.FCallMultiply(Decimal& result, Decimal d1, Decimal d2)at Microsoft.SmallBasic.Library.Primitive.Multiply(Primitive multiplicand)at Microsoft.SmallBasic.Library.Primitive.op_Multiply(Primitive primitive1, Primitive primitive2)at _SmallBasicProgram._Main()
- which is the same thing it got to on your computer because it went over how many digits you could have
