Задача
n-й член последовательности треугольных чисел задается как tn = ½n(n+1). Таким образом, первые десять треугольных чисел:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Преобразовывая каждую букву в число, соответствующее ее порядковому номеру в алфавите, и складывая эти значения, мы получим числовое значение слова. Для примера, числовое значение слова SKY равно 19 + 11 + 25 = 55 = t10. Если числовое значение слова является треугольным числом, то мы назовем это слово треугольным словом.
Используя words.txt, 16 КБ текстовый файл, содержащий около двух тысяч часто используемых английских слов, определите, сколько в нем треугольных слов.
Решение
Эти "треугольные" суммы – просто суммы последовательностей 1+2+3+4+5...
Которые образуют треугольник при разложении каждого числа в последовательности:
1
1 1
1 1 1
1 1 1 1
...
Формула уже известна: 1/2n(n+1), но я предпочитаю такую (и уже применял в прошлых задачах):
(n * n + n) / 2
Предположим, у слова получилась сумма 55, подставим и посмотрим:
(n * n + n) / 2 = 55
Далее можно упростить:
n * n + n = 110
Далее легко заметить, что мы получили школьное квадратное уравнение типа ax^2 + bx + c = 0:
n * n + n - 110 = 0
Вычислим дискриминант:
D = b^2 - 4ac = 1 - 4 * 1 * (-110) = 441
И первый корень:
x = (-b + sqrt(D)) / 2a = (-1 + sqrt(441)) / 2 = 10
Второй корень не ищем, так как он всё равно будет отрицательным.
Делаем обратную проверку:
(10 * 10 + 10) / 2 = 55
Мы нашли порядковый номер треугольного числа, как и доказательство, что оно треугольное.
Напишем функцию для тестирования сумм:
И собственно лавочку можно закрывать, дальше нужно только прочитать слова из файла, что уже делалось в Задаче 22:
Но здесь я применю более простой парсер и также сниму ограничение на длину файла, помещающегося в памяти. Для чтения будет использоваться буфер фиксированной длины в BUF_SIZE байт, а сам файл может быть хоть бесконечным.
Работает так: буфер читает из файла кусок данных и сохраняет у себя длину этого куска. Каждый раз он пытается прочитать BUF_SIZE байт, но если столько в файле не осталось, то прочитается сколько есть, и fread() вернёт размер прочитанного куска. Так что когда он станет равен 0, значит файл прочитан до конца.
Из буфера можно уже читать по одному символу. Для этого буфер хранит позицию чтения pos внутри себя. Когда позиция доходит до конца буфера, буфер читает следующий кусок из файла.
Парсеру остаётся просто читать по одному символу из буфера. Почему это не делается прямо из файла? Потому что будет медленно.
Парсер имеет два состояния: NONE и WORD. Первоначально он находится в состоянии NONE и ждёт открывающую кавычку. Дождавшись её, переходит в состояние WORD и накапливает сумму, пока не встретит закрывающую кавычку. После чего проверяет накопленную сумму, переходит обратно в NONE и т.д.
Ссылка на онлайн-компилятор языка C с текстом программы
(работать онлайн не будет, так как там нельзя подложить файл)
Подборка всех задач: