使用for循环生成数字序列(1,1,2,2,3,3等)。

Question

我查了一下，这个模式是霍夫斯塔德女性序列。方程式如下： M(n) = n-F(M(n-1)) F(n) = n-M(F(n-1)) 但我不确定如何将其编写成代码。

到目前为止，我的代码如下：

while () {
    _p++
    _r++
    if (_p % 2 === 0) {
        _r = _p - 1;
    }
}

需要帮助吗？

- Tom

---

什么编程语言？你到目前为止尝试过写什么了吗？ - StilesCrisis

面向对象编程(OOP)和中国茶叶的价格或这个问题有什么关系？ - dandavis

我猜这个问题是关于如何计算中国茶叶期货价格的 :P - Jason Sperske

JavaScript 是一门面向对象的编程语言。对象是关联数组，还加上了原型（见下文）。对象属性名是关联数组的键：obj.x = 10 和 obj["x"] = 10 是等效的，点表示法只是语法糖。属性和它们的值可以在运行时被添加、改变或删除。一个对象的属性也可以通过 for...in 循环进行枚举。 - Tom

各位，你们能否在别的地方讨论关于面向对象编程的观点？这与这个复杂的算法问题无关。 - gaborsch

Answer 1

没有 记忆化：

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(','))

输出：

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.net/KtGBg/1/

- Matt

---

我很好奇，但是只能用这个方程和两个函数来完成吗？ - Tom

是的，在原始定义中，这些方程式相互引用。 - Jason Sperske

Answer 2

如果可能的话，应该避免使用递归，这样你可以缓存已经计算过的F(n)和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;
}

这将在更大的数字下获得更快的结果（用10000试试看）。

- gaborsch

---

等等，我有点困惑，你的方法怎么避免递归呢？ - Jason Sperske

它并不是完全避免，而是对于 **F(0)、F(1)**、... F(9999) 等结果进行缓存。因此，如果我们已经有了结果，就不需要进入递归。否则，想象一下你将不得不计算多少次 **F(0)**。 - gaborsch

Answer 3

如何呢：

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))

- גלעד ברקן

---

那个字符串构建很丑。使用 for (var arr=[]; arr.length<=10; ) arr.push(F(arr.length)); console.log(arr.join(", "))。 - Bergi

@Bergi 我认为这个字符串构建活动没有任何问题。 - גלעד ברקן

Answer 4

与GaborSch的答案类似，您可以使用Doug Crockford的memoizer函数，该函数可在Javascript：The Good Parts第4章中找到。使用记忆化将男性和女性Hofstadter序列的前150项的计算时间缩短到256毫秒，而没有记忆化则需要近8秒。

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(','));

- Matthew Rankin

---

一个通用的“记忆化”函数和干净的 Hofstadter 实现。太棒了 :) - Jason Sperske

不错。感谢您测量记忆化和直接递归之间的差异。我给你点赞 :) - gaborsch