Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Общие вопросы Delphi
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Закрытая тема
Ваша тема закрыта, почему это могло произойти? Возможно,
Нет наработок или кода, если нужно готовое решение - создайте тему в разделе Фриланс и оплатите работу.
Название темы включает слова - "Помогите", "Нужна помощь", "Срочно", "Пожалуйста".
Название темы слишком короткое или не отражает сути вашего вопроса.
Тема исчерпала себя, помните, один вопрос - одна тема
Прочитайте правила и заново правильно создайте тему.
 
Опции темы Поиск в этой теме
Старый 24.12.2006, 22:00   #1
Gambler
Игрок
Форумчанин
 
Аватар для Gambler
 
Регистрация: 29.10.2006
Сообщений: 367
По умолчанию Предложите самый быстрый алгоритм!

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

#define true (Math.random()>0.5) //Удачной отладки
Gambler вне форума
Старый 25.12.2006, 02:35   #2
AVer
Андрей
Форумчанин
 
Аватар для AVer
 
Регистрация: 21.11.2006
Сообщений: 457
По умолчанию

Вот пусть не самый красивый, но зато на 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 совсем долго... (Не скажу точно - лень ждать). Но я думаю это неплохой результат. И кстати, выложи свой алгоритм.
ICQ: 5311314
[SIGPIC][/SIGPIC]

Последний раз редактировалось AVer; 25.12.2006 в 02:43.
AVer вне форума
Старый 25.12.2006, 07:49   #3
zetrix
Delphi/C++/C#
Участник клуба
 
Аватар для zetrix
 
Регистрация: 29.10.2006
Сообщений: 1,972
По умолчанию

вот код 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

Последний раз редактировалось zetrix; 09.01.2007 в 18:45.
zetrix вне форума
Старый 25.12.2006, 21:01   #4
Umen
Форумчанин
 
Аватар для Umen
 
Регистрация: 10.11.2006
Сообщений: 189
По умолчанию

Цитата:
Сообщение от 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

Последний раз редактировалось zetrix; 09.01.2007 в 18:47.
Umen вне форума
Старый 26.12.2006, 10:29   #5
Сильванович Михаил
Студент
Форумчанин
 
Регистрация: 10.11.2006
Сообщений: 196
По умолчанию

ПК: 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()
занимает приличное время - я модифицировал твой код.
Visita Interiorem Terrae Rectificando Operae Lapidem...
Сильванович Михаил вне форума
Старый 26.12.2006, 17:12   #6
Umen
Форумчанин
 
Аватар для Umen
 
Регистрация: 10.11.2006
Сообщений: 189
По умолчанию

Если уже говорить о дополнительной оптимизации,
то функцию 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 на асме написать :-)
Umen вне форума
Старый 26.12.2006, 22:44   #7
Gambler
Игрок
Форумчанин
 
Аватар для Gambler
 
Регистрация: 29.10.2006
Сообщений: 367
По умолчанию

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

#define true (Math.random()>0.5) //Удачной отладки
Gambler вне форума
Закрытая тема


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Какой самый быстрый метод заполнения массива, например двухмерного? SkAndrew Общие вопросы Delphi 11 29.05.2008 13:23
Быстрый алгоритм для вычисления синуса RIO Помощь студентам 10 17.12.2007 14:33
Самый крутой сайт Alar Свободное общение 3 05.06.2007 08:40