Подсчет кол-ва слов, начинающихся и заканчивающихся на одну и туже букву без использования готовых строковые функции

@IT_shnik · Регистрация: 21.10.2017

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

Написать функцию, входным параметром которой является строка. Функция должна вернуть количество слов в строке, у которых первый и последний символ совпадают (слова – группы символов, разделенные пробелами, или пробелом и началом (концом) строки).

Подскажите пожалуйста, как решить данную задачу не используя готовые строковые функции, буду очень благодарен!

@mrtoxas · 20.12.2017, 16:18

JavaScript
1
2
3
4
5
6
7
8
var str = 'Lorem ipsum dolor sit amet, consectetur adipisicing elit. NequN, dolored! Dolorem error tempore aperiam ipsa, ad modi dignissimos odit hic necessitatibus sint repellar deserunt ullam nulla amet omnis delectus obcaecati.';
var res = [];
[].forEach.call(str.toLowerCase().split(/[\s,.!?;:]+/),function(elem){
 if (elem[0] === elem[elem.length-1]){
   res.push(elem);
 } 
})
console.log(res.length)

Хотя, наверное, не совсем попадает под "не используя готовые строковые функции".

@kalabuni · 21.12.2017, 00:17

IT_shnik, имхо, вы явно недоозвучили условие задачи -- либо в строке гарантированно нет однобуквенных слов, либо искать надо только слова, состоящие минимум из двух символов
к примеру, предлог "у" начинается с буквы "у", и ею же заканчивается, а, значит, подпадает под параметры искомых слов, что как бы не очень здорово

JavaScript
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
var source =  'у попа была собака он ее любил она съела кусок мяса он ее убил';
// функция должна найти слова:
// 1. у
// 2. ее
// 3. любил
// 4. кусок
// 5. ее
// и вернуть результатом число 5
 
function myfind (s)
{
// вводим переменные:
var res = 0; //  начальное значение количества искомых слов
var first = s [0]; // первый символ текущего слова
 
for ( var j = 1, J = s.length - 1; j < J; j++)
if (s [j] == ' ')
   {
   if (first == s [j - 1]) res++;
   first = s [j + 1];
   }
return res
}
 
document.write ('найдено ' + myfind (source) + ' слов');

понятное дело, что всякий символ s [j] надо было перевести в какой-то один регистр, например, в нижний toLowerCase(), но это сделаете сами, я не стал загромождать код, чтобы вы смогли без помех уловить суть этого простейшего алгоритма

@Balanaar · 21.12.2017, 09:13

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

что как бы не очень здорово

Ну почему же?

В предлоге "у" первый и последний символ совпадают, что удовлетворяет условиям задачи.

@kalabuni · 21.12.2017, 13:35

Balanaar, объясняю: моя оценка "не здорово" дана озвученной формулировке задачи.
Годность/ негодность формулировки любой задачи проверяется очень легко - если существует частный случай, при котором задача превращается либо в абсурд, либо в нерешаемую, то, значит, формулировка задачи негодная, не покрывает все возможные случаи
Для данной задачи такой абсурдный частный случай - исходная строка состоит из всех 33-рёх букв русского алфавита, разделённых пробелами". Решением для этого частного случая будет число 33, что превращает задачу в абсурд
Согласны?

Если не согласны, то поясню реальным примером из моей рабочей практики:

Не по теме:

Не так давно поставили передо мной задачу:
Исходная строка очень большой (но конечной) длины состоит из любых цифровых символов в произвольном порядке. Необходимо разработать эффективный (быстрый и не требующий много памяти) алгоритм и написать программу (не на js, конечно, и делать это буду уже не я), которая найдёт в исходной строке повторяющиеся подстроки, представляющие из себя натуральные числа (при этом такая повторяющаяся подстрока может включать в себя другие подстроки или части их, и даже содержать часть повторасамой себя).
Программа должна вывести Топ-50 по частоте вхождения:
- для двузначных натуральных чисел,
- для трехзначных натуральных чисел,
для четырехзначных натуральных чисел
- и т. д., вплоть до максимальной имеющейся повторяющейся подстроки.

быстренько прикинул очевидное: для общего случая исходной строки из N символов максимальная длина возможной повторяющейся подстроки равна [N /2] -- минимальному целому от половины длины исходной строки
Но имеется частный случай, если строка состоит из N одинаковых символов, например, такая '1111111111' (много-много единиц), и тогда максимальная длина повторяющейся подстроки будет равна (N-1). Подстрока из (N-1) подряд идущих единиц будет повторяться уже начиная с индекса [1].
В итоге при больших N задача превращается в трансвычислительную, потому что суммарное количество повторов, кои программе придётся искать и потом сортировать по убыванию, приблизительно можно оценить формулой
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k = 2}^{k = N - 1} {10}^{k}$
Начальство моё долго, где-то с неделю, въезжало в эту мою мысль... но в итоге согласилось и последний пункт текста формулировки уточнило (согласовав с заказчиком), ограничив количество знаков в искомых повторах именно половиной длины строки.

@Balanaar · 21.12.2017, 13:38

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

Решением для этого частного случая будет число 33, что превращает задачу в абсурд
Согласны?

Не вижу ничего абсурдного. Также не увидел связи истории ниже с вашим примером.

@kalabuni · 21.12.2017, 13:45

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

Не вижу ничего абсурдного Также не увидел связи истории ниже с вашим примером.

и такое бывает

Начальство моё, как я упоминал, тоже целую неделю соображало

@Balanaar · 21.12.2017, 13:56

В вашей истории речь шла о трансвычислительности задачи. Что не так с 33мя буквами в строке - наверно только вам известно.

Добавлено через 6 минут
Кстати

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

быстренько прикинул очевидное: для общего случая исходной строки из N символов максимальная длина возможной повторяющейся подстроки равна [N /2] -- минимальному целому от половины длины исходной строки

Неверно, поскольку по условию

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

подстрока может ... даже содержать часть повторасамой себя

Соответственно максимальная длина возможной повторяющейся подстроки равна [N - 1]. Дальше вникать не стал.

@kalabuni · 21.12.2017, 15:32

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

Неверно

полагаете, что сможете придумать строку, содержащую повторяющуюся минимум один раз подстроку, имеющую длину более половины исходной строки?
я готов подождать... и даже целую неделю

только строки из одних единиц или из одних двоек/девяток не присылайте, ладно?
а то с вас станется, вы же у нас "Дальше вникать не стал."

@Balanaar · 21.12.2017, 15:35

123123123
123123123
Неделю ждать не обязательно

@kalabuni · 21.12.2017, 15:39

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

Что не так с 33мя буквами в строке - наверно только вам известно.

объясняю: поставят вам задачу взять текст "войны и мира", весь его отсканировать, распознать, написать программу, которая определит количество различных русских букв, использованных Львом Толстым при написании этого романа.
Возьмётесь?
Будете сканировать, распознавать, писать программу? или просто в википедии узнаете количество букв в старом алфавите с "ятями"?

@Balanaar · 21.12.2017, 15:46

Вообще не улавливаю логики в вашем сравнении.
У ТСа есть конкретная задача. Условия длины слова в задаче не было. Значит следует учитывать и тот факт, что слово может состоять из одного символа. Какие тут могут быть вопросы?

@kalabuni · 21.12.2017, 16:08

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

123123123
123123123
Неделю ждать не обязательно

отлично, значит, таки "вникать" и "голову включать" умеете

Рад за вас
а теперь зависимость для этой самой максимальной длины подстроки len_max от N в виде формулы прописать сможете?
чтобы она была точно больше, чем [N/2], но меньше, чем (N - 1)?

Добавлено через 3 минуты

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

Вообще не улавливаю логики в вашем сравнении.
У ТСа есть конкретная задача. Условия длины слова в задаче не было. Значит следует учитывать и тот факт, что слово может состоять из одного символа. Какие тут могут быть вопросы?

задачу тс'а как раз в её исходной формулировке я решил, решение выложил
но всякая задача, имхо, должна иметь практический смысл
если в результате имеющейся формулировки мы имеем результатом задачи то, что можно сделать/узнать много более простым способом, то формулировка негодна, ее надо менять... об том и спич

@Balanaar · 21.12.2017, 16:18

Да, задача должна иметь практический смысл, если решение этой задачи используется в каком-либо проекте. В данном случае ТС решает задачу с целью обучения языку, приобретения базовых навыков работы со строками и проч., о чём свидетельствует эта пресловутая фраза "без использования готовых строковых функций". Понятное дело, что на практике всегда используются эти самые строковые функции, но знать базу тоже нужно обязательно. Поэтому искать практический смысл в таких задачах и философствовать на эту тему не считаю необходимым.

Добавлено через 1 минуту
Правда с фразой "ТС решает задачу" я конечно погорячился...

@kalabuni · 21.12.2017, 16:40

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

Правда с фразой "ТС решает задачу" я конечно погорячился...

не только с ней
с фразой

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

Понятное дело, что на практике всегда используются эти самые строковые функции

вы тоже поспешили
любые эффективные (быстрые и не требующие излишней оперативной памяти) алгоритмы практических задач поиска чего-либо в строках предусматривают именно последовательный доступ к символам строки, без использования каких-либо substring'-ов и прочих indexOf'-ов

@Balanaar · 21.12.2017, 16:53

Недавно где-то в соседних темах кто-то приводил сравнение производительности методов перебора массивов. Так вот на удивление метод forEach() оказался самым быстрым. Даже быстрее обыкновенного цикла for (var i = 0; i < arr.length; i++). Возможно со строками ситуация несколько иная.

@kalabuni · 21.12.2017, 17:10

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

Недавно где-то в соседних темах кто-то приводил сравнение производительности методов перебора массивов. Так вот на удивление метод forEach() оказался самым быстрым. Даже быстрее обыкновенного цикла for (var i = 0; i < arr.length; i++). Возможно со строками ситуация несколько иная.

Знаю, эту тему как раз я начинал -- Как присвоить одинаковое значение всем элементам индексного массива длины N?
Дело в том, что на работе я занимаюсь именно алгоритмами, т.е. изыскиваю рецепт решения задачи, который потом реализуют программисты на серьёзных языках - на Jave, на Си
javascript я освоил самостоятельно, чтобы проверять на нём работоспособность алгоритмов и делать на нём анимированные презентации работы алгоритмов для наших программистов, только текстового описания часто бывает недостаточно (или им просто лень вникать иногда в очень объёмный мой текст)

Ну так как с формулой зависимости len_max подстроки от N?
слабо?

@Balanaar · 21.12.2017, 17:16

Формула зависимости максимально возможной длины повторяющейся подстроки от длины произвольной строки? Как мы уже выяснили, len_max(N) = N - 1. Возможно вы имели в виду другую зависимость. Сформулируйте корректнее.

@kalabuni · 21.12.2017, 17:24

формулирую: найти надо максимальную длину повторяющейся хотя бы один раз подстроки, имеющейся в исходной строке длиной N при условии, что количество символов алфавита исходной строки > 1
алфавитом в алгоритмах поиска в строках называются символы, из которых составлены исходная строка и кейворды (если таковые в задаче имеются -- в нашем случае запросов нет, в исходной строке могут быть 10-ть разных арабских цифр 0...9)

@Balanaar · 21.12.2017, 17:39

len_max(N, a) = N - a, где
N - длина исходной строки;
a - количество различных символов в исходной строке;
len_max - максимальная длина повторяющейся хотя бы один раз подстроки, имеющейся в исходной строке.

В частности, если условие гласит, что a > 1, то очевидно из формулы, что len_max будет максимально при a = 2. Соответственно len_max(N) = N - 2 при условии, что количество символов алфавита исходной строки > 1.

Пример:
12121212121212
12121212121212
N = 14, len_max = 12

Новые блоги и статьи Все статьи Все блоги /
Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .	PowerShell Snippets iNNOKENTIY21 11.11.2025 Модуль PowerShell 5. 1+ : Snippets. psm1 У меня модуль расположен в пользовательской папке модулей, по умолчанию: \Documents\WindowsPowerShell\Modules\Snippets\ А в самом низу файла-профиля. . .	PowerShell и онлайн сервисы. Валюта (floatrates.com руб.) iNNOKENTIY21 11.11.2025 PowerShell функция floatrates-rub Примеры вызова: # Указанная валюта 'EUR' floatrates-rub -Code 'EUR' # Список имеющихся кодов валют floatrates-rub -Available function floatrates-rub {	PowerShell и онлайн сервисы. Погода (RP5.ru) iNNOKENTIY21 11.11.2025 PowerShell функция Get-WeatherRP5rss для получения погоды с сервиса RP5 Примеры вызова Get-WeatherRP5rss с указанием id 5484 — Москва (восток, Измайлово) и переносом строки:. . .	PowerShell и онлайн сервисы. Погода (wttr) iNNOKENTIY21 11.11.2025 PowerShell Функция для получения погоды с сервиса wttr Примеры вызова: Погода в городе Омск с прогнозом на день, можно изменить прогноз на более дней, для этого надо поменять запрос:. . .
PowerShell и онлайн сервисы. Валюта (ЦБР) iNNOKENTIY21 11.11.2025 # Получение курса валют function cbr (] $Valutes = @('USD', 'EUR', 'CNY')) { $url = 'https:/ / www. cbr-xml-daily. ru/ daily_json. js' $data = Invoke-RestMethod -Uri $url $esc = 27 . . .	И решил я переделать этот ноут в машину для распределенных вычислений Programma_Boinc 09.11.2025 И решил я переделать этот ноут в машину для распределенных вычислений Всем привет. А вот мой компьютер, переделанный из ноутбука. Был у меня ноут асус 2011 года. Со временем корпус превратился. . .	Мысли в слух kumehtar 07.11.2025 Заметил среди людей, что по-настоящему верная дружба бывает между теми, с кем нечего делить.	Новая зверюга volvo 07.11.2025 Подарок на Хеллоуин, и теперь у нас кроме Tuxedo Cat есть еще и щенок далматинца: Хочу еще Симбу взять, очень нравится. . .	Инференс ML моделей в Java: TensorFlow, DL4J и DJL Javaican 05.11.2025 Python захватил мир машинного обучения - это факт. Но когда дело доходит до продакшена, ситуация не так однозначна. Помню проект в крупном банке три года назад: команда data science натренировала. . .

@IT_shnik 0 / 0 / 0 Регистрация: 21.10.2017 Сообщений: 40

	Подсчет кол-ва слов, начинающихся и заканчивающихся на одну и туже букву без использования готовых строковые функции 20.12.2017, 13:02. Показов 2411. Ответов 26 Метки нет (Все метки) Написать функцию, входным параметром которой является строка. Функция должна вернуть количество слов в строке, у которых первый и последний символ совпадают (слова – группы символов, разделенные пробелами, или пробелом и началом (концом) строки). Подскажите пожалуйста, как решить данную задачу не используя готовые строковые функции, буду очень благодарен! 0

