Комментарии 23
Интересно, а по правилам записи римских цифр это же число 3889 нельзя записать как MMMIXCM ?
Например, в Excel функция =roman() имеет необязательный аргумент «ленивости писаря» — рост значения соответствует более короткой записи. Однако именно для 3889 различий в написании нет. Судя по всему — потому, что нельзя отнимать несколько раз. Только единожды.
Нам в школе давали следующие правила:
I — это 1
X — это 10.
Прибавлять можно лишь три единички, а отнимать одну (степень числа 10) можно лишь для чисел с порядком, отличающимся не больше 1 (формулировка была не такой, разумеется, объяснение было длиннее, и далеко не все сразу сообразили, как правильно, и мини-контрольную по этим числам не все сдали успешно).
То есть, I отнимается только от V и Х, X отнимается лишь от L и C, и так далее.
И Ваша запись читается как "три тысячи девять девятьсот".
I — это 1
X — это 10.
Прибавлять можно лишь три единички, а отнимать одну (степень числа 10) можно лишь для чисел с порядком, отличающимся не больше 1 (формулировка была не такой, разумеется, объяснение было длиннее, и далеко не все сразу сообразили, как правильно, и мини-контрольную по этим числам не все сдали успешно).
То есть, I отнимается только от V и Х, X отнимается лишь от L и C, и так далее.
И Ваша запись читается как "три тысячи девять девятьсот".
Однозначного стандарта нет, но, вроде бы, "IXCM" — не допустимая форма. Вычитать можно только однородные строки, так сказать.
А я вот прочитав начало статьи просто записал самое длинное римское число, и, вы не поверите, получил MMMDCCCLXXXIX, которое внезапно оказалось простым. Это я к чему — не всегда, чтобы решить задачу, нужно писать скрипт. Иногда просто везёт)
Апдейт. Ну да, я ошибся. Самое длинное MMMDCCCLXXXVIII.
Вот так иногда неправильные мысли приводят к правильному решению. Скрипт всё же писать надо
Апдейт. Ну да, я ошибся. Самое длинное MMMDCCCLXXXVIII.
Вот так иногда неправильные мысли приводят к правильному решению. Скрипт всё же писать надо
Мне кажется что 3989 не попало в скрипт! Может всё таки гугл прав?
Проверено, таки 3989 (MMMCMLXXXIX) — примерно 135 пикселей, а 3889 (MMMDCCCLXXXIX) — 153.
Для проверки на PHP: http://pastebin.com/EXHMDYQ6
Вывод: Widest prime less than 4000 when written as a Roman numeral in Times New Roman: 3889 (MMMDCCCLXXXIX)
Для проверки на PHP: http://pastebin.com/EXHMDYQ6
Вывод: Widest prime less than 4000 when written as a Roman numeral in Times New Roman: 3889 (MMMDCCCLXXXIX)
Есть повод спросить у гугла
Какая-то неленивая лень. Хотя, если он нагуглил весь ряд простых чисел сразу, то понятно.
Но ведь тут и без скрипта длина вычисляется просто:
В числе должно быть как можно больше разрядов задействовано, ведь больше разрядов — больше цифр, и, что более важно — длиннее запись.
Для последнего разряда наидлиннейшая запись — MMM. То есть, 3000.
Переходим к третьему разряду. Наибольшая длинна у числа 800 — DCCC.
Второй разряд. Разумеется, 80 — LXXX.
Четвёртый разряд — а давайте посмотрим, есть ли простые числа, которые начинаются на 388_?
3881 и 3889. Разумеется, запись IX длиннее I на целый X.
Даже если гуглить римские цифры и простые числа, то всё вычисление займёт минут 5, включая написание этого комментария.
Но ведь тут и без скрипта длина вычисляется просто:
В числе должно быть как можно больше разрядов задействовано, ведь больше разрядов — больше цифр, и, что более важно — длиннее запись.
Для последнего разряда наидлиннейшая запись — MMM. То есть, 3000.
Переходим к третьему разряду. Наибольшая длинна у числа 800 — DCCC.
Второй разряд. Разумеется, 80 — LXXX.
Четвёртый разряд — а давайте посмотрим, есть ли простые числа, которые начинаются на 388_?
3881 и 3889. Разумеется, запись IX длиннее I на целый X.
Даже если гуглить римские цифры и простые числа, то всё вычисление займёт минут 5, включая написание этого комментария.
У вас всё-таки жадный алгоритм получился.
Хотя в данном случае верный, но просто свезло. В последних разрядах могло оказаться всё не так очевидно.
Хотя в данном случае верный, но просто свезло. В последних разрядах могло оказаться всё не так очевидно.
Алгоритм? Это ход рассуждения в голове, которое занимает время, измеряемое секундами. Стопорится лишь на простых числах.
Если бы на 388Х не было простых чисел, то искали бы на 387Х.
Я лишь хотел показать, что автор, который поленился составлять алгоритм составления простых чисел, потому что торопился узнать ответ, в итоге проделал лишнюю работу (у него же с переводом в римские цифры был затык) и потратил кучу времени.
Если бы на 388Х не было простых чисел, то искали бы на 387Х.
Я лишь хотел показать, что автор, который поленился составлять алгоритм составления простых чисел, потому что торопился узнать ответ, в итоге проделал лишнюю работу (у него же с переводом в римские цифры был затык) и потратил кучу времени.
Почитайте на досуге: Жадный алгоритм
Теперь ясна природа минусов к комментарию.
Почему-то после прочтения книги "Приключения Пети Кука в Роботландии" (лет 20 назад) в качестве Исполнителя алгоритма я воспринимаю только машину, но никак не человека. Отсюда и моё некоторое недопонимание.
А вообще, читал уже ранее, что это за алгоритм такой.
Почему-то после прочтения книги "Приключения Пети Кука в Роботландии" (лет 20 назад) в качестве Исполнителя алгоритма я воспринимаю только машину, но никак не человека. Отсюда и моё некоторое недопонимание.
А вообще, читал уже ранее, что это за алгоритм такой.
Ну у вас с такими рассуждениями могло получится 3881 (допустим это простое число). А наидлинейшее число оставшееся незамеченным 3788 или 3878.
3881 — MMMDCCCLXXXI
3788 — MMMDCCLXXXXIII
(допустим, в качестве примера 3881, 3788 и 3878 — простые числа)
3881 — MMMDCCCLXXXI
3788 — MMMDCCLXXXXIII
(допустим, в качестве примера 3881, 3788 и 3878 — простые числа)
Странные у Вас допущения — чётное число не может быть простым, соответственно, варианты с VIII (как и с IV) на конце заведомо неверны, из-за чего не рассматриваются вовсе. Сравнивать надо VII и IX. III не берём, потому что оно меньше этих двух.
А теперь, когда мы знаем это, вспоминаем про тысячи, сотни и десятки.
MMM всегда длиннее остальных вариантов с тысячами, как и DCCC с сотнями.
И если бы 3889 не было бы простым, искали бы 3877 или 3879 в нагугленной таблице простых чисел.
А теперь, когда мы знаем это, вспоминаем про тысячи, сотни и десятки.
MMM всегда длиннее остальных вариантов с тысячами, как и DCCC с сотнями.
И если бы 3889 не было бы простым, искали бы 3877 или 3879 в нагугленной таблице простых чисел.
Ну хорошо, учтем четность, в любом случае по вашему алгоритму может получится число 3881, а незамеченным простым числом оказаться 3787.
3881 — MMMDCCCLXXXI
3787 — MMMDCCLXXXXII
3881 — MMMDCCCLXXXI
3787 — MMMDCCLXXXXII
Вернее вот так:
3881 — MMMDCCCLXXXI
3787 — MMMDCCLXXXVII
3881 — MMMDCCCLXXXI
3787 — MMMDCCLXXXVII
Вариант с 1 на конце ищется лишь после того, как не найдены варианты на 7 и 9 в предыдущем десятке, потому что I короче VII больше, чем на ширину одного числа. Аналогично можно и при откате назад на сотню\тысячу (и другие числа) рассуждать.
«Второй разряд. Разумеется, 80 — LXXX.»
Я, может, слепой? Не вижу в вашем алгоритме проверку чисел с 7 и 9. Вижу только конкретное утверждение, что именно восьмой десяток будет самым длинным при условии, что в нем есть простые числа.
Так что, сработал ваш «чудо-алгоритм» только на данном примере, что является всего лишь совпадением, тычком в небо(хоть и удачным).
Я, может, слепой? Не вижу в вашем алгоритме проверку чисел с 7 и 9. Вижу только конкретное утверждение, что именно восьмой десяток будет самым длинным при условии, что в нем есть простые числа.
Так что, сработал ваш «чудо-алгоритм» только на данном примере, что является всего лишь совпадением, тычком в небо(хоть и удачным).
Если бы чисел на восьмом десятке не было бы, был бы откат назад и поиск на седьмом.
Я не стал описывать универсальный алгоритм, просто описал ход своих мыслей конкретно для данной задачи, потому что у автора была цель — "хочу поскорее узнать ответ к задаче". Да, по сути — алгоритм, но изначальной задумкой не было написание алгоритма как такового вообще.
И да, пока числа относительно маленькие, плотность простых чисел достаточно высока, чтобы так тыкать пальцем в небо.
Чтобы алгоритм был действительно полным алгоритмом, учитывающим все ситуации, там ещё проверки на 1 и 3 должны быть, но с учётом "старшинства" — проверяются они не на том же десятке, а на десятке, который короче на символ (для тройки) и на два для 1. Ну и масштабировать до сотен, тысяч и так далее.
Я не стал описывать универсальный алгоритм, просто описал ход своих мыслей конкретно для данной задачи, потому что у автора была цель — "хочу поскорее узнать ответ к задаче". Да, по сути — алгоритм, но изначальной задумкой не было написание алгоритма как такового вообще.
И да, пока числа относительно маленькие, плотность простых чисел достаточно высока, чтобы так тыкать пальцем в небо.
Чтобы алгоритм был действительно полным алгоритмом, учитывающим все ситуации, там ещё проверки на 1 и 3 должны быть, но с учётом "старшинства" — проверяются они не на том же десятке, а на десятке, который короче на символ (для тройки) и на два для 1. Ну и масштабировать до сотен, тысяч и так далее.
вроде не поправилам, после тысяч сотни положено писать…
Может быть я что-то не так понял, но у вас в массиве primes нет 3989, а ведь хотелось бы тоже это число тоже проверить.
Скопировал из статьи все простые числа в Excel, в соседней колонке вписал формулу =РИМСКОЕ(A1), растянул формулу на все числа и двойным кликом, установил автоширину колонки с римскими цифрами. Визуально MMMDCCCLXXXIX самое широкое. Заняло 2 минуты, без скриптов конечно, но результат, в принципе, получен.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Самое широкое простое число, записанное римскими цифрами