Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача на массив
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
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]);

у кого есть ещё какие-нибудь идеи?
Lapp
Цитата(Konstantin @ 15.10.2009 2:24) *
у кого есть ещё какие-нибудь идеи?
Как, например, тебе идея написать процедуру Sort?
Konstantin
Цитата(Lapp @ 15.10.2009 1:41) *

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

Идея прелестная, я мыслил в этом направлении, но не получилось... Если можно подскажите хотя бы в каком направлении думать в написании этого алгоритма
volvo
Цитата
у кого есть ещё какие-нибудь идеи?
Идея проста, как хозяйственное мыло: использовать множества (если N не превышает 255): [1 .. 5] - [5, 1, 3, 6, 2] выдаст тебе как раз [4], а уж определить, что содержится во множестве - это дело техники. Заметь, никаких сортировок (что само по себе длительная операция), все делается за один проход по массиву + быстрая операция "вычитания" множеств...
Lapp
Цитата(Konstantin @ 15.10.2009 3:01) *
в каком направлении думать в написании этого алгоритма
Вот в этом: Методы сортировок


Добавлено через 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
Цитата(volvo @ 15.10.2009 2:07) *

Идея проста, как хозяйственное мыло: использовать множества (если 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
Цитата(volvo @ 15.10.2009 13:17) *

Собственно, куда уже подробнее? Разве что кодом:
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.


Всё понял, спасибо большое. Вопрос решён.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.