Страница 1 из 1
Нахождение наибольшей подпоследовательности в массиве
Добавлено: 19 дек 2005, 22:50
Vladimir2
Большая просьба, помогите написать на Delphi програмку по такому заданию
Вводится массив. Найти в нем длину самой длинной возрастающей подпоследовательности. Например, в массиве
5 1 4 6 2 10
самая длинная возрастающая подпоследовательность имеет длину 3.
Заранее благодарю.
Добавлено: 19 дек 2005, 22:57
Oscar
1. Отсортировать.
2. Установить счётчик в 0.
3. Проходить по массиву с минимума до максимума
4. Если разница между предидущим элементом и нынешним больше единицы - устанавливать счётчик в 1, иначе инкрементировать счётчик.
Сорри, делфи под рукой нет.
Добавлено: 19 дек 2005, 23:01
Vladimir2
А если без сортировки?
Добавлено: 19 дек 2005, 23:13
Oscar
В задании сказано "без сортировки", или почему нельзя?
Если нужно сохранить исходный массив - его можно просто скопировать перед этим всем.
Если же сортировать действительно нельзя (что меня довольно таки удивляет), то нужно хорошенько задуматься...
Добавлено: 19 дек 2005, 23:18
Vladimir2
Суть такая, через listbox вводится массив "как есть". Необходимо прошерстить введенный массив, найти подпоследоватедьности, найти наибольшую подпоследовательновсть, вывести колличество знаков в ней.
Код: Выделить всё
begin
count:=0;
x:=0;
y:=0;
for i:=1 to length(mas) do
if mas[i+1] > mas[i] then
inc(count)
else x:=count; count:=0;
if x > y then y:=x;
showmessage(inttostr(y));
end;
Такой вариант не правилен, т.к. счетчик срабатывает на начало любой последовательности.
Добавлено: 19 дек 2005, 23:56
Oscar
Код: Выделить всё
<pre>
<?php
$input = array();
$max = 30;
for($i = 0; $i < $max; $i++) {
$input[$i] = rand(0, $max);
}
$input = array_unique($input);
/*
$input[0] = 5;
$input[1] = 1;
$input[2] = 4;
$input[3] = 6;
$input[4] = 2;
$input[5] = 10;
*/
$longestSequence = 0;
if (count($input) > 0) {
$temp = $input;
sort($temp);
print_r($temp);
$first = $temp[0];
$last = $temp[0];
$tempSequence = 1;
$longestSequence = 1;
for($i = 1; $i < count($temp); $i++) {
if ($first-$temp[$i] == 1) {
$tempSequence++;
$first = $temp[$i];
} else if ($temp[$i] - $last == 1) {
$tempSequence++;
$last = $temp[$i];
} else {
if ($tempSequence > $longestSequence)
$longestSequence = $tempSequence;
$tempSequence = 1;
$first = $temp[$i];
$last = $temp[$i];
}
}
}
if ($tempSequence > $longestSequence)
$longestSequence = $tempSequence;
echo "
Longest sequence: $longestSequence\n";
?>
</pre>
Это PHP.
Нужно добавить, что у текущей последовательности есть first и last элементы (проверяемый элемент должен быть на единицу меньше first элемента, или на единицу больше last элемента, только тогда нужно инкрементировать счётчик),
И счётчик нужно иметь отдельно от конечного результата ($tempSequence - счётчик, $longestSequence - конечный результат; когда обнуляется счётчик (устанавливается в единицу), конечный результат равен максимуму между текущим значением и счётчиком; то же самое нужно проделать после цикла, для последней проверяемой последовательности).
Кроме того, первый и последний элементы нужно всегда подправлять.
Добавлено: 20 дек 2005, 00:28
Oscar
Код: Выделить всё
<?php
$input = array();
$input[0] = 5;
$input[1] = 1;
$input[2] = 4;
$input[3] = 6;
$input[4] = 2;
$input[5] = 10;
$longestSequence = 0;
if (count($input) > 0) {
$temp = $input; // COPY ARRAY (to save real values)
sort($temp); // ASCENDING SORTING
$current = $temp[0]; // init current element
$tempSequence = 1; // temporary counter
$longestSequence = 1; // result
for($i = 1; $i < count($temp); $i++) {
if (abs($current - $temp[$i]) > 1) { // |current - temp| > 1
if ($tempSequence > $longestSequence)
$longestSequence = $tempSequence; // result = max(temp, result)
$tempSequence = 1; // reset counter
} else {
$tempSequence++; // increment counter
}
$current = $temp[$i]; // update current element
}
}
if ($tempSequence > $longestSequence) // result = max(temp, result)
$longestSequence = $tempSequence; // for the last sequence
echo "
Longest sequence: $longestSequence\n"; // OUTPUT
?>
Прошу прощения, разделение на FIRST и LAST не нужно (это я уже начал было думать о неотсортированном варианте).
Нужно было всего лишь добавить разницу между счётчиком и конечным результатом, являющимся максимумом этих двух значений.