Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
1

Методом "разделяй и властвуй" посчитать задания

13.06.2018, 23:06. Просмотров 388. Ответов 13
Метки нет (Все метки)

Тема больше не актуальна



Всем привет, снова мучаюсь с задачей вот уже пару дней.
Ввод:
количество заданий
время за которое выполняется каждое задание(уже отсортировано по возрастанию) , пункты за задание
Заданий с одинаковыми пунктами/одинаковым временем нет.
Вывод: количество "полезных" заданий. Задание бесполезно если есть другое задание которое можно выполнить быстрей и получить больше пунктов.
Задачу решить за O(n*log (n)) с помощью парадигмы РАЗДЕЛЯЙ и ВЛАСТВУЙ
пример:
4
1 1

3 5
6 2
8 4
Вывод:
2

Еще пример:
8
2 7
3 13
6 11
7 12
10 5
11 8
14 10
1000 6
Вывод:
4

в начале counter = 1, max = 6 (из примера сверху) начинаем с конца и считаем сколько раз обновится max:
max = 6 counter = 1;
max = 10 counter = 2;
max = 12 counter = 3;
max = 13 counter = 4;

написал код без разделяй и властвуй:
C
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
33
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main () {
    int max = 0;
    int counter = 1;
    int n = 0;
    scanf("%d", &n);
    
    int array[n][2];
 
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &array[i][0], &array[i][1]);
    }
 
    int a[n];
 
    for (int i = 0; i < n; i++) {
        a[i] = array[i][1];
    }
 
    counter = 1;
    max = a[n-1];
    
    for (int i = n-1; i > 0; i--) {
        if (max < a[i]) {
            max = a[i];
            counter++;
        }
    }
    printf("%d\n", counter);
}
Возможно это ка кто связано с задачами merge sort или подсчёт инверсий (возможно тоже в сортировке с слиянием), если да то как бы этот код адаптировать к этим задачам ведь они используют метод "разделяй и властвуй"

Думаю както разделить количество на 2 и как то рекурсивно подсчитать максимумы но как

Добавлено через 1 час 25 минут
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.06.2018, 23:06
Ответы с готовыми решениями:

Поиск максимального элемента в массиве методом "разделяй и властвуй"
Я в недоумении, поиск максимального элемента в массиве сводится к цикличной проверке всех его...

Методом "разделяй и властвуй" построить башни
Всем привет, последняя задачу которую нужно решить) Есть бесконечное количество блоков размера...

В каких случаях лучше использовать алгоритм "разделяй и властвуй"?
Подскажите, в каких случаях лучше использовать алгоритм разделяй и властвуй? Как оформить этот...

Разделяй и властвуй: сумма произведений попарных элементов массивов
Всем привет. Есть задача. Дан массив А из 150 чисел, который начинается с 2 и каждый следующий...

Поиск и вывод строки по заданному шаблону (с использованием симоволов "?", "*", "+")
Добрый день Имею такое задание: необходимо написать программу, которая сможет найти в файле...

13
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
14.06.2018, 14:41 2
про разделяй и властвуй я хз, но можно по-другому. давайте все пункты за задания умножим на -1, получим задачу "найдите максимальную цепочку пар http://www.cyberforum.ru/cgi-bin/latex.cgi?\{ \ (a_1, b_1), \ (a_2, b_2), \dots \ \} \ : \ a_i \ < \ a_{i+1} \  & \  b_i \ < \ b_{i+1}. если правильно обходить точки, то вроде достаточно только дерева отрезков для суммы, чтобы отвечать на запросы "сколько слева от меня точек с координатой (у, например) меньше, чем У.
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,525
14.06.2018, 14:59 3
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
считаем сколько раз обновится max
Неправильно.
Для a и b возможны четыре ситуации:
1. a == b
2. a < b
3. a > b
4. ни одно из вышеперечисленных

Поэтому "максов" может быть несколько.
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
14.06.2018, 15:35  [ТС] 4
Цитата Сообщение от Shamil1 Посмотреть сообщение
Неправильно.
Для a и b возможны четыре ситуации:
1. a == b
2. a < b
3. a > b
4. ни одно из вышеперечисленных
Поэтому "максов" может быть несколько.
Если у Вас a и b это количество пунктов за задания то a == b не может быть
4. ни одно из вышеперечисленных. Тоже нет, либо а больше b либо наоборот.
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Заданий с одинаковыми пунктами/одинаковым временем нет.
Если a время b пункты за задания. В программе я все "а" просто выкинул (возможно они нужны просто что б задание смысл имело) и записал все "b" в массив потом с конца посчитал сколько раз макс обновился.
Тема не актуальна, программа прошла тест хоть и без "разделяй и властвуй".
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,525
14.06.2018, 17:59 5
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Если у Вас a и b это количество пунктов за задания то a == b не может быть
4. ни одно из вышеперечисленных. Тоже нет, либо а больше b либо наоборот.
В каждой строке два числа. a и b - это пары чисел.

Цитата Сообщение от Dimitrij1 Посмотреть сообщение
В программе я все "а" просто выкинул
Пример:
3 3
1 5

Бесполезных заданий нет. А что говорит Ваша программа?
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
14.06.2018, 18:09  [ТС] 6
Цитата Сообщение от Shamil1 Посмотреть сообщение
Пример:
3 3
1 5
Бесполезных заданий нет. А что говорит Ваша программа?
Такого не может быть. Все задания отсортированы по времени по возрастанию. Нижнее время всегда больше предыдущего верхнего
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,525
14.06.2018, 20:21 7
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Такого не может быть. Все задания отсортированы по времени по возрастанию.
Откуда мне знать, какое из чисел время?

Пример:
1 5
3 3
Есть бесполезное задание. Что говорит Ваша программа?
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
14.06.2018, 20:49  [ТС] 8
Цитата Сообщение от Shamil1 Посмотреть сообщение
Пример:
1 5
3 3
Есть бесполезное задание. Что говорит Ваша программа?
Выдаёт: 1
Последнее так и так выполняется и цикл идёт от 1 (количества заданий минус один) до 0, один раз выполняется цикл и всё потом i = 0 и второй максимум не берётся

Добавлено через 9 минут
Вообщем мне эту задачу нужно решить методом "разделяй и властвуй" и провести анализ алгоритма и его сложности и показать корректность, где про это всё можно почитать? Книги есть но в них сложным языком как то написано
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,525
14.06.2018, 22:01 9
Dimitrij1,
У Вас алгоритм O(n). За такое время задача ИМХО не решается. Отсюда предположу, что алгоритм неправильный.

Добавлено через 3 минуты
Пример:
1 99
тут список из 98 бесполезных заданий
100 100

Правильно я понимаю, что максимум обновляется только один раз?
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
15.06.2018, 01:08  [ТС] 10
Цитата Сообщение от Shamil1 Посмотреть сообщение
Пример:
1 99
тут список из 98 бесполезных заданий
100 100
Правильно я понимаю, что максимум обновляется только один раз?
Тут он не обновляется а становится 100 (счет начинается с конца) и счетчик просто на 1 ставится, потом если вверх идти то чисел больше 100 нету поэтому счетчик больше не обновляется.
Кажется я не совсем правильно описал задачу, может я и сам не до конца понял. В любом случаи в ответе я уже не заинтересован, программа прошла тест хоть и без разделяй и властвуй.
Тут счетчик максимума не обновляется потому что изначально максимум 100 и счетчик = 1, последнее задание становится максимум и с него начинается счет начиная с 1.
Тут "нет" бесполезных. Бесполезные появляются только тогда когда существует задание на которое требуется меньше времени (цифра слева) и которое приносит больше пунктов (цифра справа) то есть которое лежит выше по списку.
Если 2 задания то ответ скорее всего будет всегда 1 потому что либо одно приносит больше пунктов чем другое либо наоборот а одинаковыми они не могу быть поэтому одно из двух всегда полезней другого.
Вот еще пример
Ввод: 3
1 1 (первое задание)
2 5 (второе задание)
3 4 (третье задание)
Ответ: 2
начинаем с конца
максимум: 4 счетчик: 1 (инициализация)
максимум: 5 счетчик: 2 (максимум поменялся)
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,525
15.06.2018, 12:13 11
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Если 2 задания то ответ скорее всего будет всегда 1 потому что либо одно приносит больше пунктов чем другое либо наоборот а одинаковыми они не могу быть поэтому одно из двух всегда полезней другого.
Если больше пунктов приносит то, что занимает больше времени, то нельзя сказать, какое из них полезней. Поэтому "одно из двух всегда полезней другого" не выполняется.

Цитата Сообщение от Dimitrij1 Посмотреть сообщение
В любом случаи в ответе я уже не заинтересован, программа прошла тест хоть и без разделяй и властвуй.
Вы разобраться с задачей хотели или галочку за тест получить?

Ещё раз внимательно прочитал условие. Оказывается, надо выводить количество полезных заданий. Тогда пример должен быть другим.
Ввод:
2
1 1
2 2

Вывод:
1

Правильный вывод:
2

Добавлено через 1 час 40 минут
Задание бесполезно если есть другое задание которое можно выполнить быстрей и получить больше пунктов. То есть, задание полезно, если слева от него нет задания с большим количеством пунктов. Можно использовать дерево отрезков для нахождения максимума пунктов слева. (Я бы так и делал).

Решение с использованием метода "разделяй и властвуй".
F#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
let solve (a : int array) =
    let rec f imin imax pmax =
        if imin = imax then 
            if a.[imin] > pmax then
                a.[imin], 1
            else
                pmax, 0
        else
            let imid = (imin + imax)/2
            let pmax1, cnt1 = f imin imid pmax
            let pmax2, cnt2 = f (imid+1) imax pmax1
            pmax2, cnt1+cnt2
    let _, cnt = f 0 (Array.length a - 1) 0
    cnt
Код я не тестировал - возможны ошибки.

Добавлено через 1 минуту
Цитата Сообщение от Dimitrij1 Посмотреть сообщение
Еще пример:
8
2 7
3 13
6 11
7 12
10 5
11 8
14 10
1000 6
Вывод:
4
Откуда этот пример?
Если я правильно понимаю, то тут только 2 полезных задания. Все задания после "3 13" бесполезны, так как требуют времени больше 3, а пунктов дают меньше 13.
1
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
16.06.2018, 12:55  [ТС] 12
Цитата Сообщение от Shamil1 Посмотреть сообщение
Откуда этот пример?
Если я правильно понимаю, то тут только 2 полезных задания. Все задания после "3 13" бесполезны, так как требуют времени больше 3, а пунктов дают меньше 13.
Этот пример из задачи, он правильный.

8
2 7
3 13
6 11
7 12
10 5
11 8
14 10
1000 6
Вывод:
4
Вот как это работает. Рассмотрим только эти числа:
7, 13, 11, 12, 5, 8, 10, 6
Будем начинать с конца и идти влево потому что слева задания с меньшим временем поэтому только они нас интересуют и будем искать такое которое даёт больше пунктов чем актуальный максимум. Начиная с конца инициализируем счетчик 1, максимум 6. Далее максимум обновляется 3 раза. Получается:
8
2 7
̶3̶ ̶1̶3̶ берем в ответ потому что 13 больше 12
6 11
̶7̶ ̶1̶2̶ берём в ответ потому что 12 больше 10
10 5
11 8
̶1̶4̶ ̶1̶0̶ берём ответ потому что 10 больше 6
̶1̶0̶0̶0̶ ̶6̶ изначально берём в ответ
Максимум обновился 3 раза, счетчик изначально был 1 и увеличился на 3 = 4

Цитата Сообщение от Shamil1 Посмотреть сообщение
Ввод:
2
1 1
2 2
Вывод:
1
Тут максимум изначально 2 и по ходу программы больше не обновляется.

Цитата Сообщение от Shamil1 Посмотреть сообщение
Можно использовать дерево отрезков для нахождения максимума пунктов слева. (Я бы так и делал).
Спасибо рассмотрю этот вариант

Добавлено через 8 минут
Скорее задания не зачеркиваются а добавляются в ответ
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,525
16.06.2018, 19:14 13
Ничего не понимаю. Задание бесполезно если есть другое задание которое можно выполнить быстрей и получить больше пунктов. Разве задание 1000 6 не бесполезно? Время 1000, а пунктов всего 6 дают.
0
Dimitrij1
1 / 1 / 6
Регистрация: 31.01.2016
Сообщений: 82
18.06.2018, 17:27  [ТС] 14
Насколько я понял, когда начинаю делать задания, изначально никакого нету, поэтому максимум 0. Начиная с конца вижу 6, 6 больше 0, максимум обновился 1 раз. Потом 10 больше 6, обновление второй раз и потом с 12 пунктами тоже полюбому буду делать вместо тех что с 8 и 5.и вместо 11 лучше сделать то что даёт 13 и требует меньше времени. Начинаю с конца пото му что задания по времени в возрастающем порядке отсортированы.
0
18.06.2018, 17:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.06.2018, 17:27

Алгоритм роста "квадрата" или как работает "черный ящик"
Хочу спросить совета по нахождению формулы для &quot;черного ящика&quot;, который на входе принимает 2...

Из пункта "А" приехать в пункт "Б" и показать возможные траектории движения
Задача вот такая: надо из пункта &quot;А&quot; приехать в пункт &quot;Б&quot; и показать возможные траектории движения....

Критерии вхождения "шара" в "ящик"
Дано: Ящик (С параметрами: высота, длина, ширина), n шаров в этом ящике (С радиусами ri)....


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru