Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Битовый массив

Автор: Coder 23.12.2004, 13:35

в книге "Жемчужины программирования" (Джон Бентли) описывается идея сортировки неповторяющихся чисел битовым массивом. Предлагается отсортировать телефонные номера США.
Так вот в задаче говорится что на вход поступают положителяные целые числа не превышающие N=10^7. Так вот, как я понимаю, по идее битовой сортировки, необходимо объявить массив типа TBit (0..1) диапозона [Nmin..N]. (например массив для сортировки номеров для моего города имеет вид [30000..49999]). Компилятор (BP 7) не признает числа 10^7. Как быть?
И еще постоянно говорится про неограниченную опереративную память. Я пробовал использовать динамическую, но результат один - ошибка. Может кто сталкивался с проблеммой объявления больших массивов, подскажите пожалуйста (если можно с кодом на Pascal`e). Или посоветуйте каким Pascal компилятором пользоватся, если это из-за него.

Автор: Петрович 23.12.2004, 14:01

Цитата(Coder @ 23.12.2004, 14:35)

Компилятор (BP 7) не признает числа 10^7. Как быть?

Что значит не признает? Проблема именно с '10^7' или с '9999999'?
Если с последним, то используй тип Longint. Если с первым, то естественно, это ведь не число а выражение с операцией возведения в степень (^) которой нет в Pascal'е.

Автор: Coder 24.12.2004, 09:30

Я имел в виду "99999...". так как объявить такой массив, далаю так

Код


Const
  n = 10000000; { 10^7 }
type
  TBit = 0..1;  
var
  m : array[1...N] of TBit;

выдает ошибку 23 (Ordinal type expected). так вот как с ней бороться?

Автор: chaos 24.12.2004, 16:16

я делаю обычно так(правда на делфи)

Код


var
  n: Integer; 
  dMas: array of Byte;

begin
  readLn(N);
  SetLength(dMas, N);
  ...........................
  Finalize(dMas);
end.

Добавлено @ 16:22
А почему бы не использовать действительно БИТОВЫЙ массив:

Код


var
  Bitmap: array [0..999] of Byte;

вот допустим так мы получим 8000 бит и обращатся к каждому через and

Код


function getStateBit(n: Integer): boolean;
var a,b: Byte;
begin
  a:= Bitmap[n div 8];
  b:= n-(n div 8);
  if ((a shl b) and 1) = 0 then getStateBit:= false else getStateBit:=true;
end;

Автор: Coder 25.12.2004, 01:28

хм... попробуем...

Автор: ovr2000 28.12.2004, 17:54

Паскаль по умолчанию перечисление конвертит в integer
Посчитаем кол-во памяти 10 млн*2=20Мбайт, не говоря о том, что массив в принипе ограничен 16-битной ссылкой
Т.е. массив должен быть не более 64 кбайта (а не 64к элементов)