2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Простенькая задачка на четность
Сообщение08.06.2017, 18:16 
Аватара пользователя


15/11/15
1297
Москва
Задача придумана мной только что. Очень вероятно, что она не новая.

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

 Профиль  
                  
 
 Re: Простенькая задачка на четность
Сообщение08.06.2017, 18:25 
Заслуженный участник


20/08/14
11867
Россия, Москва
Чтобы переставить фишки в обратном порядке первая должна попасть на последнее место. А она всегда прыгает лишь по нечётным числам (если нумерация позиций начинается с 1). Значит при чётном количестве фишек желаемая перестановка невозможна. Возможность перестановки при нечётном количестве фишек доказывается отдельно. ;-)

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


23/07/08
10910
Crna Gora
Dmitriy40 в сообщении #1223394 писал(а):
Возможность перестановки при нечётном количестве фишек доказывается отдельно.
Вспомнив о сортировке методом пузырька, отправим на своё новое место сначала первую фишку, потом третью и т.д. Аналогично с чётными.

 Профиль  
                  
 
 Re: Простенькая задачка на четность
Сообщение09.06.2017, 01:02 
Заслуженный участник


20/08/14
11867
Россия, Москва
svv
Да это в общем очевидно, я думал про индукцию (переставляем первые две фишки, потом уменьшаем размер задачи на 2, повторяем, задача длины 3 решается тривиально), но это фактически тот же пузырёк. Собственно это оставил недоказанным специально, ведь спрашивалось в основном про чётное количество. :-)

 Профиль  
                  
 
 Re: Простенькая задачка на четность
Сообщение09.06.2017, 11:53 
Аватара пользователя


15/11/15
1297
Москва
Про пузырек я ничего не слышал, но свое доказательство для нечетного количества фишек я провел по индукции, так, как сказал Dmitriy40.

 Профиль  
                  
 
 Re: Простенькая задачка на четность
Сообщение09.06.2017, 12:27 
Заслуженный участник


20/08/14
11867
Россия, Москва
Про сортировку пузырьком. Это один из простейших методов сортировки массива чисел, известен давно, "проходится" кажется даже в школьном курсе информатики (правда без доказательств и математики). Один из самых неэффективных. Зато прост в понимании и реализации. Я бы сказал обязателен к изучению всем интересующимся программированием как один из базовых алгоритмов обработки данных.

 Профиль  
                  
 
 Re: Простенькая задачка на четность
Сообщение09.06.2017, 12:32 
Аватара пользователя


15/11/15
1297
Москва
Dmitriy40 в сообщении #1223584 писал(а):
неэффективных

Во вычислительной сложности?

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


23/07/08
10910
Crna Gora
Да. Элементарная операция очень проста (сравнить два соседних элемента и поменять их местами, если этого требует критерий сортировки), но этих операций, по современным меркам, требуется очень много: $\frac{N(N-1)}{2}$, независимо от начальной расстановки. Последнее очень досадно: даже если элементы уже стоят в правильном порядке, тупой метод всё равно сделает $\frac{N(N-1)}{2}$ сравнений, ничего не меняя после каждого сравнения.

 Профиль  
                  
 
 Re: Простенькая задачка на четность
Сообщение09.06.2017, 16:26 
Заслуженный участник


20/08/14
11867
Россия, Москва
svv в сообщении #1223598 писал(а):
Последнее очень досадно
Как раз нет, это легко обходится простыми эвристиками, незначительно усложняющими код для больших $N$. А для малых $N$ и эвристики не нужны, время работы и так мало (в абсолютном выражении).

(Замечания о пузырьке)

Rusit8800
Основная засада (неэффективность) в росте вычислительной сложности (времени работы) как $O(N^2)$, что для средних и больших $N$ многократно превышает другие более оптимальные методы (с сложностью $O(N \ln N)$). Обычно для массивов до тысяч элементов ещё можно применять, а для десятков тысяч и более - уже слишком медленно (по сравнению с другими более сложными методами). Для массивов в миллионы элементов разница во много раз будет видна невооруженным глазом (грубо - доли секунды или минуты работы), ну а сортировку миллиардного массива можно и несколько лет ждать против минуты для других методов. Базы данных же встречаются и заметно поболее размером.
Если мне будет позволено, приведу такую аналогию: возведение в натуральную степень можно делать последовательными умножениями или использовать логарифмы и получить ответ намного быстрее. Что не отменяет знания базовых вещей типа последовательных умножений (aka сортировка пузырьком).
Простите за ликбез. :-)

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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