Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Ответ
 
Опции темы
Старый 17.12.2012, 11:41   #1
FleXt
Пользователь
 
Регистрация: 01.12.2012
Сообщений: 28
По умолчанию Определить количество строк в максимальном множестве попарно непохожих строк заданной матрицы Cи/С++

Код:
#include <stdio.h>
#define N 100
#define M 100
int i,j,k,t,l;
void input (int a[][N],int y, int u)//ввод
{
    for(int i=0;i<y;i++)
       for(int j=0;j<u;j++)
           scanf("%d", &a[i][j]);
}
void bubbleSort(int a[][M],int y, int u )//сортировка
{
   for(i=0;i<y;i++)
        for(j=0;j<u;j++)
            for(k=0;k<u-j-1;k++)
                if(a[i][k]>a[i][k+1])
                   {
                        t=a[i][k];
                        a[i][k]=a[i][k+1];
                        a[i][k+1]=t;
                   }
}
 
 
int main()
{
    int a[N][M];
    int b[N];
    int s,c;
    scanf("%d%d",&s,&c);   
    input(a,s,c);
    bubbleSort(a,s,c);
 
  
    for(i=0;i<s;i++) //удаляем  одинаковые цифры
        {
            k=0;
            for(j=1;j<c;j++)
               if(a[i][j-k-1]==a[i][j])
                  k++;
               else
                  a[i][j-k]=a[i][j];
            b[i]=c-k; //запоминаем длину каждой строчки
         }    
    t=0;
    
        

    /* Вот тут надо определить  размер максимального множества попарно непохожих строк*/
    


    printf("%d\n",t);
}
Различные строки матрицы назовем
похожими, если совпадают множества чисел, встречающихся в этих строках. В общем столкнулся с проблемой, я не знаю как осуществить сравнение и найти это самое множество , а точнее количество строк в нем. Помогите, решить.
FleXt вне форума Ответить с цитированием
Старый 17.12.2012, 11:55   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Определить количество строк в максимальном множестве попарно непохожих строк заданной матрицы
Для каждой строки, если для каждой предыдущей строки множества значений в строках не совпадают, увеличить "число строк" на 1.
Для проверки на совпадение множеств множества рекомендуется предварительно упорядочить.
Abstraction вне форума Ответить с цитированием
Старый 17.12.2012, 11:58   #3
FleXt
Пользователь
 
Регистрация: 01.12.2012
Сообщений: 28
По умолчанию

Цитата:
Сообщение от Abstraction Посмотреть сообщение
Для каждой строки, если для каждой предыдущей строки множества значений в строках не совпадают, увеличить "число строк" на 1.
Для проверки на совпадение множеств множества рекомендуется предварительно упорядочить.
строки я уже упорядочил и удалил повторяющиеся элементы, не понятно как само сравнение осуществить, подскажите алгоритм
FleXt вне форума Ответить с цитированием
Старый 17.12.2012, 12:02   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Пусть у нас есть два упорядоченных списка элементов множеств без повторений. Вам очевидно, что множества совпадают тогда и только тогда, когда эти списки равны? Является ли проблемой проверка списков на равенство?
Abstraction вне форума Ответить с цитированием
Старый 17.12.2012, 12:08   #5
FleXt
Пользователь
 
Регистрация: 01.12.2012
Сообщений: 28
По умолчанию

Цитата:
Сообщение от Abstraction Посмотреть сообщение
Пусть у нас есть два упорядоченных списка элементов множеств без повторений. Вам очевидно, что множества совпадают тогда и только тогда, когда эти списки равны? Является ли проблемой проверка списков на равенство?
Код:
   for(i=0;i<s;i++)
      for(j=0;j<s;j++)
         if(memcmp(a[i],a[j],s))
            t++;
будет ли это сравнение правильным?
FleXt вне форума Ответить с цитированием
Старый 17.12.2012, 12:20   #6
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Для каждой строки, если для каждой предыдущей строки множества значений в строках не совпадают, увеличить "число строк" на 1.
А у Вас что? Кроме того, вроде кто-то что-то сказал про удаление дубликатов - но строка "2 2 2 2 2" после удаления дубликатов состоит из одного элемента, а не из пяти.

Вообще, возьмите небольшой пример и проверяйте свой алгоритм на нём.
Скажем,
Код:
1 2 1 1
3 2 1 4
1 3 4 2
1 1 2 2
Должен получиться ответ "2", если получается другой - значит, неправильно.
Abstraction вне форума Ответить с цитированием
Старый 17.12.2012, 12:42   #7
FleXt
Пользователь
 
Регистрация: 01.12.2012
Сообщений: 28
По умолчанию

Цитата:
Сообщение от Abstraction Посмотреть сообщение
А у Вас что? Кроме того, вроде кто-то что-то сказал про удаление дубликатов - но строка "2 2 2 2 2" после удаления дубликатов состоит из одного элемента, а не из пяти.

Вообще, возьмите небольшой пример и проверяйте свой алгоритм на нём.
Скажем,
Код:
1 2 1 1
3 2 1 4
1 3 4 2
1 1 2 2
Должен получиться ответ "2", если получается другой - значит, неправильно.
Код:
for(i=0;i<s;i++)
      for(j=0;j<s;j++)
          {if(b[i]!=b[j]) {t++;break;}
            else
           if(memcmp(a[j],a[i],b[i]))
            {t++; break;}
          }


    printf("%d\n",t);
рассуждаю так, если длины строк не равны, то они уже не похожи, увеличиваю счетчик, если длины равны, то проверяю строки на равенство, но ответ все равно не верный
FleXt вне форума Ответить с цитированием
Старый 17.12.2012, 13:01   #8
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Да. Ещё раз:
Цитата:
Для каждой строки, если для каждой предыдущей строки множества значений в строках не совпадают
Где у Вас "предыдущая" строка?
Затем,
Цитата:
если длины строк не равны, то они уже не похожи, увеличиваю счетчик
Неверно логически (счётчик увеличивается, если строка не похожа ни на одну из предыдущих, а не если она не похожа хотя бы на одну), да ещё и в коде реализовано не это, а "если длины строк не равны, увеличиваю счётчик и прекращаю дальнейшие проверки".

Использование отладчика выявило бы эти проблемы мгновенно.
Abstraction вне форума Ответить с цитированием
Старый 17.12.2012, 13:10   #9
FleXt
Пользователь
 
Регистрация: 01.12.2012
Сообщений: 28
По умолчанию

Цитата:
Сообщение от Abstraction Посмотреть сообщение
Да. Ещё раз:Где у Вас "предыдущая" строка?
Затем, Неверно логически (счётчик увеличивается, если строка не похожа ни на одну из предыдущих, а не если она не похожа хотя бы на одну), да ещё и в коде реализовано не это, а "если длины строк не равны, увеличиваю счётчик и прекращаю дальнейшие проверки".

Использование отладчика выявило бы эти проблемы мгновенно.
я не могу понять как осуществить этот самый перебор , алгоритм вроде я понял : для первой строки предыдущих нет, значит увеличиваем счетчик, берем вторую строку, для нее предыдущая это первая, если не равны , то опять увеличиваем счетчик, для третье строки соответственно предыдущими будут первая и вторая, если третья не равна первой и второй, то опять увеличиваем счетчик, поясните как сделать перебор
FleXt вне форума Ответить с цитированием
Старый 17.12.2012, 13:23   #10
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Код:
Инициализировать "число уникальных" нулём
Для каждой строки,
  Инициализировать "флаг совпадения" ложью
  Для каждой ПРЕДЫДУЩЕЙ строки
    Если совпадает с текущей
    (т.е. одинаковая длина И 
    memcmp на (длина) _элементов_ - а не байт! - показывает совпадение),
      Установить "флаг совпадения" в истину
      покинуть цикл
  Если "флаг совпадения" - ложь (т.е. мы успешно перебрали предыдущие строки),
    Увеличить "число уникальных" на 1
Abstraction вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сканирования строк. Зная количество строк и первый элемент, это количество символов с троке. dimon9 Общие вопросы C/C++ 8 02.11.2012 21:40
Найти минимальный элемент среди всех элементов тех строк заданной матрицы, которые упорядочены по убыванию. KObotan Общие вопросы C/C++ 4 16.09.2012 13:54
В квадратной матрице необходимо определить количество строк состоящих из равных элементов poison777 Помощь студентам 3 15.03.2011 18:41
Найти количество строк, среднее арифметическое элементов которых меньше заданной величины Sergeo_89 Паскаль, Turbo Pascal, PascalABC.NET 3 05.12.2008 21:25


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS
Здесь нужно купить рекламу за 7 тыс руб в месяц! )
пишите сюда - alarforum@yandex.ru
ИКС 840