Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++]Задача с массивами 
V
    Опции темы
Bobrina
Дата 19.12.2011, 23:05 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 26.1.2009
Где: Москва

Репутация: нет
Всего: нет
Текст задачи:

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

Собственно не могу составить функцию проверки массивов на равенство.
Проблема в том, что по словам преподавателя, два массива равны когда в них содержатся одни и те же числа в любом порядке, т.е. {1,2,3} и {3,2,1} - одинаковые.
Сначала отсортировать массивы, а потом сравнить соответствующие элементы нельзя, ибо массивы будут использоваться после проверки. Создавать дополнительные массивы и сортировать и анализировать их тоже нельзя, т.к. нерационально. 
Брать элемент одного массива, и просто искать его во втором тоже не получится, тогда {7,7,7} и {1,1,7} получатся равными. Видимо надо делать какой-то флажок для элементов, которые уже мы "использовали" во втором массиве. Но боюсь опять придерутся что будет нерационально.
Посоветуйте что-нибудь, пожалуйста.
PM MAIL ICQ   Вверх
bobik02
Дата 20.12.2011, 00:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 451
Регистрация: 26.11.2007

Репутация: 3
Всего: 14
Тут бы  наверное очень пригодился мат. анализ (задачи оптимизации).

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


--------------------
Have a nice day
PM   Вверх
Bobrina
Дата 20.12.2011, 19:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 26.1.2009
Где: Москва

Репутация: нет
Всего: нет
Да вот очень даже интересная, настолько что никак не могу придумать как же её сделать.
PM MAIL ICQ   Вверх
Dov
Дата 20.12.2011, 23:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88
Цитата(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;
}




--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
volatile
Дата 21.12.2011, 02:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85
Цитата(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."

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

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

Чисто интуитивно, могу конечно ошибаться...
PM MAIL   Вверх
Dov
Дата 21.12.2011, 07:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

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

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

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


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Bobrina
Дата 21.12.2011, 22:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 26.1.2009
Где: Москва

Репутация: нет
Всего: нет
Спасибо большое, вроде с преподователем сошлись на том, что будем считать что они должны состоять из одинаковых элементов на любых местах и в любом количестве. Т.е. {7,7,1} {7,1,1} {7,1,1} - все равны. Проверяю это проверкой чтобы все числа из первого были во втором, а потом наоборот, числа из второго в первом.
PM MAIL ICQ   Вверх
volatile
Дата 21.12.2011, 23:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

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

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

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

а это вообще имеет какой-то смысл?
PM MAIL   Вверх
Dov
Дата 22.12.2011, 08:57 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88
Цитата(volatile @  21.12.2011,  22:26 Найти цитируемый пост)
да я пробовал

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

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

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


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Bobrina
Дата 22.12.2011, 09:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 41
Регистрация: 26.1.2009
Где: Москва

Репутация: нет
Всего: нет
Цитата(volatile @ 21.12.2011, 23:26 Найти цитируемый пост)
А это вообще имеет какой-то смысл?

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

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

Это сообщение отредактировал(а) Bobrina - 22.12.2011, 09:08
PM MAIL ICQ   Вверх
volatile
Дата 22.12.2011, 23:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85
Цитата(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 секунд
хотя есть способ быстрее, но нужна доп. память...
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0560 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.