| 15.07.2010, 05:53 | |
|
Ответы с готовыми решениями:
1272
Элементарные программы, для лучшего понимания языка...
Литература для лучшего понимания сути программирования |
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 26.01.2011, 14:35 | ||
|
А пример из процитированного вами отрывка следует тот, что числа вида Y = k * 125, где k нечетно имеют последние три цифры 125, 375, 625 или 875. При умножении каждого такого числа на 8 для определения последней ненулевой цифры знания этих последних трех цифр недостаточно, например 125 * 8 = 1000 1125 * 8 = 9000 2125 * 8 = 17000 и т.д., т.е. из того, что три последние цифры равны 125, следует только, что последняя ненулевая цифра равна 1 по модулю 8. Поэтому в этом случае нужно знать как минимум четыре цифры.
0
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 26.01.2011, 15:14 | |
|
Mr.X, Все понял. Тогда в защиту трех цифр могу сказать следующее:
Когда мы достигнем очередного числа, что его можно разложиьт так: Y = k * 125, где k целое число, то к этому времени k точно будет целым. Видимо поэтому хватает знать три последних цифры.
0
|
|
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
| 26.01.2011, 15:24 | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||
| 26.01.2011, 15:56 | ||
|
Mr.X, Все очередные числа мы получаем так:
- Сначало очередное число 1. - умножаем его на 2, получаем очередное число 2 - умножаем его на 3, получаем очередное число 6 и т.д. Т.е
Но k в этом случае будет четным (ведь мы использовали в формировании этого очередного числа много четных множителей). А вообще-то если применять операцию %10000 или %1000 к очередному числу то скорее всего очередное число никогда нельзя будет представить ввиде Y = k * 125, где k целое число
0
|
||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 26.01.2011, 16:47 | ||
|
Так что вы оказались правы.
1
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||
| 26.01.2011, 16:54 | |||
|
Mr.X, Извиняюсь, но у меня пара опечаток в предыдущих сообщениях:
0
|
|||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 26.01.2011, 19:04 | ||
|
0
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||
| 26.01.2011, 19:39 | ||
|
Сколько у нас четных чисел до первой пятерки? Два (это числа 2 и 4). Т.е. когда очередное число умножаем на 5, то оно содержит в своем разложении на простые множители уже три простых числа 2. Удалив этот очередной 0 из числа мы удаляем таким образом одну 5-ку и одну 2-ку. Но двоек гораздо больше чем пятерок при вычислении факториала числа. Вот можете проверить: 5!=120 (до получения этого числа также использованы множители 2 и 4. Т.е. всего в составе 5! имеются три 2-ки) отнимаем один ноль (на самом деле одну 5-ку и одну 2-ку). Остается 12 (в этом числе остались две 2-ки). или 10!=3628800 (до получения этого числа использованы множители 2, 4, 6, 8 и само число 10. Т.е. всего в составе 10! восемь 2-ек). Отнимаем 2 нуля (две 5-ки и две 2-ки). Остается 36288. В этом числе остались шесть двоек.
0
|
||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 26.01.2011, 22:05 | ||
|
Вы можете вычислить в своей программе (сохраняя четыре последние ненулевые цифры), чему будут равны эти цифры для факториала числа 390627 ? Добавлено через 1 час 37 минут valeriikozlov, можете посчитать чему равна последняя ненулевая цифра факториала числа 375, сохраняя сначала 3, а затем 4 ненулевые цифры. У меня получились интересные результаты.
0
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||
| 27.01.2011, 08:11 | ||||
|
k перед умножение на 375 было четным. При умножении на 375 стало нечетным (возможно). Но это нечетное k при следующем же умножении стало четным. (Т.е. нечетное k хоть и получается иногда, но с числами кратными 125 его умножения мы не дождемся) Добавлено через 1 час 33 минуты
При сохранении 3 ненулевых цифр выяснил что таких случаев 23 (в том числе и когда i равна 375). Но как и в предыдущем случае last_dig становился четным до того момента когда i снова становилась кратной 5.
0
|
||||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
| 27.01.2011, 10:01 | |
|
valeriikozlov, так вы можете сообщить чему у вас получилась равна последняя цифра в факториале 375 при сохранении трех цифр?
1
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||||||
| 27.01.2011, 12:25 | |||||||
![]() По крайней мере здесь: http://www.e-olimp.com.ua/problems-class/ нет такого теста, именно там у меня прошел вариант с сохранением 3-х последних цифр все тесты. Кстати я где-то ранее писал, что этот сайт не очень хорош по набору тестов (вот еще одно подтверждение). А другой сайт, который считаю в этом плане хорошим, на котором я всегда проверял решения, я уже писал закрылся до 1 февраля. Как откроется, обязательно проверю. Посмотрим как там с этим тестом. Добавлено через 23 минуты Mr.X, Я даже больше скажу. Оказывается для этой задачи мало и 4-х последних цифр запоминать. Точно хватит минимум 6-ти последних цифр. В доказательство запустите Ваш немного переделанный код и введите N=9999:
0
|
|||||||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|||
| 27.01.2011, 15:20 | |||
|
0
|
|||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||
| 27.01.2011, 15:34 | ||||
Кстати не можете более подробно расшифровать фразу:
0
|
||||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
| 27.01.2011, 15:43 | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 28.01.2011, 08:39 | |
|
Mr.X, Если Вас заинтересует, то есть решение, когда можно хранить всего одну последнюю ненулевую цифру (может быть это звучит немного фантастично, после всех приведенных неудачных теорий). Проверил практически правильность результатов до N=9999.
0
|
|
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
| 28.01.2011, 09:50 | |
|
0
|
|
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||||||
| 28.01.2011, 10:37 | |||||||
|
Суть решения заключается вот в чем:
При умножении двух различных чисел последняя ненулевая цифра всегда равна цифре, которая получается если умножить между собой только две последних ненулевых цифры этих чисел. Это правило характерно для всех умножаемых чисел, за исключением чисел оканчивающихся на цифру 5. Примеры: 9246*427=36503596332 или 6*7=42 У обоих получившихся чисел последнее число равно 2 Для чисел оканчивающихся на цифру 5, такой вариант бывает не проходит, например: 12*5=60 2*5=10 Получается все дело в последней цифре перемножаемых чисел - равны они 5-ке или нет. Можете сами подумать над этим, или потестировать, но это факт:
1
|
|||||||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||||
| 29.01.2011, 09:52 | ||||||||
|
На самом деле ноль получается при перемножении пятерки и четной цифры. В данном случае пятерок меньше, поэтому убираем их, а так можно было бы и двойки убрать, а пятерки оставить. Вот так работает примерно на четверть быстрее:
0
|
||||||||
|
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|||||||
| 29.01.2011, 16:49 | |||||||
|
Решение
0
|
|||||||
| 29.01.2011, 16:49 | |
|
Помогаю со студенческими работами здесь
1200
Набор задачь для тренировки и улучшения понимания программирования Проверить на правильность и закомментировать весь код для лучшего понимания Нужны задачи для тренировки
Нужны задачи для тренировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
| Опции темы | |
|
|
Новые блоги и статьи
|
|||
|
Рефакторинг программы уравнивания.
Massaraksh7 26.05.2026
Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.
|
Использование TThread в Lazarus для математических вычислений.
Massaraksh7 25.05.2026
Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .
|
Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает
anaschu 24.05.2026
Имитационная модель корпоративного здравоохранения: что показывает математика
Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .
|
Модель здравосохранения 17. Планы на выгорание
anaschu 23.05.2026
Вот конкретная схема реализации:
В классе Работник добавить:
накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни
коэффициентПрезентеизма — снижает продуктивность. . .
|
|
Изменение цветов в палитре gif файла aka фавикона
russiannick 23.05.2026
Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день.
Для работы необходим браузер,. . .
|
Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой
anaschu 23.05.2026
Отладка увольнений и настройка производительности
Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано.
. . .
|
Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15
anaschu 23.05.2026
Внезапно хорошее здоровье сотрудников не нужно капиталистам?))
|
Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул
anaschu 23.05.2026
Как мы чинили AnyLogic модель рабочего коллектива
Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .
|