Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2 3  Все   Вниз
  Печать  
Автор Тема: Массивы  (Прочитано 40746 раз)
0 Пользователей и 1 Гость смотрят эту тему.
kasper
Гость
« : 19-11-2005 23:39 » 

У нас есть два массива. Жаль
Нужно выяснить, имеются ли в них одинаковые элементы.  Вот такой я вот
Скажите чо-нибудь умное, пожалуйста! Чтоб непоследняя...
Мой собственный код этой проги получается большой! Молчу
И еще: размер массивов не лигитимирован! То есть в них может быть разное колличество элементов! Бррр
Записан
Alf
Гость
« Ответ #1 : 19-11-2005 23:44 » 

Сортировать массивы можно?

Если нет, то можно ли сделать их копию, которую потом отсортировать?
Записан
kasper
Гость
« Ответ #2 : 19-11-2005 23:51 » 

можно сортировать, можно использовать указатели и ссылки, размещать в динамич. памяти, можно делать копию
Записан
Alf
Гость
« Ответ #3 : 20-11-2005 00:00 » 

Ну если можно, тогда алгоритм простой.

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

Поскольку оба массива отсортированы по возрастанию, нужно каждый раз продвигаться на шаг по тому массиву, текущий элемент которого меньше. Тогда за один проход соберешь все совпадения.
Записан
kasper
Гость
« Ответ #4 : 20-11-2005 00:14 » 

Это получается:
о1------а1
о2------а2
о3------а3
о4------а4,
а мне надо:
о1-----а1, а2, а3, а4
о2-----а1, а2, а3, а4
о3-----а1, а2, а3, а4
о4-----а1, а2, а3, а4

Записан
Alf
Гость
« Ответ #5 : 20-11-2005 00:20 » 

Это чего такое значит? Я такого не понимаю. Где тут два массива?
Записан
kasper
Гость
« Ответ #6 : 20-11-2005 00:24 » 

a
o
Записан
Alf
Гость
« Ответ #7 : 20-11-2005 00:34 » 

Ну так сортируешь оба и сравниваешь, начиная с первого элемента. А потом тот массив, у которого текущий меньше, продвигаешь на 1 и так далее.
Записан
kasper
Гость
« Ответ #8 : 20-11-2005 00:38 » 

Пробовал, не хочет компилировать!
Сразу же говорит об ошибках. Таких, что дальнейшее использование работающей проги невозможно. Приходиться закрывать окно и мучиться дальше
Записан
Alf
Гость
« Ответ #9 : 20-11-2005 00:48 » 

Так алгоритм и не будет компилироваться. Его сначала в программу на С++ превратить нужно, и желательно без ошибок.
Записан
kasper
Гость
« Ответ #10 : 20-11-2005 00:51 » 

Улыбаюсь))
так дело в том, что не могу пока описать сей алгоритм!
знаний синтаксиса не хватает.
Делаю как могу, прога получается очень большой! Я хотел спросить, как сделать по-короче
Записан
Alf
Гость
« Ответ #11 : 20-11-2005 00:58 » new

Ну и спросил бы, что именно не получается.

Сортировка - несложная штука, хорошо в литературе описана. Мой алгоритм тоже сложным не назовешь. Не должна программа большой получиться. Покажи, что именно вызывает затруднения.
Записан
kasper
Гость
« Ответ #12 : 20-11-2005 01:06 » 

Смысл в том, что я могу сделать так:
for(int i=0; i<10; i++)
{
   if(o==a[i+1])
      cout<<o;
}
Как сделать так, чтобы не пришлось 10 раз писать это же?
И что делать если размер массива вводится с консоли, и разный?
Записан
Alf
Гость
« Ответ #13 : 20-11-2005 01:15 » 

Немного не так. Примерно вот так нужно:

Код:
for (int acurr=0, ocurr=0; acurr<amax && ocurr<omax;)
{
  if (a[acurr] == o[ocurr])
  {
    твои действия в случае совпадения элементов;
    acurr++;
    ocurr++;
  }
  else if (a[acurr] < o[ocurr])
    acurr++;
  else
    ocurr++;
}

Вроде так, если ничего наспех не пропустил.
Записан
kasper
Гость
« Ответ #14 : 20-11-2005 01:20 » 

Aif, спасибо, я завтра прокомплю. Сейчас голова не варит. Около 36 часов бодрствую.
Щас кусну чно-нибудь и спать лягу.
Записан
Alex437
Гость
« Ответ #15 : 22-11-2005 15:20 » 

А std нельзя юзать? А то бы совсем красиво было:  Ага
Код:
vector<int> a, o;
vector<int>::const_iterator it;
for(unsigned i = 0; i < a.size(); ++i) {
        it = find(o.begin(), o.end(), a[i]);
        if(it != o.end()) {
            cout << *it;
        }
}
Записан
Alf
Гость
« Ответ #16 : 22-11-2005 18:52 » 

Может, конечно, и можно. Однако по моим прикидкам алгоритм получается порядка N2 действий (при размерности массивов порядка N), а это не так уж красиво при больших N. Хотя код и получается короче на пару строчек, но эта экономия дорого обойдется в итоге.
Записан
kasper
Гость
« Ответ #17 : 24-11-2005 22:30 » 

Вот так как я это думаю:
Код:
#include<iostream.h>

int main()
{
int a[11]={10, 20, 30, 40 ,50 ,60 ,70 ,80 ,90, 100, 0};
int b[11]={15, 25, 35, 45, 55, 65, 75, 85, 95, 105, 0};
int counter=0;
do{for(int i=0; i<10; i++)
      if(a[counter]==b[i])
     cout<<"b["<<i<<"]="<<b[i]<<endl;           
    if(b[i]=='\0')
   counter++;           
}while(a[counter]!='\0');
                counter=0;
do{for(int i=0; i<10; i++)
                if(b[counter]==a[i])
     cout<<"a["<<i<<"]="<<a[i]<<endl;
                                                    if(a[i]=='\0')
   counter++;
}while(b[counter]!='\0');

return 0;
}
« Последнее редактирование: 20-12-2007 17:07 от Алексей1153++ » Записан
kasper
Гость
« Ответ #18 : 24-11-2005 22:31 » 

Попробуйте поставить одинаковые цифры в маасивах
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #19 : 01-12-2005 17:11 » 

Может, конечно, и можно. Однако по моим прикидкам алгоритм получается порядка N2 действий (при размерности массивов порядка N), а это не так уж красиво при больших N. Хотя код и получается короче на пару строчек, но эта экономия дорого обойдется в итоге.
Зато не требует предварительной сортировки обоих массивов. Если сравнивать однопроходный алгоритм вместе с сортировкой vs то, что Alex437 изобразил... Если я правильно помню оценку qsort, то получается n*m против n*ln(n)+m*ln(m)+max(m,n). А вот искать при каких m и n одно лучше другого мне сейчас лениво. Улыбаюсь
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Alf
Гость
« Ответ #20 : 01-12-2005 23:01 » 

... Если я правильно помню оценку qsort, то получается n*m против n*ln(n)+m*ln(m)+max(m,n). А вот искать при каких m и n одно лучше другого мне сейчас лениво. Улыбаюсь

А там за нас уже все давно нашли. Правда, ворочать кирпичи Кнута ради такой мелочи неохота, а более попсовые "Жемчужины программирования" Бентли оставил на работе. Однако помню, что результаты измерений Бентли на реальных задачах поражают воображение цифрами. Конечно, на десятке-сотне элементов ничего не заметишь, все за один тик таймера пролетит. А на настоящих задачах может получиться весьма зримо.

Аналогичный пример. Одиниз моих сотрудников сводил баланс нашего обмена трафиком с партнерами, кто кому сколько должен. Расчеты длились более суток, причем сервер с данными находится в удаленной сети, которая порой глюкает, и необходимо либо перезапускать задачу, либо делать откат. Я решил поглядеть, что это за суперзадача, которая на мощном компе делается так долго (мне подозрительно все, что крутится дольше нескольких минут на компе с миллиардом операций в секунду, ибо помню времена, когда мечтали о миллионе).

В результате оказалось, что подходящий тариф для направления каждый раз ищется в массиве линейным поиском(!).


Заставил товарища разбить массив на несколько частей, каждую отсортировать (что далось бесплатно, ибо исходные данные все равно берутся с SQL-сервера) и заменить линейный поиск двоичным, то есть вместо (t ~ N/2) поиск стал производиться за (t ~ log2(N/10)). В численном выражении это составило ~40 сек вместо прежних ~35 часов. Раньше парень запускал задачу и присматривал, не случилось ли чего по ходу. Теперь он, пардон, по нужде не успеет выскочить за время ее выполнения, нажал - получи результат. Как говорится, "думайте сами, решайте сами" (С).

Мораль: не заигрывайте с алгоритмами порядка N2, они не столь безобидны, как кажутся с виду. И не экономьте несколько строчек несложного кода, в конечном итоге боком выйдет.
Записан
kasper
Гость
« Ответ #21 : 02-12-2005 00:02 » 

Есть еще интересная задачка,   Вот такой я вот
я ее уже написал.  Улыбаюсь
Помучайтесь пока:  Ха-ха-ха
В линейку вбиты гвозди, находящиеся на заданных расстояниях p1, p2,…,pN друг от друга. Соседние гвозди можно связывать нитками. Не должно остаться ни к кому не привязанных гвоздей. Нужно найти способ их связывания, обеспечивающий минимум суммарной длины нитей.
Записан
Михалыч
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #22 : 02-12-2005 02:21 » 

Если условие описано дословно и корректно то мне кажется все элементарно. Улыбаюсь
Но это если понимать описанную задачу ДОСЛОВНО.
Гвозди вбиты "в линейку" - стало быть по прямой линии. Расстояния между гвоздями м.б. не одинаковым - сие и не важно. Но кратчайшее расстояние между двумя точками до сих пор была прямая линия. Стало быть и ответ сам по себе напрашивается - связывай гвозди последовательно друг за другом. И будет тебе кратчайшая нитка.
Другое дело, что это явно не так, уж больно все просто. Мне кажется, что явная неоднозначность прочтения и понимания условия задачи "зарыты" вот тут - "ни к кому не привязанных гвоздей". Уточните задачу, иначе ее решать можно исходя только из собственных предположений - см. первое решение. В нем тоже не осталось "не привязанных" гвоздей. Вопрос только КАК не привязанных Улыбаюсь
Записан

Поживем - увидим... Доживем - узнаем... Выживу - учту  Улыбаюсь
Alf
Гость
« Ответ #23 : 02-12-2005 10:40 » 

Есть еще интересная задачка,  Вот такой я вот
я ее уже написал. Улыбаюсь

За какое время твоя программа обсчитывает сотню гвоздей?
Записан
kasper
Гость
« Ответ #24 : 03-12-2005 21:06 » 

Закон такой:
если в задаче есть неточности,  и что то непонятно, то делай так как понял.
Мое решение:

Код:
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#include<iomanip.h>

int main()
{
int sum, odd=1, even=0, pass, zero=1, counter=0, hold;
int array[10];
cout<<endl<<"* Enter coordinate nail (santimetre): "<<endl;
sum=0;
cout<<"  ";
for(int i=0; i<10; i++)
{array[i]=rand() % 99 + 1;}
for(pass=0; pass<10; pass++)
for(i=0; i<10; i++)
if(array[i]>array[i+1])
{hold=array[i];
array[i]=array[i+1];
array[i+1]=hold;}
for(i=0; i<10; i++)
{cout<<array[i]<<setw(3);
counter++;
if(counter==2)
{cout<<"      ";
  counter=0;}      
}do{sum=sum+((array[odd])-(array[even]));
    odd=odd+2;
even=even+2;
}while(even<10);
cout<<endl<<"  For ligament only nearby nails, it is necessary"<<endl
<<"  "<<sum<<" santimetre niton"<<endl;
return 0;
}

Alf, честно говоря незнаю и нужно ли это?
« Последнее редактирование: 13-01-2009 18:02 от Вад » Записан
Alf
Гость
« Ответ #25 : 03-12-2005 21:35 » 

...
Alf, честно говоря незнаю и нужно ли это?

Хм... Даже затрудняюсь ответить, такой поворот мне и в голову не приходил. С какой целью тогда была написана программа?

Еще Козьма Прутков учил: "Бросая в воду камешки, смотри на круги, ими образуемые; иначе такое бросание будет пустою забавою." Чтобы написание подобной программы не стало пустой забавой, нужно одно из двух:  либо получить выгодный подряд на связывание  гвоздей нитками (в чем я сомневаюсь), либо пожелать научиться чему-то новому (что больше похоже на правду).

Наиболее очевидный алгоритм, который первым приходит в голову, - это перебрать все комбинации и для каждой оценить суммарную длину нитей, после чего выбрать минимальную длину. Незатейливо, однако по моей прикидке потребует 2N операций, а следовательно, будет работать лишь при N~10. Именно поэтому и спросил про сотню гвоздей - алгоритм, способный обсчитать сотню за разумное время, должен быть весьма элегантным, и мне хотелось бы на него посмотреть. В противном случае это тривиальный перебор, не представляющий никакого интереса.
Записан
kasper
Гость
« Ответ #26 : 03-12-2005 21:39 » 

да, наверно.
я пока немогу делать привязку к таймеру.
как это?
Записан
nikedeforest
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #27 : 03-12-2005 21:52 » 

Засеки время в начале выполнения алгоритма и в конце. Благодарям простым алгебраическим операциям узнаешь как долго работате твой алгоритм. Это, если конечно именно это имелось ввиду.
Записан

ещё один вопрос ...
kasper
Гость
« Ответ #28 : 03-12-2005 21:54 » 

Это нужно отобразить в исходнике, если я правильно понял.
Какими операторами или функциями?
Записан
nikedeforest
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #29 : 03-12-2005 21:56 » 

Под винду пишешь? Среду разработки скажи.
Записан

ещё один вопрос ...
Страниц: [1] 2 3  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines