Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Алгоритмы Алгоритм нахождения среднего значения http://www.cyberforum.ru/algorithms/thread2205237.html
Здравствуйте, помогите написать алгоритм нахождения среднего значения между числами, которые берутся из синусоиды через каждые 8мс. Сначала мы должны найти среднее в промежутке от 1...7, второе...
Список Алгоритмы
Приветствую. Задача реализовать список. Он уже реализован мной, однако нужно уточнить одну вещь. В условии сказано, что в списке есть повторяющиеся элементы и при удалении надо соответственно...
Протокол Фейга — Фиата — Шамира Алгоритмы
Здравствуйте, пытаюсь реализовать идентификацию с нулевым разглашением с помощью протокола Протокол Фейга — Фиата — Шамира. Имеется следующий код: public static void main(String args) throws...
Алгоритмы рекуррентное отношение помогите решить ,найти точную оценку T(N) = 2T(N — 1) + N если T(1) = 2; http://www.cyberforum.ru/algorithms/thread2205129.html
Алгоритмы Найти наименьшую сумму n слагаемых для ряда чисел http://www.cyberforum.ru/algorithms/thread2204324.html
Вот, дан ряд чисел, и дано количество слагаемых, а найти нужно наименьшую сумму для каких то n чисел писал на c# примерно такое using System; using System.Globalization; namespace samolet {...
Алгоритмы Тема на диплом связанная с алгоритмами
Учусь на 3 курсе, дали задание выбрать тему на диплом. Большинство тем в нашем университете всегда звучит как "Веб-сайт + 11-2 слова", "Интернет-магазин". Мне как-то не особо заниматься этим....
Быстрые алгоритмы нахождения чисел-палиндромов на заданном промежутке Алгоритмы
Какие существуют быстрые алгоритмы нахождения палиндромов на промежутке?
Алгоритмы Кольцевой буффер Делаю задания с книги Algorithms, 4th Edition by Robert Sedgewick : 1.3.37 Кольцевой буфер. Кольцевой или кольцевая очередь - это структура данных с правилом FIFO фиксированного размера N,... http://www.cyberforum.ru/algorithms/thread2203880.html
Алгоритмы Количество доменов в матрице http://www.cyberforum.ru/algorithms/thread2203692.html
Необходимо посчитать количество доменов в матрице. Пример матрицы: 1 0 0 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0
Алгоритмы Зоны влияния Всем привет, Есть матрица n на n элементов. Каждый элемент может принимать в себя одно из двух значений 0 или 1. Допустим пользователь оградил некую территорию в матрице. <- ( На рисунке ниже... http://www.cyberforum.ru/algorithms/thread2201381.html
Shamil1
Модератор
2270 / 1567 / 352
Регистрация: 26.03.2015
Сообщений: 5,651
05.03.2018, 13:09 0

Задача на подмножества

05.03.2018, 13:09. Просмотров 873. Ответов 4
Метки (Все метки)

Лучший ответ Сообщение было отмечено Chvick как решение

Решение

Цитата Сообщение от Chvick Посмотреть сообщение
каким методом решать
Дерево отрезков.


Вершину дерева нужно определить так, чтобы можно было складывать (комбинировать) две вершины:
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
public struct SegmentNode
{
    public bool Result;
    public int Left;
    public int Right;
    public bool HasValue;
    
    public SegmentNode(int value)
    {
        Result = true;
        Left = value;
        Right = value;
        HasValue = true;
    }
    
    public static SegmentNode operator+(SegmentNode x, SegmentNode y)
    {
        if(!x.HasValue) return y;
        if(!y.HasValue) return x;
        return new SegmentNode
        {
            Result = x.Result && y.Result && x.Right <= y.Left,
            Left = x.Left,
            Right = y.Right,
            HasValue = true,
        };
    }
}



Стандартное дерево отрезков:
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class SegmentTree
{
    public SegmentTree(int[] a) 
    {
        last = a.Length - 1;
        tree = new SegmentNode[4 * a.Length];   
        Build(a, 1, 0, last);
    }
    
    public bool Request(int l, int r)
    {
        return Request(1, 0, last, l, r).Result; 
    }
    
    public void Update(int pos, int newValue)
    {
        Update(1, 0, last, pos, newValue);
    }
    
    int last;
    SegmentNode[] tree;
 
    void Build(int[] a, int v, int tl, int tr)
    {
        if (tl == tr)
        {
            tree[v] = new SegmentNode(a[tl]);
            return;
        }
        
        int tm = (tl + tr) / 2;
        Build(a, v * 2, tl, tm);
        Build(a, v * 2 + 1, tm + 1, tr);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
    
    SegmentNode Request(int v, int tl, int tr, int l, int r)
    {
        if (l > r)
            return new SegmentNode();
            
        if (l == tl && r == tr)
            return tree[v];
            
        int tm = (tl + tr) / 2;
        return Request(v * 2, tl, tm, l, Math.Min(r, tm)) + Request(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r);
    }
 
    void Update(int v, int tl, int tr, int pos, int new_val)
    {
        if (tl == tr)
        {
            tree[v] = new SegmentNode(new_val);
            return;
        }
        
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            Update(v * 2, tl, tm, pos, new_val);
        else
            Update(v * 2 + 1, tm + 1, tr, pos, new_val);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
}

Программа для тестирования:
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void Main()
{
    Test1();
}
 
void Test1()
{
    var rnd = new Random();
    int n = 100;
    int k = 5;
    int[] a = Enumerable.Repeat(rnd, n).Select(x => x.Next(-k * n, k * n + 1)).ToArray();
    //Console.WriteLine(string.Join(", ", a));
    var st = new SegmentTree(a);
    CheckAll(a, st);
    
    // random updates
    for(int i = 0; i < n/2; i++)
    {
        int j = rnd.Next(0, n);
        int val = rnd.Next(-k * n, k * n + 1);
        a[j] = val;
        //Console.WriteLine($"Update {i}: a[{j}] = {val};");
        st.Update(j, val);
        CheckAll(a, st);
    }
 
    // check all requests
    Console.WriteLine("OK");
}
 
void CheckAll(int[] a, SegmentTree st)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i; j < a.Length; j++)
        {
            var res = st.Request(i, j);
            var res2 = Check(a, i, j);
            if (res != res2)
            {
                Console.WriteLine(string.Join(", ", a));
                //st.t.Dump();
                throw new ApplicationException($"{res} != {res2} for [{i}, {j}]");
            }
        }
}
 
bool Check(int[] a, int l, int r)
{
    for (int i = l + 1; i <= r; i++)
    {
        if(a[i] < a[i-1])
            return false;
    }
    return true;
}


Вернуться к обсуждению:
Задача на подмножества
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2018, 13:09

подмножества
Задано натуральное число n, определить и вывести на экран (по одному разу) все подмножества...

Подмножества множества {0,....,n-1}
Сгенерировать все подмножества данного N-элементного множества {0,....,n-1}. Решение: Заведем...

подмножества и множества
Разработать алгоритм генерации всех подмножеств n-элемента множества Помогите решить ее!

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