Оптимизация задачи под большые числа Опции

[Witaliy]

Всем привет!

У меня есть задача:
Нужно подсчитать сумму всех счестливых числел в промежутке [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 - 23.02.2009 7:36

[volvo]

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

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 млрд)... Результаты, опять же, совпадают...