|
September 22, 2005
I haven't used visual informatics in so long, I feel like I
starting to go blind! Although, I did take some time out to
viddy,
and oh, baby--the memories of places and times correlate strongly with some
of these machines.
How about first getting the recursive function for
integer partitions working and then look into some visuals? Plan?
My first implementation is very simple:
///
recursive call F(n,k) = F(n-k,k) + F(n,k+1)
#include <iostream>
using
namespace std;
// Recursive function
int f(int,
int);
void main() {
cout <<
"****************************************************\n"
<< "* Compute the number of
integer partitions
*\n"
<< "* of a number N by the
recursive call
*\n"
<< "* F(n,k) = F(n-k,k) +
F(n,k+1).
*\n"
<< "* For instance, F(5,1) =
F(4,1) + F(5,2) =
*\n"
<< "* = (F(3,1) + F(4,2)) +
(F(3,2) + F(5,3)) =
*\n"
<< "* = (F(2,1) + F(3,2) + F(2,2)
+ F(4,3)) + (1 + 1) *\n"
<< "* = 2 + 1 + 1 + 1 + 2
*\n"
<< "* = 7
*\n"
<<
"****************************************************\n";
int n=1;
while(n>0)
{
cout << "\n\n
Enter the integer whose partition value will be computed: ";
cin >> n;
cout << "
Partiions(" << n << ") = "
<< f(n,1);
}
} // end main
int f(int
n, int k) {
if(k>n)
return 0;
else
if(k>n/2)
return 1;
else
return f(n-k,k) + f(n,k+1);
} |
The output is shown below. As is
characteristic of these recursive functions, the time to compute the
partitions of 100 was rather long, and this seems to be close to the limit
of what this code can do.
****************************************************
* Compute the number of integer partitions
*
* of a number N by the recursive call
*
* F(n,k) = F(n-k,k) + F(n,k+1).
*
* For instance, F(5,1) = F(4,1) + F(5,2) =
*
* = (F(3,1) + F(4,2)) + (F(3,2) + F(5,3)) =
*
* = (F(2,1) + F(3,2) + F(2,2) + F(4,3)) + (1 + 1) *
* = 2 + 1 + 1 + 1 + 2
*
* = 7
*
****************************************************
Enter the integer whose partition value will be computed: 9
Partiions(9) = 30
Enter the integer whose partition value will be computed: 11
Partiions(11) = 56
Enter the integer whose partition value will be computed: 15
Partiions(15) = 176
Enter the integer whose partition value will be computed: 25
Partiions(25) = 1958
Enter the integer whose partition value will be computed: 100
Partiions(100) = 190569292
Enter the integer whose partition value will be computed: |
|