Задача на массив Опции

[Konstantin]

Добрый день. Задача звучит примерно так:
Дан массив целых чисел от 1 до N, заполненный всеми числами от 1 до N (не упорядоченно).
Проверить, все ли числа в массиве есть от 1 до N, если все- вывести 0, если нет - вывести элемент массива, на котором сбивается последовательность.
Тобишь 5 4 1 3 2 - должно вывести 0, а кпримеру 5 1 3 6 2 уже не подходит, нету четвёрки.
Из идей было отсортировать массив процедурой Sort, но в Pascal ABC она почему-то не работает. А так бы здорово получилось - сортируем элементы по возрастанию, и проверям в цикле

Код

for i:=1 to N do
if(a[i]-a[i+1]<>1) then writeln('Последовательность чисел сбивается на элементе', a[i]);

у кого есть ещё какие-нибудь идеи?

Сообщение отредактировано: Konstantin - 15.10.2009 1:25

[Lapp]

у кого есть ещё какие-нибудь идеи?

Как, например, тебе идея написать процедуру Sort?

[Konstantin]

Как, например, тебе идея написать процедуру Sort?

Идея прелестная, я мыслил в этом направлении, но не получилось... Если можно подскажите хотя бы в каком направлении думать в написании этого алгоритма

[volvo]

у кого есть ещё какие-нибудь идеи?

Идея проста, как хозяйственное мыло: использовать множества (если N не превышает 255): [1 .. 5] - [5, 1, 3, 6, 2] выдаст тебе как раз [4], а уж определить, что содержится во множестве - это дело техники. Заметь, никаких сортировок (что само по себе длительная операция), все делается за один проход по массиву + быстрая операция "вычитания" множеств...

[Lapp]

в каком направлении думать в написании этого алгоритма

Вот в этом: Методы сортировок


Добавлено через 12 мин.
Метод volvo хорош - жаль, что не для целых (как в условии)
Вот еще вариант:

const
  n=10;

var
  a,b: array[1..n]of integer;
  i: integer;

begin
  {input a}
  for i:=1 to n do b[i]:=0;
  for i:=1 to n do if a[i]<=n then b[a[i]]:=1;
  i:=1;
  while (i<=n)and(b[i]=1) do Inc(i);
  if i>n then i:=0;
  WriteLn(i)
end.

(не проверял)

[Konstantin]

Идея проста, как хозяйственное мыло: использовать множества (если N не превышает 255): [1 .. 5] - [5, 1, 3, 6, 2] выдаст тебе как раз [4], а уж определить, что содержится во множестве - это дело техники. Заметь, никаких сортировок (что само по себе длительная операция), все делается за один проход по массиву + быстрая операция "вычитания" множеств...

мм... а можно по-подробнее?

[volvo]

а можно по-подробнее?

Собственно, куда уже подробнее? Разве что кодом:

const
  n = 5; { <--- n не должно быть больше 255!!! }
  arr: array[1 .. n] of integer =
  (
    5, 1, 3, 6, 2
  );
var
  s: set of byte;
  i: integer;

begin
  s := [];
  for i := 1 to n do
    include(s, arr[i]);
  s := [1 .. n] - s;

  for i := 1 to n do
    if i in s then write(i:4);
  writeln;
end.

[Konstantin]

Собственно, куда уже подробнее? Разве что кодом:

const
  n = 5; { <--- n не должно быть больше 255!!! }
  arr: array[1 .. n] of integer =
  (
    5, 1, 3, 6, 2
  );
var
  s: set of byte;
  i: integer;

begin
  s := [];
  for i := 1 to n do
    include(s, arr[i]);
  s := [1 .. n] - s;

  for i := 1 to n do
    if i in s then write(i:4);
  writeln;
end.

Всё понял, спасибо большое. Вопрос решён.