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

[ЮрийFM]

посидел подумал...листик почёркал много раз...но вроде доехало по ходу так...

Код:

for(i=0; i<n; i++)
j=0;
if(A[i]==A[i++]) k++; //вот кол одинаковых х в массиве А
if(B[j]==B[j++]) m++; //вот кол этого х в массиве В
if(A[i]=B[j]) t=m*k;

?

[Вад]

Нет
Во-первых, в приведённом коде цикл будет лишь присваивать j значение 0, остальной код выполнится 1 раз

Во-вторых, код

Код:

A[i]==A[i++]

сравнит A[i] с A[i] и лишь потом увеличит значение счётчика, а потом счётчик ещё раз будет увеличен при входе на новую итерацию цикла - то есть, каждый 2й элемент и вовсе будет пропущен.

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

[ЮрийFM]

может так ??

Код:

for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i]==A[i--]) k++; //сравнивает i-1 элемент массива А с i 
if(A[i]==B[j--]) m++; //
if(B[j]==B[j--]) m++; //

t=m*k;

...
как в В массиве предусмотреть совподение чисел как и  в А...?  и ещё ..можно ли это сделать без дополнительных переменных m  и к...тока с t допустим...
да...казалось куда проще..

[Вад]

я вот тут накидал решение на Haskell - разумеется, оно в функциональном стиле, но принцип, думаю, неплохо иллюстрирует

Код: (Text)

count_pairs :: [Int]->[Int]->Int
count_pairs [] _ = 0
count_pairs as@(a:_) bs = (move_a as bs a 0) where

        move_a :: [Int]->[Int]->Int->Int->Int
        move_a [] bs x m = move_b [] bs x m 0
        move_a s@(a:as) bs x m  | a == x = move_a as bs x (m+1)
                                | a > x = move_b s bs x m 0

        move_b :: [Int]->[Int]->Int->Int->Int->Int
        move_b _ [] _ m n = m*n
        move_b as s@(b:bs) x m n | b == x = move_b as bs x m (n+1)
                                 | b < x = move_b as bs x m n
                                 | b > x = (m * n) + count_pairs as s

[ЮрийFM]

Haskell...если бы я его знал было бы  ....но
код вроде не сложный да и есть сходство ...можно и разобраться если постараться ...

А если так???
просто можно код прописать через goto...т.е. ссылаться на цикл пока допустим не найдёт все х одинаковые...потом идёт на массив В ищёт там х ...если его нет то на start

[Вад]

ЮрийFM, ну не писать же мне для тебя полное решение на C++ - это было бы не спортивно В сущности, моё решение - это подобие 2 циклов, но не таких, какими их организовывал ты. То есть, не "от первого до последнего", а несколько похитрее

[ЮрийFM]

 :)да..да...надобно самому..

[ЮрийFM]

  ну...вроде всю хитрость использовал...на какой-то код убиваю уже какой день...туплю...
да сёровно и проверяю код по строкам и вроде правильно кидаю его в прогу ..нифига...вот последнее что пробовал...голова уже не варит

Код:

    for(i=0; i<n; i++)
x=A[i];
if(x==A[i--]) k++;
for(j=0; j<n; j++)
x=B[j];
if(x==B[j--]) m++;

[Антон (LogRus)]

x==A[i--] убиться веником. при анализе условия изменяем индекс цикла? нафига?

A=1112345
B=1145

1. два первых элемента совпали: общее число совпадений +1, число совпадений с текущего элемента A с B +1
2. подвинули  ++b
3. A[0] и B[1] совпали: общее число совпадений +1, число совпадений с текущего элемента A с B +1
4. подвинули  ++b
5. A[0] и B[2] не совпали: ++a
6. A[0] == A[1]: к общему число совпадений прибавляем число совпадений с предыдущего элемента A
7. подвинули  ++a
8. A[1] == A[2]: к общему число совпадений прибавляем число совпадений с предыдущего элемента A
9. подвинули  ++a
10. A[2] != A[3]: совпадений предыдущего элемента A обнуляем
11. выравниваем индексы до совпадения после чего продолжаем с пункта 1

и забудь про вложенные циклы

[Вад]

LogRus, вложенный цикл возможен, но можно и без него.

ЮрийFM, твоя проблема начинается вот с этого:

Код:

for(i=0; i<n; i++)

циклы можно организовывать не только так. Если рассматривать только for, то можно, например, так:

Код:

for ( i = 0 ; i < n; )
{
    if (expression) // если нужно увеличить счётчик, мы это делаем. иначе - нет.
        ++i;
}

тогда цикл будет выполнять не n итераций, а столько, сколько потребуется для достижения нужного результата. Например, пока не пройдёт оба массива до конца. Хотя уж проще выразить то же самое оператором while - он для того и существует.

[ЮрийFM]

  понял) Спасиб

[ЮрийFM]

 вот что -то похожее

Код:

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

[Вад]

Зациклится ведь Потому как в цикле будет исполняться только это:

Код:

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

[ЮрийFM]

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

[ЮрийFM]

Код:

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

но почему...?? 

Код:

if(A[i]==B[j]) t++;

если это не выполняется то должно идти дальше...и если да то T++ и тоже вниз

[Вад]

Я это написал до того, как ты пофиксил, добавив скобки. Теперь если и виснет, то по другой причине  

