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

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

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

 
 Ответить  Открыть новую тему 
> Оптимизация задачи под большые числа
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

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


Всем привет!

У меня есть задача:
Нужно подсчитать сумму всех счестливых числел в промежутке [a;b].
Счастливые числа - числа которые состоят только из 4 и 7
например
Входные данные:
5 49
Выходные данные:
98
(7+44+47=98)
1 <= A <= B <= 1000000000 (10^9)

Вот моё решение:
{$n+}
program my;
var a,b,i : longint;
sum : extended;
function isLucky(c : longint) : boolean;
var s : string;
i,r : integer;
begin
r := 0;
str(c,s);
for i := 1 to length(s) do
if (s[i]= '7') or(s[i]='4') then
inc®;
if r = length(s) then
isLucky := true
else
islucky := false;
end;
begin
sum := 0;
readln(a,b);
if a < 4 then
a:=4;
if b > 77777777 then
b := 77777777;

for i := a to b do
if isLucky(i) = true then
sum := sum+i;
writeln(sum:1:0);
end.


Но программа очень медленно роботает, а ограничение велики. Помогите сделать что-то, что бы можно были делать и под 1 и 10^9.
Спасибо!

Сообщение отредактировано: Lapp -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Во-первых, избавляешься от преобразования числа в строку. Это ОЧЕНЬ медленно...

function isLucky(c: longint) : boolean;
begin
islucky := false;
while c > 0 do begin
if not ((c mod 10) in [4, 7]) then exit;
c := c div 10;
end;
islucky := true;
end;

так будет в среднем (по замерам времени выполнения) в 15 раз быстрее на больших значениях b... Но это еще не все... For выполняется медленнее, чем While, опять же по замерам выигрыш - около 3-5% времени, это тоже нельзя сбрасывать со счетов... Но и это еще не все.... Вместо того, чтобы постоянно крутить цикл с шагом 1, и проверять число, которое ЗАВЕДОМО не может быть счастливым, будем пропускать некоторые числа, и проверять только те, последняя цифра которых - 4 или 7. Вот так это делается:

var a,b,i : longint;
sum : extended;

function isLucky(c: longint) : boolean;
begin
islucky := false;
while c > 0 do begin
if not ((c mod 10) in [4, 7]) then exit;
c := c div 10;
end;
islucky := true;
end;


var d: integer;
begin
sum := 0;
i := a;
while not ((i mod 10) in [4, 7]) do inc(i);

if i mod 10 = 4 then d := 3 else d := 7;

while i <= b do begin
if isLucky(i) = true then sum := sum + i;

inc(i, d);
d := 10 - d;
end;
writeln(sum:1:0);
end.
Разберешься, почему именно так, или объяснить? Результаты работы твоей и моей программы совпадают...

Update
НО... И это еще не предел... Как ни странно, тут рекурсия дает тысячекратные выигрыши во времени. Смотри, вместо того, чтобы крутить циклы из миллионов (и больше) итераций, просто напросто генерируешь все счастливые числа. А их - всего чуть больше 1000. И к тому же не надо проверять их. Они изначально счастливые:
program my;
var
a,b: longint;
sum : extended;

procedure sum_lucky(n: longint);
begin
if (n >= a) and (n <= b) then sum := sum + n;
if n > b div 10 then exit;
sum_lucky(10*n + 4);
sum_lucky(10*n + 7);
end;

begin

readln(a, b);
if a < 4 then a := 4;
if b > 777777777 then b := 777777777;

sum := 0;
sum_lucky(0);
writeln(sum:1:0);
end.

- выполняется мгновенно, против 11 секунд для вышеприведенного варианта на максимальных входных данных (от 1 до 1 млрд)... Результаты, опять же, совпадают...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

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


М
Witaliy, пожалуйста, срочно приведи название темы в соответствие с Правилами.



--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

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


ОЧЕНЬ большое спасибо всем! Даже не думал что так просто можно это сделать)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

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


У меня еще есть такая задача:
Счастливые числа єто те числа, которые делятся одновременно и на x и на y и на z
Найти все такие числа в промежутке [a;b].
Например
2 3 4
12 24
Результат: 2
(это числа 12, 24).

Вот мой код:

program my;
var x,y,z,a,b,i,res : longint;
function is_Lucky(c : longint): boolean;
begin
if (c mod x = 0) and (c mod y = 0) and (c mod z = 0) then
is_Lucky := true
else
is_Lucky := false;
end;
begin
readln(x,y,z);
readln(a,b);
res := 0;
for i := a to b do
if is_Lucky(i)= true then
inc(res);
writeln(res);
end.


Сново не знаю как оптимизировать. Возможно тоже надо делать while?

Спасибо огромное.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Я, конечно, могу ошибаться, но мне почему-то кажется, что можно вообще выбросить цикл за ненадобностью:
writeln(((b - a) div LCМ(x, y, z)) + 1);
выдаст тебе нужный результат... LCM - это Least Common Multiple - наименьшее общее кратное чисел (НОК)... Как находится НОК было на форуме неоднократно, ищи...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

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


Извините, искал, но не нашло... если можете, дайте ссилку... спасибо.

Сообщение отредактировано: Witaliy -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Цитата
есди можете, дайте ссилку...
Ну, вот тут хотя бы: прцедура
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

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


Такой вариант не пройдёт, неверные ответы. Нужно как-то оптимизировать мой код.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата
неверные ответы
Ну, значит и в твоем решении ответы - неверные... Так? И вообще, я не знаю, что ты там намудрил, и как что вызывал... Поэтому входные данные, для которых ответы по-твоему неверные, в студию... И, заодно, какие при этих данных по-твоему должны быть верные ответы - тоже...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

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


Я здаю задачу на контестер, и не знаю какие входные данные там должны быть
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Ну, в таком случае тебе ее и решать, для контестера... А то очень мудрые все стали: "Кто-то решает, а кто-то сдает"...
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 28.03.2024 19:42
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name