Как мне решить это без рекурсии?

Question

Я пытаюсь помочь моему сыну решить математическую задачу. Кажется, это хорошая возможность познакомить его с программированием. Я вижу рекурсивное решение, но, возможно, итеративное было бы легче объяснить. Язык, который он изучил до сих пор, был SmallBasic , который не очень хорошо поддерживает рекурсию (без локальных переменных). Я не против преподавания другого языка, но все же хочу понять, есть ли хороший способ решить это без рекурсии.

Проблема заключается в следующем: Учитывая последовательность чисел 1 2 3 4 5 6 7 8 9, вставьте «+» и «-» между числами, чтобы результат составил до 101. Например, 1 + 23 + 4 + 5 + 67-8 + 9 = 101.

Рекурсивное решение выглядит примерно так:

next(total, number, nextNumber, sequenceString)
{
    //add
    next(total + number, ...);

    //subtract
    next(total - number, ...);

    //do nothing (multiply)
    next(total, number * 10, ...);
}

Существует ли итеративное решение, которое не слишком сложно?

Answer 1

Рассмотрим пробелы между числами 1 2 3 4 5 6 7 8 9. Существует 8 таких промежуточных пространств или слотов.

Каждое такое пространство может быть заполнено +, - или ничем (указывая большее число формируется).

Это три варианта в каждом из восьми слотов. Назначьте цифры для трех возможных заполнителей как:

 0 --> +
 1 --> -
 2 --> (nothing)

Теперь каждая 8-значная тройная строка соответствует решению. Например:

 00000000 --> 1+2+3+4+5+6+7+8+9
 00000001 --> 1+2+3+4+5+6+7+8-9
 00000002 --> 1+2+3+4+5+6+7+89
 22222222 --> 123456789

Теперь напишите простой цикл, который считает от 00000000 до 22222222 в тринах. Интерпретируйте каждое число по пути как решение, как указано выше, остановитесь, как только вы достигнете решения, дающего цель, 101, или сообщите об ошибке, если дойдете до конца, не достигнув целевого значения.

Есть 3 ^ 8 (показатель степени, а не xor, или 3 ** 8 для фортраноидов, или

 3*3*3*3*3*3*3*3

для интенсивно буквально) возможных решений. Это только 6561; Вы можете легко перебить его таким способом.

Answer 2

Рекурсия - важный момент в информатике. Если ваша цель - научить вашего сына, почему бы вам не объяснить ему рекурсию прямо сейчас? ;)

Answer 3

У вас есть 3 основных операции:

• Добавить (опция "0");
• Substract (опция "1");
• Ничего не делать (опция «2»);

Итак, в основном у вас есть 3 ^ 8 возможных решений; просто попробуйте их все.

Это код PHP, но он включает в себя преобразование чисел в другие базы, что 8-летний мальчик, вероятно, не поймет быстро Может быть, вы можете найти поворот для этого:

<?php

$limit = pow(3, 8);
for($op = 0; $op < $limit; $op++){
  // Get this operation.
  $op_base3 = base_convert($op, 10, 3);

  // Fill leading 0's.
  $op_base3 = str_pad($op_base3, 8, "0", STR_PAD_LEFT);

  // Here you get something like 00212120, which would say:
  // 1[+]2[+]3[nothing]4[-]5[nothing]6[-]7[nothing]8[+]9
  // That's: 1+2+34-56-78+9

  // Compute and if result's correct, output solution.
}

?>

Answer 4

Конечно, это можно решить с помощью простой итерации. Вам нужно только преобразовать строку в стек.

Answer 5

Это можно сделать итеративно, но не так просто, как это. Что еще более важно, вы собираетесь использовать это как возможность научить своего сына сложности алгоритма?

Answer 6

Учитывая ограниченную глубину рекурсии, массив может использоваться как стек.