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


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