Реферат: Программирование различных типов задач
End;
Итак, мы научились за O(n) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.
Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).
сначала они в сортируем по младшему на один беспорядке: разряду: выше: и еще раз:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554
Hу вот мы и отсортировали за O(k*n) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то 'поразрядная сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'!
Реализация алгоритма "распределяющей" сортировки:
Const
n = 8;
Type
arrType = Array[0 .. Pred(n)] Of Byte;
Const
m = 256;
a: arrType =
(44, 55, 12, 42, 94, 18, 6, 67);
Procedure RadixSort(Var source, sorted: arrType);
Type
indexType = Array[0 .. Pred(m)] Of Byte;
Var
distr, index: indexType;
i: integer;
begin
fillchar(distr, sizeof(distr), 0);
for i := 0 to Pred(n) do
inc(distr[source[i]]);
index[0] := 0;
for i := 1 to Pred(m) do
index[i] := index[Pred(i)] + distr[Pred(i)];
for i := 0 to Pred(n) do
begin
sorted[ index[source[i]] ] := source[i];
index[source[i]] := index[source[i]]+1;
end;
end;
var
b: arrType;
begin
RadixSort(a, b);
end.
Теория чисел.
Теория чисел является, возможно, самым интересным и красивым разделом математики. Доказательство Евклидом существования бесконечного количества простых чисел остается таким же четким и ясным сегодня, каким оно было более двух тысяч лет назад. Такие невинные вопросы, как существуют ли решения уравнения аn +bn =cn для целых a,b,c и n>2, часто оказывается совсем не такими невинными. Более того, это формулировка великой теоремы Ферма!
Компьютеры уже долгое время используют в исследованиях теории чисел. Проведение некоторых вычислений, связанных с теорией, для больших чисел требует значительной эффективности. К счастью, существует множество алгоритмов, которые могут помочь в этом.
Простые числа
Целое число р>1 называют простым, если оно делится только на 1 и на само себя. Говоря другими словами, если р – простое число, то равенство р=a*b для целых a≤b эквивалентно тому, что a=1 и b=p. Первые десять простых чисел: 2, 3, 5, 7,11, 13, 17, 19, 23 и 29.
Мы говорим, что число р является множителем числа х, если оно входит в его разложение на простые множители. Любое число не являющееся простым, называется составным.
Нахождение количества делителей и самих делители числа а .
Для этого будем перебирать все числа i, подходящие на роль делителя. Очевидно, что 1 <= i <= a. Чтобы ускорить работу алгоритма заметим, что если i – делитель а, то a/i – тоже делитель a, и к тому же одно из чисел i и a/i не превышает Sqrt(a) (если предположить противное, то получим a = i*(a/i) > Sqrt(a)*Sqrt(a) = a – противоречие). Поэтому достаточно перебирать числа i в пределах от 1 до Trunc(Sqrt(a)) и при нахождении, что некоторое i – делитель выдавать, что a/i – тоже делитель и увеличивать количество делителей на 2. Этот алгоритм не будет работать, когда a – точный квадрат, что легко исправляется.
Приведенные соображения реализованы в алгоритме (2):
c:= 0;
For i:= 1 to Trunc(Sqrt(a)) do
If a mod i = 0 then begin
If i*i = a then begin
c:= c+1;
WriteLn(‘Найден делитель ’, i);
end
else begin
c:= c+2;
if i=a div i then c:=c-1;
WriteLn(‘Найден делитель ‘, i);
WriteLn(‘Найден делитель ‘, a div i);
end;
end;
WriteLn(‘Количество делителей ‘, c);
Для того, чтобы проверить, является ли число простым, нужно посчитать количество его делителей, используя алгоритм 2.
Нахождение всех простых чисел, не превосходящих заданное число N.
Возможны несколько подходов к решению этой задачи: