Array  break  case  catch  const  continue  default  Date  do Error  else  Function  false  finally  for

function  if  in  instanceof  Infinity  Math  NaN  Number  new  null  Object  Promise  prototype  RegExp

return  String  switch  this  then  throw  try  true  undefined  var  with  while
	
alert(s)
appendChild(tagName)
fillRect()
pow(base, n)
sin(radians)
cos(radians)
random()
isNaN()
test()
sqrt(n)
prompt(s)
parseInt(s) parseFloat(s)
floor(f) 
ceil(f)
charAt(n)
indexOf(substring, offset)
substring(start, end)
replace(pattern, replacement)
toLowerCase(s)
toUpperCase(s)
abs(n)
splice(start, length, newItem1, newItem2, ...)
split(pattern, limit)
toString()
createElement(tagName)

getElementById(id)

getContext(contextType)

removeChild(domElement)

strokeText(text, x, y)

fillText(text, x, y)

measureText(text)

setItem(key, value)

join(delimeter)

round(floatNumber)
	

Задачи на функции

В текстах заданий могут упоминаться "процедуры". Это связанно с тем, что задачки задумывались для языка программирования Паскаль, в нем функция, не возвращающая значение вызывающей программе называется процедурой. В JavaScript такого понятия нет, если нам не надо возвращать значения из функции, мы его просто не возвращаем.

Первая задача

Составить функцию для нахождения наименьшего нечетного натурального делителя k (k != 1) любого заданного натурального числа n.

function example_6_1() {
	var n = parseInt( readln('Введите целое число N') ), r;
	if (isNaN(n)) {
		writeln('Недопустимое значение');
		return;
	}
	
	function getMinimumDivider(n) {
		var i, result;
		for (i = 3; i < n; i = i + 2) {
			result = n / i;
			if (result == Math.floor(n / i)) {
				return i;
			}
		}
		return false;
	}
	
	if ( r = getMinimumDivider(n) ) {
		writeln("Наименьший нечетный делитель числа " + n + " равен " + r);
	} else {
		writeln("У числа " + n + " не существует нечетного делителя в пределах (1," + n + ")");
	}
}

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

Однако логику нахождения наименьшего нечетного делителя я перенес в функцию getMinimumDivider. Алгоритм в функции проще не придумаешь: в цикле for от 3 до n - 1 включительно делю заданное число n на i (думаю ни для кого уже не новость, что i принимает значения от 3 до n - 1, однако обратите внимание, что в данном цикле i изменяется с шагом 2, чтобы все числа были нечетными (мы ищем нечетный делитель) ). Как только частное n / i становится равно своему же округлению вниз (floor округляет вниз, то есть Math.floor(3.9) вернет 3), считаем, что мы нашли то, что искали. Возвращаем i, используя return. Если найти наименьший делитель не удалось (все попытки разделить n на i отдают дробный результат), возвращаем из функции false.

Далее, я вызываю функцию getMinimumDivider и проверяю , не равно ли возвращенное ей значение false. Фрагмент кода

