Задание по рекурсии PHP

174

25 июня 2021, 00:40

Дана последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4,… По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом.

Я решил это так

function recursion($k, $i = 0) {
    if($k === $i) { return; }
    echo (string)$k . "\n";
    recursion($k, ++$i);
}
recursion(4);

Подскажите, это правильное решение? Или по условию не так надо

Answer 1

Какая рекурсия? Вы о чем? Чистая математика. Для числа k в последовательности будет k * (k + 1) / 2 членов

$n = 10;
$cur = 0;
for ($i = 1; $i <= $n; $i++) {
    if ($i > $cur * ($cur + 1) / 2)
        $cur++;
    echo $cur . ' ';
}

SandBox

Update

Вариант с рекурсией

$n = 10;
function func($cur, $idx, $cnt) {
    if ($idx === 0)
        return;
    if ($cnt === 0) {
        $cur++;
        $cnt = $cur;
    }
    echo $cur . ' ';
    func($cur, $idx - 1, $cnt - 1);
}
func(1, $n, 1);

SandBox

Функция func принимает три параметра

$cur - текущее выводимое число
$idx - сколько осталось вывести членов
$cnt - сколько осталось вывести текущее число

Answer 2

Чистая математика.

На практике стоит избавиться от умножение в цикле:

function f (int $n) : array {
  $a = [];
  for (
    $i = 0, $j = 1, $k = 0;
    $i < $n;
    $i++, $k = ($k == 0) ? $j++ : $k - 1
  )
    $a [] = $j;
  return $a;
}