|
Yo, so I started project euler a couple days ago, and some of the problems are pretty challenging already, for someone who's only had 10 grades of math. I've done quite a bit of googling, compared some codes and whatnot, but i never found a c++ example, and it's the only language i'm somewhat familiar with, so other's solutions are hard to understand. I know that asking for help on a project euler problem is pretty lame, but i'm completely stuck and very curious as to what i'm doing wrong. Not really the right place to ask either, but I don't know where else would be more appropriate, so here we go:
The problem:
+ Show Spoiler +
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
I've checked and double-checked my solution many times but I can't for the life of me see how it's wrong, here's the code: (Pretty sloppy but w/e, it's short)
+ Show Spoiler +
#include <iostream>
#include <windows.h>
#include "conio.h"
using namespace std;
int temp = 0; // temp stores chain length
int maxnum = 0; // max chain
int begnum = 0; // max beginning number
int tempbegnum = 0; // temp max beginning number
void sequence(int n)
{
temp = 0;
tempbegnum = n;
while (n > 1)
{
if (n % 2 == 0)
{
n = n/2;
}
else
{
n = n*3+1;
}
temp++;
}
if (temp > maxnum && n == 1)
{
maxnum = temp;
begnum = tempbegnum;
}
return;
}
int main()
{
for (int i = 0; i < 1000000; i++)
{
sequence(i);
}
cout << maxnum << endl << begnum;
_getch();
return 0;
}
 
|
Kau
Canada3500 Posts
I just skimmed your code so this question might be useless, but what happens if several chains have the same chain length? Do you take the smallest number or the largest?
|
I didn't really think of it because I assumed one definite answer, but only if the current chain is OVER the max chain will it be stored.
|
Canada9720 Posts
don't have the time now to help out, but a general tip: if you want people to read your code, some indenting will help.
|
I'm sorry that would be the forum's fault. Don't know how to fix it.
|
Canada9720 Posts
|
Canada9720 Posts
#include <iostream>
#include <windows.h>
#include "conio.h"
using namespace std;
int temp = 0; // temp stores chain length
int maxnum = 0; // max chain
int begnum = 0; // max beginning number
int tempbegnum = 0; // temp max beginning number
void sequence(int n)
{
temp = 0;
tempbegnum = n;
while (n > 1)
{
if (n % 2 == 0)
{
n = n/2;
}
else
{
n = n*3+1;
}
temp++;
}
if (temp > maxnum && n == 1)
{
maxnum = temp;
begnum = tempbegnum;
}
return;
}
int main()
{
for (int i = 0; i < 1000000; i++)
{
sequence(i);
}
cout << maxnum << endl << begnum;
_getch();
return 0;
}
|
Sick, how'd you do that? For future reference.
|
United States4991 Posts
With the [code] tag 
You could hit quote and it shows you what he used to make his post.
Without actually writing code or solving the problem: are you sure you are not overflowing int?
|
Project Euler is badass. Good for you for taking on the challenge. You will learn a lot in the process.
|
it counts one to many. But since it does it with al of the numbers, the number with the most is still the number with the most. But the array is one number shorter.
(i tested it with i < 5, it says 7 / 3, meaning array(3) has seven items, which is untrue: 3 10 5 16 8 4 2 1)
|
United States4991 Posts
OK, I did it in C# using a similar method to yours and it works fine using a long instead of an int. (I don't mean for the chain length--I mean for the value that you actually change to n/2 or 3n+1)
On November 05 2009 05:00 Navane wrote:
it counts one to many. But since it does it with al of the numbers, the number with the most is still the number with the most. But the array is one number shorter.
(i tested it with i < 5, it says 7 / 3, meaning array(3) has seven items, which is untrue: 3 10 5 16 8 4 2 1)
I don't really understand what you're trying to communicate with this post. He never uses an array...?
e: In case it's not clear, I never ran your code
This was my C# solution. And no I don't write actual ugly code like the for statement in production :D
+ Show Spoiler + static void Main(string[] args)
{
int longest = 0;
int longestIndex = 1;
for (int i = 1; i < 1000000; i++)
{
int temp = ChainLength(i);
if (temp > longest)
{
longestIndex = i;
longest = temp;
}
}
Console.WriteLine(string.Format("{0}: {1}", longestIndex, longest));
Console.Read();
}
private static int ChainLength(long a)
{
int c;
for (c = 0; a != 1; c++, a = (a % 2 == 0) ? a / 2 : (3 * a) + 1) ;
return c;
}
|
OK, I did it in C# using a similar method to yours and it works fine using a long instead of an int. (I don't mean for the chain length--I mean for the value that you actually change to n/2 or 3n+1)
I don't even know what to say to this... I'm so bad.
Atleast I got it solved, right? ONWARDS!
|
United States4991 Posts
On November 05 2009 05:11 Adeny wrote:Show nested quote +OK, I did it in C# using a similar method to yours and it works fine using a long instead of an int. (I don't mean for the chain length--I mean for the value that you actually change to n/2 or 3n+1) I don't even know what to say to this... I'm so bad.
You mean you don't know what to say that you missed that, or you don't know what I mean?
e: nevermind, you edited your post so it's clear what you mean
|
How do you know it's wrong?
|
I'm thinking a way to optimize it would be have an array to store the results of lower numbers of how long before the chain terminates. AKA, if you did sequence(13), and found that it takes 10 steps before it ends, you store 10 at array index 13, so the NEXT time a bigger number arrives at 13, you know that it's gonna end in 10 steps so you don't have to waste time calculating the rest. Do it recursively and it should be wayyyy faster.
|
|
|
On November 05 2009 05:36 AssuredVacancy wrote:
I'm thinking a way to optimize it would be have an array to store the results of lower numbers of how long before the chain terminates. AKA, if you did sequence(13), and found that it takes 10 steps before it ends, you store 10 at array index 13, so the NEXT time a bigger number arrives at 13, you know that it's gonna end in 10 steps so you don't have to waste time calculating the rest. Do it recursively and it should be wayyyy faster.
Interesting, but execution time is near-immediate on this, and I'm not good enough to think about optimalizations yet, it's challenging enough just to come up with the right answer, as you've seen.
Also I noticed now that when my program didn't work with the beginning value set to zero i changed the if (tempstring > maxstring) or whatever to if (tempstring > maxstring && n == 1), which is obviously very stupid as that gets checked every loop, right after while (n > 1), completely unecessary. I don't know where my mind whas at when I decided upon that instead of just changing it to start counting from 3 or something.
|
you program with C# peter...this makes me sad
|
United States4991 Posts
On November 05 2009 05:54 iSiN wrote:
you program with C# peter...this makes me sad
Programming in C# is part of my job. What's wrong with that?
|
On November 05 2009 07:30 HnR)Insane wrote:Show nested quote +On November 05 2009 05:54 iSiN wrote:
you program with C# peter...this makes me sad Programming in C# is part of my job. What's wrong with that?
I'm so sorry.
(I hate C# so much but then again I hate java and I'm pretty sure I'll be programming in java when I get in the field)
|
Artosis
United States2140 Posts
|
|
|
|
|
|
EPT
