| 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 | |
|
Набор задачь для тренировки и улучшения понимания программирования Проверить на правильность и закомментировать весь код для лучшего понимания Нужны задачи для тренировки
Нужны задачи для тренировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов.
alhaos 10.06.2026
Задача
Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов.
Сигнатура
func Fetch(urls string, maxConcurrent int) Result
Пример
urls :=. . .
|
[golang] Состояние гонки (race condition)
alhaos 10.06.2026
Состояние гонки (race condition)
Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .
|
Взрослые отношения, и почему они не получаются
kumehtar 09.06.2026
Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .
|
[golang] Worker Pool
alhaos 09.06.2026
Worker Pool
Worker Pool — паттерн конкурентной обработки задач в Go.
Суть: фиксированное количество горутин-воркеров читают задачи из общего канала
и пишут результаты в общий канал результатов. . . .
|
|
[golang] Pipeline
alhaos 08.06.2026
Pipeline
Pipeline — паттерн конкурентной обработки данных в Go.
Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .
|
Свет внутри себя
kumehtar 07.06.2026
Пусть это будет здесь
lIs4oanZS9Y
|
Программа для com-порта
Uhbif79 05.06.2026
Всем привет, давно хотел изучить Qt, начинал, бросал, потом снова начинал. И сейчас вот смог написать свою первую программу.
До этого имел опыт программирования микроконтроллеров, писал прошивки на. . .
|
Транскрипция 55-минутного видео через Whisper: WhisperDesktop облажался, спас Google Colab[
anaschu 01.06.2026
Понадобилось получить текст из свежезагруженного видео на YouTube. Казалось бы, задача на пять минут. Заняла полтора часа. Делюсь опытом — может кому пригодится последовательность решений.
. . .
|