Третий алгоритм базируется на использовании
Совет 3 (общий)
Третий алгоритм базируется на использовании массива индикаторов. Так как значения элементов исходного массива принадлежат интервалу [0,32767], то заводится 32 768 битовых индикаторов (4096 байт). В начале все индикаторы сбрасываются в нуль, а затем выполняется цикл одноразового просмотра элементов исходного массива. Для значения каждого элемента a[i] проверяется соответствующий бит в массиве индикаторов и, если он равен 0, в него заносится 1 и к счетчику разных чисел добавляется единица. Если проверяемый бит индикаторов отличен от нуля, то соответствующее значение уже встречалось.
Совет 4 (Си)
Массив индикаторов (b) можно явным образом запрашивать при входе в подпрограмму и освобождать при выходе, хотя локальные данные в процедурах и функциях все равно выделяются и освобождаются автоматически. Но в библиотеке Си есть полезная функция calloc, которая одновременно выделяет память и чистит ее. Переменные byte и bit использованы для определения байта и бита в массиве индикаторов, соответствующих анализируемому значению a [i].
Программа 4_09a.bas
DECLARE SUB SORT (A() AS INTEGER, N%)
DECLARE FUNCTION DIFFERENCE% (A() AS INTEGER, N%)
DEFINT A-Z
DIM A(5)
DATA 0,0,0,0,0
DATA 1,1,1,1,1
DATA 0,1,1,1,1
DATA 0,0,1,1,2
DATA 0,1,2,3,4
DATA 1,2,3,4,5
CLS
FOR k=1 TO 5
FOR I=0 TO 4: READ A(I): NEXT I
PRINT "Количество разных чисел в массиве ";k;" = ";
PRINT DIFFERENCE(A(), 5} NEXT k END
FUNCTION DIFFERENCE (A() AS INTEGER, N%)
SORT A(),N%
M=l
FOR I=0 TO N%-2
IF A(I)<>A(I+1) THEN M=M+1
NEXT I
DIFFERENCE=M
END FUNCTION
SUB SORT(A() AS INTEGER,N%)
REM тело любой процедуры сортировки
END SUB
Программа 4_09b.bas
DECLARE SUB SORT (A() AS INTEGER, N%)
DECLARE FUNCTION DIFFERENCE% (A() AS INTEGER, N%)
DEFINT A-Z
DIM A0(5),A1{5),A2(5),A3(5},A4(5),A5(5)
DATA 0,0,0,0,0
FOR I=0 TO 4: READ А0(I): NEXT I
DATA 1,1,1,1,1
FOR I=0 TO 4: READ A1(I): NEXT I
DATA 0, 1,1, 1, 1
FOR I=0 TO 4: READ A2(I): NEXT I
Содержание Назад Вперед