@kalabuni супермизантроп 3941 / 2979 / 692 Регистрация: 18.04.2012 Сообщений: 8,629
	21.12.2017, 13:35
	Balanaar, объясняю: моя оценка "не здорово" дана озвученной формулировке задачи. Годность/ негодность формулировки любой задачи проверяется очень легко - если существует частный случай, при котором задача превращается либо в абсурд, либо в нерешаемую, то, значит, формулировка задачи негодная, не покрывает все возможные случаи Для данной задачи такой абсурдный частный случай - исходная строка состоит из всех 33-рёх букв русского алфавита, разделённых пробелами". Решением для этого частного случая будет число 33, что превращает задачу в абсурд Согласны? Если не согласны, то поясню реальным примером из моей рабочей практики: Не по теме: Не так давно поставили передо мной задачу: Исходная строка очень большой (но конечной) длины состоит из любых цифровых символов в произвольном порядке. Необходимо разработать эффективный (быстрый и не требующий много памяти) алгоритм и написать программу (не на js, конечно, и делать это буду уже не я), которая найдёт в исходной строке повторяющиеся подстроки, представляющие из себя натуральные числа (при этом такая повторяющаяся подстрока может включать в себя другие подстроки или части их, и даже содержать часть повторасамой себя). Программа должна вывести Топ-50 по частоте вхождения: - для двузначных натуральных чисел, - для трехзначных натуральных чисел, для четырехзначных натуральных чисел - и т. д., вплоть до максимальной имеющейся повторяющейся подстроки. быстренько прикинул очевидное: для общего случая исходной строки из N символов максимальная длина возможной повторяющейся подстроки равна [N /2] -- минимальному целому от половины длины исходной строки Но имеется частный случай, если строка состоит из N одинаковых символов, например, такая '1111111111' (много-много единиц), и тогда максимальная длина повторяющейся подстроки будет равна (N-1). Подстрока из (N-1) подряд идущих единиц будет повторяться уже начиная с индекса [1]. В итоге при больших N задача превращается в трансвычислительную, потому что суммарное количество повторов, кои программе придётся искать и потом сортировать по убыванию, приблизительно можно оценить формулой $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{k = 2}^{k = N - 1} {10}^{k}$ Начальство моё долго, где-то с неделю, въезжало в эту мою мысль... но в итоге согласилось и последний пункт текста формулировки уточнило (согласовав с заказчиком), ограничив количество знаков в искомых повторах именно половиной длины строки. 0

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	21.12.2017, 15:35
	123123123 123123123 Неделю ждать не обязательно 0

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	21.12.2017, 15:46
	Вообще не улавливаю логики в вашем сравнении. У ТСа есть конкретная задача. Условия длины слова в задаче не было. Значит следует учитывать и тот факт, что слово может состоять из одного символа. Какие тут могут быть вопросы? 0

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	21.12.2017, 16:18
	Да, задача должна иметь практический смысл, если решение этой задачи используется в каком-либо проекте. В данном случае ТС решает задачу с целью обучения языку, приобретения базовых навыков работы со строками и проч., о чём свидетельствует эта пресловутая фраза "без использования готовых строковых функций". Понятное дело, что на практике всегда используются эти самые строковые функции, но знать базу тоже нужно обязательно. Поэтому искать практический смысл в таких задачах и философствовать на эту тему не считаю необходимым. Добавлено через 1 минуту Правда с фразой "ТС решает задачу" я конечно погорячился... 0

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	21.12.2017, 16:53
	Недавно где-то в соседних темах кто-то приводил сравнение производительности методов перебора массивов. Так вот на удивление метод forEach() оказался самым быстрым. Даже быстрее обыкновенного цикла for (var i = 0; i < arr.length; i++). Возможно со строками ситуация несколько иная. 0

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	21.12.2017, 17:16
	Формула зависимости максимально возможной длины повторяющейся подстроки от длины произвольной строки? Как мы уже выяснили, len_max(N) = N - 1. Возможно вы имели в виду другую зависимость. Сформулируйте корректнее. 0

@kalabuni супермизантроп 3941 / 2979 / 692 Регистрация: 18.04.2012 Сообщений: 8,629
	21.12.2017, 17:24
	формулирую: найти надо максимальную длину повторяющейся хотя бы один раз подстроки, имеющейся в исходной строке длиной N при условии, что количество символов алфавита исходной строки > 1 алфавитом в алгоритмах поиска в строках называются символы, из которых составлены исходная строка и кейворды (если таковые в задаче имеются -- в нашем случае запросов нет, в исходной строке могут быть 10-ть разных арабских цифр 0...9) 0

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	21.12.2017, 17:39
	len_max(N, a) = N - a, где N - длина исходной строки; a - количество различных символов в исходной строке; len_max - максимальная длина повторяющейся хотя бы один раз подстроки, имеющейся в исходной строке. В частности, если условие гласит, что a > 1, то очевидно из формулы, что len_max будет максимально при a = 2. Соответственно len_max(N) = N - 2 при условии, что количество символов алфавита исходной строки > 1. Пример: 12121212121212 12121212121212 N = 14, len_max = 12 0