| 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
Набор задачь для тренировки и улучшения понимания программирования Проверить на правильность и закомментировать весь код для лучшего понимания Нужны задачи для тренировки
Нужны задачи для тренировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Расчёт переходных процессов в цепи постоянного тока
igorrr37 16.01.2026
/ *
Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам
Кирхгофа, решает её и находит токи на L и напряжения на C в установ. режимах до и. . .
|
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым.
Но восстановить их можно так.
Для этого понадобится консольная утилита. . .
|
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
|
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
|
|
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11
— это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
|
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11
Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
|
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
|
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/
O1rJuneU_ls
https:/ / vkvideo. ru/ video-115721503_456239114
|