Как мы можем получить минимум два рекурсивных вызова, один из которых добавляет, другой вычитает? - PullRequest
Новая
       26

Как мы можем получить минимум два рекурсивных вызова, один из которых добавляет, другой вычитает?

0 голосов
/ 22 марта 2020

Мы выполняем это упражнение по программированию: Офис № 2 - Ближайшая тройка из двух . Утверждение таково:

Вам нравится слушать музыку c в офисе.

Вам часто приходится менять громкость в наушниках благодаря разговорчивым коллегам, и вы находите, что самостоятельно используя + и - на клавиатуре, чтобы сделать это. Клавиши увеличивают и уменьшают громкость на 2 с каждым нажатием клавиши. Есть только одна проблема - вы предпочитаете числа, которые делятся на 3.

Иногда ваши коллеги громко, а иногда они на обед или поздно на работу - Отрегулируйте громкость соответственно!

Напишите функцию, которая принимает текущую громкость и выводит, сколько раз вам придется нажимать клавишу - или + на клавиатуре, чтобы сделать громкость цифрой, делимой на три.

Муси c может 't go ниже уровня 0 в этой плоскости существования.

ex: volume = 8: output = 1 (один ход клавиши - приведет вас к 6, что делится на 3, а чем два нажатия клавиши +, чтобы добраться до 12)

Мы написали следующий код: 

function musicalOCD(volume) {
  console.log("\n\nvolume: "+volume);
  if(volume%3==0) return 0;
  return Math.min(1+musicalOCD(volume+2),1+musicalOCD(volume-2));
}

Однако он проходит только тест базового случая, когда объем делится на 13.

Если мы перейдем в другой том, он выдаст: 

RangeError: Maximum call stack size exceeded
    at Socket.Readable.removeListener (_stream_readable.js:852:47)
    at write (console.js:172:12)
    at Console.log (console.js:200:3)
    at musicalOCD (test.js:5:11)
    at musicalOCD (test.js:7:21)

Будучи трассировкой: 

volume: 2


volume: 4


volume: 6


volume: 2


volume: 4


volume: 6

Таким образом, мы могли бы написать код просто делать рекурсивные вызовы, добавляя значения к объему: 

function musicalOCD(volume) {
  console.log("\n\nvolume: "+volume);
  if(volume%3==0) return 0;
  return 1+musicalOCD(volume+2);
}
* 1 032 * Однако в следующих тестах: 
describe("Fixed tests", function() {
  const testing = (volume, exp) => it(`Testing for ${volume}`, () => assert.strictEqual(musicalOCD(volume), exp));
  testing(4, 1);
  testing(12, 0);
  testing(20, 1);
  testing(22, 1);
  testing(68, 1);
});

Тестирование для 20 и 68 выдаст 2 вместо 1 ...

И если мы сделаем обратное: 

function musicalOCD(volume) {
  console.log("\n\nvolume: "+volume);
  if(volume%3==0) return 0;
  return 1+musicalOCD(volume-2);
}

Тогда при проверке 22 и 4 будет выведено 2 вместо 1 ...

Как мы можем объединить оба рекурсивных вызова в общем ответе?

Мы прочитали:

Ответы [ 2 ]

1 голос
/ 22 марта 2020 

const testing = (volume, exp) => {
  console.assert(musicalOCD(volume) === exp, 'Testing for ${volume} - failure');
};

testing(4, 1);
testing(12, 0);
testing(20, 1);
testing(22, 1);
testing(68, 1);
console.log('Run tests - done');

function musicalOCD(volume) {
  return Math.min( // <------- will return min value of two tests 
    _musicalOCD(volume, +2),
    _musicalOCD(volume, -2)
  );
}

function _musicalOCD(volume, mod) {
  if (volume < 0) return 0;
  if (volume >= 100) return 0;
  //console.log("\n\nvolume: " + volume);
  if (volume % 3 == 0) return 0;

  return 1 + _musicalOCD(volume + mod, mod);
}
0 голосов
/ 22 марта 2020

Вы можете использовать подход, в котором вы разветвляете рекурсивный вызов, проверяя декремент forst, а затем инкремент. 

function musicalOCD(volume) {
    if (volume % 3 === 0) return 0;
    return 1 + (musicalOCD(volume - 2) && musicalOCD(volume + 2));
}

[[4, 1], [12, 0], [20, 1], [22, 1], [68, 1]].forEach(([v, r]) => console.log(v, musicalOCD(v), r));

С указаниями по тестированию. 

function musicalOCD(volume, dir) {
    console.log(dir);
    if (volume % 3 === 0) return 0;
    return 1 + (musicalOCD(volume - 2, 'down') && musicalOCD(volume + 2, 'up'));
}

[[4, 1], [12, 0], [20, 1], [22, 1], [68, 1]].forEach(([v, r]) => console.log(v, musicalOCD(v), r));
.as-console-wrapper { max-height: 100% !important; top: 0; }
...