Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Потрепаться";
Текущий архив: 2002.05.30;
Скачать: [xml.tar.bz2];

Вниз

Очередная несложная разминка   Найти похожие ветки 

 
MBo   (2002-04-15 18:03) [0]

Тренировка для начинающих.

Составить программу разложения целых чисел, скажем, до 10000 на множители
пример вывода

2=prime
3=prime
4=2*2
...
10000=2*2*2*2*5*5*5*5 или 10000=2^4*5^4 по вкусу


 
Андрей Сенченко   (2002-04-15 18:49) [1]

Например в таком направлении ?
X := исходное число
For i := 1 to 9 do
begin
IF X div Y = X / Y // -> сохраняем Y в массив решений, переназначаем результат в X
Else BREAK
IF X = 1 BREAK
end;


 
Андрей Сенченко   (2002-04-15 18:51) [2]

По хорошему, цикл не
to 9, а to X/2 наверное


 
Blackweber   (2002-04-15 19:14) [3]

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls,math;

type
TForm1 = class(TForm)
Edit1: TLabeledEdit;
Edit2: TLabeledEdit;
Button1: TButton;
Label1: TLabel;
Label2: TLabel;
procedure Button1Click(Sender: TObject);
end;

var
Form1: TForm1; e:integer;st:string;
a:array[1..100] of real;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin
st:=""; e:=0; edit2.Text:="";
a[1]:=strtofloat(edit1.Text);
repeat
inc(e);
a[e+1]:=trunc(log2(a[e]));
a[e+2]:=a[e]-power(2,a[e+1]);
st:=st+"2^"+floattostr(a[e+1])+" + ";
a[e+1]:=a[e+2];
until a[e+2]=0;
delete(st,length(st)-2,3);
edit2.Text:=st;
end;
end.


 
Mystic   (2002-04-15 23:34) [4]

Уже загадывал, но хорошей тренировкой будет программа на Delphi (консольная), которая выведет на экран собственный исходник (доступ к pas файлу запрещен, в ресурсы ничего не пихать и т. д.)


 
Doom   (2002-04-15 23:38) [5]

Задачки такие а ыв школе на бейсике делал помню.
> Андрей Сенченко © (15.04.02 18:51)
> По хорошему, цикл не
> to 9, а to X/2 наверное


Цикл до SQRT(X)


 
MBo   (2002-04-16 06:52) [6]

>Blackweber
это совсем не то - твоя процедура составляет число из степеней двойки. Замечу, что эта задача для двоек решается махом, стоит только вспомнить представление чисел в компе. Для другого основания твой способ с исправлениями в общем-то подходит.


 
Alx2   (2002-04-16 08:00) [7]

Довольно объемный код, но заточенный под скорость.

Const
PrimetblSize = 100; // Из-за разумных ограничений объема цитируемости таблицы, делаем ее размер = 100. Но здесь реально лучше использовать 10000. Иначе выигрыш по скорости незначителен.
Const
PrimeTable: Array[1..PrimetblSize] Of Integer = (
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541);
Function isPrime(A: Integer): Boolean; Forward;
Procedure Divide(A, B: Integer; Var C, D: Integer); Assembler; Stdcall; // C=A div B; D = A mod B. Т.е. используем приятную особенность операции деления, позволяющую одновременно найти частное и остаток.

asm
mov eax,a
cdq
idiv b
mov ecx,c
mov [ecx],eax
mov ecx,d
mov [ecx],edx
end;
Function SearchNearestPrime(Pattern: Integer): Integer;
Function Search(Start, Stop: Integer): Integer;
Var C: Integer;
Begin
If Start < Stop Then
Begin
C := (Start + Stop) Shr 1;
If PrimeTable[C] < Pattern Then
Result := Search(C + 1, Stop) Else
If PrimeTable[C] > Pattern Then
Result := Search(Start, C - 1)
Else
Result := C;
End
Else
If Start > Stop Then
Result := Stop Else
Result := Start
End;
Begin
Result := Search(1, PrimetblSize);
End;

Function PrevPrime(A: Integer): Integer;
Begin
If (A > 2) And (A <= PrimeTable[PrimetblSize]) Then
Begin
Result := SearchNearestPrime(A);
If PrimeTable[Result] >= A Then Result := PrimeTable[Result - 1]
Else Result := PrimeTable[Result];
End
Else
If A <= 2 Then Result := 2
Else
Begin
dec(A);
If A And 1 = 0 Then dec(A);
While Not isPrime(A) Do dec(A, 2);
Result := A;
End;
End;


Function isPrime(A: Integer): Boolean;
Var K: Integer;
Begin
If A < 0 Then A := -A;
Result := (A <= 2) Or (PrimeTable[SearchNearestPrime(A)] = A);
If Not Result Then
Begin
Result := ((A And 1) = 1);
If Result
Then
Begin
K := PrevPrime(Round(Sqrt(A)) + 1);
While (K > 2) And (A Mod K <> 0) Do K := PrevPrime(K);
Result := K = 2;
End;
End;
End;

