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

Поиск буквы бинарным поиском в тексте - C++

Восстановить пароль Регистрация
 
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
31.05.2013, 20:25     Поиск буквы бинарным поиском в тексте #1
Здравствуйте помогите пожалуйста написать программу, а то в понедельник сдавать,а я вообще не знаю как ее делать. Само задание: Дан текстовый файл из него считывается информация нужно найти букву бинарным поиском. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.05.2013, 20:25     Поиск буквы бинарным поиском в тексте
Посмотрите здесь:

Процентное содержание в тексте буквы а C++
C++ Посчитать в тексте количество слов с заглавной буквы
C++ в заданном тексте после каждой буквы «b» добавляет буквы «ak».
Буквы в русском тексте C++
Удвоить вхождение некоторой буквы в тексте. C++
C++ Количество вхождений в тексте каждой буквы
C++ найти в тексте все гласные буквы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хулиган
 Аватар для Хулиган
85 / 80 / 12
Регистрация: 08.08.2012
Сообщений: 737
31.05.2013, 20:52     Поиск буквы бинарным поиском в тексте #2
бинарный поиск самому нужно реализовать или можно воспользоватся стандартным?
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
31.05.2013, 21:04  [ТС]     Поиск буквы бинарным поиском в тексте #3
самому
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
31.05.2013, 21:29     Поиск буквы бинарным поиском в тексте #4
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
#include <iostream>
#include <string>
 
int main() {
  std::string s = "abcdefghijklmnop";
  int first = 0, average = 0, last = s.length() - 1;
  char ch;
  std::cout << "String: " << s << std::endl;
  std::cout << "Please enter char: ";
  std::cin >> ch;
  while(first < last) {
    average = first + (last - first) / 2;
    if(ch <= s[average])
      last = average;
    else
      first++;
  }
  
  if(s[last] == ch)
    std::cout << "Index: " << last << std::endl;
  else
    std::cout << "Not Found!" << std::endl;
  
  return 0;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
12085 / 6946 / 782
Регистрация: 27.09.2012
Сообщений: 17,230
Записей в блоге: 2
Завершенные тесты: 1
01.06.2013, 09:28     Поиск буквы бинарным поиском в тексте #5
Считывать из файла можете?
Считали, потом std::sort и std::binary_search
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
01.06.2013, 11:37  [ТС]     Поиск буквы бинарным поиском в тексте #6
В считывании то и был вопрос остальные то алгоритмы есть, а то в интренет искал, но не нашел
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
01.06.2013, 11:51     Поиск буквы бинарным поиском в тексте #7
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
#include <iostream>
#include <fstream>
#include <string>
 
int binarySearch(std::string, char);
 
int main() {
  std::ifstream fin("file.txt");
  std::string str, tmp;
  
  while(!fin.eof()) {
    std::getline(fin, tmp);
    str.append(tmp);
  }
  fin.close();
  
  char ch;
  std::cout << "String: " << str << std::endl;
  std::cout << "Enter char: ";
  std::cin >> ch;
  
  int index = binarySearch(str, ch);
  if(ch == str[index])
    std::cout << "Index: " << index << std::endl;
  else
    std::cout << "Not found" << std::endl;
  return 0;
}
 
int binarySearch(std::string str, char ch) {
  int first = 0, average = 0, last = str.length() - 1;
  while(first < last) {
    average = first + (last - first) / 2;
    if(ch <= str[average])
      last = average;
    else
      first++;
  }
  return last;
}
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
01.06.2013, 16:59  [ТС]     Поиск буквы бинарным поиском в тексте #8
Спасибо, но программа работает только для одного слова, плюс ищет только одно совпадение, то есть если будет слово Good и искомой буквой будет о, то индекс выведет 1, а 2 не будет как это исправить?
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
01.06.2013, 17:26     Поиск буквы бинарным поиском в тексте #9
Цитата Сообщение от vladislav23 Посмотреть сообщение
но программа работает только для одного слова?
Файл:
Кликните здесь для просмотра всего текста
abcde fghijkl mnopqrst uvwxyz

Бинарный поиск применяется для отсортированного массива(строки как здесь)

Добавлено через 16 минут
Я думаю что бинарный поиск лучше здесь не использовать
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
02.06.2013, 15:41  [ТС]     Поиск буквы бинарным поиском в тексте #10
А можете пожалуйста скинуть фрагмент кода, где идет посимвольной считывание текста в чаровый массив

Добавлено через 5 часов 45 минут
...
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
02.06.2013, 15:43     Поиск буквы бинарным поиском в тексте #11
Цитата Сообщение от vladislav23 Посмотреть сообщение
А можете пожалуйста скинуть фрагмент кода, где идет посимвольной считывание текста в чаровый массив

Добавлено через 5 часов 45 минут
...
Здесь нету "массива чаров", здесь используется класс string
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
02.06.2013, 18:14  [ТС]     Поиск буквы бинарным поиском в тексте #12
это я понимаю, а если использовать чаровый массив его преобразовать в интовой отсортировать по ASCII кодам и там уже искать, так можно же?
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
02.06.2013, 18:15     Поиск буквы бинарным поиском в тексте #13
Цитата Сообщение от vladislav23 Посмотреть сообщение
это я понимаю, а если использовать чаровый массив его преобразовать в интовой отсортировать по ASCII кодам и там уже искать, так можно же?
Массив уже отсортирован по ASCII кодам, он и ищет по ним
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.06.2013, 18:21     Поиск буквы бинарным поиском в тексте #14
Цитата Сообщение от MarVaL Посмотреть сообщение
average = first + (last - first) / 2;
а слабо вот так : average = (last + first) / 2;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.06.2013, 18:21     Поиск буквы бинарным поиском в тексте
Еще ссылки по теме:

Буквы в русском тексте C++
C++ Каждое предложение в тексте сделать с заглавной буквы
C++ Найти в тексте слова, длина которых 4 буквы
Поиск бинарным методом C++
C++ Поиздеавться над бинарным поиском

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

Или воспользуйтесь поиском по форуму:
MarVaL
С++ Beginner
 Аватар для MarVaL
116 / 116 / 16
Регистрация: 28.02.2013
Сообщений: 246
02.06.2013, 18:21     Поиск буквы бинарным поиском в тексте #15
Цитата Сообщение от Ternsip Посмотреть сообщение
а слабо вот так : average = (last + first) / 2;
да, да)
Yandex
Объявления
02.06.2013, 18:21     Поиск буквы бинарным поиском в тексте
Ответ Создать тему
Опции темы

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