Массивы

[kasper]

У нас есть два массива.
Нужно выяснить, имеются ли в них одинаковые элементы.
Скажите чо-нибудь умное, пожалуйста!
Мой собственный код этой проги получается большой!
И еще: размер массивов не лигитимирован! То есть в них может быть разное колличество элементов!

[Alf]

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

Если нет, то можно ли сделать их копию, которую потом отсортировать?

[kasper]

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

[Alf]

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

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

Поскольку оба массива отсортированы по возрастанию, нужно каждый раз продвигаться на шаг по тому массиву, текущий элемент которого меньше. Тогда за один проход соберешь все совпадения.

[kasper]

Это получается:
о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]

Это чего такое значит? Я такого не понимаю. Где тут два массива?

[kasper]

a
o

[Alf]

Ну так сортируешь оба и сравниваешь, начиная с первого элемента. А потом тот массив, у которого текущий меньше, продвигаешь на 1 и так далее.

[kasper]

Пробовал, не хочет компилировать!
Сразу же говорит об ошибках. Таких, что дальнейшее использование работающей проги невозможно. Приходиться закрывать окно и мучиться дальше

[Alf]

Так алгоритм и не будет компилироваться. Его сначала в программу на С++ превратить нужно, и желательно без ошибок.

[kasper]

))
так дело в том, что не могу пока описать сей алгоритм!
знаний синтаксиса не хватает.
Делаю как могу, прога получается очень большой! Я хотел спросить, как сделать по-короче

[Alf]

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

Сортировка - несложная штука, хорошо в литературе описана. Мой алгоритм тоже сложным не назовешь. Не должна программа большой получиться. Покажи, что именно вызывает затруднения.

[kasper]

Смысл в том, что я могу сделать так:
for(int i=0; i<10; i++)
{
   if(o==a[i+1])
      cout<<o;
}
Как сделать так, чтобы не пришлось 10 раз писать это же?
И что делать если размер массива вводится с консоли, и разный?

[Alf]

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

Код:

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]

Aif, спасибо, я завтра прокомплю. Сейчас голова не варит. Около 36 часов бодрствую.
Щас кусну чно-нибудь и спать лягу.

[Alex437]

А 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]

Может, конечно, и можно. Однако по моим прикидкам алгоритм получается порядка N² действий (при размерности массивов порядка N), а это не так уж красиво при больших N. Хотя код и получается короче на пару строчек, но эта экономия дорого обойдется в итоге.

[kasper]

Вот так как я это думаю:

Код:

#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;
}

[kasper]

Попробуйте поставить одинаковые цифры в маасивах

[Dimka]

Может, конечно, и можно. Однако по моим прикидкам алгоритм получается порядка N² действий (при размерности массивов порядка N), а это не так уж красиво при больших N. Хотя код и получается короче на пару строчек, но эта экономия дорого обойдется в итоге.

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

[Alf]

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

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

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

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

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

Мораль: не заигрывайте с алгоритмами порядка N², они не столь безобидны, как кажутся с виду. И не экономьте несколько строчек несложного кода, в конечном итоге боком выйдет.

[kasper]

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

[Михалыч]

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

[Alf]

Есть еще интересная задачка,
я ее уже написал.

За какое время твоя программа обсчитывает сотню гвоздей?

[kasper]

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

Код:

#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, честно говоря незнаю и нужно ли это?

[Alf]

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

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

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

Наиболее очевидный алгоритм, который первым приходит в голову, - это перебрать все комбинации и для каждой оценить суммарную длину нитей, после чего выбрать минимальную длину. Незатейливо, однако по моей прикидке потребует 2^N операций, а следовательно, будет работать лишь при N~10. Именно поэтому и спросил про сотню гвоздей - алгоритм, способный обсчитать сотню за разумное время, должен быть весьма элегантным, и мне хотелось бы на него посмотреть. В противном случае это тривиальный перебор, не представляющий никакого интереса.

[kasper]

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

[nikedeforest]

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

[kasper]

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

[nikedeforest]

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