Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 13.10.2018
Сообщений: 3

Бинарный поиск в отсортированном тексте

24.03.2019, 20:33. Показов 710. Ответов 0

Студворк — интернет-сервис помощи студентам
Задание было, на мой взгляд, простое: произвести бинарный поиск в тексте по одному символу. С последовательным поиском вроде все нормально, однако в бинарном у меня находятся далеко не все символы, не могу понять, с чем это связано, или где ошибка в коде...Прошу помочь

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include "pch.h"
#include <iostream>
#include <fstream>
#include <locale> 
#include <string>
#include <conio.h>
#include <stdio.h>
#include <iomanip>
#include <windows.h>
 
using namespace std;
 
int check1(string s, string slova) {
    if (slova[0] == s[0])
        return 1;
    else return 0;
}
int check2(string s, string slova) {
    if (slova[1] == s[1])
        return 1;
    else return 0;
}
int check3(string s, string slova) {
    if (slova[2] == s[2])
        return 1;
    else return 0;
}
int check4(string s, string slova) {
    if (slova[3] == s[3])
        return 1;
    else return 0;
}
 
//Бинарный поиск
int bin(string str, char simbol)
{
    int size_of_str = size(str); int schet = 0;
    int left = 0; int right = size_of_str;
    while (left <= right)
    {
        int center = left + (right- left) / 2;//int center = (left + right) / 2;
        if (str[center] == simbol)
        {
            schet++; 
            int k = center;
            while (str[k+1] == simbol)
            {
                k++; 
                schet++;
            }
            k = center;
            while (str[k-1] == simbol)
            {
                k--;
                schet++;
            }
            return schet;
        }
        if (simbol < str[center])
            right = center - 1;//center;
        else
            left = center + 1;
    }
    if (schet == 0) return 0;
        //return schet;
}
 
 
string sortAscii(string st)
{
    char tmp;
    for (int i = 1; i < st.length(); i++)
    {
        for (int k = i; k > 0 && st[k - 1] > st[k]; k--)//&& st[k] > 0
        {
            tmp = st[k - 1];
            st[k - 1] = st[k];
            st[k] = tmp;
        }
    }
    return st;
    //cout << st << "\n";
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    //SetConsoleCP(1251);
    //SetConsoleOutputCP(1251);
 
 
    cout << "Дан текст. Дано слово. Найти количество совпадений первой буквы слова с первыми буквами слов в тексте, первых двух букв слова с первыми двумя, первых трех и первых четырех. Бинарный поиск - по первому символу слова." << endl;
    ifstream in("input.txt");
 
    string str; string text;
    int n = 0, d1[1000], d2[1000], d3[1000], d4[1000], s1 = 0, s2 = 0, s3 = 0, s4 = 0;
    string word;
    string*st;  st = new string[1000];
 
metka:
    cout << "Введите слово" << endl;
    cin >> word;
    cout << "word = " << word << endl;
    if (!word[0]) {
        cout << "Слово не введено" << endl << endl;
        goto metka;
    }
 
    else {
       cout << endl << "=== ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК ===" << endl;
 
       while (!in.eof())
       {
           in >> str;
           text = text + str;
           text += ' ';
           st[n] = str;
           n++;
 
           d1[n] = 0;
           d2[n] = 0;
           d3[n] = 0;
           d4[n] = 0;
           if (str.length() >= 1 && check1(str, word)) {
               d1[n]++;
               if (str.length() >= 2 && check2(str, word)) {
                   d2[n]++;
                   if (str.length() >= 3 && check3(str, word)) {
                       d3[n]++;
                       if (str.length() >= 4 && check4(str, word))
                           d4[n]++;
                   }
               }
           }
       }
       if (!text.empty()) {
           cout << endl << "Заданный текст -> " << endl << text << endl; 
       }
    }
                    
    for (int i = 1; i <= n; i++) {
           s1 = s1 + d1[i];
           s2 = s2 + d2[i];
           s3 = s3 + d3[i];
           s4 = s4 + d4[i];
    }
 
    cout << endl << "Первая:" << s1 << " вторая:" << s2 << " третья:" << s3 << " четвертая:" << s4 << endl;
 
                //////////////////////////////////////////////////////////////////////////////////////////////////////
                /////////////////////////////БИНАРНЫЙ ПОИСК ПО 1 СИМВОЛУ/////////////////////////////////
 
            cout << endl << "=== БИНАРНЫЙ ПОИСК ===" << endl;
 
    cout << endl <<  "sortAscii text -> " << endl;
    string sss = sortAscii(text);
    cout << sss << endl;
    int q = size(text);
    cout << "size text = " << q << endl;
        
    char xx = word[0];
    cout << "Бинарный поиcк по первому символу введенного слова => " << xx << endl;
    
    int f;  
    f = bin(text, xx);
    if (f == 0)
        printf("Совпадений не найдено!\n");
    else
        printf("Совпадений найдено: %d\n", f);
    cout << "f111 = " << f << endl;
    
    system("pause");
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
24.03.2019, 20:33
Ответы с готовыми решениями:

Бинарный поиск в отсортированном массиве
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { ...

В отсортированном массиве произвести бинарный поиск индекса элемента со значением K
Дан линейный целочисленный массив из N элементов. Отсортировать элементы массива в порядке не убывания их значений (метод сортировки...

Поиск в отсортированном массиве
Доброго времени суток, столкнулся с трудностью, пишу метод &quot;шаг младенца, шаг великана&quot; заполнил 2 массива, теперь мне нужно их...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
24.03.2019, 20:33
Помогаю со студенческими работами здесь

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

Поиск элемента в отсортированном массиве
какое минимальное колличество итераций при поиске элемента в отсортированом массиве по возрастанию из 100 элементов?

Двоичный поиск в отсортированном массиве
вот у меня есть псевдокод как надо писать двоичный поиск lowerBound = 0 upperBound = size M = (lowerBound + upperBound)...

Поиск в отсортированном массиве структур
Всем привет, пожалуйста помогите с поиском в отсортированном массиве структур. Нужно найти абитуриента со средним баллом 287 ( .ball )....

Поиск нужного элемента в отсортированном массиве
Здраствуйте. Решаю задачу 2 день, неполучается. Подумал сюда обратиться. В общем задача такая. Есть отсортированый массив integer (int a),...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
Расскажи мне о Мире, бродяга
kumehtar 12.11.2025
— Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru