IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Делитель числа n, состоящий из цифр 0, 7 и 2.
S_lip
сообщение 14.08.2008 21:25
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 29
Пол: Мужской
Реальное имя: B1-66ER

Репутация: -  1  +


Такая задача. Дано число 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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
volvo
сообщение 15.08.2008 20:16
Сообщение #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 и смотри там "Математика, алгоритмы -> Арифметика, системы счисления, комплексные числа -> Очень большие числа -> Огромные числа" модуль для работы с большими числами... Только учти: я здесь убрал всю работу со строками, везде только целочисленные типы. Как только будешь работать с конвертацией "строка -> число" и наоборот - получишь замедление...
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 28.07.2025 12:31
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"