Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
St@nton
3 / 3 / 2
Регистрация: 04.01.2013
Сообщений: 72
1

Разделяй и властвуй: сумма произведений попарных элементов массивов

25.04.2015, 21:49. Просмотров 571. Ответов 5
Метки нет (Все метки)

Всем привет. Есть задача. Дан массив А из 150 чисел, который начинается с 2 и каждый следующий элемент больше предыдущего в три раза минус один. Т.е. Xn = Xn-1 * 3 - 1. Массив A = [2, 5, 14, 41, 122, ...].
Пользователь вводит натуральное число userIput.
Нужно найти массив В такой же длины (т.е. 150), элементы которого принадлежат множеству {-1, 0, 1} и такой, что сумма произведений попарных элементов массива А и массива В равнялась бы введённому пользователем числу.

Пример: (для наглядности попарные элементы массивов пишу друг под другом)

userIput = 3;
A = [ 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, ...].
Result: B = [-1, 1, 0, 0, 0, 0, ...] , т.е. все остальные элементы равны нулю.
Т.е.: -2 + 5 = 3

userIput = 30000;
A = [ 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, ...].
Result: B = [ 1, 0, -1, 0, 1, 1, 0, 0, 0, ...] , т.е. все остальные элементы равны нулю.
Т.е.: 2 - 14 + 122 + 365 + 29525 = 30000

Мне кажется, что тут скорее нужно сначала получить все возможные перестановки, но дело в том, что задачу нужно решить с помощью метода разделяй и властвуй, а так же применив принцип динамического программирования. Но я что-то никак не пойму, что тут можно разделить и над чем потом властвовать.
Может кто сталкивался с подобной задачей. Подскажете принцип? Только не принцип метода разделяй и властвуй, а принцип решения конкретно этой задачи.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2015, 21:49
Ответы с готовыми решениями:

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

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

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

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

Для двух массивов получите сумму попарных произведений их членов (скалярное произведение)
Для двух массивов получите сумму попарных произведений их членов (скалярное произведение).

5
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
27.04.2015, 09:14 2
"Разделяй и властвуй" означает что ты сможешь перефразировать задачу таким образом, что станет возможно разбить её на две или более таких же задач "размером поменьше", что дает возможность решать через рекурсию.
Согласно Википедии, чтобы подтвердить что ты можешь сделать рекурсию сначала следует доказать правильность решения через метод математической индукции.

Мне кажется, что постановка задачи не полная, не указан первый элемент последовательности, и при проверке возможности решения задачи на вводимых числах от 1 до 10 выясняется что (на основе набора чисел из предложенной последовательности-примера) не все числа можно так выразить. А вот если добавить число "1" в начало последовательности, то решение сразу находится для всех выбранных чисел от 1 до 10.
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
27.04.2015, 11:51 3
по сути вам нужно набрать число http://www.cyberforum.ru/cgi-bin/latex.cgi?userInput с помощью слагаемых из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{ \ A[1], \ -A[1], \ A[2], \ -A[2], \ ... \ , \ A[150], \ -A[150] \ }. ну это легко решается за http://www.cyberforum.ru/cgi-bin/latex.cgi?\mathcal{O}(|A| \ \cdot \ userInput). алгоритм вроде ровно такой же как и в рюкзаке.
1
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,522
27.04.2015, 22:48 4
ИМХО можно решить жадным алгоритмом.
А как тут применить "разделяй и властвуй", не представляю. Разве что заменить логарифм бинарным поиском и назвать его (бинарный поиск) "разделяй и властвуй".

Добавлено через 4 часа 24 минуты
Каждое слагаемое вычисляется за О(1).
В строке 19 я добавляю 1. Но так как в условии ряд начинается с 2, то на самом деле нужно сигнализировать, что решения нет.

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()
{
    var num = BigInteger.Parse("1298475703294438754389752394");
    var res = FindArray(num);
    foreach(var n in res)
        Console.WriteLine(n);
}
 
List<BigInteger> FindArray(BigInteger num)
{
    var num0 = num;
    var list = new List<BigInteger>();
    BigInteger lastNum = 0;
    var sign = 1;
    while(num > 0)
    {
        if(num == 1 )
        {
            list.Add(sign);
            break; // False
        }
        
        var n = (int)BigInteger.Log(num*4-1, 3)-1;
        var pow3n = BigInteger.Pow(3,n);
        var xn = pow3n/2 + 1; 
        var xn1 = xn*3 - 1;
        var sumn1 = (pow3n + 2*n - 1)/4 - 1 + xn;
        if(xn1 < num)
        {
            sumn1 += xn1;
            xn = xn1;
            xn1 = xn*3 - 1;
        }
        
        Debug.Assert(xn <= num && num <= xn1, string.Format("num = {0}, n = {1}, xn = {2}, xn1 = {3}", num, n, xn, xn1));
        
        if(sumn1 < num || lastNum != xn1 && (xn1 - sumn1) == num)
        {
            list.Add(sign*xn1);
            lastNum = xn1;
            num = xn1 - num;
            sign = -sign;
        }
        else
        {
            list.Add(sign*xn);
            lastNum = xn;
            num = num - xn;
        }
    }
    
    Debug.Assert(list.Aggregate((a,c) => a + c) == num0, string.Format( "{0} != {1}", num0, list.Aggregate((a,c) => a + c)));
    
    return list; // True
}
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
28.04.2015, 09:14 5
Если я не ошибся, то не рекурсивная формула
http://www.cyberforum.ru/cgi-bin/latex.cgi?A[k]={3}^{k}-{3}^{k-1}-{3}^{k-2}-....-{3}^{1}-*{3}^{0}
отсюда сумма первых элементов от нулевого (A[0]=1) до К
http://www.cyberforum.ru/cgi-bin/latex.cgi?S[k]={3}^{k}-0*{3}^{k-1}-1*{3}^{k-2}-2*{3}^{k-3}-....+(2-k)*{3}^{1}+(1-k)*{3}^{0}
Может эти формулы и не понадобятся, но пусть будут.
Далее делаем рекурсивный алгоритм:
находим http://www.cyberforum.ru/cgi-bin/latex.cgi?K: S[k]\geq N > S[k-1]
очевидно, что K-тый элемент нужно брать со знаком "+"
находим число M = N-A[k]
если М = 0 то нужно остановиться
если M > 0 то запускаем алгоритм рекурсивно для N = M
если М < 0 то запускаем алгоритм рекурсивно для N = -M, и с условием что все последующие полученные знаки нужно инвертировать.
0
Shamil1
Модератор
2258 / 1541 / 351
Регистрация: 26.03.2015
Сообщений: 5,522
28.04.2015, 13:09 6
У меня код немного грязноватый из-за того что я не вычистил остатки предыдущих вариантов.

Форумулы:
http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n} = (3^n - 1)/2 + 1
http://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n} = (3^{n+1} + 2n + 1)/4

Алгоритм:
1. Находим http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n} и http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+1} такие, что http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n} \leq M \leq x_{n+1}.

Числа http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+2} и больше не могут участвовать в разложении, так как http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+2} - s_{n+1} > s_{n+1} \geq num. То есть, если мы включим число http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+2}, то даже если мы включим все меньшие с противоположным знаком, результат будет больше, чем http://www.cyberforum.ru/cgi-bin/latex.cgi?M.

2. Находим сумму http://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n}.

a. Если http://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n} < M, то http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+1} должно участвовать в разложении.
b. Если http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+1} - s_{n} > M, то http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+1} не может участвовать в разложении, а http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n} должно участвовать в разложении, так как http://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n-1} < x_{n} \leq M.
c. Числа http://www.cyberforum.ru/cgi-bin/latex.cgi?x_{n+1} - s_{n} \leq M \leq s_{n} можно было бы разложить двумя способами, если бы наш ряд начинался с 1. А так, один из способов может не сработать... и мы не знаем, какой.

3. Вычитаем найденный множитель из числа. (В случае 2с надо попробовать оба варианта.)
Получаем ту же задачу, но для меньшего числа. Переходим к пункту 1.


А вот код с поправками для правильной обработки отсутствия 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
56
57
58
List<BigInteger> FindArray(BigInteger num, BigInteger lastNum)
{
    var num0 = num;
    var list = new List<BigInteger>();
    var sign = 1;
    while(num > 0)
    {
        if(num == 1 )
        {
            list.Add(sign);
            return null; // False
        }
        
        var n = (int)BigInteger.Log(num, 3);
        var pow3n = BigInteger.Pow(3,n);
        var xn = pow3n/2 + 1; 
        var xn1 = xn*3 - 1;
        var sumn1 = (pow3n + 2*n - 1)/4 - 1 + xn;
        if(xn1 < num)
        {
            sumn1 += xn1;
            xn = xn1;
            xn1 = xn*3 - 1;
        }
        
        Debug.Assert(xn <= num && num <= xn1, string.Format("num = {0}, n = {1}, xn = {2}, xn1 = {3}", num, n, xn, xn1));
        
        if(sumn1 < num)
        {
            list.Add(sign*xn1);
            lastNum = xn1;
            num = xn1 - num;
            sign = -sign;
            continue;
        }
        if(lastNum != xn1 && (xn1 - sumn1) <= num)
        {
            var res2 = FindArray(xn1 - num - xn, xn);
            if(res2 != null)
            {
                list.Add(sign*xn1);
                list.Add(-sign*xn);
                foreach(var x in res2)
                    list.Add(-sign*x);
                break;
            }
        }
        {
            list.Add(sign*xn);
            lastNum = xn;
            num = num - xn;
        }
    }
    
    Debug.Assert(list.Aggregate((a,c) => a + c) == num0, string.Format( "{0} != {1}", num0, list.Aggregate((a,c) => a + c)));
    
    return list; // True
}
0
28.04.2015, 13:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2015, 13:09

Разделяй и властвуй
Всем добрый вечер. Требуется написать рекурсивную функцию (методом разделяй и властвуй),...

Найти сумму попарных произведений элементов массива
Дан линейный вещественный массив а. Найти : aa+ aa+...+ aa. Спасибо

Найти сумму указанных попарных произведений элементов массива
n натуральное, a1,...,an действительные числа. Найти : a1a2n+a2a2n-1+...+anan+1


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

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

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