| 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 / 1799 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|||||||
| 29.01.2011, 16:49 | |||||||
|
Решение
0
|
|||||||
| 29.01.2011, 16:49 | |
|
Набор задачь для тренировки и улучшения понимания программирования Проверить на правильность и закомментировать весь код для лучшего понимания Нужны задачи для тренировки
Нужны задачи для тренировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
|