2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Простая численная задача, но что за ней?
Сообщение28.12.2022, 14:13 


17/02/15
71
Имеется простая задача

Дано целое число $n$. Выведите следующее за ним четное число.

Решение:
$n=int(input())
print(2(n//2)+2)$

Вопрос: какая наука стоит за этим? Можно быстро догадаться, но почему это работает? Предполагаю, что эта задача является входом в какую-то интересную часть математики (дискретной математики). Получается, что это в этой формуле специальная функция на множестве действительных чисел. Так как все числа с плавающей запятой из интервала [n,n+2) однозначно переходят в одну точку-целое от деления на 2, а потом эта точка скачком попадает в "следующее четное". Что это за функция?

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 14:25 
Заслуженный участник
Аватара пользователя


16/07/14
8346
Цюрих
Для кода есть отдельный тег syntax:
Используется синтаксис Python
n = int(input())
print(2 * (n // 2) + 2)

(предполагаю что вы потеряли звездочку, а не используете странный язык, в котором 2 является функцией)

Не очень понятно, в чем вопрос, и почему вы говорите то о числах с плавающей запятой, то о целых.
Если вопрос, как это работает - то разберите для начала случай четного n, потом нечетного (учтите, что по спецификации (2 * k + 1) // 2 == k).
Если вопрос, как эта функция называется - вряд ли у неё есть общепринятое название, "наименьшее четное число, большее данного" для называния вполне сойдет.

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 14:37 


17/02/15
71
Это скорее математический вопрос. На вход поступает число в плавающей, после того, как взяли целое от деления любого числа (не важно какого) из [n,n+2), оно уже может быть описано единственным целым K, и следующий переход $2(K+1)$ - дает результат задачи, ближайшее четное.
Почему? Какая теория стоит за этой простой задачей? Тут можно находить аналогии с движением по графам. Имеется возможность числа из бесконечного множества однозначно перегонять в числа с требуемыми свойствами.

Тогда я задам вопрос, а какие еще задачи известны, которые используют похожие алгоритмы?
А также, какая теорема стоит за этой простой формулой?

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 14:44 
Заслуженный участник
Аватара пользователя


16/07/14
8346
Цюрих
Да нет тут ничего глубокого, просто берем максимальное целое число, не превосходящее нашего (округляем вниз). При желании, конечно, можно накрутить умных слов, что множество целых чисел неограничено снизу и полно по Дедекинду (любое его непустое ограниченное сверху подмножество имеет точную верхнюю грань), поэтому функция "максимальное целое число, не превосходящее данного" корректно определена. Но это уже что-то в духе определения единицы по Бурбаки.

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:02 


17/02/15
71
Здесь нет округления. И получается не "максимальное целое не превосходящее нашего".

Например, любое из [10,12) переходит в 5, затем в 6, затем в 12. То есть имеется отображение [10,12) в {12} (а в промежутке можно построить еще два отображения из [10,12) в фиксированные 5 и 6, имеющие свои свои свойства, пусть на данном этапе рассмотрения не ясные.)

Любое из [12,14) переходит в 6, затем в 7, затем в 14. То есть имеется отображение [12,14) в {14}.
Любой элемент множества [n,n+2) дает одно значение функции.
Это очень полезное свойство функции. Вот я и спрашиваю, есть еще такие функции с такими свойствами, переводящие любой из множества в фиксированную точку, и как и где они используются?

Есть математика на остатках от деления, а здесь математика на целых от деления! Кто знает, что за область?

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:06 


05/09/16
11466
A.M.V. в сообщении #1575323 писал(а):
Дано целое число $n$. Выведите следующее за ним четное число.

Решение:
$n=int(input())
print(2(n//2)+2)$

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

Почему действительных если дано целое $n$?
Я бы писал так (синтаксис PARI/GP)
Код:
m(n)=n+2-n%2

Это же будет работать и для "Дано целое число $n$. Выведите следующее за ним число, делящееся на k", в таком виде:
Код:
m(n,k)=n+k-n%k

Тут процент означает остаток от деления того что слева на то что справа. (a%b это навроде a mod b). Будет работать и с отрицтельными n, по крайней мере в PARI/GP
А ещё, остаток от деления на 2 это младший бит в двоичной записи числа, можно и так запрограммировать.

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:14 
Заслуженный участник
Аватара пользователя


16/07/14
8346
Цюрих
A.M.V. в сообщении #1575330 писал(а):
Здесь нет округления
Есть. Прочитайте, что делает //.
A.M.V. в сообщении #1575330 писал(а):
Любое из [12,14) переходит в 6, затем в 7, затем в 14.
В приведенной вами записи - в 6, потом в 12, потом в 14. Чтобы было в 6, 7 и 14 должно быть 2 * (n // 2 + 1).
A.M.V. в сообщении #1575330 писал(а):
Вот я и спрашиваю, есть еще такие функции с такими свойствами, переводящие любой из множества в фиксированную точку, и как и где они используются?
Да сколько угодно. Берете множество, берете фиксированную точку, и вот вам функция.

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:20 


05/09/16
11466
A.M.V. в сообщении #1575330 писал(а):
Вот я и спрашиваю, есть еще такие функции с такими свойствами, переводящие любой из множества в фиксированную точку, и как и где они используются?

Ну есть функция "целая часть" $f(x)=\lfloor x \rfloor$ например... Собсно формула с ней для вашей задачи "следующее за $n$ четное число" будет $f(n)=2\lfloor \frac n2 \rfloor +2$

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:23 


17/02/15
71
wrest в сообщении #1575335 писал(а):
A.M.V. в сообщении #1575330 писал(а):
Вот я и спрашиваю, есть еще такие функции с такими свойствами, переводящие любой из множества в фиксированную точку, и как и где они используются?

Ну есть функция "целая часть" $f(x)=\lfloor x \rfloor$ например... Собсно формула с ней для вашей задачи "следующее за $n$ четное число" будет $f(n)=2\lfloor n/2 \rfloor +2$


Да, согласна. А следующие уровни математических надстроек над этой функцией?

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:27 


05/09/16
11466
A.M.V. в сообщении #1575336 писал(а):
Да, согласна. А следующие уровни математических надстроек над этой функцией?

"следующее за действительным числом $n$ целое число, делящееся на натуральное число $k$ без остатка" равно значению функции $f(n,k)=k(\lfloor \frac nk \rfloor+1)$
"следующее за" = "наименьшее, большее чем"

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 15:59 


17/02/15
71
wrest в сообщении #1575337 писал(а):
A.M.V. в сообщении #1575336 писал(а):
Да, согласна. А следующие уровни математических надстроек над этой функцией?

"следующее за действительным числом $n$ целое число, делящееся на натуральное число $k$ без остатка" равно значению функции $f(n,k)=k(\lfloor \frac nk \rfloor+1)$
"следующее за" = "наименьшее, большее чем"


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

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение28.12.2022, 16:32 


05/09/16
11466
A.M.V. в сообщении #1575343 писал(а):
В какой литературе об этом можно прочесть? Не прямо о том, что уже понятно,и здесь прозвучало, а следующие уровни обобщений. Как это называется, черт возьми?

Я не понимаю ваш вопрос, извините. Бывают, например "кусочно-заданные" функции, такие как "кусочно-линейные" или "кусочно-постоянные" (но не только они).
Вот кусочно-постоянные перескакивают в конечное/счетное количество значений. Функция "целая часть вещественного числа" $f(x)=\lfloor x \rfloor$ как раз такая -- кусочно-постоянная функция. Функция "модуль вещественного числа" $f(x)=|x|$ -- кусочно-линейная. Или вот такая $f(x)=x\lfloor x \rfloor$ тоже кусочно-линейная.

 Профиль  
                  
 
 Re: Простая численная задача, но что за ней?
Сообщение29.12.2022, 08:27 
Аватара пользователя


28/10/21
99
A.M.V. в сообщении #1575323 писал(а):
Дано целое число $n$. Выведите следующее за ним четное число.

Решение:
$n=int(input())
print(2(n//2)+2)$

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


Решение просто собирается из готовых кусочков.

Например, вариант рассуждений 1:

1. Выровняем наше число вниз на границу, кратную 2
2. Прибавим к нему 2

Шаг 1 (выравнивание вниз) реализуется как
1.1. Разделим наше число на 2 с округлением вниз
1.2. Умножим результат на 2

Целочисленное деление с округлением вниз языки программирования обычно предоставляют сразу "из коробки". В вашем случае это именно //. В результате сразу получаем именно приведенную вами формулу

Используется синтаксис Python
print(n // 2 * 2 + 2)


Вариант рассуждений 2:

1. Увеличим наше число на 1
2. Выровняем его вверх на границу, кратную 2.

Шаг 2 (выравнивание вверх) реализуется как
2.1. Разделим число на 2 с округлением вверх
2.2. Умножим результат на 2

Шаг 2.1 (деление с округлением вверх) реализуется как
2.1.1. Прибавим к числу 1
2.1.2. Разделим число на 2 с округлением вниз

Целочисленное деление с округлением вниз, еще раз, языки программирования обычно предоставляют сразу "из коробки".

Собираем все вместе и получаем

Используется синтаксис Python
print((n + 1 + 1) // 2 * 2)


Несложно показать, что эта формула эквивалентна вашей.

Вариант рассуждений 3:

1. Увеличим наше число на 2
2. Выровняем его вниз на границу, кратную 2.

Это тоже даст нам вариант

Используется синтаксис Python
print((n + 2) // 2 * 2)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group