Пара советов:
Форматируй код, чтобы для себя было ясно, что в какой последовательности выполняется.  И комментируй, чтобы было более ясно, что пытается сделать код

Не очень понятно, как с помощью увеличения t исключительно оператором ++ ты хочешь учесть m*n пар в двух массивах

[ЮрийFM]

Код:

{
i=0;
while (i<n)
{
if(A[i]==B[j]) m++;
j++;
if(A[i]==B[j]) m++;
j++;
if(A[i]!=B[j]) i++;
if(A[i]==A[i++]) k++;
i++;
if(A[i]==A[i++]) k++;
i++;
if(A[i]!=A[i++]) k--;
if(i<j) j--;
i--;
}
t=m*k;
}

хотя через while для этого случая удобнее

Код:

for(j=0;j<n;)
for(i=0; i<n;))

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

[Вад]

ЮрийFM, твой код в любом случае делает нечто странное Я же указал принцип в своём коде - там не обязательно знать язык, хотя бы просто отследить, в каком порядке и что делается, и спокойно расставить всё по полочкам. Действий всего два: движение по A и движение по B.
Пока я вижу попытку угадать результат - ведь этот код работает совсем не так, как надо, да?

[ЮрийFM]

да верно...вот пробую

Код:

{
for(i=0; i<n;) //пока i<n выполнять
for(j=0; j<n;) //пока j<n выполнять
{
if(A[i]==B[j]) m++;  //если А0 равно В0 то прибавляем к M единицу (m++) 
j++;                  //увеличиваем j то есть берем В1
if(A[i]==B[j]) m++;   //уже если А0 равно В1 то прибавляем к M единицу (m++)
j++;                    //увеличиваем j то есть берем В2
if(A[i]!=B[j]) i++;      ////уже если А0 неравно В3 то увеличиваем счётчик  i берем А1
if(A[i]==A[i++]) k++;     // если А1 равно А2 то увеличиваем k на единицу
i++;                      //увеличиваем i то есть берем A2
if(A[i]==A[i++]) k++;   // если А2 равно А3  то увеличиваем k на единицу
i++;                   //увеличиваем i то есть берем A3
if(A[i]!=A[i--]) i--;  //есди А3 не равно А2 то уменьшаем i на единицу
if(i<j) j--;            //тут идёт уравнивание
i--;
}
t=m*k;
}

[Вад]

Код:

if(A[i]!=B[j]) i++;      ////уже если А0 неравно В3 то увеличиваем счётчик  i берем А1

А если A0 таки равно B3?

[ЮрийFM]

а если тако равно то нада прибавить к j 1(единицу) и опять сравнивать if(A==B[j]) m++;


так вот же!!!! у меня и с этим все проблемы я же не буду прописывать код в котором буду придавлять к житому элемнту единицу н раз...это не тактично...и причём не экономично) чтоли цикл там вставить while к примеру..но если даже цикл вставить то у меня циклит а чего..? всё перепробывал
 свой вариант писал...но опять же в это всё упирается...хотя можно обойти это каким-то боком но каким я не знаю

[Вад]

Ну а даже если и цикл - то какой цикл? С каким условием?

[ЮрийFM]

ну тут всё просто если (A[i]==B[j]) то надо j++

for(;A[i]==B[j]; j++) так походу ?

[ЮрийFM]

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

нет..нет..надо найти количесво совподающих элементов массива А и В...тут не  про пары..т.е. t=m+k

[ЮрийFM]

я тупил чё то))... через x... вроде Вад имел это ввиду хитрого кода)

Код:

for (i = 0; i < n; i++)
 {
    x=A[i];

  for (j = 0; j < n; j++)
   {
    if (x==B[j])
	{ m++; }
    if (i==j)
	{ continue; }
    if (x==A[j])
	{ k++; }
   }
   }
t=k+m;

это вот тот код который правильный...100%

[Вад]

Хм. а сложность у тебя всё равно квадратичная А если совпадающих чисел больше, чем одно (которое x)?

[ЮрийFM]

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

[Вад]

ЮрийFM, про сортировку слиянием слышал когда-нибудь? Там очень похожий случай на этапе слияния двух массивов, стандартная реализация как раз подразумевает слияние двух отсортированных массивов в один отсортированный за линейное время. По сути, разница между тем алгоритмом и твоим - только в том, что тебе нужно не копировать значения, а считать одинаковые. Более детальную подсказку придумать сложно

А последняя интерпретация условия мне кажется какой-то мутной: то есть, если в A и B есть одинаковые элементы, то сумма увеличивается на количество вхождений элемента в A и в B? Странно как-то, ну да ладно.

[ЮрийFM]

про слияние массивов...нет честно нет...я пробовал обычным способом...ибо я изучаю си не так давно и кидаюсь на всё что не знакомо... слиянием эт сделать как 2 пальца...и проще...даже)

[ЮрийFM]

программка как раз и выполняет параллельную проверку в двух массивах, т.е. одновременно. Берет i-й элемент, приравнивает его к x, а потом x сравнивает одновременно с элементами A[j] и B[j], пока не достигнет конца массивов. Затем идет следующий цикл, Берется следующий i+1-элемент, и все проверяется заново...
но... а если за х идет элемнт равный х ...вот и сэкономим место и время...если это условие учесть )

Кстати, эта программа может работать и с неупорядоченным массивом