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

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

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

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

C++

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 минут
помогите пожалуйста...

@Thinker · 29.11.2011, 21:23

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

Так мы же про strchr говорим, а она принимает символ для поиска, а не строку символов.

fasked, хорошо, по-другому, в посте 39 приведен пример использования strchr, но пример как не эффективно использовать эту функцию. Вы же не привели свой алгоритм решения задачи с set и s

@~~alkagolik~~ · 29.11.2011, 21:34

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

Зачем так? Если символ s[i] совпал с одним из символов строки set, то дальше зачем поиски?

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

Представьте ситуацию, есть строка set и строка s (тысячи, миллионы символов). Ваша цель - подсчитать количество символов строки s, входящих в строку set. Ваш алгоритм? Например, set = "abc", s="abcxyzabcxyzabc". Ответ 9.

решение

C

for (int i = count = 0; i < strlen(set); ++i)
{
    count += f(s, set[i]);
}

@fasked · 29.11.2011, 21:35

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

хорошо, по-другому, в посте 39 приведен пример использования strchr, но пример как не эффективно использовать эту функцию.

Ну по-началу пошел бы по пути наименьшего сопротивления:

C

for (p = set; *p; ++p) {
   for (q = s; *q; ++q) {
      if (*q == *p) ++count;
   }
}

@Thinker · 29.11.2011, 21:38

alkagolik, моя вина, что не сказал, что set - множество символов, то есть там нет одинаковых символов.

Добавлено через 1 минуту
fasked, сложность вашего алгоритма O(mn), где m = strlen(set), n = strlen(s)

@~~alkagolik~~ · 29.11.2011, 21:38

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

alkagolik, моя вина, что не сказал, что set - множество символов, то есть там нет одинаковых символов.

так это же ничего не меняет. вы наверное запутались.

@fasked · 29.11.2011, 21:39

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

моя вина, что не сказал, что set - множество символов, то есть там нет одинаковых символов.

Давайте-ка точнее

set - без повторовю А найти надо что? Общее количество совпадений? Или просто определить встречается ли каждый из символов в строке хотя бы один раз?

@Thinker · 29.11.2011, 21:40

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

так это же ничего не меняет. вы наверное запутались.

Если символ c входит в строку set, то другого такого же символа c в set уже нет, я об этом

@~~alkagolik~~ · 29.11.2011, 21:41

ну видимо я запутался

@Thinker · 29.11.2011, 21:42

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

Давайте-ка точнее

set - без повторовю А найти надо что? Общее количество совпадений? Или просто определить встречается ли каждый из символов в строке хотя бы один раз?

set это строка без повторяющихся символов, s - произвольная строка. Требуется подсчитать количество символов из строки s, содержащихся в set. Например, set = "123". s = "321abc11". Ответ 5

@~~alkagolik~~ · 29.11.2011, 21:45

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

Ваша цель - подсчитать количество символов строки s, входящих в строку set.

или все таки вы?

Добавлено через 2 минуты
Thinker, решение ссылка + ссылка = решение

@Thinker · 29.11.2011, 21:47

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

или все таки вы?

Нет, я же придумал задачу

У нас вопрос не сколько различных символов из s принадлежит set (это другая задача, тоже интересная), а сколько в строке s символов, которые принадлежат set, например, усли set="01...9", то мы считаем количество цифр в строке и т.д.

@~~alkagolik~~ · 29.11.2011, 21:48

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

а сколько в строке s символов, которые принадлежат set, например, усли set="01...9", то мы считаем количество цифр в строке и т.д.

так я вам уже несколько раз показал решение и конечно strchr тут неуместно.

@Thinker · 29.11.2011, 21:52

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

так я вам уже несколько раз показал решение и конечно strchr тут неуместно.

Хорошо, ваш алгоритм к строкам set = "123", s = "321abc1122" какой ответ дает?

@~~alkagolik~~ · 29.11.2011, 21:57

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

Хорошо, ваш алгоритм к строкам set = "123", s = "321abc1122" какой ответ дает?

Код

deadman@gnomik:~$ cat file.c 
#include <stdio.h>

int f(char *s, char x)
{
    int a = 0;
    while (*s)
    {
        if ( *s == x)
            ++a;
        ++s;
    }
    return a;
}

int main(void)
{
    char *s = "321abc1122"; // 9
    char *set = "123";
    int count = 0;

    while(*set)
    {
        count += f(s, *set);
        ++set;
    }
    printf("%i\n", count);

    return 0;
}deadman@gnomik:~$ gcc file.c 
deadman@gnomik:~$ ./a.out 
7
deadman@gnomik:~$

@fasked · 29.11.2011, 21:57

Thinker, мы говорим о символах в сферическом вакууме или символах char? Если про char, то можно предложить отсортировать строку set, и уже далее использовать бинарный поиск. Получится O(lg(n) * m).

C

for (p = s; *p; ++p) {
   if (bsearch(set, *p)) // найти символ 'p' в строке 'q'
      ++count;
}

А под конкретные данные (множества set) можно много чего придумать.

@Thinker · 29.11.2011, 22:00

alkagolik, хорошо, спасибо, только сложность алгоритма O(mn).
fasked, о типе char. с бинарным поиском сложность алгоритма будет $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n\cdot \log_2 m)$ , уже лучше

@~~alkagolik~~ · 29.11.2011, 23:33

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

@fasked · 29.11.2011, 23:45

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

уже лучше

Как вариант упаковывать все по 4 или 8 байт, что уменьшит сложность в 8 или 4 раза, но это опять же константа и брать ее во внимание неразумно.

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

При расчете сложности не учитана сложность сортировки.

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

@~~alkagolik~~ · 30.11.2011, 00:13

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

Как вариант упаковывать все по 4 или 8 байт

кодировать? можно немного подробней?

@fasked · 30.11.2011, 00:55

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

можно немного подробней?

В общем-то формировать из 4 символов один int. Потом как-нибудь хитро это "заксорить" с искомым символом и проверить на наличие нулей. Я думаю, что в strchr именно так и сделано, но разбираться, если честно, лень

Это прибавит скорости машинной, но не алгоритмической. Поэтому неинтересно.

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 21:38	44
	alkagolik, моя вина, что не сказал, что set - множество символов, то есть там нет одинаковых символов. Добавлено через 1 минуту fasked, сложность вашего алгоритма O(mn), где m = strlen(set), n = strlen(s) 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	29.11.2011, 21:39	46
	Сообщение от Thinker моя вина, что не сказал, что set - множество символов, то есть там нет одинаковых символов. Давайте-ка точнее set - без повторовю А найти надо что? Общее количество совпадений? Или просто определить встречается ли каждый из символов в строке хотя бы один раз? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 21:42	49
	Сообщение от fasked Давайте-ка точнее set - без повторовю А найти надо что? Общее количество совпадений? Или просто определить встречается ли каждый из символов в строке хотя бы один раз? set это строка без повторяющихся символов, s - произвольная строка. Требуется подсчитать количество символов из строки s, содержащихся в set. Например, set = "123". s = "321abc11". Ответ 5 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 21:47	51
	Сообщение от alkagolik или все таки вы? Нет, я же придумал задачу У нас вопрос не сколько различных символов из s принадлежит set (это другая задача, тоже интересная), а сколько в строке s символов, которые принадлежат set, например, усли set="01...9", то мы считаем количество цифр в строке и т.д. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 21:52	53
	Сообщение от alkagolik так я вам уже несколько раз показал решение и конечно strchr тут неуместно. Хорошо, ваш алгоритм к строкам set = "123", s = "321abc1122" какой ответ дает? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 21:23	41
	Сообщение от fasked Так мы же про strchr говорим, а она принимает символ для поиска, а не строку символов. fasked, хорошо, по-другому, в посте 39 приведен пример использования strchr, но пример как не эффективно использовать эту функцию. Вы же не привели свой алгоритм решения задачи с set и s 0

@~~alkagolik~~ Заблокирован
	29.11.2011, 21:38	45
	Сообщение от Thinker alkagolik, моя вина, что не сказал, что set - множество символов, то есть там нет одинаковых символов. так это же ничего не меняет. вы наверное запутались. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 21:40	47
	Сообщение от alkagolik так это же ничего не меняет. вы наверное запутались. Если символ c входит в строку set, то другого такого же символа c в set уже нет, я об этом 0

@~~alkagolik~~ Заблокирован
	29.11.2011, 21:41	48
	ну видимо я запутался 0

@~~alkagolik~~ Заблокирован
	29.11.2011, 21:45	50
	Сообщение от Thinker Ваша цель - подсчитать количество символов строки s, входящих в строку set. или все таки вы? Добавлено через 2 минуты Thinker, решение ссылка + ссылка = решение 0

@~~alkagolik~~ Заблокирован
	29.11.2011, 21:48	52
	Сообщение от Thinker а сколько в строке s символов, которые принадлежат set, например, усли set="01...9", то мы считаем количество цифр в строке и т.д. так я вам уже несколько раз показал решение и конечно strchr тут неуместно. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	29.11.2011, 22:00	56
	alkagolik, хорошо, спасибо, только сложность алгоритма O(mn). fasked, о типе char. с бинарным поиском сложность алгоритма будет $https://www.cyberforum.ru/cgi-bin/latex.cgi?O(n\cdot \log_2 m)$ , уже лучше 0

@~~alkagolik~~ Заблокирован
	29.11.2011, 23:33	57
	самообман. При расчете сложности не учитана сложность сортировки. Реально задача реализуется сравнением каждого байта массива s. Можно конечно (и нужно) оптимизировать под наиболее вероятные случаи, но сути это не меняет. 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	29.11.2011, 23:45	58
	Сообщение от Thinker уже лучше Как вариант упаковывать все по 4 или 8 байт, что уменьшит сложность в 8 или 4 раза, но это опять же константа и брать ее во внимание неразумно. Сообщение от alkagolik При расчете сложности не учитана сложность сортировки. Строка set очень коротка, поэтому сортировка пройдет почти незаметно. Впрочем, бинарный поиск по ней тоже не сильно будет отличаться от линейного. 0

@~~alkagolik~~ Заблокирован
	30.11.2011, 00:13	59
	Сообщение от fasked Как вариант упаковывать все по 4 или 8 байт кодировать? можно немного подробней? 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	30.11.2011, 00:55	60
	Сообщение от alkagolik можно немного подробней? В общем-то формировать из 4 символов один int. Потом как-нибудь хитро это "заксорить" с искомым символом и проверить на наличие нулей. Я думаю, что в strchr именно так и сделано, но разбираться, если честно, лень Это прибавит скорости машинной, но не алгоритмической. Поэтому неинтересно. 0