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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
SpblrT
1 / 1 / 0
Регистрация: 24.11.2011
Сообщений: 40
#1

Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы - C++

20.12.2011, 20:06. Просмотров 1648. Ответов 15
Метки нет (Все метки)

)заданы 2 символьные строки А и Б . Требуется вычислить сколькими способами можно получить строку В из строки А, вычеркивая некоторые символы, например для строк aaabbbccc и abc это число равно 36

хотябы 1 стособ

 Комментарий модератора 
Создавайте темы с осмысленными и понятными названиями - это серьезно повышает шансы, что на ваш вопрос ответят.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2011, 20:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сколькими способами можно получить строку "В" из строки "А", вычеркивая некоторые символы (C++):

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

После каждого знака препинания (".", ",", ";") вставить в строку пробел, если там его нет - C++
Выполните задания с использованием библиотечного класса string. Даны строка S. Необходимо после каждого знака препинания (".", ",",...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Вывести текст файла, заменив цифры от 0 до 9 на слова "ноль", "один"."девять", начиная каждое предложение с новой строки - C++
Написать программу, которая считывает текст из файла и выводит его на экран, заменив цифры от 0 до 9 на слова "ноль", "один"..."девять",...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс "вентилятор" содержащий в себе классы:...

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 05:33 #2
Какие ограничения на длины строк и на время выполнения программы?
0
challengerr
43 / 36 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:03 #3
например для строк aaabbbccc и abc это число равно 36
Не может ли кто-нибудь объяснить, почему количество способов 36? (если оно действительно 36)
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:09 #4
Цитата Сообщение от challengerr Посмотреть сообщение
Не может ли кто-нибудь объяснить, почему количество способов 36? (если оно действительно 36)
для данного случая кол-во способов: 3^3=36
0
challengerr
43 / 36 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:16 #5
для данного случая кол-во способов: 3^3=36
3^3 = 27 (3*3*3 = 27)
У меня получается 90 способов при ручном построении дерева
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:28 #6
Цитата Сообщение от challengerr Посмотреть сообщение
3^3 = 27 (3*3*3 = 27)
насчет 3^3=36 я погорячился, правильный ответ будет 27:
aaa - можно выбрать a тремя вариантами.
aaabbb - можно выбрать ab - 3*3 вариантами
aaabbbccc - можно выбрать abc - 3*3*3 вариантами
а Вы покажите свой способ на 90 вариантов
0
challengerr
43 / 36 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:32 #7
Где я ошибся в логике?
Начальная строка (aaabbbccc)
Три варианта вычеркивания с получением следующих строк:
(aabbbccc)=k1 и (aaabbccc)=k2 и (aaabbbcc)=k3
Из строки (aabbbccc)=k1 вычеркиванием можно получить:
(abbbccc)=k11 и (aabbccc)=k12 и (aabbbcc)=k13
Из строк k2, k3 эквивалентно k1
Из строки (abbbccc)=k11 вычеркиванием получают:
(abbccc)=k111 и (abbbcc)=k112
Из строки (abbccc)=k111 вычеркиванием получают:
(abccc) и (abbcc)
(abccc) - 1 способ получить (abc)
(abbcc) - 2 способа получить (abc)
Из строки (abbbcc)=k112 вычеркиванием получают:
(abbcc) и (abbbc)
(abbcc) - 2 способа получить (abc)
(abbbc) - 1 способ получить (abc)
Итого: 6 способов для k11

Из строки (aabbccc)=k12 вычеркиванием получают:
(abbccc)=k121 и (aabccc)=k122 и (aabbcc)=k123
Из строки (abbccc)=k121 вычеркиванием получают:
(abccc)=k1211 и (abbcc)=k1212
(abccc) - 1 способ получить (abc)
(abbcc) - 2 способа получить (abc)
Из строки (aabccc)=k122 вычеркиванием получают:
(abccc)=k1221 и (aabcc)=k1222
(abccc) - 1 способ получить (abc)
(aabcc) - 2 способа получить (abc)
Из строки (aabbcc)=k123 вычеркиванием получают:
(abbcc)=k1231 и (aabcc)=k1232 и (aabbc)=k1233
(abbcc) - 2 способа получить (abc)
(aabcc) - 2 способа получить (abc)
(aabbc) - 2 способа получить (abc)
Итого: 12 способов для k12
Итого: 12 способов для k13
Итого для k11 и для k12 и для k13 12+12+6 = 30 способов для k1
Аналогично 30 способов для k2
Аналогично 30 способов для k3
де ошибся в рассуждениях, если 36?
1
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:41 #8
Цитата Сообщение от challengerr Посмотреть сообщение
Начальная строка (aaabbbccc)
Три варианта вычеркивания с получением следующих строк:
(aabbbccc)=k1 и (aaabbccc)=k2 и (aaabbbcc)=k3
Не три варианта. Например вариант (aabbbccc)=k1 можно получить не одним способом а тремя:
- первый вариант - вычеркнуть первую букву a
- второй вариант - вычеркнуть вторую букву a
- третий вариант - вычеркнуть третью букву a
Вы ошибаетесь вот в чем:
Например есть строка: abcxy
Нужно получить строку: abc
Здесь один вариант: вычеркнуть x и y
А у Вас будет получаться два варианта:
- первый вариант - вычеркнуть сначало x, потом вычекнуть y
- второй вариант - вычеркнуть сначало y, потом вычеркнуть x
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
21.12.2011, 09:45 #9
Простой алгоритм - можно подсчитать количество каждой буквы из строки Б в строке А. Потом так же перемножить как в случае с aaabbbccc и abc, где умножается 3 ( количество букв а ) на 3 ( количество букв b ) и еще раз на 3 ( количество букв c ).
1
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 09:47 #10
Цитата Сообщение от Toshkarik Посмотреть сообщение
Простой алгоритм - подсчитать количество каждой буквы из строки Б в строке А. Потом так же перемножить как в случае с aaabbbccc и abc, где умножается 3 ( количество букв а ) на 3 ( количество букв b ) и еще раз на 3 ( количество букв c ).
такой алгоритм не подойдет к варианту:
aabbccabc <- первая строка
abc <- вторая строка
1
challengerr
43 / 36 / 2
Регистрация: 30.07.2008
Сообщений: 136
21.12.2011, 09:52 #11
У меня были варианты вычеркивания без учета расположения элементов.
Вы написали варианты с учетом расположения элементов.
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
21.12.2011, 09:52 #12
valeriikozlov, Почему же? Все вполне так же, 27 вариантов. Или я не допонял задание? Нельзя подразумевать перестановку?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 10:00 #13
Цитата Сообщение от Toshkarik Посмотреть сообщение
Все вполне так же, 27 вариантов
Вручную покажете, как из строки:
aabbccabc
получить строку:
abc
не переставляя буквы, а только их вычеркивая?
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
21.12.2011, 10:07 #14
Так я же и спросил про перестановку, про нее в задании ничего не сказано, тогда почему нельзя ее делать?
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2011, 10:20 #15
Цитата Сообщение от Toshkarik Посмотреть сообщение
Так я же и спросил про перестановку, про нее в задании ничего не сказано, тогда почему нельзя ее делать?
ну вроде как в задании сказано только про вычеркивание.

Добавлено через 9 минут
Цитата Сообщение от challengerr Посмотреть сообщение
У меня были варианты вычеркивания без учета расположения элементов.
Вы написали варианты с учетом расположения элементов.
У меня вариант естественно с учетом расположения элементов (потому что в задании сказано только про вычеркивание).
Ваш вариант тоже кстати учитывает расположение элементов, но еще он учитывает порядок вычеркивания (а мой вариант учитывает какие именно элементы были вычеркнуты).
Я не говорю что Ваш вариант не правильный, оба варианты правильные - просто для разных случаев подсчета.
В условии задачи есть недосказанность:
Например для Вашего варианта можно было бы написать так:
Различный порядок вычеркивания одних и тех же элементов - является разными вариантами.
А для моего варианта можно было бы написать:
Вычеркивание одних и тех же букв находящихся на различных местах является разными вариантами.
Не исключаю, что имеется еще какой-то вариант учета вычеркиваний, который даст результат именно 36.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.12.2011, 10:20
Привет! Вот еще темы с ответами:

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Как использовать символы из русского алфавита, а так же символы типа "█" "░" и т.д.? - C++
Как использовать символы из русского алфавита, а так же символы типа &quot;█&quot; &quot;░&quot; и т.д.?

Из слова "яблоко" путем склеек и вырезок его букв получить слова "блок" и "око" - C++
Самым самым самым простым способом.


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

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

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