Вывести все слова, в которых есть буква "a"

@mister pOO · Регистрация: 26.11.2011

Студворк — интернет-сервис помощи студентам

не могу найти ошибку

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
int i=0,j=0,a=0,schet=0;
char s[50],s1[50];
     cin.getline(s,50);
             while(i<50)
{
                        if((isspace(s[i])) && (isalnum(s[i-1])))
{    
     j=i-1;schet=0;
             while((!isspace(s[j])) || (s[j]=='\n'))
{    
     j--;
                        if(s[j]=='a')
     schet++;
     }
             for(j;j<i+1;j++)
{
                        if(schet>=1)
     s1[j]=s[j];
}
 
}
    i++;
}cout<<s1<<endl;
getch();

нужно вывести все слова в которых есть буква a

Добавлено через 2 часа 30 минут
помогите пожалуйста...

@alkagolik · 30.11.2011, 01:35

Сообщение от fasked

но разбираться, если честно, лень

та же беда

@Thinker · 30.11.2011, 16:26

Сообщение от alkagolik

самообман. При расчете сложности не учитана сложность сортировки. Реально задача реализуется сравнением каждого байта массива s. Можно конечно (и нужно) оптимизировать под наиболее вероятные случаи, но сути это не меняет.

Все учитано, мы же рассматриваем O-большое. При этом сложность подсчитана для среднего случая. Итак, мы остановились пока на алгоритме сложностью O(nlog(m))

Добавлено через 8 часов 56 минут
fasked,alkagolik, ну так что, выкладывать алгоритм сложностью m+n?

@fasked · 30.11.2011, 16:30

Сообщение от Thinker

ну так что, выкладывать алгоритм сложностью m+n?

Давно пора

@Thinker · 30.11.2011, 16:30

Итак, сложность данного алгоритма m+n:

C
1
2
3
4
5
6
7
8
9
10
int Count(char *s, char *set)
{
    int i, count = 0, set_flag[256] = {0};
    for(i = 0; set[i]; i++)
         set_flag[set[i]] = 1;
    for(i = 0; s[i]; i++)
        if (set_flag[s[i]])
            count++;
    return count;
}

@fasked · 30.11.2011, 16:52

Thinker, думал об этом, но отбросил мысль до вопроса "о сферических символах"

Для остальных типов данных не подойдет.

@Thinker · 30.11.2011, 16:54

Сообщение от fasked

Для остальных типов данных не подойдет.

А нам и не нужны другие типы данных в данной задаче

А метод хорош и очень быстр! Можно сделать с арифметикой указателей, но принцип тот же остается

@alkagolik · 30.11.2011, 17:09

Thinker, и раз уж на то пошло, то массив флагов можно объявить как char set_flag[256]. 4 байта не нужно для хранения одного бита. Минимум что мы можем предоставить это 1 байт. Молодец

@Thinker · 30.11.2011, 17:20

alkagolik, ну int или char это переделать легко, главное скорость удалась

@fasked · 30.11.2011, 17:24

Мне в таком случае больше по душе такая реализация, без сравнений:

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
#include <stdio.h>
 
size_t *make_histo(char *s, size_t *histo)
{   
    while (*s)
        ++histo[*s++];
        
    return histo;
}
 
size_t count(char *set, size_t *histo)
{
   size_t cnt = 0;
   
   while (*set) {
      cnt += histo[*set++];
   }
   
   return cnt;
}
 
int main() {
   size_t histo[256] = { 0 };
   size_t cnt = 0;
   
   cnt = count("da", make_histo("abcdefabcdefabcdef", histo));
   printf("%u ", cnt);
   
   return 0;
}

@Thinker · 30.11.2011, 17:39

fasked, согласен, и в моем алгоритме тоже можно написать count += set_flag[s[i]] и работать адресной с арифметикой, но моя цель была показать направление в сторону быстрого алгоритма. За счет узкого диапазона значений и удалось так сделать

Новые блоги и статьи Все статьи Все блоги /
Гайд, как ворваться в вайб-кодинг в мае 2026 Noname2331 17.05.2026 Простите за получившееся полотно текста, я даже не знаю, как его разбить на главы. Тут, что называется, ни добавить ни убавить, одна сцена одним дублем. На моих глазах недавно случилось чудо. Как. . .	[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .
Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .

@fasked 5045 / 2624 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 5
	30.11.2011, 16:52
	Thinker, думал об этом, но отбросил мысль до вопроса "о сферических символах" Для остальных типов данных не подойдет. 0

@alkagolik 1599 / 622 / 113 Регистрация: 15.07.2011 Сообщений: 3,548
	30.11.2011, 17:09
	Thinker, и раз уж на то пошло, то массив флагов можно объявить как char set_flag[256]. 4 байта не нужно для хранения одного бита. Минимум что мы можем предоставить это 1 байт. Молодец 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	30.11.2011, 17:20
	alkagolik, ну int или char это переделать легко, главное скорость удалась 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	30.11.2011, 17:39
	fasked, согласен, и в моем алгоритме тоже можно написать count += set_flag[s[i]] и работать адресной с арифметикой, но моя цель была показать направление в сторону быстрого алгоритма. За счет узкого диапазона значений и удалось так сделать 0

Опции темы