if ( r = getMinimumDivider(n) ) {...

работает так же как сработал бы код

r = getMinimumDivider(n);

if (r) {...

Напомню, что при передаче в круглые скобки после if переменной if работает так: если переменная равна false, null, 0, NaN, undefined или пустой строке '', то вход в блок в фигурных скобках сразу после if(...) не произойдет.

То есть блок

if ( r = getMinimumDivider(n) ) {...

работает так: вычисляется getMinimumDivider(n), вычисленное значение помещается в r, значение r обрабатывается условным оператором if.

Вторая задача

Дано четное число n > 2. Проверить для него гипотезу Гольдбаха: каждое четное n представляется в виде суммы двух простых чисел.

function example_6_2() {
	"use strict"
	var n = parseInt( readln('Введите четное целое число N > 2') ),
		inputErrorMessage = 'Было введено недопустимое значение, выход',
		r, a, b;
	if (isNaN(n)) {
		writeln(inputErrorMessage);
		return;
	}
	r = ( Math.floor(n / 2) === (n / 2));//n - четное число?
	if (!r) {
		writeln(inputErrorMessage);
		return;
	}
	if (n < 4 ) {
		writeln(inputErrorMessage);
		return;
	}
	//n - простое число?
	function isSimpleNumber(n) {
		var x = 2, ctrl1, ctrl2;
		for (x; x < n; x = x + 1) {
			ctrl1 = n / x;
			ctrl2 = Math.floor(ctrl1);
			if (ctrl1 == ctrl2) {
				return false;
			}
		}
		return true;
	}
	//Получить следующее простое, большее чем аргумент. Аргумент - простое число.
	function getNextSimpleNumber(n) {
		var firstSimpleNumbers = [2,3,5,7,11,13,17,19,23,29,31,37,41], i, D, x;
		if (n < 41) {
			for (i = 0; i < firstSimpleNumbers.length; i++) {
				if (firstSimpleNumbers[i] > n) {
					return firstSimpleNumbers[i];
				}
			}
		} else if (n > 41 && n < 1601 ) {
			D = 1 - 4*(41 - n); //Дискриминант
			x = (-1 + Math.sqrt(D)) / 2;
			n = x * x + x + 41;
			return n;
		} else {
			n += 2;
			if (n / 2 == Math.ceil( n / 2)) { //вдруг было передано четное n
				n += 1;
			}
			while (true) {
				if (isSimpleNumber(n)) {
					return n;
				}
				n += 2;
			}
		}
	}
	b = 2;
	a = n - b;
	while (!(isSimpleNumber(a) && isSimpleNumber(b)) ) {//пока a и b не простые числа
		b = getNextSimpleNumber(b);
		if (b > n) {
			writeln("Не удалось найти два простых слагаемых для n = " + n);
			return;
		}
		a = n - b;
	}
	writeln(n + " состоит из двух простых слагаемых " + a + " и " + b);
}

Для решения задачи мне понадобится функция, определяющая, простое ли число n. Я назвал её isSimpleNumber. Также понятно, что недостаточно вычесть из четного n первое попавшееся простое число, чтобы осталось еще одно простое. Об этом говорит тот факт, что вычтя из шести (четное число) двойку (простое число) я получу непростое число четыре. Значит, мне нужна функция, которая возвращает очередное простое число. Я назову ее getNextSimpleNumber. Я не математик, но я могу увеличивать каждое простое число большее двойки на два и проверять, а не получилось ли простое. Однако, решая эти примеры я познакомился с формулой F = x*x + x + 41 котрая дает простые числа при x принадлежащем интервалу [0, 40). Простых чисел от двух до сорока одного немного, поэтому я выписал их в массив. Если функция getNextSimpleNumber получает аргумент меньше 41, она просто проходит по этому массиву, иначе хочется использовать формулу. Но я могу это сделать когда n не больше чем значение F(39) = 1601, так как F(40) дает непростое число. 40 * 40 + 40 + 41 = 1681. Также, мне необходимо найти x чтобы получить F(x + 1). Значит, мне нужна еще одна функция, решающая квадратное уравнение. Впрочем, здесь частный случай, когда коэффициенты квадратного уравнения a и b равны единицам, c всегда равно 41 - n, и я жду корень больший 0. Это упрощает задачу и я не стал выносить ее в отдельную функцию. В случае, когда n >= 1601 я начинаю увеличивать аргумент на два и проверять, а не получилось ли простое число.

После того, как обе вспомогательные функции реализованы, поиск простых чисел , сумма которых дает заданное n становится простым. Я отнимаю от n наименьшее простое число 2 и запускаю цикл, который выполняется до тех пор, пока оба слагаемых не станут простыми числами. Если в процессе очередное простое число оказалось больше, чем n я вывожу сообщение, что для заданного n не удалось найти два простых слагаемых.

Рекурсия, поведение аргументов функции, понятие о тестировании кода

Есть задача: дано n различных натуральных чисел. Напечатать все перестановки этих чисел.

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

Пусть есть функция, которая принимает в качестве аргументов массив, объект, число и строку.

function argumentsBehaviorExample () {
	"use strict"
	var my_array = [1, 2, 3],
		my_object = {x:1, y:2},
		n = new Number(5),
		s = new String('Hello');
	function F(array, object, number, string) {
		array[0] = 99;
		object.x = 99;
		number = 99;
		string = '99';
	}
	writeln("my_array[0] = " + my_array[0] + ", my_object.x = " + my_object.x + ", n = " + n + ", s = " + s);
	F(my_array, my_object, n, s);
	writeln("my_array[0] = " + my_array[0] + ", my_object.x = " + my_object.x + ", n = " + n + ", s = " + s);
}

Я специально использовал при определении (инициализации) переменных n и s конструкторы, чтобы убедится, что в данном случае их использование или не использование не играет никакой роли (то есть пример работает так же, если заменить n = new Number(5); на n = 5; и s = new String('Hello'); на s = 'Hello';). Мы видим, что после вызова функции F значения переменных массив и объект изменились, а значения переменных строка и число не изменилось. Это надо учитывать при передаче функции параметров при ее вызове.

Перейдем к рекурсии. При решении третьего примера по теме Циклы я уже описывал функцию вычисления факториала. Напомню свое решение:

function factorial(n) {
	n = parseInt(n);
	if (!n) {
		n = 0;
	}
	if (n < 2) {
		return 1;
	}
	var result = 1;
	for (var i = 1; i <= n; i++) {
		result = result * i;
	}
	return result;
}

Привожу аргумент к целому числу. Если это вдруг оказалось не число, принимаю его равным нулю. Если число меньше двух, возвращаю единицу, так как 0! равен 1. Далее от единицы до n включительно умножаю значение i на результат и запоминаю это произведение в результате. Результат возвращаю, это факториал числа n.

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

function recursiveFactorialExample() {
	"use strict"
	var n = parseInt( readln('Введите n') );
	if (isNaN(n)) {
		n = 0;
	}
	var f = recursiveFactorial(n);
	function recursiveFactorial(n) {
		if (isNaN(n)) {
			n = 0;
		}
		if (n < 2) {
			return 1;
		}
		return n * recursiveFactorial(n - 1);
	}
	writeln("Факториал " + n + " = "  + f);
}

Здесь я пользуюсь тем, что факториал любого числа n равен n умноженное на факториал n - 1. При этом факториал нуля равен 1, единицы соответственно тоже (1 * 0! = 1). Поэтому я внутри функции recursiveFactorial беру аргумент, и умножаю его на результат вызова функции recursiveFactorial которой передаю свой аргумент минус единица.

Функция, которая в процессе своей работы вызывает саму себя, называется рекурсивной.

Перейдем теперь к решению задачи (дано n различных натуральных чисел. Напечатать все перестановки этих чисел). Мое решение этой задачи вряд ли можно считать эталоном в смысле производительности алогритма, но зато оно мое собственное и ниже мы убедимся, что оно еще и верное.

Если вы будет вводить более 6 чисел на вход программы, лучше делайте это в браузере google chrome, так как интерпретатор JavaScript в нем самый быстрый. Firefox будет выдавать предупреждение каждые десять секунд о том что сценарий выполняется слишком долго, IE 9 "зависнет" и пока не прервете скрипт, не "отвиснет", opera 12.16 для Linux кстати отработала медленно, но верно, однако Opera 25.0 для windows зависла на 8 минут прежде чем выдать верный результат.

Очевидно, что наиболее простым представляется частный случай, когда n = 2 (n < 2 не рассматриваю, так как там переставлять нечего). В этом случае всего два варианта перестановки: исходный и отраженный. Имея понятие о рекурсивных функциях, довольно легко догадаться, что для любого n > 2 можно просто переставить два числа в исходном множестве, а потом передать полученное сочетание в рекурсивную функцию, которая сделает то же самое, но будет работать не со всеми элементами множества, а с правыми n - 1 элементами. Вот что я имею ввиду (красным обозначены элементы, которые будут переставлены):

Первый вызов функции

1,2,3,4, ...

Следующий вызов функции:

1,2,3,4, ...

Следующий вызов функции:

1,2,3,4, ...

Следующий вызов функции:

1,2,3,4, ...

И так далее, пока переставлять будет нечего. Остается вопросом, как именно переставлять элементы. Попробовав несколько способов я остановился на таком, при котором на место каждого элемента ставится правый от него, а на место крайнего правого ставится тот, что был первым слева до начала перестановки. Начну с реализации такой перестановки, без рекурсивных вызовов.

function combinations() {
	var s = String(readln("Введите несколько чисел разделяя их запятой")),
		array = s.split(","), i, ctrl;
	for (i = 0; i < array.length; i++) {
		ctrl = parseInt(array[i]);
		if (isNaN(ctrl) || ctrl != array[i]) {
			writeln("Недопустимые данные. Выход");
			return;
		}
	}
	function writeVariants(array, n) {
		if (!n) {
			n = 0;
		}
		var lim, i, j, b;
		lim = (array.length - n) * (array.length - n);
		for (i = 0, j = n; i < lim; i++, j++) {
			if (j == n) {
				b = array[j];
			}
			if (j == array.length - 1) {
				array[j] = b;
				writeln(array.toString());
				j = n - 1;
				continue;
			}
			array[j] = array[j + 1];
		}
	}
	writeln("Сочетания:");
	writeVariants(array);
}

В начале определения функции combinations происходит проверка корректности ввода. Если данные корректны, они помещаются в массив array. Затем следует определение функции writeVariants в которой и будет происходить вывод сочетаний. Так как в дальнейшем функция будет вызываться рекурсивно, я добавил второй аргумент n. В него будет передаваться смещение от начала массива. Элементы части массива от этого смещения и до конца будут перестанавливаться при вызове функции, но пока что я этого не далаю.

В функции writeVariants определен цикл, внутри которого происходит перестановка элементов. Чтобы сдвинуть все элементы массива влево, помещая вышедшей за пределы массива элемент в конец, нужно пройти по массиву из N элементов N*N раз. Как только индекс массива выходит за пределы длины массива, ему присваивается значение аргумента n. После каждого сдвига происходит вывод значений массива.

Далее я добавил рекурсивный вызов функции writeVariants. Алгоритм сработал, но вывел много дублей. Избежать их удалось добавив условие перед печатью элементов массива: выводим последнюю полученую в цикле последовательность только в том случае, если отступ n равен 0. В этом случае вложенный вызов writeVariants не выводит ту последовательность, которая пришла к нему на вход (а этого не надо делать, потому что мы ее уже напечатали перед вложенным вызовом).

function combinations() {
	var s = String(readln("Введите несколько чисел разделяя их запятой")),
		array = s.split(","), i, ctrl;
	for (i = 0; i < array.length; i++) {
		ctrl = parseInt(array[i]);
		if (isNaN(ctrl) || ctrl != array[i]) {
			writeln("Недопустимые данные. Выход");
			return;
		}
	}
	function writeVariants(array, n) {
		if (!n) {
			n = 0;
		}
		var lim, i, j, b;
		lim = (array.length - n) * (array.length - n);
		for (i = 0, j = n; i < lim; i++, j++) {
			if (j == n) {
				b = array[j];
			}
			if (j == array.length - 1) {
				array[j] = b;
				if (i < lim - 1 || n == 0) {
					writeln(array.toString());
				}
				writeVariants(array, n + 1);
				j = n - 1;
				continue;
			}
			array[j] = array[j + 1];
		}
	}
	writeln("Сочетания:");
	writeVariants(array);
}

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

Конечно нет. По хорошему я должен был бы математически доказать работоспособность алгоритма, но я не могу этого сделать. Но самое малое, что я должен сделать, это написать функцию тестирования. Модифицирую алгоритм writeVariants так, чтобы функция не просто выводила результаты, но и проверяла их на правильность. Сделать это в каждом конкретном случае легко, если знать, что количество перестановок N чисел равно N!.

function combinations() {
	"use strict"
	var s = String(readln("Введите несколько чисел разделяя их запятой")),
		array = s.split(","), i, ctrl;
	for (i = 0; i < array.length; i++) {
		ctrl = parseInt(array[i]);
		if (isNaN(ctrl) || ctrl != array[i]) {
			writeln("Недопустимые данные. Выход");
			return;
		}
	}
	function writeVariants(array, n, ctrlUnique, ctrlLength) {
		var lim, i, j, b, a;
		if (!n) {
			n = 0;
			ctrlUnique = {};
			ctrlLength = {val:0};
		}
		lim = (array.length - n) * (array.length - n);
		for (i = 0, j = n; i < lim; i++, j++) {
			if (j == n) {
				b = array[j];
			}
			if (j == array.length - 1) {
				array[j] = b;
				if (i < lim - 1 || n == 0) {
					a = array.toString();
					writeln(a);
					if (ctrlUnique[a] == 1) {
						throw new Error("Дубль в выводе!");
					}
					ctrlUnique[a] = 1;
					ctrlLength.val++;
				}
				writeVariants(array, n + 1, ctrlUnique, ctrlLength);
				j = n - 1;
				continue;
			}
			array[j] = array[j + 1];
		}
		if (n == 0) {
			if (ctrlLength.val != factorial(array.length)) {
				writeln("Неверный результат, количество перестановок не равно n! ");
				return;
			}
		}
	}
	function factorial(n) {
		n = parseInt(n);
		if (!n) {
			n = 0;
		}
		if (n < 2) {
			return 1;
		}
		var result = 1;
		for (var i = 1; i <= n; i++) {
			result = result * i;
		}
		return result;
	}
	writeln("Сочетания:");
	writeVariants(array);
}

Я добавил два аргумента функции writeVariants - объект в котором буду хранить уже найденные сочетания и объект, в котором буду хранить записанное число сочетаний. Всякий раз после того, как выведено очередное сочетание, в объект ctrlUnique добавляется поле с именем, равным строке, представляющей собой это сочетание. Но перед этим проверяет, нет ли уже в объекте поля с таким именем. Это позволяет контролировать дубли. Также при успешном добавлении увеличивается значение счетчика ctrlLength.val. После окончания вывода проверяется, равно ли значение счетчика факториалу длины исходного массива.

Тест на новые слова

  • Несохраненный_файл.js
Строка: 0, Символ: 0

  • {name}
  • У вас пока нет файлов
 

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

 

Правильно!

Не забывайте переодически проходить этот тест по мере чтения новых статей.

 

Ошибка!

 

Осталось: 0 сек.

Health:

Score:

 

Что значит:

 

 

 


Информация

Загрузите файл с исходным кодом программы на языке яваскрипт.

Файл должен содержать одну главную функцию, имя которой должно совпадать с именем файла.

Например, файл называется task1.js, имя главной функции должно быть task1.

Все остальные функции должны быть определены внутри главной.

*

Информация

Сохраняемый код должен содержать одну главную функцию.

Например:

function myFirstProgram() {
	//Тут все остальное, включая вспомогательные функции
}
					




Простой пароль
Пароли не совпадают