весь сыр-бор здесь:
После отработки iFactor List содержит разложение на простые множители числа A.
Procedure iFactor(A: Integer; Lst: TList);</n>
Var
K : Integer;
M, R: Integer;
Begin
If A < 0 Then A := -A;
Lst.Clear;
If (A <= 2) Or (isPrime(A)) // Если A - простое, то нечего и раскладывать
Then
Lst.Add(Pointer(A))
Else
Begin
K := PrevPrime(Round(Sqrt(A)) + 1); // Находим ближайшее с низу к квадратному корню из A простое число.
While (K > 2) Do
Begin
Divide(A, K, M, R); // M = A div K; R = A mod K
If (R = 0) Then // Если поделилось нацело,
Begin // то продолжаем деление далее
Repeat
Lst.Add(Pointer(K));
A := M;
Divide(A, K, M, R);
Until (R <> 0);
K := Round(Sqrt(A)) + 1
End;
K := PrevPrime(K);
End;

If A And 1 = 0 Then // если A четное
Begin // то дополняем List двойками
Repeat
Lst.Add(Pointer(2));
A := A shr 1; // Делим A на два
// asm
// shr A,1
// end;
Until (A And 1) = 1; // Выходим, если A нечетное
End;
If (A > 1)
Then
Lst.Add(Pointer(A));
End;
End;



 
Alx2   (2002-04-16 08:13) [8]

Да, чуть не забыл описать идею:
Раскладывая число A, замечаем, что если A непростое, то наибольший член в разложении не превысит Round(Sqrt(A)) + 1.
Находим этот член, делим на него A и все повторяем снова. В итоге количество итераций O(log2(A))


 
MBo   (2002-04-16 08:31) [9]

OK, работает очень быстро.


 
Nemesis   (2002-04-16 09:50) [10]

Alx2 © (16.04.02 08:00)

Const
PrimeTable: Array[1..PrimetblSize] Of Integer = (
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541);

А автоматически расчитать все простые числа в некотором диапазоне слабо ...


 
MBo   (2002-04-16 10:07) [11]

не слабо ;)
вот глупый код
var
X: array [1..10000] of Boolean;
procedure ResetNoPrimes;
var
I, J: Integer;
begin
FillChar(X, SizeOf(X), True);
for I := 2 to 100 do
for J := I to 5000 do
if I * J <= 10000 then
X[I * J] := False;
end;


 
Nemesis   (2002-04-16 10:17) [12]

MBo © (16.04.02 10:07)

не слабо ;)

А почему там не вставил


 
igorr   (2002-04-16 11:14) [13]

To MBo, Alx2: А что значит быстро?

Предлагаю так.


type
TForm1 = class(TForm)
Edit1: TEdit;
Button1: TButton;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
end;

var
Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var
Num, Simple:Integer;
Str:String;
begin
Num:=StrToInt(Edit1.Text);
Str:=Edit1.Text+"=";
Simple:=2;
while Num<>1 do begin
if Num Mod Simple = 0
then begin
Num:=Num Div Simple;
Str:=Str+IntToStr(Simple)+" * ";
Continue;
end
else Inc(Simple);
end;
Delete(Str,Length(Str)-2,3);
Label1.Caption:=Str;
end;

end.



 
Alx2   (2002-04-16 11:55) [14]

>Nemesis © (16.04.02 09:50)
>А автоматически расчитать все простые числа
>в некотором диапазоне слабо ...
Ты думаешь я их не автоматически искал? :))


 
igorr   (2002-04-16 12:06) [15]

Виноват. Континью - лишняя.


 
MBo   (2002-04-16 13:18) [16]

>igorr
ОК, работает

>А что значит быстро
числа от 2 до 10000 махом раскладывает
мой вариант намного медленнее, правда, он полностью функционально закончен, в него вывод встроен внутрь, что и тормозит, кроме того, простые насчитываются по ходу дела и хранятся (я его пока не приводил)


 
MBo   (2002-04-22 09:18) [17]

приведу свой вариант

procedure TForm1.Button2Click(Sender: TObject);
var
PrList:Tlist;
MulList:TStringList;
i,Num,Temp,MaxPrime:integer;
s:string;
N:integer;
begin
N:=10000;
PrList:=Tlist.Create;
PrList.Capacity:=100;
MulList:=TStringList.Create;
MulList.Capacity:=N;
for Num:=2 to N do begin
Temp:=Num;
MaxPrime:=2;
s:=IntToStr(Temp)+"=";
i:=-1;
while (Temp >= MaxPrime) and (i<PrList.Count-1) do begin
inc(i);
while (Temp >= MaxPrime) and (Temp mod Integer(PrList[i])=0) do begin
MaxPrime:=Integer(PrList[i]);
Temp:=Temp Div MaxPrime;
s:=s+IntToStr(MaxPrime)+"*";
end;
end;
if Temp=Num then begin
PRList.Add(Pointer(Num));
s:=s+"Prime";
end
else Delete(s,Length(s),1);
MulList.add(s);
end;
PrList.Free;
MulList.SaveToFile("C:\Primes.txt");
MulList.Free;
end;



Страницы: 1 вся ветка

Форум: "Потрепаться";
Текущий архив: 2002.05.30;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.5 MB
Время: 0.006 c
3-97198
Savage
2002-05-08 15:52
2002.05.30
Очень интересная ошибка с ADO


6-97371
Antoshka
2002-03-21 09:36
2002.05.30
Загрузить файл с Интернета


14-97384
Morfey
2002-04-20 19:12
2002.05.30
декоммпилятор


6-97366
новенький в Делфи
2002-03-19 18:45
2002.05.30
Виснет сканер портов


6-97365
ev
2002-03-16 13:38
2002.05.30
утечка в Indy





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский