как найти количество совпадающих значений элементов массива А и В

[ЮрийFM]

задача такова :: Даны два упорядоченных массива А и В (необязательно одинаковой длины). В каждом из массивов могут быть совподающие элементы. Не используюя дополнительной памяти, найти количесво совподающих значений элементов А и В (т.е количество t, для которых t=A[i ] = B[j ]


вот мой код ...ситуация такова что функция randomize которая должна выдовать мне случайные числа работает не совсем как надо.

Код:

# include <stdio.h>
# include <conio.h>
# include <math.h>
# include <time.h>
# include <stdlib.h>
int  main(void)
{int a[1000],b[1000],n,m,w,i,j,l;
clrscr();
randomize();
puts("\n Vvedite kol masA: ");
scanf("%d",&n);
puts("\n Vvedite kol masB: ");
scanf("%d",&m);

puts("Mass A:");
for (i=0;i<=n-1;i++) {
a[i]=random(40);
printf("%5d",a); }


puts("\nMass B:");
for (i=0;i<=m-1; i++) {
b[i]=random(40);
printf("%5d",b); }

			

l = 0;
for (i=0; i<n; i++) {
t=0;
for (j=0;j<m;j++)
if (a[i]==b[j]) t++;
if (t==1)
l++;
}

printf("\n%u",t);
getch();}

[Paul]

ЮрийFM, вместо random(40) используй

Код:

a[i]=random() % 40
b[i]=random() % 40

[ЮрийFM]

ЮрийFM, это в каком же модуле C нашёл ты паскалевские функции Randomize и Random? Не правильнее ли говорить, что это вообще не работает?

Но, допустим, что они есть, и где (в каком месте) тогда у тебя Randomize выдаёт случайные числа, как ты спрашиваешь?

 Соответствующая функция существует и в Turbo Pascal.
а это же СИ++ вот попробуй кинуть random, как и randomize в Си++
 #include <stdio.h>
 
 #include <stdlib.h> //- в этом файле
 
 int main(void)
 
 {
 
    int i;
 
    randomize();
 
    printf("10 случайных чисел от 0 до 99 \n\n");
 
    for (i=0; i<10; i++)
 
        printf("%d\n", rand()%100);
 
 return 0;
 
 }

[Finch]

ЮрийFM, Стандартно в этом хедере нет такой функции. Есть rand и srand. Я нашел похожее упоминание такой функции в своем справочнике, но это соотносится для FreeBSD. Но там связка random - srandom.

[ЮрийFM]

Вот походу и вся задача...тока один вопросик как отсортировать два этих массива... т.е. А и В

Код:

 #include <stdio.h>
#include <stdlib.h>
#include <conio.h>
const int n=1000;
void main()
{
int l=0,i,j,A[n],B[n];
randomize();
for( i=0 ; i<n ; i++ )
{
A[i]=rand()%100;
B[i]=rand()%100;
}
clrscr();
for( i=0 ; i<n ; i++ )
{
for( j=0 ; j<n ; j++ )
if (A[i]==B[j]) l++;
}
printf("l=%d",l); 
getch();
}

[Вад]

Есть много алгоритмов сортировки Выбирай на вкус. Быстрая сортировка Хоара подходит в большинстве случаев, но если нужно самое простое решение - см сортировку пузырьком или что-нибудь в таком духе.

[ЮрийFM]

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

Код:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
const int n=10;
void main()
{
int l=0,i,j,A[n],B[n],k;
randomize();
for( i=0 ; i<n ; i++ )
{
A[i]=rand()%100;
B[i]=rand()%100;
};
 for (i=n;i>1;i--)   //вот код на сортировку
  for (j=0;j<i-1;j++)
   if (A[i]>A[i+1])
    {
    k=A[i];
    A[i]=A[i+1];
    A[i+1]=k;
    printf(" %d",k); //конец кода
};
{
clrscr();
for( i=0 ; i<n ; i++ )
{
for( j=0 ;j<n ; j++ )
if (A[i]==B[j]) l++;
}
puts("Kolvo sovpavshih elementov A[i] and B[j] :");
printf("l=%d",l); 
getch();
}
}

[ЮрийFM]

Вот...сортировку Хоара...впервые слышу ...объясните как она работает...просто очень интересно...

[Вад]

У тебя, насколько понимаю, попытка реализовать сортировку пузырьком. Ошибка в неверной индексации - точнее, в не совсем правильных значениях счётчиков. Вот пример реализации этой сортировки на C из википедии:

Код:

# define SWAP(A,B) {A=A^B;B=A^B;A=A^B;}
void bubblesort(int A[], int n)
{
    int i, j;
 
    for(i = n-1 ; i > 0 ; i--)
     {
        for(j = 0 ; j < i ; j++)
         {
            if( A[j] > A[j+1] ) SWAP(A[j],A[j+1]);
         }
     }
}

А так, как у тебя, выйдет за границу массива (a[i], a[i+1]) и просто не совсем те элементы будет обменивать - по сути, совершит только 1 проход

Раз интересно, описание сортировки Хоара в Википедии - там же есть и ряд других

[ЮрийFM]

извините что вопросов очень много ..но именно учёба залог успеха......вот и ещё один вопрос ....а можно ли вывести упорядоченный массив а и б на экран..сначало а и потом б ..я как пробовал то у меня выводит таким макаром Сначало число идёт массива а и после его число массива б ... и так далее...т.е. неудобство..

[Вад]

Показывай, как пробовал Кстати, у тебя в предыдущем коде только 1 массив сортируется - не забудь и про это (лучше сортировку в отдельную функцию оформить).

[ЮрийFM]

да...я сначало хочу посмотреть чтобы одни хотябы массив сортировало...а вот мой код

Код:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define swap(A,B) {A=A^B; B=A^B; A=A^B;}  
void sort(int A[],int n) // -вот через прототип sort я хочу чтобы после заполнения массива функция переходила на этот код...
{
int i, j;
for(i=n-1;i>0; i--)
{
for(j=0; j<i; j++)
{
if(A[j]> A[j+1]) swap(A[j],A[j+1]);
}
}
}
const int n=20;
void main()
{
int l=0,i,j,A[n],B[n];
randomize();
for(i=0; i<n; i++)
{
A[i]=rand()%100;
printf(" %d",rand()%100 ); //печатает один элемент массива А 
B[i]=rand()%100;
printf(" %d",rand()%100);// печатает один элемент массива В 
}
sort(A,n);               // тут я хочу перейти на сортировку но не фурычит на моё горе
for(i=n;i>0;i--)
while((A[i]-A[i-1])>1)
//clrscr();                 //очистку экрана я пока отложил чтобы видеть что поисходит после выполнен.
for( i=0 ; i<n ; i++ )
{
for( j=0 ;j<n ; j++ )
if (A[i]==B[j]) l++;
}
puts("Kolvo sovpavshih elementov A[i] and B[j] :");
printf("l=%d",l);
getch();

}

[Вад]

Так. Во-первых, если хочешь выводить 2 массива раздельно - так и сделай для них циклы заполнения раздельно.
Во-вторых, твоя сортировка у меня работает только я заменил ещё randomize() на srand(time(0)) - оно как-то привычнее (нужно включить ещё один заголовок - #include <time.h>)

Код:

int main() {
    // ...

    return 0;
}

- это по стандарту так должно быть в C++. А то void main() ещё не на всех компиляторах обязано компилироваться, это вольность такая

а вот этот кусок зависает - не выходит из цикла:

Код:

    for(i=n;i>0;i--)
        while((A[i]-A[i-1])>1)
            for( i=0 ; i<n ; i++ )
            {
                for( j=0 ;j<n ; j++ )
                    if (A[i]==B[j]) l++;
            }

[ЮрийFM]

Вот мучался...но сделал))) Я прототипом сортировку сначало указал...а потом просто тыкнул на её в коде..а randomize я бы и не пользовался ..просто с паскаля осталось...А массивы отсортированные выводил по отдельности самым простым способом как и сортировал пузырьком.  решил на СИ++ ..перейти..вот тока граматика храмает...но это исправимо)))

Код:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define swap(a,b) {int tmp=a;a=b;b=tmp;}
const int n=100;
void main()
{
int l=0,i,j,A[n],B[n];
randomize();
for( i=0 ; i<n ; i++ )
{
A[i]=rand()%100;
B[i]=rand()%100;
}
clrscr();
{
puts(" Eto MASS_A");
for (i=0; i<n;i++)
for (j=n-1;j>i;j--)
if(A[j-1]>A[j]) swap(A[j-1],A[j]);
for(i=0; i<n; i++)
printf(" %d",A[i]);
};
{
puts("\n Eto MAS_B");
for (i=0; i<n;i++)
for (j=n-1;j>i;j--)
if(B[j-1]>B[j]) swap(B[j-1],B[j]);
for(i=0; i<n; i++)
printf(" %d",B[i]);
};

for( i=0 ; i<n ; i++ )
{
for( j=0 ; j<n ; j++ )
if (A[i]==B[j]) l++;
}
printf("\n l=%d",l);
getch();
}

[ЮрийFM]

Спасибо большое за помощь...   Тут походу правильно...верно?

[Антон (LogRus)]

Код:

#include <stdio.h>
for( i=0 ; i<n ; i++ )
{
for( j=0 ; j<n ; j++ )
if (A[i]==B[j]) l++;
}
}

Совсем не оптимально. Есть способ поизящней в условии не спроста массивы отсортированы

[ЮрийFM]

Сопосб по изящней...в чём его изящество???

[Вад]

ЮрийFM, полагаю, изящество способа, на который намекает LogRus - в линейном времени исполнения упорядоченные массивы позволяют оптимизировать подсчёт числа всех пар: время выполнения O(M+N) - где M и N - размеры двух массивов соответственно. Твой способ требует квадратичных затрат времени.

[Антон (LogRus)]

ЮрийFM, кроме того, будь я преподом, за твоё решенье поставил бы 3 от силы  4, просто так в условии про упорядоченность не пишут.

[Антон (LogRus)]

Вад, да ты как всегда прав

ЮрийFM, будь я преподом, за твоё решенье поставил бы 3 от силы  4, просто так в условии про упорядоченность не пишут.
Во вторых подумай о предельных значениях, например, 1E6 элементов в каждом массиве, твой способ будет медленнее в 1E6 раз медленнее, а из-за особенностей работы CPU, то скорее всего еще медленней.

[ЮрийFM]

ДА...вы правы... Еслиб я знал..то я бы так и сделал...а как мне это реализовать в своей пограмме?

[Вад]

ЮрийFM, подумай в направлении того, как бы пройти оба массива только по одному разу (а не проходить один из массивов n раз). Они сортированные, и это даёт подсказку

Имхо, самый простой способ догадаться: напиши две строчки чисел на бумаге, чтобы в каждой строке числа были упорядочены. Вроде такого:
1 3 3 5 6 9 10 10 14
3 6 8 9 9 9 11 16 19
Попробуй на бумаге отыскать подход, как двигаться по каждому из массивов, подсчитывая количество совпадающих элементов, чтобы двигаться по массивам только один раз и в одном направлении.

[ЮрийFM]

 ...блин точно...сначало просто не обратил внимание...сортировка не ишла и я без сортировки пробовал смотреть одинаковые элементы...
да ниче не скажешь.... мужик...спасибо Вад за наводку)

[ЮрийFM]

вот походу так вроде...

Код:

j=0;
for( i=0 ; i<n ; i++ )
if (A[i]==B[j++]) t++;

[Вад]

Мне кажется, не совсем. Результат сходится с результатом неоптимального варианта? Что будет, если в массиве A или B два и более элементов подряд одинаковые?

[ЮрийFM]

тоже верняк...а что если брать тока один массив допустим А и попорядку каждый элемент массива А сверять с i ммассивом В...и в случае совподения t++    и пройдёт цикл тока один раз... или есть другой вариант..по такому же макару тока можно поверять в массиве В последовательность одинаковых элементов... т.е. если А= какому небудь элементу массива В то можно сделать есть ли ещё этот элемент в этом массиве..

[ЮрийFM]

вот ...
походу нужно так...берём i массива А  и смотрим идет ли за i одинаковое число...если идёт то t++ -подсчитываем кол-во одинокаовых элементов(но только при том что А=B[j]) так же надо смотреть масиив В идет ли за j  элемент равный i если идёт то t++..

Код:

for(i=0; i<n; i++)
for(j=0; j<n; j++)
if ((A[i]==A[i++]) && (A[i]==B[j])) t++;
if ((B[j]==B[j++]) && (B[j]==A[i])) t++;

это написанно не верно...возможно я не верно мыслю...

[Вад]

ЮрийFM, подсказка: если в массиве A некоторое число x встречается n раз, а в массиве B - m раз - то t будет увеличено на n*m, так?

[ЮрийFM]

да....логично)) тока наверно

t будет увеличено на n+m может??

по скольку.. если умножим то получиться произведение совпавших элементов массивов... а не количетво. 

[Вад]

ЮрийFM, m*n - получится количество всех возможных пар одинаковых чисел x из A и B. Вроде, в условии про это.