Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Сколько комбинаций в строке  (Прочитано 12426 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mfcer__
Команда клуба

ru
Offline Offline

« : 27-11-2003 20:40 » 

Добрый день!

У меня есть вот такая задачка:
Есть объект CString : "aabcabac"
Нужно посчитать сколько комбинаций из двух символов встречается в этой строке  и занести это в динамически создаваемую двумерную матрицу. То есть для приведенного выше примера нужно сделать так:
 
Цитата
--a            b           c
------------------------------
a    1            2           1
------------------------------
b    1            0           1
------------------------------
c    1            0           0

То есть комбинация "аа" встречается 1 раз
"ab" - 2
"ac" - 1
"ba" - 1
"bb" - 0
"bc" - 1
и так далее
Если кто поможет буду очень балгодарен
Записан
Alf
Гость
« Ответ #1 : 27-11-2003 20:56 » 

Пока что слишком нечеткое условие задачи.
Для начала не мешало бы определиться с алфавитом.
Какие вообще символы допустимы в строке? Могут ли попадаться пробелы, знаки препинания и т.д.? Если могут, то учитывать ли их в сочетаниях или же пропускать, считать только буквы?
Наконец, в какой кодировке должна работать программа? Достаточно 256-символьного набора ASCII или же могут встретиться любые символы UNICODE?
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #2 : 27-11-2003 21:49 » 

256 сивольного набора ANSI хватит. Символы могут встречаться и их нужно учитывать если их код > 32.
Записан
Alf
Гость
« Ответ #3 : 27-11-2003 22:13 » 

ОК, завтра вечером накидаю решение.
А если самому захочется попробовать раньше, идея такая.
Заводим матрицу счетчиков 256*256 и обнуляем их.
Смотрим текущий символ и следующий за ним. Если код обоих >32, то код первого символа берем за номер строки в матрице, второго - за номер столбца и инкрементируем элемент на их пересечении. И так до упора, пока строка не закончится.
Тут другой вопрос щекотливый возникает: куда потом это добро девать? Марица ведь неслабая получается, 64К элементов. Даже если первые 32 символа откинуть, и то под 50К будет. Не на экран же эту благодать выводить.
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #4 : 27-11-2003 22:25 » 

а зачем делать матрицу 256 на 256  Я шокирован! , ведь нам известно сколько в строке рназных символов. Смотри пример выше: матрица 3 на 3.
Записан
Mfcer__
Команда клуба

ru
Offline Offline

« Ответ #5 : 27-11-2003 23:06 » 

while(str.Find(temp)!=-1)
 действия
что в этой строчке не так
Записан
SlavaI
Главный специалист

ru
Offline Offline

« Ответ #6 : 28-11-2003 07:09 » 

Для этого дела надо использовать контейнер map из STL. А дальше все просто- проходишь один раз по строке и заносишь данные. Каких сочетаний не буде в map- 0 значит.
Записан
Serega
Гость
« Ответ #7 : 28-11-2003 09:40 » 

Глянь, может такой код подойдет
Код:
struct CharPair
{
char first;
char second;

CharPair(char f, char s) : first(f), second(s) {}

CharPair(const CharPair& other) : first(other.first), second(other.second) {}

bool operator<(const CharPair& other) const
{
if( first < other.first ) return true;
if( second < other.second ) return true;
return false;
}
};

typedef std::map< CharPair, int > pair_matrix;

pair_matrix CountCharPairs(CString str)
{
pair_matrix result;
int i = 0;
char first = str[i];
char second;
while( ++i < str.GetLength() )
{
second = str[i];
result[CharPair(first,second)]++;
first = second;
}
return result;
}

void Print(pair_matrix& matrix)
{
pair_matrix::iterator begin = matrix.begin();
pair_matrix::iterator end   = matrix.end();
for(; begin != end; ++begin )
{
std::cout << begin->first.first << begin->first.second;
std::cout << " - " << begin->second << std::endl;
}
}
« Последнее редактирование: 22-11-2007 16:08 от Алексей1153++ » Записан
Alf
Гость
« Ответ #8 : 28-11-2003 12:43 » 

Цитата: Mfcer__
а зачем делать матрицу 256 на 256  Я шокирован! , ведь нам известно сколько в строке рназных символов. Смотри пример выше: матрица 3 на 3.

Во-первых, откуда мы это знаем заранее, на момент написания программы?
При таком подходе мы сначала должны проанализировать строку, выудить из нее уникальные символы, а только затем уже строить матрицу по их количеству.
Во-вторых, нет гарантии, что коды символов идут подряд, а не вразброс. Тогда нам придется строить дополнительно таблицу соответствия кода символа номеру строки/столбца в матрице и обращаться к элементам матрицы косвенно.
Наилучший вариант, конечно, - тот, который указал SlavaI, т.е. использование ассоциативного массива. К тому же он будет работать и в случае, если понадобится, скажем, считать комбинации по 3 символа и более. Но раз уж в условии задачи сказано, что это должна быть именно матрица, его пришлось отложить.
Записан
ysv_
Помогающий

ua
Offline Offline

« Ответ #9 : 28-11-2003 15:34 » 

Пример программы:
=============================================
#include <string>
#include <map>
#include <iostream>
#include <cstring>

class CharMatrix
{
  public:
    typedef std::map<char, int> chars;

  public:
    CharMatrix(const char* s): s_(s), cntArray_(0)
    {
//      int len=std::strlen(s);
      int j=0;
      for (const char* p=s; *p!=0; ++p)
      {
        if (*p<32) continue;
        if (chars_.insert(chars::value_type(*p, j)).second) ++j;
      }
     
      cntArray_=new int[GetRowCount()*GetRowCount()];
     
      memset(cntArray_, 0, sizeof(int)*GetElemCount());
     
      int i=0;
      for (const char *p=s; *p!=0; ++p)
      {
        i=chars_.find(*p)->second;
        if (*(p+1)==0) break;
        j=chars_.find(*(p+1))->second;
//        std::cout<<i<<", "<<j<<'\n';
        ++cntArray_[i*GetRowCount()+j];
      }

    }

    ~CharMatrix() {delete cntArray_;}
    int GetRowCount() {return chars_.size();}
    int GetElemCount() {return GetRowCount()*GetRowCount();}
    int GetElement(int i, int j) {return cntArray_[i*GetRowCount()+j];}

  private:
    std::string s_;
    int *cntArray_;
    chars chars_;
};

int main()
{
  CharMatrix m("aabcabac");
  std::cout<<m.GetRowCount()<<std::endl;
  int i, j;
  for (i=0; i<m.GetRowCount(); ++i)
  {
    for (j=0; j<m.GetRowCount(); ++j)
    {
      std::cout<<m.GetElement(i, j)<<' ';
    }
    std::cout<<std::endl;
  }
}
=============================================
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines