Сортировка дробных чисел

@Mikstereo · Регистрация: 05.11.2018

Студворк — интернет-сервис помощи студентам

Задача:
Жил себе мирно в лесу мальчик Вася, но беды приходят неожиданно. С горы падают камни. Изначально Василий находится на интервале [0, 1]. Потом упадут n камней, а Вася будет убегать от камней. Камни последовательно пронумерованы от 1 до n в порядке их падения.
Камни всегда падают точно в центр интервала Василия. Когда Вася занимает интервал [k - d, k + d] и камень падает в точку k, мальчик бежит налево или направо. Если он убежит налево, его новый интервал будет [k - d, k]. Если побежит направо, его новый интервал будет [k, k + d].
Вам дана строка s длины n. В строке s i-ый символ — это либо «l», либо «r», то есть, когда падает i-ый камень, Василий побежит налево или направо, соответственно. Найдите последовательность номеров камней слева направо после того, как упадут все n камней.
Решение задачи ясно как день, опишу его и проблему с сортировкой дробных чисел:
l,r- левая и правая границы интервала(изначально они равны 0 и 1 соответственно)
Идем по всем символам строки, если i-й символ это 'l' то k=(l+r)/2; d=(r-k); l=k-d; r=k; и в словарь(например) запишем пару (i+1,k),где i+1 будет номером камня,k-его координата
если i-й символ это 'r' то k=(l+r)/2; d=(r-k); l=k; r=k+d; и в словарь запишем пару (i+1,k)
В конце надо отсортировать все пары по k, и после вывести все номера камней.
Проблема в том, что для строк длины больше 300(примерно) значения k в словаре выходят с огромным количеством знаков после запятой, а тип float столько знаков не может хранить, и отсекает большую часть, в итоге чего сортировка выходит неверная.
Возможно ли реализовать такую сортировку, если вместо float использовать тип Decimal(там вроде как почти не ограничено кол-во знаков), и если да, то как?

@Arsegg · 13.10.2019, 21:54

fractions

Python
1
2
3
4
5
6
7
8
9
In [1]: from fractions import Fraction
 
In [2]: sorted((Fraction(1, 2), Fraction(1, 4), Fraction(1, 3), Fraction(2, 3), Fraction(3, 4),))
Out[2]:
[Fraction(1, 4),
 Fraction(1, 3),
 Fraction(1, 2),
 Fraction(2, 3),
 Fraction(3, 4)]

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@Mikstereo 98 / 36 / 18 Регистрация: 05.11.2018 Сообщений: 231

	Сортировка дробных чисел 12.10.2019, 22:11. Показов 4285. Ответов 1 Метки python compiler (Все метки) Задача: Жил себе мирно в лесу мальчик Вася, но беды приходят неожиданно. С горы падают камни. Изначально Василий находится на интервале [0, 1]. Потом упадут n камней, а Вася будет убегать от камней. Камни последовательно пронумерованы от 1 до n в порядке их падения. Камни всегда падают точно в центр интервала Василия. Когда Вася занимает интервал [k - d, k + d] и камень падает в точку k, мальчик бежит налево или направо. Если он убежит налево, его новый интервал будет [k - d, k]. Если побежит направо, его новый интервал будет [k, k + d]. Вам дана строка s длины n. В строке s i-ый символ — это либо «l», либо «r», то есть, когда падает i-ый камень, Василий побежит налево или направо, соответственно. Найдите последовательность номеров камней слева направо после того, как упадут все n камней. Решение задачи ясно как день, опишу его и проблему с сортировкой дробных чисел: l,r- левая и правая границы интервала(изначально они равны 0 и 1 соответственно) Идем по всем символам строки, если i-й символ это 'l' то k=(l+r)/2; d=(r-k); l=k-d; r=k; и в словарь(например) запишем пару (i+1,k),где i+1 будет номером камня,k-его координата если i-й символ это 'r' то k=(l+r)/2; d=(r-k); l=k; r=k+d; и в словарь запишем пару (i+1,k) В конце надо отсортировать все пары по k, и после вывести все номера камней. Проблема в том, что для строк длины больше 300(примерно) значения k в словаре выходят с огромным количеством знаков после запятой, а тип float столько знаков не может хранить, и отсекает большую часть, в итоге чего сортировка выходит неверная. Возможно ли реализовать такую сортировку, если вместо float использовать тип Decimal(там вроде как почти не ограничено кол-во знаков), и если да, то как? 0

Опции темы