// I looked it up and this pattern is Hofstadter Female sequence. The equations are:
M(n) = n-F(M(n-1))
F(n) = n-M(F(n-1))
but I'm not sure how to put that into code.
So far I have:
while () {
_p++
_r++
if (_p % 2 === 0) {
_r = _p - 1;
}
}
Any help?
I looked it up and this pattern is Hofstadter Female sequence. The equations are:
M(n) = n-F(M(n-1))
F(n) = n-M(F(n-1))
but I'm not sure how to put that into code.
So far I have:
while () {
_p++
_r++
if (_p % 2 === 0) {
_r = _p - 1;
}
}
Any help?
Share Improve this question edited Feb 6, 2014 at 18:33 gaborsch 15.8k6 gold badges40 silver badges50 bronze badges asked Feb 6, 2014 at 18:17 TomTom 1,0952 gold badges13 silver badges31 bronze badges 17- 2 What programming language? And what have you tried writing so far? – StilesCrisis Commented Feb 6, 2014 at 18:18
-
1
This sounds like a job for a
whileloop. – helrich Commented Feb 6, 2014 at 18:18 - 4 what does OOP have to do with the price of tea in china or this question? – dandavis Commented Feb 6, 2014 at 18:25
- 3 @Zhafur JavaScript is heavily object-based. Objects are associative arrays, augmented with prototypes (see below). Object property names are associative array keys: obj.x = 10 and obj["x"] = 10 are equivalent, the dot notation being merely syntactic sugar. Properties and their values can be added, changed, or deleted at run-time. The properties of an object can also be enumerated via a for...in loop. – Tom Commented Feb 6, 2014 at 18:26
- 4 Guys, would you discuss your opinions about OOP somewhere else? I has nothing to to with this plex algorithmic question here. – gaborsch Commented Feb 6, 2014 at 18:29
4 Answers
Reset to default 5Without memoization:
function F(n)
{
return 0 < n ? n - M(F(n-1)) : 1
}
function M(n)
{
return 0 < n ? n - F(M(n-1)) : 0
}
var N = 10;
var f = [];
var m = [];
for (var i = 0; i <= N; ++i) {
f.push(F(i));
m.push(M(i));
}
console.log('F: ' + f.join(','))
console.log('M: ' + m.join(','))
Output:
F: 1,1,2,2,3,3,4,5,5,6,6
M: 0,0,1,2,2,3,4,4,5,6,6
http://jsfiddle/KtGBg/1/
Recursion should be avoided, if possible, so you can cache the already-calculated values for F(n) and M(n) :
var f = new Array();
var m = new Array();
function F(n){
if(f[n] != undefined) {
return f[n];
}
if (n==0) {
value = 1;
} else {
value = n - M(F(n-1));
}
f[n] = value;
return value;
}
function M(n){
if(m[n] != undefined) {
return m[n];
}
if (n==0) {
value = 0;
} else {
value = n - F(M(n-1));
}
m[n] = value;
return value;
}
This yields a much faster result for greater numbers (try it with 10000)
how about:
function F(n){
if (n==0) return 1
else return n - M(F(n-1))
}
function M(n){
if (n==0) return 0
else return n - F(M(n-1))
}
var str = ""
for(var i=0; i<=10; i++) str += F(i) + ", "
console.log(str.substr(0,str.length-2))
Similar to GaborSch's answer, you could use Doug Crockford's memoizer function, which can be found in Chapter 4 of Javascript: The Good Parts. Using memoization took the calculation time for the first 150 terms of the male and female Hofstadter sequences down to 256 ms as pared to almost 8 seconds without memoization.
var memoizer = function (memo, formula) {
var recur = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = formula(recur, n);
memo[n] = result;
}
return result;
};
return recur;
};
var maleHofstadter = memoizer([0], function (recur, n) {
return n - femaleHofstadter(recur(n-1));
});
var femaleHofstadter = memoizer([1], function (recur, n) {
return n - maleHofstadter(recur(n-1));
});
var N = 150;
var f = [];
var m = [];
for (var i = 0; i <= N; ++i) {
f.push(femaleHofstadter(i));
m.push(maleHofstadter(i));
}
console.log('F: ' + f.join(','));
console.log('M: ' + m.join(','));