Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++]Задача с массивами


Автор: Bobrina 19.12.2011, 23:05
Текст задачи:

"Составить функцию, которая, получив два массива, определяет, равны ли они. Два массива будем считать равными, если они содержат одинаковые числа. 
Используя эту функцию решить следующую задачу: 
Даны три массива действительных чисел.  Если эти три массива равны между собой, создать новый массив, все элементы которого равны утроенным элементам  одного из них, в противном случае создать массив, склеив все три исходных массива в порядке 1, 2 и 3."

Собственно не могу составить функцию проверки массивов на равенство.
Проблема в том, что по словам преподавателя, два массива равны когда в них содержатся одни и те же числа в любом порядке, т.е. {1,2,3} и {3,2,1} - одинаковые.
Сначала отсортировать массивы, а потом сравнить соответствующие элементы нельзя, ибо массивы будут использоваться после проверки. Создавать дополнительные массивы и сортировать и анализировать их тоже нельзя, т.к. нерационально. 
Брать элемент одного массива, и просто искать его во втором тоже не получится, тогда {7,7,7} и {1,1,7} получатся равными. Видимо надо делать какой-то флажок для элементов, которые уже мы "использовали" во втором массиве. Но боюсь опять придерутся что будет нерационально.
Посоветуйте что-нибудь, пожалуйста.

Автор: bobik02 20.12.2011, 00:40
Тут бы  наверное очень пригодился мат. анализ (задачи оптимизации).

Интересная задчка.

Автор: Bobrina 20.12.2011, 19:50
Да вот очень даже интересная, настолько что никак не могу придумать как же её сделать.

Автор: Dov 20.12.2011, 23:30
Цитата(Bobrina @  19.12.2011,  22:05 Найти цитируемый пост)
Посоветуйте что-нибудь, пожалуйста.

Разве что, пройтись XOR`ом по массивам...
Код
#define SZ 5

bool compareArray(int * arr1, int * arr2)
{
    int n = 0;

    for(int i = 0; i < SZ; i++)
    {
        n ^= arr1[i];
        n ^= arr2[i];
    }

    return (n == 0);
}

int main()
{
    int first[]  = {1,2,3,4,5};
    int second[] = {3,2,1,5,4};
    int third[]  = {4,2,1,3,5};
    
    if(compareArray(first, second) && compareArray(first, third))
    {
        // создать новый массив, все элементы которого равны утроенным элементам  одного из них
    }
    else
    {
        // создать массив, склеив все три исходных массива в порядке 1, 2 и 3
    }

    return 0;
}

Автор: volatile 21.12.2011, 02:16
Цитата(Dov @  20.12.2011,  23:30 Найти цитируемый пост)
Разве что, пройтись XOR`ом по массивам...

Dov, одинаковый XOR - это вовсе не гарантия одинакового набора.
Например попробуйте эти массивы, они все с одинаковым ксором:
Код

1,2,3,8,9
1,2,3,9,8
1,2,4,0,6
1,2,4,1,7
1,2,4,2,4
1,2,4,4,2
1,2,4,6,0
1,2,4,7,1
1,2,5,0,7
1,2,5,1,6
1,2,5,2,5
1,2,5,3,4
1,2,5,4,3
1,2,5,5,2
1,2,5,6,1
1,2,5,7,0
1,2,6,0,4
1,2,6,1,5
1,2,6,2,6
1,2,6,3,7
1,2,6,4,0
1,2,6,5,1
1,2,6,6,2
1,2,6,7,3
1,2,7,0,5
.. еще стопицот штук.


Цитата(Bobrina @  19.12.2011,  23:05 Найти цитируемый пост)
о словам преподавателя, два массива равны когда в них содержатся одни и те же числа в любом порядке

Рискну предположить, что препод слегка перегнул палку.
Из условия это вовсе не следует. Он массивы спутал со множествами.
Но это не можества,  тем более что
Цитата(Bobrina @  19.12.2011,  23:05 Найти цитируемый пост)
клеив все три исходных массива в порядке 1, 2 и 3."

Для множеств, не существует порядка склеивания. (косвенное подтверждение что составители не имели ввиду множества).

Данная задача, в том виде как поставлена, имхо, не решаема.
Нужно либо дополнительная память (копия массива для сортировки, или примерно такой-же массив флагов)
либо, дополнительное время (подсчет кол-ва символов в обоих массивах, на каждой итерации )

Чисто интуитивно, могу конечно ошибаться...

Автор: Dov 21.12.2011, 07:35
Цитата(volatile @  21.12.2011,  01:16 Найти цитируемый пост)
Dov, одинаковый XOR - это вовсе не гарантия одинакового набора.

volatile, а это никто и не утверждает.  smile 

Цитата(volatile @  21.12.2011,  01:16 Найти цитируемый пост)
Например попробуйте эти массивы, они все с одинаковым ксором:

А ты пробовал? Там, выше, функция есть для проверки "на равенство" любых двух массивов.  Имеется ввиду "равенство", данное по условию задачи, т.е. когда в массивах находятся одинаковые значения, но в разном порядке. 

Автор: Bobrina 21.12.2011, 22:53
Спасибо большое, вроде с преподователем сошлись на том, что будем считать что они должны состоять из одинаковых элементов на любых местах и в любом количестве. Т.е. {7,7,1} {7,1,1} {7,1,1} - все равны. Проверяю это проверкой чтобы все числа из первого были во втором, а потом наоборот, числа из второго в первом.

Автор: volatile 21.12.2011, 23:26
Цитата(Dov @  21.12.2011,  07:35 Найти цитируемый пост)
А ты пробовал? Там, выше, функция есть для проверки "на равенство" любых двух массивов.

да я пробовал
http://liveworkspace.org/code/bcf5f06dbed0b7795444eba7a1dd7f06

Цитата(Bobrina @  21.12.2011,  22:53 Найти цитируемый пост)
Спасибо большое, вроде с преподователем сошлись на том, что будем считать что они должны состоять из одинаковых элементов на любых местах и в любом количестве. Т.е. {7,7,1} {7,1,1} {7,1,1} 

а это вообще имеет какой-то смысл?

Автор: Dov 22.12.2011, 08:57
Цитата(volatile @  21.12.2011,  22:26 Найти цитируемый пост)
да я пробовал

Да, ошибочка вышла...  smile 

Цитата(volatile @  21.12.2011,  22:26 Найти цитируемый пост)
а это вообще имеет какой-то смысл?

Видно они тренируются в работе с массивами. 

Автор: Bobrina 22.12.2011, 09:07
Цитата(volatile @ 21.12.2011, 23:26 Найти цитируемый пост)
А это вообще имеет какой-то смысл?

Даже не подозреваю, единственный смысл - сдать лабораторную преподавателю.
Цитата(Dov @  22.12.2011, 08:57 Найти цитируемый пост)
Видно они тренируются в работе с массивами. 

Совершенно верно.

Автор: volatile 22.12.2011, 23:36
Цитата(Dov @  22.12.2011,  08:57 Найти цитируемый пост)
Да, ошибочка вышла...   

Вот уважаю таких людей! smile респект.

Цитата(Bobrina @  21.12.2011,  22:53 Найти цитируемый пост)
вроде с преподователем сошлись на том, что будем считать что они должны состоять из одинаковых элементов на любых местах и в любом количестве. Т.е. {7,7,1} {7,1,1} {7,1,1} - все равны

Что интересно, я даже в этом случае не вижу быстрого алгоритма.  smile
Ваш способ
Цитата(Bobrina @  19.12.2011,  23:05 Найти цитируемый пост)
Брать элемент одного массива, и просто искать его во втором
 имеет сложность N^2
сортировка и то быстрее. (нормальная сортировка N*logN)
Впрочем, если главная цель 
Цитата(Bobrina @  22.12.2011,  09:07 Найти цитируемый пост)
сдать лабораторную преподавателю.

и этого преподавателя удовлетворил этот способ, то пусть будет так...  smile

Добавлено через 11 минут и 49 секунд
хотя есть способ быстрее, но нужна доп. память...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)