Форум программистов, компьютерный форум CyberForum.ru

не используя доп. памяти , найти кол. совподающих значений элементов массива А и В - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
ЮрийFM
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
26.12.2008, 19:38     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #1
Задача такова:
Даны два упорядоченных массива А и В (необязательно одинаковой длины). В каждом из массивов могут быть совподающие элементы. Не используя дополнительной памяти, найти количество совподающих значений элементов А и В (т.е. колличество t, для которых t= A[i]=B[j] )

буду очень рад если поможите

Добавлено через 4 минуты 47 секунд
Вот пока что я написал...проблема заключается в том что у меня функция randomize т.е. заполнение случайными числами массива как A так и В. Работает не верно причнины я пока не нахожу... заполняет массив но одинаковыми числами...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2008, 19:38     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В
Посмотрите здесь:

C++ Найти номера элементов массива i и j, дающих минимальную разницу значений Xi-Yj
C++ Расчет кол-ва неотрицательных элементов массива
C++ В одномерном массива x(15) найти: 1)кол-во элементов, удовлетворяющих условию -0.5<sinх<=0;2)Минимальный элемент
C++ Найти кол-во элементов двумерного массива отличающихся от среднего менее, чем на 17%
Посчитать кол-во элементов между максимальным и минимальным значением элементов двумерного массива( подразумевается, что эти значения уже найдены) C++
Найти сумму наибольших значений элементов строк массива C++
В двухмерном целочисленном массиве (размеры массива N, M и значения его элементов вводить с клавиатуры) найти указанное значение. Массив в памяти разм C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Prorok
 Аватар для Prorok
105 / 105 / 3
Регистрация: 26.12.2008
Сообщений: 166
26.12.2008, 23:59     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #2
Вот мой вариант:
#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
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
27.12.2008, 01:05  [ТС]     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #3
Спасибо оказывается можно и проще чем я написал
ЮрийFM
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
29.12.2008, 02:23  [ТС]     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #4
ещё один вопрос возник...как этих два массива отсортировать...

Добавлено через 1 час 1 минуту 1 секунду
я пробывал вот так ...но что -то тут не то..не могу догнать..и после сортировки хочу вывести два массива на экрнан отсортированных
Код
#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);           // тут он заканчивается  выводом на экран к (т.е. упорядоченного массива А)
};
{
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();
}
}
упорядочив два массива...походу можно похитрее написать код на совподениее элементов...т.к. некоторые элементы одинаковы...задача такова...допустим некоторое число х есть в массиве А и В и оно может быть там не один раз...вот...мне надо возможное кол-во совпадений...я тут написал...но не работает так как мне это надо..
Код
{
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;
}
вот...я немогу впихнуть цикл чтобы работало ...т.е. мне постоянно надо увеличивать j элемент в случае совподения ...но я же не буду прописывать 10 раз его ..это не экономично...и не тактично...тут надо что-то похитрее..
ЮрийFM
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
05.01.2009, 12:43  [ТС]     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #5
упорядочив два массива...походу можно похитрее написать код на совподениее элементов...т.к. некоторые элементы одинаковы...задача такова...допустим некоторое число х есть в массиве А и В и оно может быть там не один раз...вот...мне надо возможное кол-во совпадений...я тут написал...но не работает так как мне это надо..
Код
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;
}
вот...я немогу впихнуть цикл чтобы работало ...т.е. мне постоянно надо увеличивать j элемент в случае совподения ...но я же не буду прописывать 10 раз его ..это не экономично...и не тактично...тут надо что-то похитрее..
manfeese
 Аватар для manfeese
128 / 127 / 16
Регистрация: 04.01.2009
Сообщений: 415
05.01.2009, 13:44     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #6
Что ты тут намудрил??? Если тебе надо найти количество повторений элемента А[i] в массиве B[j] то это делается намного проще...

Добавлено через 5 минут 5 секунд
Напиши поточнее как тебе это надо?

Добавлено через 11 минут 27 секунд
Из того условия, что я понял, написал примерно такое:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  for (i = 0; i<=1; i++)
  {
    for (j = 0; j < n ; j++)
    {
    if (i==0)
         { if (A[i]==B[j]) //Сналача ищем повторения элемента A[i] в массиве B[]
             { m++; }
         }
    else
         {if (A[i-1]==A[i])//Затем ищем повторения элемента A[i] в массиве А[]
             { k++; }
         }
    }
  }
 
  t=m+k;  //И сумму повторений складываем
Добавлено через 4 минуты 11 секунд
Да, 10 строка будет такой:
C++
1
{if (A[i-1]==A[j+1])
Просто писал на быструю руку. Ну а вообще это еще проще сделать с помощью двух независимых циклов, только заранее нужно указать какой элемент надо сравнивать
ЮрийFM
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
05.01.2009, 17:37  [ТС]     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #7
вся суть в этом...если в массиве A некоторое число x встречается n раз, а в массиве B - m раз - то t будет увеличено на n*m,
m*n - получится количество всех возможных пар одинаковых чисел x из A и B..

Добавлено через 2 часа 48 минут 57 секунд
и нам дано два массива А и В...заполненных случайным образом... и упорядоченных

Добавлено через 35 минут 19 секунд
в общем говоря я пробывал написать код по такому макару...но у меня предыдущий код не работает как надо...вот берем первый элемент массива А сравниваем с массивом В причём в массиве В может быть несколько этого элемена идущих один за одним т.к. массив упорядочен...и входе если равно то M++ потом когда уже не равен следующий элемент массива В то перебрасываемся на массив А и ищем такой же элемент..опять в массиве А элемен может н раз повторяться...походу действий срвавнений К++ ..когда уже не равен то надобно уровнять элемены и перепрыгиваем в начало цикла
manfeese
 Аватар для manfeese
128 / 127 / 16
Регистрация: 04.01.2009
Сообщений: 415
05.01.2009, 19:07     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #8
Еще один вариант нахождения пар себе подобных из двух массивов. Для работы с А массивом одновременно необходимо i-й элемент приравнять некой переменной, скажем temp:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 0; i < n; i++)
 {
    int m = 0, k = 0;
    temp=A[i];
 
  for (int j = 0; j < n; j++)
   {
    if (temp==B[j])
        { m++; }
    if (i==j) 
        { continue; }
    if (temp==A[j]) 
        { k++; }
   }
   printf("m[%i]=%i\n",i,m);
   printf("k[%i]=%i\n\n",i,k);
 }
На экране появляются пары k[i] m[i], указывающие сколько пар в А и В массивах соответственно найдено для i-го элемента массива А

P.S. А вообще писать вот так программы со слов - это не дело. Если не получается написать прогу, напиши полное задание...
ЮрийFM
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
06.01.2009, 11:46  [ТС]     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #9
Пасиб ..большое выручил)


Цитата Сообщение от manfeese Посмотреть сообщение
P.S. А вообще писать вот так программы со слов - это не дело. Если не получается написать прогу, напиши полное задание...

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

Добавлено через 3 минуты 19 секунд
да...и таким пробывал способом только через переменную х ...но у меня была ошибка ты вводил цикл последовательно..т.е. выполнение один за другим...я одновременно...да и на что я надеялся.. спасиб большое!!!

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


Тут вовсе не про пары идёт речь "найти количество совподающих значений элементов А и В"...
Код
for( i=0 ; i<n ; i++ )
{
for( j=0 ; j<n ; j++ )
if (A[i]==B[j]) l++;
}
вот этот код он выполяется за квадрат времени...ведь можно работать сразу с двумя массивами а не по отдельности
manfeese
 Аватар для manfeese
128 / 127 / 16
Регистрация: 04.01.2009
Сообщений: 415
06.01.2009, 13:36     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #10
Можно. А пары я тебе специально выделил; дальше делай с ними что тебе надо!

Добавлено через 6 минут 41 секунду
Так подожди!!! Моя то программка как раз и выполняет параллельную проверку в двух массивах, т.е. одновременно. Берет i-й элемент, приравнивает его к temp, а потом temp сравнивает одновременно с элементами A[j] и B[j], пока не достигнет конца массивов. Затем идет следующий цикл, Берется следующий i+1-элемент, и все проверяется заново...

Добавлено через 1 минуту 51 секунду
Кстати, эта программа может работать и с неупорядоченным массивом
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.01.2009, 16:45     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В
Еще ссылки по теме:

C++ Используя классы, найти сумму всех элементов массива
Используя классы, найти сумму всех элементов массива C++
C++ Используя классы, найти сумму всех элементов массива
Найти произведение положительных элементов массива, используя оператор ветвления if else в цикле for C++
Найти min среди элементов массива с четными индексами, все элементы до него расместить в памяти динамически C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ЮрийFM
0 / 0 / 0
Регистрация: 26.12.2008
Сообщений: 9
06.01.2009, 16:45  [ТС]     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В #11
да ...может но условие что массивы упорядочены дно ведь не просто так))) тут какойто есть нюанс...т.е. можно не каждый брать элемент массива а и б а если идёт за ним одинаковый элемент то можно уже не брать следующий элемент а этот же и дальше сравнивать...

Добавлено через 10 минут 42 секунды
да..и решение нерациональное)) Если данные не упорядочены - то да, требуется либо жертвовать время на сортировку, либо тратить дополнительную память, либо брать трудоёмкий алгоритм, вроде этого

Если же данные по условию упорядочены - то естественно найти более экономное решение специально для этого случая.
Yandex
Объявления
06.01.2009, 16:45     не используя доп. памяти , найти кол. совподающих значений элементов массива А и В
Ответ Создать тему
Опции темы

Текущее время: 02:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru