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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 446
#1

Сколько палиндромов длиной n можно образовать из 26 букв - C++

11.12.2013, 08:05. Просмотров 1725. Ответов 23
Метки нет (Все метки)

Сколько палиндромов длиной n можно образовать из 26 букв

Подскажите, как можно реализовать? Идей нет...

Может ввести массив из 26 букв. И попробовать найти слова, которые будут полиндромами? Но как программа поймет, что то, что она нашла это слово, а не просто тупой набор букв?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2013, 08:05
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сколько палиндромов длиной n можно образовать из 26 букв (C++):

Сколько цифр можно составить из заданных букв? - C++
Дана последовательность из букв. Найти сколько цифр можно составить из этих букв, вывести их и то, что осталось невостребованным. ...

Определить сколько слов можно составить из букв прочитанного слова - C++
Прошу помощи, задание : Считываю слово с файла, например, abb,нужно посчитать, сколько других слов можно из него составить и вывести. Т.е....

Сколько возможных комбинаций из 4х символов длиной в 5 - C++
Сколько возможных комбинаций из 10и символов в строке длиной в 5 символов, с условием, что одинаковых в строке не больше 3х, а одинаковых...

Перебор всех слов латинского алфавита длиной 1-4 букв - C++
Задали такую программу, а как ее писать - даже не знаю) Конечно представляю, что 1 пункт массив, а вот дальше... "1)Перебор всех...

Удалить из предложения повторяющиеся слова длиной менее трёх букв - C++
Ввести предложение, слова в котором разделены пробелами и запятыми. Распечатать это предложение, удалив из него те слова, которые...

Сколько существует способов составить отрезок длиной 1 метр? - C++
Сколько существует способов составить отрезок длиной 1 метр из отрезков длиной А и В см?

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.12.2013, 00:08  [ТС] #16
никто ничего не ответит... поэтому хоть как-то хочу решить задачу. расскажи, какие у тебя есть идеи?
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.12.2013, 11:20 #17
Цитата Сообщение от Dani Посмотреть сообщение
что-то ты фигню написал. Не все размещения будут палиндромами же.
это вы не поняли идею решения, хотя всё просто.
kpoxaa, у меня такое ощущение, что вы не читали про размещения, раз до сих пор не поняли как решить задачу.
хорошо, если всё так туго, то вот подробнее:
вначале про 26 букв:
я понял, что каждую букву можно использовать в палиндроме ровно 2 раза. почему не меньше? да потому что палиндром состоит из двух одинаковых половин. почему не больше? потому что иначе получатся размещения с повторениями и если
Цитата Сообщение от kpoxaa Посмотреть сообщение
Мне подсказали, что это как-то высчитывается через факториал
, то одними факториалами там не обойдешься, нужно будет отдельно определять для каждого набора букв кол-во повторов каждой буквы, а таких наборов может быть сто тыщ мильонов, короче это сложная задача.
теперь само решение:
Четные палиндромы: палиндром состоит из 2 одинаковых половин. нам достаточно перебрать все различные комбинации для половин палиндромов. а это называется РАЗМЕЩЕНИЯМИ (А) из 26 букв по n/2. кол-во размещений A и будет являться ответом. почему? чтобы получился палиндром, нужно в конец каждой комбинации из n/2 символов добавить ее обращение.
Нечетные палиндромы: решается так же как для четных, но n/2 - это целая часть от частного, а центральным элементом может быть любой из неиспользованных символов для каждой комбинации, т.е. любой из (26 - n/2) штук. в итоге для нечетных n кол-во палиндромов равно A * (26 - n/2).
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.12.2013, 11:34  [ТС] #18
Цитата Сообщение от ya_noob Посмотреть сообщение
что вы не читали про размещения
ну вообще-то я не вникал. ок прочитаю нормально

Добавлено через 1 минуту
ya_noob, спасибо) хоть что-то прояснилось.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
15.12.2013, 11:36 #19
забыл добавить, что все 26 букв должны быть попарно различными, а также n не должно быть больше 52, иначе будут размещения с повторениями (а про них я писал выше).
vndtta
89 / 66 / 13
Регистрация: 17.10.2011
Сообщений: 231
Завершенные тесты: 1
15.12.2013, 12:14 #20
я так понял что решения до сих пор нет

ответ будет 26^[(n+1)/2] ну если n>0
это количество комбинаций первой пловины слова включая среднюю букву, если слово состоит из нечетного количества букв

Добавлено через 7 минут
Цитата Сообщение от ya_noob Посмотреть сообщение
это вы не поняли идею решения, хотя всё просто.
kpoxaa, у меня такое ощущение, что вы не читали про размещения, раз до сих пор не поняли как решить задачу.
хорошо, если всё так туго, то вот подробнее:
вначале про 26 букв:
я понял, что каждую букву можно использовать в палиндроме ровно 2 раза. почему не меньше? да потому что палиндром состоит из двух одинаковых половин. почему не больше? потому что иначе получатся размещения с повторениями и если , то одними факториалами там не обойдешься, нужно будет отдельно определять для каждого набора букв кол-во повторов каждой буквы, а таких наборов может быть сто тыщ мильонов, короче это сложная задача.
теперь само решение:
Четные палиндромы: палиндром состоит из 2 одинаковых половин. нам достаточно перебрать все различные комбинации для половин палиндромов. а это называется РАЗМЕЩЕНИЯМИ (А) из 26 букв по n/2. кол-во размещений A и будет являться ответом. почему? чтобы получился палиндром, нужно в конец каждой комбинации из n/2 символов добавить ее обращение.
Нечетные палиндромы: решается так же как для четных, но n/2 - это целая часть от частного, а центральным элементом может быть любой из неиспользованных символов для каждой комбинации, т.е. любой из (26 - n/2) штук. в итоге для нечетных n кол-во палиндромов равно A * (26 - n/2).
где это написано что только 2 раза можно использовать, слово ZZZZZZ -палиндром длиной 6 - условию задачи удовлетворяет если Z входит в алфавит и n=6

вообще задача проста до нельзя - а вы тут какие-то дополнительные условия выдумавыете
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 446
15.12.2013, 12:51  [ТС] #21
Цитата Сообщение от vndtta Посмотреть сообщение
ответ будет 26^[(n+1)/2] ну если n>0
осталось это как-то на си++ написать
vndtta
89 / 66 / 13
Регистрация: 17.10.2011
Сообщений: 231
Завершенные тесты: 1
15.12.2013, 13:03 #22
Цитата Сообщение от kpoxaa Посмотреть сообщение
осталось это как-то на си++ написать

C++
1
2
3
4
5
#include <math.h>
int solve(int n, int letters)
{
    return pow( letters, (int)((n+1)/2) );
}
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
15.12.2013, 13:48 #23
ya_noob, аа, т.е. еще буквы несколько раз использовать. Ну если два раза, тогда однозначно размещениями (если использовать все буквы).
kpoxaa
72 / 33 / 1
Регистрация: 03.08.2012
Сообщений: 446
16.12.2013, 23:19  [ТС] #24
А если другой вариант:

k!/(k-m)!
C++
1
2
3
4
5
6
int m = n/2; // длинна полиндрома деленная на 2
int k = 26; 
unsigned long int res = 1; 
 
for(int i = k-m; i<k+1; i++) 
    res = res * i;
Миниатюры
Сколько палиндромов длиной n можно образовать из 26 букв  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2013, 23:19
Привет! Вот еще темы с ответами:

Найти сколько раз символ & в строку символов длиной 70 - C++
Найти сколько раз символ &amp; в строку символов длиной 70...

[C++] Установить можно ли, разбив строку на подстроки длиной N... - C++
Заданная строка с N2 цифр. Установить можно ли, разбив строку на подстроки длиной N, записать их в строки двумерного массива N x N по одной...

Сколько различных строк можно образовать из букв слова? - Комбинаторика
Пусть задано слово ТРОТУАР. Вычислить: a. Сколько различных строк можно образовать из букв слова, используя все буквы? б. Сколько...

Сколько различных букв азбуки Морзе можно образовать - Комбинаторика
4) Буквы Азбуки Морзе образуются как последовательность и … сколько различных букв можно образовать используя: А) 5 символов; Б) не...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.12.2013, 23:19
Ответ Создать тему
Опции темы

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