Кодирование Kata: Какой оптимальный алгоритм для решения этой проблемы?

Question

Я пытался решить случайное кодирование ката и нашел это, мой вопрос здесь заключается в том, каков оптимальный алгоритм и лучший подход к проектированию для решения этого ката?

Учитывая последовательность чисел, определить типпоследовательность, вычислить и вернуть следующее число в последовательности.

Integer guessNextNumber(List<Integer> sequence);

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

Арифметическая последовательность определяется как: Arith_seq(p, q) = p, p + q, (p + q) + q,… Пример: Arith_seq (7,3) = 7, 10, 13, 16, 19,…

Геометрическая последовательностьопределяется как: Geo_seq (p, q) = p, p * q, (p * q) * q,… Пример: Geo_seq (2,3) = 2, 6, 18, 54,…

Ожидаетсявход и выход: входная последовательность будет иметь как минимум 3 числа.Для входной последовательности (7, 10, 13, 16, 19) возвращаемое значение будет 22. Для входной последовательности (2, 6, 18, 54) возвращаемое значение будет 162.

Алгоритм:

1. Проверьте входную последовательность, если у нас есть последовательность как (a, b, c), тогда,

2. , если разница между элементами последовательности (ba) или (cb)равен его арифметической последовательности.

3. если разделение между элементами последовательности равно, например: b / a и c / b, то его геометрическая последовательность

Мой вопрос, что будетбыть оптимальным алгоритмом для его решения?

Обновление: возможно ли решить это постоянное время выполнения?

Answer 1

Допустим, ваша коллекция a,b,c,d

• b - a + b = c тогда это арифметика
• b / a * b = c это геометрические

Чтобы вернуть правильную последовательность, вы можете сделать

• d - c + d = e, а если e - d = d - c, вернуть e
• иначе
• d / c * d = e, а если e / d = d / c, вернуть e

Java будет (при условии, что оно будет либо искусственным, либо геометрическим, а не чем-то другим, и всегда будет не менее 3 записей)

public int nextInt(int[] s){
  if( s[1] - s[0] == s[2] - s[1] ) return ( s[1] - s[0] ) + s[s.length - 1];
  return ( s[1] / s[0] ) * s[s.length - 1];
}

Безопасный код будет

public int nextInt(int[] s){
  if(s!=null && s.length > 3){
    if( s[1] - s[0] == s[2] - s[1] ) return ( s[1] - s[0] ) + s[s.length - 1];
    if( s[1] / s[0] == s[2] / s[1] ) return ( s[1] / s[0] ) * s[s.length - 1];
  }
  return -1;
}

со списком вместо массива

public Integer guessNextNumber(List<Integer> sequence){
  if( sequence.get(1) - sequence.get(0) == sequence.get(2) - sequence.get(1) ) return (    sequence.get(1) -  sequence.get(0) ) +  sequence.get(sequence.size() - 1);
  return ( sequence.get(1) / sequence.get(0) ) * sequence.get(sequence.size() - 1);
}

Answer 2

Вопрос в его нынешнем виде прост: найдите различия между первыми тремя числами последовательности и сравните. Если они равны, последовательность арифметическая. Если это не так, последовательность является геометрической.

Рассмотрим арифметическую последовательность 5, 2.

5, 7, 9, 11, 13, 15.

Рассмотрим геометрическую последовательность 5, 2.

5, 10, 20, 40.

Различия между числами в первой последовательности: 2. Различия между числами во второй последовательности: 5, 10, 20.

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

def determineProgression(xs: List[Int]): String = {
    assert(xs.length >= 3, "The list must be at least three elements long.")

    if ((xs(1) - xs(0)) == (xs(2) - xs(1)))
        "This is an arithmetic sequence. The most likely next step is " + (xs.last + (xs(1) - xs(0)))
    else if ((xs(1) / xs(0)) == (xs(2) / xs(1)))
        "This is a geometric sequence. The most likely next step is " + (xs.last * (xs(2) / xs(1)))
    else "This sequence is neither arithmetic nor geometric."
}