Files

camperbot 5c868af2b8 chore(i18n,learn): processed translations (#44851 )

2022-01-20 20:30:18 +01:00

4.5 KiB

Raw Permalink Blame History

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
594810f028c0303b75339ad6	ゼッケンドルフの定理	5	302346	zeckendorf-number-representation

--description--

数字を 10 (10 進数) または 2 (2 進数) の累乗の倍数の和として位取り記数法で表現できるように、すべての正の整数は、フィボナッチ数列のそれぞれ異なる要素の 1 倍または 0 倍の和として表現できます。最初の 6 つの個々のフィボナッチ数は以下のとおりでした: 1, 2, 3, 5, 8, 13.

10 進数の 11 は、各列がフィボナッチ数列の特定の要素による乗算を表す位取り記数法で 0*13 + 1*8 + 0*5 + 1*3 + 0*2 + 0*1 または 010100 のように記述することもできます。先頭のゼロを落として、10 進数の 11 が 10100になるようにします。フィボナッチ数から 11 を作る方法は 10100 だけではありませんが、 0*13 + 1*8 + 0*5 + 0*3 + 1*2 + 1*1 または 010011もまた、10 進数の 11 を表しています。真のゼッケンドルフ表現については、2 つの連続するフィボナッチ数を使用できないという追加の制限があり、それが前の一意の解ということにつながります。

--instructions--

n のゼッケンドルフ表現を生成して返す関数を記述してください。

--hints--

zeckendorf は関数とします。

assert.equal(typeof zeckendorf, 'function');

zeckendorf(0) は 0 を返す必要があります。

assert.equal(zeckendorf(0), 0);

zeckendorf(1) は 1 を返す必要があります。

assert.equal(zeckendorf(1), 1);

zeckendorf(2) は 10 を返す必要があります。

assert.equal(zeckendorf(2), 10);

zeckendorf(3) は 100 を返す必要があります。

assert.equal(zeckendorf(3), 100);

zeckendorf(4) は 101 を返す必要があります。

assert.equal(zeckendorf(4), 101);

zeckendorf(5) は 1000 を返す必要があります。

assert.equal(zeckendorf(5), 1000);

zeckendorf(6) は 1001 を返す必要があります。

assert.equal(zeckendorf(6), 1001);

zeckendorf(7) は 1010 を返す必要があります。

assert.equal(zeckendorf(7), 1010);

zeckendorf(8) は 10000 を返す必要があります。

assert.equal(zeckendorf(8), 10000);

zeckendorf(9) は 10001 を返す必要があります。

assert.equal(zeckendorf(9), 10001);

zeckendorf(10) は 10010 を返す必要があります。

assert.equal(zeckendorf(10), 10010);

zeckendorf(11) は 10100 を返す必要があります。

assert.equal(zeckendorf(11), 10100);

zeckendorf(12) は 10101 を返す必要があります。

assert.equal(zeckendorf(12), 10101);

zeckendorf(13) は 100000 を返す必要があります。

assert.equal(zeckendorf(13), 100000);

zeckendorf(14) は 100001 を返す必要があります。

assert.equal(zeckendorf(14), 100001);

zeckendorf(15) は 100010 を返す必要があります。

assert.equal(zeckendorf(15), 100010);

zeckendorf(16) は 100100 を返す必要があります。

assert.equal(zeckendorf(16), 100100);

zeckendorf(17) は 100101 を返す必要があります。

assert.equal(zeckendorf(17), 100101);

zeckendorf(18) は 101000 を返す必要があります。

assert.equal(zeckendorf(18), 101000);

zeckendorf(19) は 101001 を返す必要があります。

assert.equal(zeckendorf(19), 101001);

zeckendorf(20) は 101010 を返す必要があります。

assert.equal(zeckendorf(20), 101010);

--seed--

--seed-contents--

function zeckendorf(n) {

}

--solutions--

// zeckendorf :: Int -> Int
function zeckendorf(n) {
  const f = (m, x) => (m < x ? [m, 0] : [m - x, 1]);
  return parseInt((n === 0 ? ([0]) :
    mapAccumL(f, n, reverse(
      tail(fibUntil(n))
    ))[1]).join(''));
}

// fibUntil :: Int -> [Int]
let fibUntil = n => {
  const xs = [];
  until(
      ([a]) => a > n,
      ([a, b]) => (xs.push(a), [b, a + b]), [1, 1]
  );
  return xs;
};

let mapAccumL = (f, acc, xs) => (
  xs.reduce((a, x) => {
    const pair = f(a[0], x);

    return [pair[0], a[1].concat(pair[1])];
  }, [acc, []])
);

let until = (p, f, x) => {
  let v = x;
  while (!p(v)) v = f(v);
  return v;
};

const tail = xs => (
   xs.length ? xs.slice(1) : undefined
);

const reverse = xs => xs.slice(0).reverse();

4.5 KiB Raw Permalink Blame History