Omnimaga
General Discussion => Other Discussions => Math and Science => Topic started by: Munchor on January 30, 2011, 06:16:50 pm
-
Hey Omnimathematicians!
Who knows what the Catalan Number is?
You can find some information here (http://en.wikipedia.org/wiki/Catalan_number).
But in other "images", this what a catalan number is:
(http://img172.imageshack.us/img172/7093/5078678100871.gif)
So, I just made a simple program in C (I had already made one in python) to calculate the catalan number of n. However, I do not know how to do the opposite :S Can anyone help me with that?
#include <stdio.h>
main() {
// This program was coded by David
// This program calculates Catalan Numbers and the opposite too
printf("Choose:\n");
printf("1: Calculate Catalan Number of given number\n");
printf("2: Calculate original number of Catalan Number\n");
int answer;
scanf("%d",&answer);
if (answer == 1)
{
// Returns the catalan number
printf("Enter original number: ");
int input;
scanf("%d",&input);
int catalanNumber = factorial(2*input)/(factorial(input+1)*factorial(input));
printf("The catalan number is: %d",catalanNumber);
}
if (answer == 2)
{
// Returns the original number
printf("Not finished for now.");
//printf("Enter catalan number: ");
//int catalan;
//scanf("%d,&cataln);
}
getch();
return 0;
}
int factorial( int n )
{
if ( n <= 1 )
return 1;
else
return n * factorial( n-1 );
}
The .exe is executable, try it!
-
The Catalan number of 5 is 42 O.O
-
The Catalan number of 5 is 42 O.O
Yes it is ;D
-
For doing the opposite you can go the naive or brute force way: calculate catalan numbers until it match (do not forget to handle bad inputs).
I am thinking in a better approach but the factorial is dragging me off.
Offtopic: cool so much recent interest on mathematics here. :)
-
For doing the opposite you can go the naive or brute force way: calculate catalan numbers until it match (do not forget to handle bad inputs).
I am thinking in a better approach but the factorial is dragging me off.
Offtopic: cool so much recent interest on mathematics here. :)
A loop that goes through all of them would be possible, but quite slow :S
-
For doing the opposite you can go the naive or brute force way: calculate catalan numbers until it match (do not forget to handle bad inputs).
I am thinking in a better approach but the factorial is dragging me off.
Offtopic: cool so much recent interest on mathematics here. :)
A loop that goes through all of them would be possible, but quite slow :S
Yes, but I can't find any function that is to factorial what logarithm is to exponential.
Factorial is also a difficult thing to compute and very easily overflows integer variables. Try 20! and see on how many bits it will fill into.
The only thing I could think of is using http://en.wikipedia.org/wiki/Stirling%27s_approximation solve it in order of n. Does it even will work? Maybe only with very large factorials... Still a ugly solution.
-
#include <stdio.h>
main() {
// This program was coded by David
// This program calculates Catalan Numbers and the opposite too
printf("Choose:\n");
printf("1: Calculate Catalan Number of given number\n");
printf("2: Calculate original number of Catalan Number\n");
int answer;
scanf("%d",&answer);
if (answer == 1)
{
// Returns the catalan number
printf("Enter original number: ");
int input;
scanf("%d",&input);
int catalanNumber = factorial(2*input)/(factorial(input+1)*factorial(input));
printf("The catalan number is: %d",catalanNumber);
}
if (answer == 2)
{
// Returns the original number
printf("Enter catalan number: ");
int catalan;
scanf("%d",&catalan);
int i;
for(i = 0; i <= catalan; i++)
{
if ((factorial(2*i)/(factorial(i+1)*factorial(i))) == catalan)
{
printf("The original number is: %d",i);
break;
}
}
}
getch();
return 0;
}
int factorial( int n )
{
if ( n <= 1 )
return 1;
else
return n * factorial( n-1 );
}
Done. Now it does the opposite, it goes through a loop. It's actually quite fast compared to what I thought it would be. Afterall, C is really fast language ;D
Any ideas?
-
By the way, converted to C++ for fun:
#include <iostream>
#include <stdio.h>
using namespace std;
int factorial(int n);
int main() {
// Coded by David
printf("Choose:\n");
printf("1: Calculate Catalan Number of given number\n");
printf("2: Calculate original number of Catalan Number\n");
int answer;
scanf("%d",&answer);
if (answer==1)
{
printf("Enter input number: ");
int input;
scanf("%d",&input);
int catalanNumber = factorial(2*input)/(factorial(input+1)*factorial(input));
printf("The catalan number is: %d",catalanNumber);
getchar();
}
if (answer==2)
{
printf("Enter output number: ");
int input;
scanf("%d",&input);
int i;
for (i=0;i<=input;i++)
{
if ((factorial(2*i)/(factorial(i+1)*factorial(i))) == input)
{
printf("The original number is: %d",i);
getchar();
break;
}
}
}
getchar();
return 0;
}
int factorial(int n) {
if ( n <= 1 )
return 1;
else
return n * factorial( n-1 );
}
I did use C libraries, though.
EDIT:
Only C++ Libraries now:
#include <iostream>
using namespace std;
int factorial(int n);
int main() {
// Coded by David
cout << "Choose:\n";
cout << "1: Calculate Catalan Number of given number\n";
cout << "2: Calculate original number of Catalan Number\n";
int answer;
cin >> answer;
if (answer==1)
{
cout << "Enter input number: ";
int input;
cin >> input;
int catalanNumber = factorial(2*input)/(factorial(input+1)*factorial(input));
cout << "The catalan number is: " << catalanNumber;
getchar();
}
if (answer==2)
{
cout << "Enter output number: ";
int input;
cin >> input;
int i;
for (i=0;i<=input;i++)
{
if ((factorial(2*i)/(factorial(i+1)*factorial(i))) == input)
{
cout << "The original number is: "<< i;
getchar();
break;
}
}
}
getchar();
return 0;
}
int factorial(int n) {
if ( n <= 1 )
return 1;
else
return n * factorial( n-1 );
}
-
ooh, recursive functions are always fun. I always like adding a answer == 42 type thing. ;-) Anyway, does this handle negatives correctly?
-
ooh, recursive functions are always fun. I always like adding a answer == 42 type thing. ;-) Anyway, does this handle negatives correctly?
Recursive functions are sweet!
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1)+fib(n-2)
The fibonacci function was the first one I learnt ;D
Not sure if it handles negatives right, though, I have to test it yet.
-
ooh, recursive functions are always fun. I always like adding a answer == 42 type thing. ;-) Anyway, does this handle negatives correctly?
Recursive functions are sweet!
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1)+fib(n-2)
The fibonacci function was the first one I learnt ;D
Not sure if it handles negatives right, though, I have to test it yet.
From that code, it won't because you don't have constants for negatives, so it will recursively go until you run out of memory. I would just do a if n<=0 return 0, or a if n<0 n=-n
-
No graphmastur, the negative numbers is about the catalan program, not the fibonacci.
-
No graphmastur, the negative numbers is about the catalan program, not the fibonacci.
Ah, okay, my bad. I just figured they might try and pass a negative number and I would hate for the routine to be unable to handle it.
-
No graphmastur, the negative numbers is about the catalan program, not the fibonacci.
Ah, okay, my bad. I just figured they might try and pass a negative number and I would hate for the routine to be unable to handle it.
Nobody who knows what the fibonacci sequence is would input negative numbers. In fact, any sequence, a sequence can't have it's -1th member xD
-
No graphmastur, the negative numbers is about the catalan program, not the fibonacci.
Ah, okay, my bad. I just figured they might try and pass a negative number and I would hate for the routine to be unable to handle it.
Nobody who knows what the fibonacci sequence is would input negative numbers. In fact, any sequence, a sequence can't have it's -1th member xD
True, but I like bounding stuff like that anyway. It's a strange quirk I have to check a bunch of stuff to be null or not, or check if it's outside bounds even though it probably never will be.
-
To calculate bigger numbers, you could have the program simplify the expression before actually computing it.
-
BTW, on the subject of negative Fibonacci numbers, they do exist. Just reverse the recursion (F_n+F_{n+1} = F_{n+2}) => (F_{n-2} = F_n-F_{n-1}) and it works.
(Though they aren't terribly interesting: F_{-i} = -F_i * (-1)^i, so the negativeth Fibonacci number is either the negation of or equal to the positiveth Fibonacci number)
-
Of course phenomist would know about this stuff.
-
Of course phenomist would know about this stuff.
lol
BTW, on the subject of negative Fibonacci numbers, they do exist. Just reverse the recursion (F_n+F_{n+1} = F_{n+2}) => (F_{n-2} = F_n-F_{n-1}) and it works.
(Though they aren't terribly interesting: F_{-i} = -F_i * (-1)^i, so the negativeth Fibonacci number is either the negation of or equal to the positiveth Fibonacci number)
Yeah, there's not much interest there, but thanks :D
-
I know I'm abusing this Catalan Number thing, but it's great to learn new things about languages, so I made it Java GUI using Awt and Swing.