10 / 10 / 0
Регистрация: 11.08.2011
Сообщений: 51
1

Полный перебор массива чисел

01.02.2012, 23:20. Показов 12037. Ответов 6
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте!
Помогите, пожалуйста решить задачку. Я так понимаю, нужен полный перебор. Но даже не представляю, каким образом это всё делать. Ограничение по времени - 1 сек.
Задача:
http://images.i-files.org/i/BNd6KGDo.png

Заранее огромное спасибо!!!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.02.2012, 23:20
Ответы с готовыми решениями:

Задача на полный перебор.
Расшифровать ребус, полученный в результате замены одинаковых букв одинаковыми цифрами:...

Интересная задача на полный перебор
Добрый вечер! Требуется программу, которая распределит камни в две кучи так, чтобы модуль разности...

Полный перебор (расшифровать ребус 7 * Блок = Стена)
Расшифровать ребус, полученный в результате замены одинаковых букв одинаковыми цифрами. Найти...

Полный перебор (расшифровать ребус 6 * Стена = Здание)
Расшифровать ребус, полученный в результате замены одинаковых букв одинаковыми цифрами. Найти...

6
17 / 16 / 9
Регистрация: 20.02.2011
Сообщений: 26
02.02.2012, 14:13 2
для каждого числа находишь длину наибольшей возрастающей подпоследовательности (НВП) оканчивающейся этим числом, причем если таких вариантов подпоследовательности несколько то увеличиваешь множитель для данного числа на 1.
Т.е. из примера 2 в задаче:
Для числа 5 имеем 2 варианта НВП длиной 3: 1 2 5 и 1 4 5. Следовательно множителем будет 2.
Сумма всех длин НВП для каждого числа с учитыванием множителя и будет ответом.

В решении потребуется находить НВП за NlogN, т.к. решение за квадрат не пройдет по времени.
прочитать про алгоритм можешь здесь.

ADDED:
что-то совсем ослеп)
решение за квадрат также пройдет. так что задача довольно простая.
1
10 / 10 / 0
Регистрация: 11.08.2011
Сообщений: 51
02.02.2012, 16:05  [ТС] 3
GodLikeRu, огромнейшее СПАСИБО!!!
Вы очень помогли мне!!!
0
17 / 16 / 9
Регистрация: 20.02.2011
Сообщений: 26
02.02.2012, 17:42 4
Решение не совсем верное, поэтому вот небольшая поправка:
Храним в массиве w длиной n количество подпоследовательностей длины i( 1<=i<=n).
Во время поиска НВП заполняем этот массив. Пусть a - исходный массив элементов, с[i] - длина НВП оканчивающейся элементом a[i], m[i] количество НВП длиной c[i].
Допустим, a[i] - текущий рассматриваемый элемент, a[j] - элемент, расположенный перед ним.
Pascal
1
2
3
4
5
if a[i]>a[j] then
 begin
  inc(w[2]); //увеличиваем количество последовательностей длины 2 на единицу
  inc(w[c[j]+1],m[j]); //увеличиваем количество подпоследовательностей длины c[j]+1 на количество подпоследовательностей c[j] у элемента j
 end;
Просуммировав массив w получим искомое количество вариантов запуска фейерверков.
1
10 / 10 / 0
Регистрация: 11.08.2011
Сообщений: 51
02.02.2012, 22:14  [ТС] 5
GodLikeRu, извините, я не могу понять, как посчитать массив w и m, а также, как и куда прикрепить "поправку".
Вот алгоритм нахождения длины НВП по O(n^2):
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Var
     a,d: Array[1..2000] of Integer;
     i,j,ans,N: Integer;
Begin
     readln(N);
     for i:=1 to N do
     begin
          read(a[i]);
     end;
     readln;
 
     for i:=1 to N do
     begin
          d[i] := 1;
          for j:=1 to i-1 do
          begin
               if (a[j] < a[i]) then
               begin
                    if d[j]+1 > d[i] then d[i]:=d[j]+1;
               end;
          end;
     end;
 
     ans:=d[1];
     for i:=1 to N do
     begin
          if d[i] > ans then ans:=d[i];
     end;
 
     writeln(ans);
     readln;
End.
Пожалуйста, объясните подробнее весь алгоритм, учитывая поправки.
0
17 / 16 / 9
Регистрация: 20.02.2011
Сообщений: 26
06.02.2012, 10:38 6
для каждого числа в массиве w храним количество возрастающих последовательностей в которые входит это число. просуммировав массив получим ответ на задачу.
Pascal
1
2
3
4
5
6
for i:=1 to n do
begin
w[i]:=1;
for j:=1 to i-1 do
 if a[i] > a[j] then inc(w[i],w[j]);
end;
1
10 / 10 / 0
Регистрация: 11.08.2011
Сообщений: 51
06.02.2012, 18:30  [ТС] 7
GodLikeRu, проверил, действительно работает на всех случаях!!!
Сначала даже удивился) трудная задача, и такое простое решение, но оказывается действительно мощное и верное решение!!!
Большое Вам СПАСИБО!!! Без Вас, наверно, никак бы сам не решил.
Ещё раз спасибо!!! Выручили меня!
0
06.02.2012, 18:30
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.02.2012, 18:30
Помогаю со студенческими работами здесь

Полный перебор чисел массива
Доброго вам времени суток. Количество элементов массива задавать вручную - собственно N. Массив...

Полный перебор и сокращенный перебор, путем исключения одного цикла
1) Разработать на основе метода полного перебора программу razmen1 для решения задачи о способах...

Полный перебор
Дано множество целых чисел. Требуется разбить множество на две части суммы элементов которых равны....

Полный перебор
Всем привет. Когда у нас есть фиксированное количество переменных и для них есть фиксированная...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru