Предложите самый быстрый алгоритм!

[Gambler]

Привет всем! Парни, сегодня был на городской олимпиаде, ток вот, там задание было написать программу которая выводит все "N" значные числа Армстронга! Кто не знает что это такое, объясняю на примере: короче 153 - число Армстронга, потому что 153=1^3+5^3+3^3 (5^3 это пять в степени три) степень - это количество цыфр в числе. Значит так: входные данные: длина числа "n", 1<n<10, выходные: сами числа! О как! Сам не понял че написал.... Ну так вот, эту задачу решил я на Delphi и один паренек на QBasiс-е и надо сказать у него работала на много быстрее. Алгоритм у нас был один и тот же. Парни предложите пожалуйста какой нибудь шустрый алгоритм, а то у меня на n=5 минут пять бился. Короче, если вы ничего не придумаете я приложу свой алгоритм, попробуем его аптимизировать, но мне хотелось бы еще выши посмотреть.

[AVer]

Вот пусть не самый красивый, но зато на 100% рабочий код. На Форме лежат Edit1 для ввода длины числа, ListBox1 для вывода результата и Button1 - куда уж без нее .

unit Unit1;

interface

uses
  Windows, SysUtils, Classes, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    ListBox1: TListBox;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

Var N:Integer;

Function Armstrong(X:Integer):Boolean;
Var B,I,M,J:Integer;
    S:String;
Begin
M:=0;
Armstrong:=False;
S:=IntToStr(X);
For I:=1 to N do
 begin
 B:=StrToInt(S[I]);
 For J:=1 to Length(S)-1 do
 B:=B*StrToInt(S[I]);
 M:=M+B;
 end;
If X = M then Armstrong:=True;
end;

procedure TForm1.Button1Click(Sender: TObject);
Var I,D,D2:Integer;
    S:String;
begin
ListBox1.Clear;
N:=StrToInt(Edit1.Text);
S:='1';
For I:=1 to N-1 do
S:=S+'0';
D:=StrToInt(S);
S:='';
For I:=1 to N do
S:=S+'9';
d2:=StrToInt(S);
For I:=D to D2 do
If Armstrong(I) then
ListBox1.Items.Add(InttoStr(I));
ShowMessage('Ok');
end;

end.

При N=5 считает 2 секунды, при N=6 уже 15 секунд, а при N=7 совсем долго... (Не скажу точно - лень ждать). Но я думаю это неплохой результат. И кстати, выложи свой алгоритм.

[zetrix]

вот код Aver, переделаный:

unit Unit1;

interface

uses
  Windows, SysUtils, Classes, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    ListBox1: TListBox;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  a:array[0..9]of longint;
implementation

{$R *.dfm}

Var N:Integer;

Function Armstrong(X:Integer):Boolean;
Var I,M:Integer;
    S:String;
Begin
M:=0;
s:=inttostr(x);
for i:=1 to length(s) do M:=M+a[strtoint(s[i])];
if X=M then Armstrong:=true;
end;

procedure TForm1.Button1Click(Sender: TObject);
Var I:Integer;
begin
ListBox1.Clear;
N:=StrToInt(Edit1.Text);
a[0]:=0;
a[1]:=1;
for i:=2 to 9 do a[i]:=round(exp(N*ln(i)));
For I:=round(exp((N-1)*ln(10))) to round(exp(N*ln(i)))-1 do
If Armstrong(i) then
ListBox1.Items.Add(InttoStr(i));
ShowMessage('Ok');
end;

end.

Тестировался на P3 600MHz, при вводе числа 6 результат через 7 сек.
Думаю мы уже неплохо оптимизировали
Число 5 - результат около секунды, чуть больше.
Число 7 - результат 1 мин 10 сек вот полученные числа:
1741725
4210818
9800817
9926315

[Umen]

Сообщение от zetrix

For I:=round(exp((N-1)*ln(10))) to round(exp(N*ln(i)))-1 do
If Armstrong(i) then
ListBox1.Items.Add(InttoStr(i));

Тут ошибка: to round(exp(N*ln(i)))-1
Должно быть to round(exp(N*ln(10)))-1

//точно, просто косячнулся. zetrix

[Сильванович Михаил]

ПК: AMD AthlonXP 3500+ (2200Mhz)
время - 7 сек
числа:
1741725
4210818
9800817
9926315

Код:

unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Edit1: TEdit;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
a:array[0..9]of longint;
c: PChar;
implementation
{$R *.dfm}
Function Armstrong(X:Integer):Boolean;
Var i,m: Integer;
s: string;
Begin
m:=0;
s:=inttostr(x);
for i:=1 to length(s) do m:=m+a[strtoint(s[i])];
if x=m then Armstrong:=true;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i,n: integer;
begin
c:='';
n:=StrToInt(Edit1.Text);
a[0]:=0;
a[1]:=1;
for i:=2 to 9 do a[i]:=round(exp(N*ln(i)));
For i:=round(exp((N-1)*ln(10))) to round(exp(N*ln(10)))-1 do
If Armstrong(i) then c:=PChar(c+IntToStr(i)+' '+#13#10);
ShowMessage(c);
end;
end.

P.S. To Zetrix: При каждом проходе вызывать функцию TListBox.Items.Add()
занимает приличное время - я модифицировал твой код.

[Umen]

Если уже говорить о дополнительной оптимизации,
то функцию Armstrong тоже можно модифицировать

сразу же вместо

for i:=1 to length(s) do

можно использовать

for i:=1 to N do

естественно объявить N как глобальную

дальше можно избавиться от inttostr и strtoint, которые,
по моему мнению должны
прилично замедлять работу
(особенно при большом N)

вот мой вариант (пишу на работе - в блокноте, так что сильно
не пинайте если ошибки будут).

unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
  TForm1 = class(TForm)
     Button1: TButton;
     Edit1: TEdit;
     ListBox1: TListBox;
     procedure Button1Click(Sender: TObject);
     private
     { Private declarations }
     public
     { Public declarations }
   end;
var
   Form1: TForm1;
   a:array[0..9] of longint;
   rcount: integer;
   res:array[0..10000] of integer;  //с запасом :-)
   c: PChar;
   N: integer;
   Lower: integer;
 
implementation
{$R *.dfm}
Function Armstrong(X:integer):Boolean;
Var
   I, M: integer;
   b, St, d: integer;
Begin                             // внутри только целочисленные операции
     M := 0;                      // никакой работы со строками
     b := X;                      
     St := Lower;
     for i := 1 to N do begin
          d := b div St;
          b := b - d * St;
          St := St div 10;
          M := M + a[d];
     end;
     if X = M then
        Armstrong := true;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  i: integer;
  Higher: integer;
begin
  N := StrToInt(Edit1.Text);
  a[0] := 0;
  a[1] := 1;
  for i := 2 to 9 do 
    a[i] := round(exp(N*ln(i)));
  Lower := round(exp((n-1)*ln(10)));
  Higher := round(exp(N*ln(10)))-1;
  rcount := 0;
  For i := Lower to Higher do
    If Armstrong(i) then begin
        inc(rcount);
        res[rcount - 1] := i;
    end;
 
  For i := 0 to rcount - 1 do
     ListBox1.Items.Add(InttoStr(res[i]));
 
end;
end.

Протестировать по понятным причинам не могу....

Если ещё подумать, то можно Armstrong на асме написать :-)

[Gambler]

По идее алгоритм у меня такой же, но в виду отсутствия в Delphi функции возведения числа в степень (или я ее просто не знаю), писал сам, но вынес ее в отдельную функцию. Наверное на этом и был главный тормоз.... Да и комп не очень...600 Мгц (не больше).