![]() |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
![]() |
S_lip |
![]()
Сообщение
#1
|
Новичок ![]() Группа: Пользователи Сообщений: 29 Пол: Мужской Реальное имя: B1-66ER Репутация: ![]() ![]() ![]() |
Такая задача. Дано число n (0<n<500000). Нужно найти число s, которое делило бы n без остатка и состояло бы только из цифр 7, 2 и 0. s может содердать до 20 знаков. Гарантируется, что число s существует.
Примеры: n=3 s=27 n=59 s=22007 n=1312 s=270272 Я ничего умнее не придумал, кроме как решить через лоб: взял массиб из 20 байтов. На каждом шаге учеличивал на "1"( т.е. 2 -> 7 -> 20 -> 27 -> 70 ...) и проверял, есть ли остаток при делении на n. Понятно, что в худшем случае придестя увеличивать s 3^20 раз, а это слишком много. Может, есть какой-нибудь более красивый способ для решения этой задачи? Источник (я чуть изменил условие): www.lio.lv/olimps/uzdevumi.php?show=18 Сообщение отредактировано: S_lip - 14.08.2008 21:33 |
![]() ![]() |
volvo |
![]()
Сообщение
#2
|
Гость ![]() |
Хм... Я тут немного ускорил программу (за счет того, что всего при моем способе возможно 224 = чуть больше 16 с половиной миллионов итераций, а при том, что я предложил раньше - порядка 230, ну ты и сам сказал об этом...) Смотри:
uses
windows;
function my_sys(n: integer): qword;
var
s: qword;
count: qword;
const
radix = 3;
digits: array[0 .. pred(radix)] of integer = (0, 2, 7);
begin
s := 0; count := 1;
repeat
s := digits[(n mod radix)] * count + s;
n := n div radix;
count := count * 10;
until n = 0;
result := s;
end;
const max_n = 500000;
var
T: dword;
n, q: qword;
i, delta: integer;
begin
n := 49999;
T := gettickcount();
// тут небольшая хитрость: если число ближе к концу интервала, чем к началу,
// то я иду от конца, т.к. больше шансов, что ответ будет большим. Но это надо
// проверить, всегда ли выдается правильный ответ. Может надо идти строго от
// начала к концу с Delta = +1 ...
if n > max_n div 2 then begin
i := (1 shl 24) - 1; delta := -1;
end
else begin
while my_sys(i) < n do inc(i); // пропускаем все числа, которые меньше N
delta := 1;
end;
repeat
if my_sys(i) mod n = 0 then break;
inc(i, delta)
until false;
writeln(my_sys(i), ' : ', n, '':3, 'time = ', gettickcount() - T);
end.
А теперь посмотри лог новой программы:Цитата 270272 : 1312 time = 0 Для сравнения: старая программа выдавала:270772020722 : 19999 time = 156 2022070707777 : 49999 time = 343 7022200720227 : 80411 time = 672 270277207207207 : 199999 time = 5531 2020707070077777 : 499999 time = 328 Цитата 2022070707777 : 49999 = 40442223 27672 (результатов при n = 499999 и 199999 я просто не дождался)Итого - ускорение в десятки раз (в среднем - в 50, где-то больше, где-то меньше). Посмотри, может еще что сможешь ускорить, я пока никакого решения алгоритмическим путем, а не перебором, придумать не могу. Кстати. Чуть не забыл. Если тебе все же хочется работать не с QWord (хотя все результаты по-моему помещаются в QWord), то открывай DRKB и смотри там "Математика, алгоритмы -> Арифметика, системы счисления, комплексные числа -> Очень большие числа -> Огромные числа" модуль для работы с большими числами... Только учти: я здесь убрал всю работу со строками, везде только целочисленные типы. Как только будешь работать с конвертацией "строка -> число" и наоборот - получишь замедление... |
![]() ![]() |
![]() |
Текстовая версия | 28.07.2025 12:31 |