Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.9.171] |
|
Сообщ.
#1
,
|
|
|
- Математика и числа - Чётность/нечётность чисел if Odd (Number) then writeln (Number, ' нечётно') else writeln (Number, ' чётно') if Number and 1 = 0 then writeln(Number,' чётно') else writeln(Number,' нечётно') Делимость (кратность) чисел if Number mod 3 = 0 then writeln (Number, ' делится на 3 без остатка'); Наибольший Общий Делитель (НОД, англ. Greatest Common Divisor) { Евклид (Euclidus) } function GCD (A: integer; B: integer): integer; begin while (a <> 0) and (b <> 0) do if a >= b then a := a mod b else b := b mod a; GCD := a + b; { один - ноль } end; Наименьшее Общее Кратное (НОК, англ. Least Common Multiplier) function LCM (A: integer; B: integer): integer; begin LCM := a * b div GCD (a, b) end; Степень Для целых чисел function Power(Base, N: integer): longint; { Base - основание , N - степень } var Result: longint; i: word; begin Result := 1; { придаём начальное значение } for i := 1 to N do Result := Result * Base; Power := Result; end; Для вещественных чисел Возвести A в степень N. Ограничения: только для A > 0 function PowerExp (A, N: real): real; begin if A > 0 then PowerExp := Exp ( N * Ln (A) ) else PowerExp := 0; end; Факториал ( дополнительная информация: Факториал числа - N! ) function Factorial(N: word): longint; var Result: longint; i: word; begin Result := 1; for i := 1 to N do Result := Result * N; Power := Result; end; С использованием рекурсии function Factorial (N: word): longint; begin if N = 0 then Factorial := 1 else Factorial := N * Factorial (N - 1); end; Вещественный и целый типы Round - Округляет значение вещественного типа до значения целого типа, округляя. Trunc - Округляет значение вещественного типа до значения целого типа, отбрасывая дробную часть. Frac - Возвращает дробную часть аргумента. Int - Возвращает целую часть аргумента. var r : real; begin r := Round ( 123.456); { 123 } r := Round ( 123.778); { 124 } r := Trunc ( 123.456); { 123 } r := Trunc (-123.778); { -123 } r := Frac ( 123.456); { 0.456 } r := Int ( 123.456); { 123.0 } r := Int (-123.456); { -123.0 } end. Случайные числа Процедура Randomize - инициализирует генератор чисел. Функция Random (N) выдает целочисленные значения в диапазоне от 0 до N-1 ! Например, чтобы сгенерировать число X в диапазоне -N..N , пишем так: Randomize; X := Random (N + 1) - 2 * N; Если не написать сначала Randomize; , то будут генерироваться одни и те же числа. |
Сообщ.
#2
,
|
|
|
Как проверить простое ли число?
function isPrime(X: word): boolean; var i: integer; Begin isPrime:=false; if not odd(x) and (x<>2) { проверяем на чётность } then exit; i:=3; while i <= sqrt(x) do { проверяем только нечётные } begin if x mod i = 0 then Exit; inc(i,2); end; isPrime:=true; End; Разложение числа на множители procedure Factorization(x: word); var i: word; procedure DivX; { делим на простое число, пока делится без остатка } begin while (x>1) and (x mod i = 0) do begin write(i:4); x:= x div i; end; end; begin i:=2; DivX; i:=3; while (i < x div 2) do begin DivX; inc(i,2); { <=> i:=i+2; только нечётные числа } end; if x>1 then writeln(x:4); end; Приближённое представление числа в виде дроби VAR p,q,qmax:integer; d, r, min: real; BEGIN write('r, qmax='); readln(r, qmax); { r - не целое число, qmax - кол-во итераций (циклов) } p:=0; q:=1; min:=r; REPEAT IF p / q < r THEN inc(p) ELSE inc(q); d:=abs(r-p/q); IF d < min THEN BEGIN min:=d; writeln(p:7,'/',q) END UNTIL (q >= qmax) OR (d = 0); readln; END. Как работать с отдельными битами? FUNCTION IsBitOn (n: word; b : BYTE): BOOLEAN; { Проверяем, установлен ли бит } BEGIN isBitOn:=((n SHR b) AND 1) = 1 END; PROCEDURE SetBitOn (VAR n: Word; b: BYTE); { Устанавливаем бит } BEGIN N:= N OR (1 SHL b) END; PROCEDURE XORBit (VAR n: Word; b: BYTE); { Переключаем бит } BEGIN N:= N XOR (1 SHL b) END; |
Сообщ.
#3
,
|
|
|
Более быстрое разложение числа на множители.
В методе, описанном romtek-ом, количество проверок пропорционально sqrt(N), т.е. для разложение числа порядка 1012 потребуется около 106 операций, причем используется деление! Существуют методы поиска делителей, которые справляются со своей задачей намного быстрее (без операций деления). В методе Ферма предполагается, что N - нечетное число, причем N = uv. Попробуем подобрать такие числа X и Y, что будет выполняться: N = p2 - q2. Обозначим u = (p + q) / 2 и v = (p - q) / 2. Будем пытаться приблизить числа p и q с разных сторон, чтобы выполнялось N = p2 - q2. Итак, сам алгоритм: * Присвоим x = 2 * trunc(sqrt(N)) + 1, y = 1, r = sqr(trunc(sqrt(N))) - N (во время выполнения алгоритма числа x, y и r будут соответствовать 2p + 1, 2q + 1 и p2 - q2 - N) * Если r = 0, то выполнение алгоритма заканчивается. Имеем N = ((x-y)/2)((x+y-2)/2) и (x-y)/2 - наибольши делитель числа N. * Присвоить r = r + x, x = x + 2 (шаг по x) * Присовить r = r - y, y = y - 2 (шаг по y). Делать этот шаг, пока r > 0. * Перейти к проверке r = 0 Так как все действия алгоритма - это сложения и вычитания, то они на компьютере выполняются очень быстро. В результате работы алгоритма будет получено одно число - наибольший делитель числа N. Замечание: данный алгоритм лучше использовать для поиска больших делителей, нежели для маленьких! {$N+,E+} Function FermaFactorization(N : Comp) : Comp; Var X, Y, R : Comp; Begin X:=2 * Trunc(Sqrt(N)) + 1; Y:=1; R:=Sqr(Trunc(Sqrt(N))) - N; While (R <> 0) Do Begin R:=R + X; X:=X + 2; Repeat R:=R - Y; Y:=Y + 2; Until R <= 0; End; FermaFactorization:=(X - Y) / 2; End; Begin Writeln(FermaFactorization(917979909):0:0); End. PS: источник - D.E. Knuth, The Art of Computer Programming, Vol.2 |
Сообщ.
#4
,
|
|
|
Как узнать из каких цифр состоит целое число?
Var X : Integer; Begin X:=12345; Writeln('Число состоит из таких цифр:'); While X <> 0 Do Begin Writeln(X Mod 10); X:=X Div 10; End; End. |
Сообщ.
#5
,
|
|
|
Как быстро делить/умножать числа на степень двойки?
Как известно, опрерации умножения и деления занимаю много машинного времени. Если требуется скорость, то целесообразно использовать логические сдвиги: i:=i shl 1; { i:=i * 2^1} i:=i shl 2; { i:=i * 2^2} {и т.д.} i:=i shr 1; { i:=i div 2^1} i:=i shr 2; { i:=i div 2^2} {и т.д.} Примечание: корректно работает только с целыми беззнаковыми типами (word, byte...)! Если производить эти операции со знаковыми типами, то бит знака тоже сдвигается и в рез-те число может поменять свой знак! Сообщения были разделены в тему "Численные методы" |