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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
gor777
0 / 0 / 0
Регистрация: 21.06.2014
Сообщений: 5
#1

Счетчик в Binsearch - C++

21.06.2014, 02:12. Просмотров 269. Ответов 1
Метки нет (Все метки)

Поиск в отсортированной строке длины n буквы (char k)
Помогите поставить счетчик, который будет показывать, сколько раз встречается эта буква в слове
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int BinSearch(string M, int n, char k)
{
    int L = 0;
    int R = n; 
    int m;
    int z = 0;
    if (M[0]==k){m=1;}
    else{
    while (L<R && z!=n) 
    {
        z++;
        m = (L+R)/2;   
        if (k > M[m]) L = m; 
        if (k < M[m]) R = m;
    if (k == M[m]) break; // надо не break, а цикл, в котором и вставить счетчик количества совпадений
    }
    }
    if (z==n){m=0;}
    return m; // надо заменить на вывод счетчика
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2014, 02:12     Счетчик в Binsearch
Посмотрите здесь:

Простейший счетчик C++
C++ Счетчик С++
счетчик дескрипторов C++
Переменная-счетчик C++
C++ Нужен с счетчик
Счетчик циклов C++
C++ Счетчик нужен
счетчик цикла for C++
C++ Счетчик
C++ Счетчик попыток
Счетчик сравнения C++
C++ Электрический счетчик. С++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
21.06.2014, 02:39     Счетчик в Binsearch #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
1)а зачем передавать n в функцию, если искать надо все равно во всей строке???
2) тут надо 2 бинпоиска писать, один найдет самое левое вхождение, другой - самое правое, и ответ будет их разница + 1ж

Добавлено через 21 минуту
вот накидал.

C++ (Qt)
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
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int f(string s, char k)
{
    if(s[0] > k)
        return 0;
    if(s[s.length() - 1] < k)
        return 0;
 
    int n = s.length();
    int l = 0, r = n - 1;
    while(r - l > 1)
    {
        int mid = (l + r) / 2;
        if(s[mid] >= k)
            r = mid;
        else
            l = mid;
    }
 
    while(l < n && s[l] < k)
        l++;
    if(l == n)
        return 0;
 
    if(s[l] != k)
        return 0;
 
    int lf = l;
 
    l = 0, r = n - 1;
    while(r - l > 1)
    {
        int mid = (l + r) / 2;
        if(s[mid] <= k)
            l = mid;
        else
            r = mid;
    }
 
    while(l + 1 < n && s[l + 1] == k)
        l++;
 
    int rg = l;
 
    return rg - lf + 1;
}
 
int main()
{
    string s;
    getline(cin, s);
    sort(s.begin(), s.end());
    cout << s << endl;
 
    for(char c = 'a'; c <= 'z'; c++)
    {
        cout << "symbol == " << c << " cnt == " << f(s, c) << endl;
    }
    return 0;
}
Yandex
Объявления
21.06.2014, 02:39     Счетчик в Binsearch
Ответ Создать тему
Опции темы

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