Маленькие локальные программы на JS, серия 1

Стр.02 Задача 1. Для заданного числа N найти количество способов его записи в виде суммы положительных чисел.

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

Калькулятор - тренажер для расчета.

Расчет количества способов записи

Число:

Рассчитать

Результат будет здесь:

---

Описание работы алгоритма

*** 1 ***
Получаем число над которым будем работать из формы HTML:
let task1_1 = jQuery('#task1_1').val();

*** 2 ***
Допустим, ввели число 4.
Разбиваем это число на массив temp_ar(4)[1,1,1,1]
Размерность массива temp_ar соответствует числу task1_1, все варианты разложения которого мы ищем.

*** 3 ***
Делаем цикл с условием while(temp_ar[0] < task1_1)
Т.е. проходим по циклу до тех пор, пока нулевой элемент массива temp_ar[0] не станет равным числу над которым работаем.
При этом значение числа task1_1 остается неизменным, а над массивом temp_ar проводим манипуляции, описанные далее

*** 4 ***
Проходим по массиву temp_ar от нулевого элемента до предпоследнего. При этом к минимальному элементу в текущем состоянии массива прибавляем 1
temp_ar[min1index] += 1;

*** 5 ***
При этом мы удаляем следующий элемент:
temp_ar.splice(min1index+1);

*** 6 ***
Дополняем массив необходимым количеством единиц на конце:
temp_ar.push(1);
Делаем это так, чтобы в любом текущем варианте состояния массива temp_ar, сумма его элементов всегда должна быть равна task1_1 (т.е. 4 в нашем примере)

*** 7 ***
После завершения основного цикла, временный массив temp_ar будет содержать единственный элемент, равный по значению числу task1_1
temp_ar: [4]

Всего для данного тестового примера получаем 5 вариантов:
1) 1+1+1+1=4
2) 2+1+1=4
3) 2+2=4
4) 3+1=4
5) 4=4

---

В данной реализации допустимый диапазон вводимого значения: от 1 до 24.

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

Имеете полное право и возможность.

При желании вы можете скачать програмы js и стили.

Для справки.

• програмы js здесь
• стили здесь

Оценка временной сложности этой задачи: O(n²)

Стр.03 Задача 2. Найти наибольшее число в массиве, являющееся полным квадратом.

Задача 2. Найти наибольшее число в массиве, являющееся полным квадратом (квадратом некоторого целого числа).

Калькулятор - тренажер для расчета.

Форма ввода чисел для формирования массива

Число 1:
Число 2:
Число 3:
Число 4:
Число 5:

Запуск поиска

Результат будет здесь:

---

Описание работы алгоритма

*** 1 ***
Вводим несколько чисел из формы HTML, в нашем примере: 49, 64, 77, 25, 99.
Формируем массив:
temp_ar = [49,64,77,25,99];
Или мы можем создать массив, напрямую в программе js, минуя форму ввода:
temp_ar = [0,2,4,16,25,64,99,49,13,155];

Далее будем считать, что работаем с массивом:
temp_ar = [49,64,77,25,99];

*** 2 ***
Проходим циклом по этому массиву от нулевого элемента до последнего:
for (let x = 0; x < temp_ar.length; x++)
При проходе выполняем пункт 3.

*** 3 ***
Определяем, является ли текущий элемент полным квадратом с помощью специальной функции: is_int_cur_kv_fun(temp_ar[x])
Если текущий элемент является полным квадратом, выполняем пункт 4.

*** 4 ***
Проверяем, является ли текущий элемент большим по значению, чем max_int (изначально let max_int = null;)
if (temp_ar[x]>max_int)
Если больше, то фиксируем:
max_int = temp_ar[x];

*** 5 ***
Для данного набора чисел получаем результат 64, с такой расшифровкой:
1) 49 КВАДРАТ
2) 64 КВАДРАТ * Максимальный *
3) 77 НЕ квадрат
4) 25 КВАДРАТ
5) 99 НЕ квадрат

---

В данной реализации допустимый диапазон вводимых значений: от 0 до 100.

В этой версии мы просто берем из HTML формы данные для массива.

Но вы можете создать массив прямо в программе, например:
temp_ar = [0,2,4,16,25,64,99,49,13,155];

Ограничение на 5 элементов связано только с формой HTML. В самой программе ограничений нет, можете поэспериментировать с большими массивами.

Ссылки на программы js и стили см выше, к задаче 1.

Оценка временной сложности этой задачи: O(n)

Стр.04 Задача 3. Факториал натурального числа.

Задача 3. Факториал натурального числа.

Факториал, - это число, умноженное на "себя минус один", затем на "себя минус два", и так далее до 1. Факториал n обозначается как n!

Калькулятор - тренажер для расчета.

Форма ввода числа для расчета факториала

Число:

Запуск расчета факториала

Результат будет здесь:

---

Описание работы алгоритма

*** 1 ***
Вводим в форму целое число, например: 5

*** 2 ***
Получаем результат: 120
5! = 120

*** 3 ***
Функция:

function fact_fun(n) {
  // делаем рекурсию только если n больше 1
  if (n > 1) {
    return n * fact_fun(n - 1);
  }
  else {
    return 1;
  };
//
}; // function fact_fun(n) {
//

*** 4 ***
В этой функции fact_fun интересно то, что она вызывает саму себя. Такой прием, когда функция вызывает сама себя, называется Рекурсия.

Чтобы стало совсем все понятно, попробуем визуализировать эту абстракцию с помощью картинки.

---

Ссылки на программы js и стили см выше, к задаче 1.

Оценка временной сложности этой задачи: O(n)