Deltron Z
Expert Cheater
![]() Reputation: 1
Joined: 14 Jun 2009
Posts: 164
|
 Posted: Thu Mar 17, 2011 10:19 pm Post subject: |
 |
|
What is there to say? there's a formula to calculate the Nth triangle number in O(1) - constant time, unlike the other function which calculates the number in O(n) operations.
The functions names are confusing because they're wrong - "recursion" isn't recursive and "iteration" has only one iteration. o.o
Regarding to problem 12 - I think you shouldn't use a function. as you can see, besides the formula (which includes multiply and division - quite expensive operations) there's another way to represent a triangle number.
a0 = 1
ai+1 = ai+1 + di
d0 = 1
di+1 = di + 1
so you can calculate the next triangle number with two simple operations - addition.
A simple solution, but not very inefficient would look something like this:
| Code: | int t = 0, d = 1;
do
{
t += d;
d++;
} while (count_divisors(t) < 500);
return t; |
This problem isn't that difficault - so you don't even really need such a good count_divisors function. a simple loop to the square root should be fast enough, something like this:
| Code: | int count_divisors(int n)
{
int count = 2; //1 and n
int sqrt = (int)sqrt(n);
int odd = n & 1;
for (int i = 2 + odd; i < sqrt; i += 1 + odd)
{
if (n % i == 0)
count += 2; //n % i == 0 && n % (n / i) == 0
}
if (n % sqrt == 0) //square number
count++;
return count;
} |
Edit: I wrote this code:
| Code: | #include <stdio.h>
#include <math.h>
int count_divisors(int n)
{
int count = 2; //1 and n
int sqroot = (int)sqrt((double)n);
int odd = n & 1;
for (int i = 2 + odd; i < sqroot; i += 1 + odd)
{
if (n % i == 0)
count += 2; //n % i == 0 && n % (n / i) == 0
}
if (n % sqroot == 0) //square number
count++;
return count;
}
int problem12()
{
int n = 0, d = 1;
do
{
n += d;
d++;
} while (count_divisors(n) < 500);
return n;
}
int main()
{
printf("%d\n", problem12());
return 0;
} |
I changed the name of the variable "sqrt" to "sqroot" because there was a function named sqrt... I wrote the previous code in the browser. 
_________________
SharpDisassembler
"When I find my code in tons of trouble,
Friends and colleagues come to me...
Speaking words of wisdom:
Write in C."
#pragma message("Let there be byte!") |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
