Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/26: Рейтинг темы: голосов - 26, средняя оценка - 5.00
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
1

Найти в строке string наиболее часто встречающуюся пару символов и заменить на один новый символ

31.08.2010, 20:32. Показов 5419. Ответов 17
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
нужно найти в строке пару символов, которые повторяются чаще всех и заменить их на один новый символ например acfghhachfjiac "ac" заменить на "X" и чтобы в итоге вышло XfghhXhfjiX

как считать строку из файла в стринг, если она содержит пробелы (нужно считать из файла строку с пробелами)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.08.2010, 20:32
Ответы с готовыми решениями:

Строка, найти в данной строке наиболее часто встречающуюся букву
Строка, введенная с клавиатуры, содержит набор символов: буквы, цифры, знаки операций, спец....

Ввести строку символов. Найти букву, наиболее часто встречающуюся в тексте.
НЕ могу решить задачу!! Помогите! Ввести строку символов. Найти букву, наиболее часто...

Найти наиболее часто встречающуюся букву и также вывести на экран в отдельной строке
Помогите с прогой. : В произвольном тексте (взятом из файла), содержащем не более 10 строк, в...

Заменить в строке пару символов на один
Доброго времени суток! Помогите, пожалуйста, с программой Задание: Составить программу, которая...

17
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
31.08.2010, 20:39 2
Mayonez, 2
C++
1
std::getline(имя потока, имя строки);
1
Заблокирован
31.08.2010, 20:45 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <fstream>
using std::ifstream;
#include <string>
using std::string;
 
int main(){
    string s;
    ifstream f;
 
    f.open("in.txt");
    if(!f)
        return 1;
 
    while(!f.eof())
        s+=f.get();
 
    return 0;
}
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
31.08.2010, 20:48 4
Mayonez,
Навскидку, первое, что пришло в голову... Проходя по строке в первый раз, создать таблицу уникальных пар (т.е. в строке acfghhachfjiac уникальными парами будут ac, cf, fg, gh, hh, ha, ch, hf, fj, ji и ia). Затем для каждой пары поставить в соответствие количество раз, которое она встречается в строке (для каждой пары делаем проход по строке и считаем количество совпадений). Ну а затем в новый массив переписываем входную строку, постоянно отслеживая пару, повторяющуюся максимальное число раз, и при переписывании заменяем её на требуемый символ...

Кстати, первый и второй пункты можно объединить (видим пару - проверяем, нет ли её в таблице, если нет - добавляем, а если нашли, тут же увеличиваем её счётчик и переходим к следующей паре).
0
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
31.08.2010, 21:50  [ТС] 5
Цитата Сообщение от silent_1991 Посмотреть сообщение
Mayonez,
Навскидку, первое, что пришло в голову... Проходя по строке в первый раз, создать таблицу уникальных пар (т.е. в строке acfghhachfjiac уникальными парами будут ac, cf, fg, gh, hh, ha, ch, hf, fj, ji и ia). Затем для каждой пары поставить в соответствие количество раз, которое она встречается в строке (для каждой пары делаем проход по строке и считаем количество совпадений). Ну а затем в новый массив переписываем входную строку, постоянно отслеживая пару, повторяющуюся максимальное число раз, и при переписывании заменяем её на требуемый символ...

Кстати, первый и второй пункты можно объединить (видим пару - проверяем, нет ли её в таблице, если нет - добавляем, а если нашли, тут же увеличиваем её счётчик и переходим к следующей паре).
это я понимаю, но реализовать как-то не получается
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
31.08.2010, 21:57 6
Mayonez,
Почти дописал))) Правда на Си будет, ну и с файлами я не стал заморачиваться, сделал ввод с клавиатуры, так что тебе останется только ввод-вывод переделать.

Добавлено через 5 минут
Кстати, а если несколько пар повторяются одинаковое число раз, и это как раз максимальное число повторений, как тогда поступить?
0
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
31.08.2010, 22:08  [ТС] 7
заменить или любую из пар или обе но на две разные буквы
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
31.08.2010, 22:09 8
Т.е. возможно любое решение? Разрешите, я остановлюсь на первом, когда выложу код, скажу идеи, как его можно переделать под второй вариант...
0
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
31.08.2010, 22:11  [ТС] 9
окей, давай
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
31.08.2010, 22:48 10
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
struct pair
{
    char p[2];
    int counter;
    struct pair *next;
};
 
struct pair *search(struct pair *start, char *need);
void max(struct pair *start, char *need);
struct pair *unique(char *str);
void exchange(struct pair *first, char ch, char *instr, char *outstr);
 
struct pair *search(struct pair *start, char *need)
{
    while (start)
    {
        if (start->p[0] == need[0] && start->p[1] == need[1])
            return start;
 
        start = start->next;
    }
 
    return NULL;
}
 
void max(struct pair *start, char *need)
{
    int max;
    
    max = start->counter;
    need[0] = start->p[0];
    need[1] = start->p[1];
    
    while (start)
    {
        if (start->counter > max)
        {
            max = start->counter;
            need[0] = start->p[0];
            need[1] = start->p[1];
        }
 
        start = start->next;
    }
}
 
struct pair *unique(char *str)
{
    struct pair *first, *last, *node;
    char temp[2];
    int i;
    
    first = (struct pair *)malloc(sizeof(struct pair));
    first->p[0] = str[0];
    first->p[1] = str[1];
    first->counter = 1;
    first->next = NULL;
    node = first;
    last = first;
    
    for (i = 1; i < strlen(str) - 1; i++)
    {
        temp[0] = str[i];
        temp[1] = str[i + 1];
        node = search(first, temp);
        
        if (!node)
        {
            node = (struct pair *)malloc(sizeof(struct pair));
            node->p[0] = temp[0];
            node->p[1] = temp[1];
            node->counter = 1;
            last->next = node;
            node->next = NULL;
            last = node;
        }
        else
        {
            node->counter++;
        }
    }
    
    return first;
}
 
void exchange(struct pair *first, char ch, char *instr, char *outstr)
{
    char need[2];
    int i, j;
    
    max(first, need);
    
    for (i = 0, j = 0; i <= strlen(instr); i++)
    {
        if (instr[i] == need[0] && instr[i + 1] == need[1])
        {
            outstr[j++] = ch;
            i++;
        }
        else
        {
            outstr[j++] = instr[i];
        }
    }
}
 
int main()
{
    char instr[40];
    char outstr[40];
    char c;
    struct pair *p;
    
    printf("Vvedite stroku: ");
    scanf("%s", instr);
    printf("Vvedite simvol: ");
    scanf("%s", &c);
    p = unique(instr);
    exchange(p, c, instr, outstr);
    printf("Rezultat: %s", outstr);
    
    getch();
    return 0;
}
Добавлено через 7 минут
Для, того, чтобы заменять другие пары, нужно сохранить найденное в первый раз максимальное число повторений, затем, после того, как произошла первая замена, входной строкой мы делаем получившуюся выходную (в которой один вид пар уже заменён некоторым символом), а из списка пар удаляем элемент, соответствующий заменяемой только что паре. Далее ищем в списке элемент, значение counter которого совпадает с ранее найденным максимальным значением (его менять больше не будем), и производим замену в строке уже этой пары. И это всё проделываем в цикле, пока есть элементы списка, значение counter которых совпадает с найденным в самый первый раз максимальным значением.
1
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
01.09.2010, 15:57  [ТС] 11
вот что получилось у меня на с+++STL
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
//поиск и замена
string search(string s);
string replace(string what, string slov);
 
int main()
{
   string s;
   cin>>s;
   //если найдены пары, которые повторяются, то
   while(search(s)!="")
   //заменяем их на новый символ
      s=replace(search(s), s);
      
   //что получилось в конце
   cout<<s<<endl;
   return 0;
}
 
string search(string s)
{
   vector<int> max(s.size(), 1);
   int result, back=0;
   for(int i=0; i<s.size(); i++)
      for(int j=0; j<s.size(); j++)
      {
         if(j==i || j+1==i) {j+=2; continue;}
         if(s[j]==s[i] && s[j+1]==s[i+1]) max[i]++;
      }
   result=max[0];
   for(int i=0; i<max.size()-1; i++)
      if(max[i]>result) {result=max[i]; back=i;}
   string zam;
   string no="";
   zam+=s[back];
   zam+=s[back+1];
   if(result==1) return no;
   return zam;
}
 
string replace(string what, string slov)
{
   string result;
   static char simvol=128;
   for(int i=0; i<slov.size()-1; i++)
   {
      if(what[0]==slov[i] && what[1]==slov[i+1])
      {
         result+=simvol;
         i++;
      }
      else 
      result+=slov[i];
   }
   simvol++;
   return result;
}
у меня заменяет абсолютно все пары, которые повторяются
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
01.09.2010, 17:45 12
А вот что у меня получилось C++ + STL:
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
#include <iostream>
#include <cstdlib>
#include <map>
#include <string>
#include <algorithm>
 
bool compareMap(const std::pair<std::string, size_t>& a,
                const std::pair<std::string, size_t>& b)
{
    return a.second < b.second;
}
 
int main()
{
    std::string str;
    std::map<std::string, size_t> pairs;
    std::cout << "Input the string to proccess: ";
    std::getline(std::cin, str);
    char c;
    std::cout << "Input the character to replace: ";
    std::cin >> c;
    size_t index = 0;
    while(index != str.size() - 2)
    {
        std::string pair = str.substr(index++, 2);
        if(pair.find(' ') == std::string::npos)
            ++pairs[pair];
    }
    std::map<std::string, size_t>::const_iterator it =
            std::max_element(pairs.begin(), pairs.end(), compareMap);
    std::cout << "Replacing \'" << it->first << "\' with \'" << c << "\'..."
            << std::endl;
    while((index = str.find(it->first)) != std::string::npos)
        str.replace(index, 2, 1, c);
    std::cout << "Proccessed string: \'" << str << "\'" << std::endl;
    return EXIT_SUCCESS;
}
2
2 / 2 / 0
Регистрация: 30.08.2010
Сообщений: 12
02.09.2010, 10:06 13
Цитата Сообщение от Mayonez Посмотреть сообщение
заменить или любую из пар или обе но на две разные буквы
нда... интересно, как это (замена на две разные буквы) получится с последовательностью ababababababab (ab и ba встречаются одинаково часто)
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
02.09.2010, 10:09 14
Банально - первая найденная пара - ab - будет первой в списке уникальных. При поиске пар с максимальной повторяемостью она также всплывёт первой - её-то и будем заменять... А то, что есть ещё и ba, мы и не узнаем потом, да и это нюансы, которые обычно решаются так, как я и описал выше, по принципу "кто первый встал - того и тапки"...
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
02.09.2010, 10:13 15
Цитата Сообщение от punhin Посмотреть сообщение
ababababababab (ab и ba встречаются одинаково часто)
Как так - одинаково? ab встречается 7 раз, ba - 6.
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
02.09.2010, 10:14 16
abababababababa
А так?
0
Nameless One
02.09.2010, 10:38
  #17

Не по теме:

silent_1991, тут ты меня и подловил :)

0
392 / 284 / 53
Регистрация: 26.12.2009
Сообщений: 874
03.09.2010, 14:50  [ТС] 18
Цитата Сообщение от punhin Посмотреть сообщение
нда... интересно, как это (замена на две разные буквы) получится с последовательностью ababababababab (ab и ba встречаются одинаково часто)
скомпилируй програму из моего кода и увидишь...
0
03.09.2010, 14:50
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.09.2010, 14:50
Помогаю со студенческими работами здесь

Задача. В последовательности символов, оканчивающихся точкой, найти наиболее часто встречающийся символ
Задача. В последовательности символов, оканчивающихся точкой, найти наиболее часто встречающийся...

Найти цифру наиболее часто встречающуюся в тексте
Дан непустой текст из цифр, за которым следует точка. Найдите цифру, наиболее часто встречающуюся...

Найти букву, наиболее часто встречающуюся в тексте.
Ввести строку символов. Найти букву, наиболее часто встречающуюся в тексте. Нужно написать на СИ,...

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


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru