ADru/Mod/S18_Поиск.odc

(*  Общие сведения о примерах: Справка *)
(*  Исправления и подготовка примеров: (С) Ф.В.Ткачев, 2009, info21 AT inr.ac.ru *)

MODULE  ADruS18_Поиск;  (* Иллюстрация алгоритмов поиска, раздел 1.8. *)

	IMPORT  Log := StdLog,  In := i21sysIn,  R := ObxRandom;
	
	PROCEDURE InitRandom ( OUT a: ARRAY OF INTEGER ); (* инициализация массива случайными числами *)
		VAR  i: INTEGER;
	BEGIN
		R.InitSeed( 12345 );
		FOR  i := 0  TO  LEN( a )  - 1  DO
			a[ i ] := 1 + SHORT( ENTIER( ( LEN( a ) )* R.Uniform() ) );
			ASSERT( a[ i ] > 0 ); (* гарантируем инициализацию только положительными числами *)
		END;
	END InitRandom;
	
	PROCEDURE InitSorted ( OUT a: ARRAY OF INTEGER ); (* инициализация массива упорядоченными числами *)
		VAR  i: INTEGER;
	BEGIN
		FOR  i := 0  TO  LEN( a ) - 1  DO
			a[ i ] := 1 + i ; 
			ASSERT( a[ i ] > 0 ); (* гарантируем инициализацию только положительными числами *)
		END;
	END InitSorted;
	
	
	PROCEDURE Линейный*; (* несколько программных фрагментов из раздела 1.8.1 *)
		VAR
			a: POINTER TO ARRAY OF INTEGER; (* указатель на массив, в котором поиск *)
			N: INTEGER; (* кол-во элементов, среди которых ищем *)
			x: INTEGER; (* искомое значение или "аргумент поиска" *)
			i: INTEGER;
			
			a1, a2, a3, a4: POINTER TO ARRAY OF INTEGER;
	BEGIN
		Log.Ln;
		Log.String('Проверяем примеры линейного поиска:');  Log.Ln;
		
		N := 10;
		x := 0;  (* в примерах будем всегда искать значение нуль *)
		
		(* в каждом примере размещаем новый массив а, но запоминаем указатель на него, чтобы иметь возможность заглянуть в содержимое массивов в конце*)
		
		(* Простейший линейный поиск *)
		
		(* Пример 1. Искомое значение присутствует в массиве *)
		NEW( a, N );
							a1 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
		InitRandom( a );
		a[ 5 ] := 0;
		a[ 8 ] := 0; (* помещаем дважды, найдется первое вхождение *)
		
		(* собственно поиск, фрагмент из книги, с.50: ****************)
		i := 0; 
		WHILE ( i < N ) & ( a[ i ] # x ) DO  INC( i )  END;
		(* конец фрагмента. ************************************)
		
		ASSERT( i = 5 ); (* нашли наименьшую позицию *)
		Log.String('Выполнен пример 1.');  Log.Ln;
		
		(* Пример 2. Искомого значения в массиве нет *)
		NEW( a, N );
							a2 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
		InitRandom( a );
		
		i := 0; 
		WHILE ( i < N ) & ( a[ i ] # x ) DO  INC( i )  END;

		ASSERT( i = N ); (* не нашли *)
		Log.String('Выполнен пример 2.');  Log.Ln;
		
		(* Линейный поиск с барьером *)
		
		(* Пример 3. Искомое значение присутствует в массиве *)
		NEW( a, N + 1 ); (* нужен один лишний элемент для барьера *)
							a3 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
		InitRandom( a );
		a[ 5 ] := 0;
		
		a[ N ] := 0; (* выставили барьер *)
		i := 0; 
		WHILE  a[ i ] # x  DO  INC( i )  END;
		ASSERT( i = 5 ); (* нашли наименьшую позицию *)
		Log.String('Выполнен пример 3.');  Log.Ln;
		
		(* Пример 4. Искомого значения в массиве нет *)
		NEW( a, N + 1 ); (* нужен один лишний элемент для барьера *)
							a4 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
		InitRandom( a ); (* в массиве только положит. числа *)

		(* фрагмент из книги, с.51, вверху: *******************************)
		a[ N ] := x;  i := 0; 
		WHILE  a[ i ] # x  DO  INC( i )  END;
		(* конец фрагмента *******************************************)
		ASSERT( i = N ); (* нашли только сам барьер *)
		Log.String('Выполнен пример 4.');  Log.Ln;
		
		a := NIL;
		HALT( 0 ); (* чтобы заглянуть в содержимое всех 4х массивов, кликать по синим ромбам и черным стрелочкам в окошке Трапа *)
	END Линейный;

	PROCEDURE ДелениемПополам*; (* к разделу 1.8.2 *)
		VAR
			a: POINTER TO ARRAY OF INTEGER; (* указатель на массив, в которых поиск *)
			N: INTEGER; (* кол-во элементов, среди которых ищем *)
			n: INTEGER; (* позиция искомого значения *)
			x: INTEGER; (* искомое значение или "аргумент поиска" *)
			L, R, m: INTEGER;
			found: BOOLEAN;
	BEGIN
		Log.Ln;
		Log.String('Проверяем поиск делением пополам:');  Log.Ln;
		
		N := 100000;
		n := ( 3 * N ) DIV 4;
		
		(* Пример 1. В массиве нет искомого значения *)
		NEW( a, N );
		InitSorted( a ); (* возрастающие положительные *)
		x := 0;
		
		(* фрагмент из книги, с.51 внизу: ******************************)
		L := 0;  R := N - 1;  found := FALSE;
		WHILE ( L <= R ) & ~found DO
			m := ( L + R ) DIV 2; (* любое значение между L и R *)
			IF  a[ m ] = x  THEN
				found :=  TRUE
			ELSIF  a[ m ] < x  THEN
				L := m + 1
			ELSE
				R := m - 1
			END
		END;
		(* конец фрагмента ******************************************)
		ASSERT( ~found ); (* не нашли *)
		Log.String('Выполнен пример 1.');  Log.Ln;
		
		(* Пример 2. В массиве ровно одно искомое значение *)
		NEW( a, N );
		InitSorted( a ); (* возрастающие положительные *)
		x := a[ n ]; (* искомое значение в массиве *)
		
		L := 0;  R := N - 1;  found := FALSE;
		WHILE ( L <= R ) & ~found DO
			m := ( L + R ) DIV 2; (* любое значение между L и R *)
			IF  a[ m ] = x  THEN
				found :=  TRUE
			ELSIF  a[ m ] < x  THEN
				L := m + 1
			ELSE
				R := m - 1
			END
		END;
		ASSERT( m = n ); (* т.е. успешно нашли позицию значения x *)
		Log.String('Выполнен пример 2.');  Log.Ln;
		
		(* Пример 3. В массиве искомое значение в нескольких экземплярах *)
		NEW( a, N );
		InitSorted( a ); (* возрастающие положительные *)
		x := a[ n ]; (* искомое значение в массиве *)
		a[ n+1 ] := x; (* чтобы усложнить жизнь *)
		a[ n-1 ] := x; (* чтобы усложнить жизнь *)
		
		L := 0;  R := N - 1;  found := FALSE;
		WHILE ( L <= R ) & ~found DO
			m := ( L + R ) DIV 2; (* любое значение между L и R *)
			IF  a[ m ] = x  THEN
				found :=  TRUE
			ELSIF  a[ m ] < x  THEN
				L := m + 1
			ELSE
				R := m - 1
			END
		END;
		ASSERT( ( m = n ) OR ( m = n-1 ) OR ( m = n+1) ); (* т.е. успешно нашли позицию значения x *)
		Log.Int( n );  Log.Int( m );  Log.Ln;
		Log.String('Выполнен пример 3.');  Log.Ln;
		
		(* Пример 4. Немного ускоренный вариант, с.52 *)
		NEW( a, N );
		InitSorted( a ); (* возрастающие положительные *)
		x := a[ n ]; (* искомое значение в массиве *)

		(* фрагмент из книги, с.52 внизу: *********************************)
		L := 0;  R := N;
		WHILE  L < R  DO
			m := (L+R) DIV 2;
			IF a[m] < x THEN L := m+1 ELSE R := m END
		END;
		(* конец фрагмента ********************************************)
		ASSERT( ( L = n ) OR ( L = n+1) );
		Log.Int( n );  Log.Int( L );  Log.Ln;
		Log.String('Выполнен пример 4.');  Log.Ln;
	
	END ДелениемПополам;
	
END  ADruS18_Поиск.


ADruS18_Поиск.Линейный   При выполнении выскочит окошко Trap из-за вставленной в конце процедуры команды HALT(0). Это чтобы можно было заглянуть в содержимое всех 4х массивов, для чего кликать по синим ромбам и черным стрелочкам в окошке Трапа. 	
	Закрывается окошко Трапа обычным способом, и можно продолжать:
	
ADruS18_Поиск.ДелениемПополам